Documentation Source Text

Check-in [a7b39daebb]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Initial check-in of the rtree documentation. Very incomplete.
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: a7b39daebb4236bc4f29b835c9004b2e76a49ade
User & Date: drh 2008-06-27 17:20:48
Context
2008-06-27
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
2008-06-26
18:03
Bring the compile.html document up-to-date. check-in: c6f9f40d64 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Added pages/rtree.in.



































































































































































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
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>&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>