Documentation Source Text

<title>The SQLite R*Tree Module</title>
<tcl>hd_keywords rtree</tcl>

<h1>1.0 Overview</h1>

<p>
An <a href="http://en.wikipedia.org/wiki/R-tree">R-Tree</a> is a special
index that is designed for doing range queries.  R-Trees are most commonly
used in geospatial systems where each entry is a rectangle with minimum and
maximum X and Y coordinates.  Given a query rectangle, an R-Tree is able
to quickly find all entries that are contained within the query rectangle
or which overlap the query rectangle.  This idea is easily extended to
three dimensions for use in CAD systems.  R-Trees also find use in time-domain
range look-ups.  For example, suppose a database records the starting and
ending times for a large number of events.  A R-Tree is able to quickly
find all events, for example, that were active at any time during a given
time interval, or all events that started during a particular time interval,
or all events that both started and ended within a given time interval.
And so forth.
</p>

<p>
The R-Tree concept originated with 
<a href="http://www.baymoon.com/~tg2/">Toni Guttman</a>: 
<i>R-Trees: A Dynamic Index Structure for Spatial Searching</i>,
Proc. 1984 ACM SIGMOD International Conference on Management of Data,
pp. 47-57.
The implementation found in SQLite is a refinement of Guttman's original
idea, commonly called "R*Trees", that was described by
Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger:
<i>The R*-Tree: An Efficient and Robust Access Method for Points
and Rectangles.</i> SIGMOD Conference 1990: 322-331.
</p>

<h1>2.0 Compiling The R*Tree Module</h1>

<p>
The source code to the SQLite R*Tree module is included as part
of the [amalgamation] but is disabled by default.  To enable the
R*Tree module, simply compile with the [SQLITE_ENABLE_RTREE] 
C-preprocessor macro defined.  With many compilers, this is accomplished
by adding the option "-DSQLITE_ENABLE_RTREE=1" to the compiler
command-line.
</p>

<h1>3.0 Using the R*Tree Module</h1>

<p>
The SQLite R*Tree module is implemented as a
[sqlite3_create_module | virtual table].  Each R*Tree index is a
virtual table with and odd number of columns between 3 and 11.
The first column is always a 64-bit signed integer primary key.
The other columns are minimum- and maximum-value pairs (stored as
32-bit floating point numbers) for each
dimension.  A 1-dimensional R*Tree thus has 3 columns.  
A 2-dimensional R*Tree (the most common case) has 5 columns.
A 5-dimensional R*Tree has 11 columns.  The SQLite R*Tree implemention
does not support R*Trees wider than 5 dimensions.
</p>

<p>
The first column of an SQLite R*Tree must always be an integer
primary key.
The min/max-value pair columns are always stored as
32-bit floating point values.  Unlike regular SQLite tables which
can store data in a variety of datatypes and formats, the R*Tree
indices rigidly enforce these two storage types.  Attempts to insert
something other than an integer into the first column, or something
other than a floating point value into the other columns, will result
in an error.
</p>

<h2>3.1 Creating An R*Tree Index</h2>

<p>
A new R*Tree index is created as follows:
</p>

<blockquote><pre>
CREATE VIRTUAL TABLE <i>&lt;name&gt;</i> USING rtree(<i>&lt;column-names&gt;</i>);
</pre></blockquote>

<p>
The <i>&lt;name&gt;</i> is the name your application chooses for the
R*Tree index and <i>&lt;column-names&gt;</i> is a common separated list
of between 3 and 11 columns.
The virtual &lt;name&gt; table creates three "shadow" tables to actually
store its content.  The names of these shadow tables are:
</p>

<blockquote>
<i>&lt;name&gt;</i><b>_node</b><br>
<i>&lt;name&gt;</i><b>_rowid</b><br>
<i>&lt;name&gt;</i><b>_parent</b>
</blockquote>

<p>
The shadow tables are ordinary SQLite data tables.  You can query them 
directly if you like, though his unlikely to reveal anything particularly
useful. 
And you can [UPDATE], [DELETE], [INSERT] or even [DROP TABLE | DROP] 
the shadow tables, though doing so will corrupt your R*Tree index.
So it is best to simply ignore the shadow tables.  Recognize that they
are there to hold your R*Tree index information and let it go as that.
</p>

<p>
As an example, consider creating a two-dimensional R*Tree index for use in 
spatial queries:
</p>

<blockquote><pre>
CREATE VIRTUAL TABLE demo_index USING rtree(
   id,              -- Integer primary key
   minX, maxX,      -- Minimum and maximum X coordinate
   minY, maxY       -- Minimum and maximum Y coordinate
);
</pre></blockquote>

<h2>3.2 Populating An R*Tree Index</h2>

<p>
The usual [INSERT], [UPDATE], and [DELETE] commands work on an R*Tree
index just like on regular tables.  So to insert some data into our sample
R*Tree index, we can do something like this:
</p>

<blockquote><pre>
INSERT INTO demo_index VALUES(
    1,                   -- Primary key
    -80.7749, -80,7747   -- Longitude range
    30.3776, 30.3778     -- Latitude range
);
INSERT INTO demo_index VALUES(
    2,
    -81.0, -79.6,
    35.0, 36.2
);
</pre></blockquote>

<p>
The entires above might represent (for example) a bounding box around
the offices for SQLite.org and bounding box around the
12th Congressional District of North Carolina in which SQLite.org is located.  
</p>

<h2>3.3 Querying An R*Tree Index</h2>

<p>
Any valid query will work against an R*Tree index.  But the R*Tree
implementation is designed to make two kinds of queries especially
efficient.  First, queries against the primary key are efficient:
</p>

<blockquote><pre>
SELECT * FROM demo_index WHERE id=1;
</pre></blockquote>

<p>
Of course, an ordinary SQLite table will do a query against its
integer primary key efficiently, so the previous is no big deal.
The real reason for using an R*Tree in the first place is so that
you can efficiently do inequality queries against the coordinate
ranges.  To find all elements of the index that are contained within
the vicinity of Charlotte, North Carolina, one might do:
</p>

<blockquote><pre>
SELECT id FROM demo_index
WHERE minX>=-81.08 AND maxX<=-80.58
  AND minY>=35.00 AND maxY<=35.44;
</pre></blockquote>

<p>
The query above would very quickly locate id of 1 even if the
R*Tree contained millions of entries.  The previous is an example
of a "contained-within" query.  The R*Tree also supports "overlapping"
queries.  For example, to find all bounding boxes that overlap the
Charlotte area:
</p>

<blockquote><pre>
SELECT id FROM demo_index
WHERE maxX>=-81.08 AND minX<=-80.58
  AND maxY>=35.00 AND minY<=35.44;
</pre></blockquote>

<p>
This second query would find both entry 1 (the SQLite.org office) which
is entirely contained within the query box and also
Mel Watt's Congressional District which extends well outside the
query box but still overlaps the query box.
</p>