Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.
|Comment:||Initial check-in of the rtree documentation. Very incomplete.|
|Timelines:||family | ancestors | descendants | both | trunk|
|Files:||files | file ages | folders|
|User & Date:||drh 2008-06-27 17:20:48|
|18:56||Additional work on the R-Tree documentation. check-in: 010e1a52d7 user: drh tags: trunk|
|17:20||Initial check-in of the rtree documentation. Very incomplete. check-in: a7b39daebb user: drh tags: trunk|
|18:03||Bring the compile.html document up-to-date. check-in: c6f9f40d64 user: drh tags: trunk|
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193
<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><name></i> USING rtree(<i><column-names></i>); </pre></blockquote> <p> The <i><name></i> is the name your application chooses for the R*Tree index and <i><column-names></i> is a common separated list of between 3 and 11 columns. The virtual <name> table creates three "shadow" tables to actually store its content. The names of these shadow tables are: </p> <blockquote> <i><name></i><b>_node</b><br> <i><name></i><b>_rowid</b><br> <i><name></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>