Return to README CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / sqlite3 / ext / rtree

sqlite3

    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.