README
1
2This directory contains an SQLite extension that implements a virtual
3table type that allows users to create, query and manipulate r-tree[1]
4data structures inside of SQLite databases. Users create, populate
5and query r-tree structures using ordinary SQL statements.
6
7 1. SQL Interface
8
9 1.1 Table Creation
10 1.2 Data Manipulation
11 1.3 Data Querying
12 1.4 Introspection and Analysis
13
14 2. Compilation and Deployment
15
16 3. References
17
18
191. SQL INTERFACE
20
21 1.1 Table Creation.
22
23 All r-tree virtual tables have an odd number of columns between
24 3 and 11. Unlike regular SQLite tables, r-tree tables are strongly
25 typed.
26
27 The leftmost column is always the pimary key and contains 64-bit
28 integer values. Each subsequent column contains a 32-bit real
29 value. For each pair of real values, the first (leftmost) must be
30 less than or equal to the second. R-tree tables may be
31 constructed using the following syntax:
32
33 CREATE VIRTUAL TABLE <name> USING rtree(<column-names>)
34
35 For example:
36
37 CREATE VIRTUAL TABLE boxes USING rtree(boxno, xmin, xmax, ymin, ymax);
38 INSERT INTO boxes VALUES(1, 1.0, 3.0, 2.0, 4.0);
39
40 Constructing a virtual r-tree table <name> creates the following three
41 real tables in the database to store the data structure:
42
43 <name>_node
44 <name>_rowid
45 <name>_parent
46
47 Dropping or modifying the contents of these tables directly will
48 corrupt the r-tree structure. To delete an r-tree from a database,
49 use a regular DROP TABLE statement:
50
51 DROP TABLE <name>;
52
53 Dropping the main r-tree table automatically drops the automatically
54 created tables.
55
56 1.2 Data Manipulation (INSERT, UPDATE, DELETE).
57
58 The usual INSERT, UPDATE or DELETE syntax is used to manipulate data
59 stored in an r-tree table. Please note the following:
60
61 * Inserting a NULL value into the primary key column has the
62 same effect as inserting a NULL into an INTEGER PRIMARY KEY
63 column of a regular table. The system automatically assigns
64 an unused integer key value to the new record. Usually, this
65 is one greater than the largest primary key value currently
66 present in the table.
67
68 * Attempting to insert a duplicate primary key value fails with
69 an SQLITE_CONSTRAINT error.
70
71 * Attempting to insert or modify a record such that the value
72 stored in the (N*2)th column is greater than that stored in
73 the (N*2+1)th column fails with an SQLITE_CONSTRAINT error.
74
75 * When a record is inserted, values are always converted to
76 the required type (64-bit integer or 32-bit real) as if they
77 were part of an SQL CAST expression. Non-numeric strings are
78 converted to zero.
79
80 1.3 Queries.
81
82 R-tree tables may be queried using all of the same SQL syntax supported
83 by regular tables. However, some query patterns are more efficient
84 than others.
85
86 R-trees support fast lookup by primary key value (O(logN), like
87 regular tables).
88
89 Any combination of equality and range (<, <=, >, >=) constraints
90 on spatial data columns may be used to optimize other queries. This
91 is the key advantage to using r-tree tables instead of creating
92 indices on regular tables.
93
94 1.4 Introspection and Analysis.
95
96 TODO: Describe rtreenode() and rtreedepth() functions.
97
98
992. COMPILATION AND USAGE
100
101 The easiest way to compile and use the RTREE extension is to build
102 and use it as a dynamically loadable SQLite extension. To do this
103 using gcc on *nix:
104
105 gcc -shared rtree.c -o libSqliteRtree.so
106
107 You may need to add "-I" flags so that gcc can find sqlite3ext.h
108 and sqlite3.h. The resulting shared lib, libSqliteRtree.so, may be
109 loaded into sqlite in the same way as any other dynamicly loadable
110 extension.
111
112
1133. REFERENCES
114
115 [1] Atonin Guttman, "R-trees - A Dynamic Index Structure For Spatial
116 Searching", University of California Berkeley, 1984.
117
118 [2] Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger,
119 "The R*-tree: An Efficient and Robust Access Method for Points and
120 Rectangles", Universitaet Bremen, 1990.
121