This directory contains an SQLite extension that implements a virtual

table type that allows users to create, query and manipulate r-tree[1]

data structures inside of SQLite databases. Users create, populate

and query r-tree structures using ordinary SQL statements.

1. SQL Interface

1.1 Table Creation

1.2 Data Manipulation

1.3 Data Querying

1.4 Introspection and Analysis

2. Compilation and Deployment

3. References

1. SQL INTERFACE

1.1 Table Creation.

All r-tree virtual tables have an odd number of columns between

3 and 11. Unlike regular SQLite tables, r-tree tables are strongly

typed.

The leftmost column is always the primary key and contains 64-bit

integer values. Each subsequent column contains a 32-bit real

value. For each pair of real values, the first (leftmost) must be

less than or equal to the second. R-tree tables may be

constructed using the following syntax:

CREATE VIRTUAL TABLE <name> USING rtree(<column-names>)

For example:

CREATE VIRTUAL TABLE boxes USING rtree(boxno, xmin, xmax, ymin, ymax);

INSERT INTO boxes VALUES(1, 1.0, 3.0, 2.0, 4.0);

Constructing a virtual r-tree table <name> creates the following three

real tables in the database to store the data structure:

<name>_node

<name>_rowid

<name>_parent

Dropping or modifying the contents of these tables directly will

corrupt the r-tree structure. To delete an r-tree from a database,

use a regular DROP TABLE statement:

DROP TABLE <name>;

Dropping the main r-tree table automatically drops the automatically

created tables.

1.2 Data Manipulation (INSERT, UPDATE, DELETE).

The usual INSERT, UPDATE or DELETE syntax is used to manipulate data

stored in an r-tree table. Please note the following:

* Inserting a NULL value into the primary key column has the

same effect as inserting a NULL into an INTEGER PRIMARY KEY

column of a regular table. The system automatically assigns

an unused integer key value to the new record. Usually, this

is one greater than the largest primary key value currently

present in the table.

* Attempting to insert a duplicate primary key value fails with

an SQLITE_CONSTRAINT error.

* Attempting to insert or modify a record such that the value

stored in the (N*2)th column is greater than that stored in

the (N*2+1)th column fails with an SQLITE_CONSTRAINT error.

* When a record is inserted, values are always converted to

the required type (64-bit integer or 32-bit real) as if they

were part of an SQL CAST expression. Non-numeric strings are

converted to zero.

1.3 Queries.

R-tree tables may be queried using all of the same SQL syntax supported

by regular tables. However, some query patterns are more efficient

than others.

R-trees support fast lookup by primary key value (O(logN), like

regular tables).

Any combination of equality and range (<, <=, >, >=) constraints

on spatial data columns may be used to optimize other queries. This

is the key advantage to using r-tree tables instead of creating

indices on regular tables.

1.4 Introspection and Analysis.

TODO: Describe rtreenode() and rtreedepth() functions.

2. COMPILATION AND USAGE

The easiest way to compile and use the RTREE extension is to build

and use it as a dynamically loadable SQLite extension. To do this

using gcc on *nix:

gcc -shared rtree.c -o libSqliteRtree.so

You may need to add "-I" flags so that gcc can find sqlite3ext.h

and sqlite3.h. The resulting shared lib, libSqliteRtree.so, may be

loaded into sqlite in the same way as any other dynamicly loadable

extension.

3. REFERENCES

[1] Atonin Guttman, "R-trees - A Dynamic Index Structure For Spatial

Searching", University of California Berkeley, 1984.

[2] Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger,

"The R*-tree: An Efficient and Robust Access Method for Points and

Rectangles", Universitaet Bremen, 1990.