1 2 This directory contains an SQLite extension that implements a virtual 3 table type that allows users to create, query and manipulate r-tree[1] 4 data structures inside of SQLite databases. Users create, populate 5 and 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 19 1. 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 99 2. 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 113 3. 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
