third_party/sqlite/src/ext/rtree/README

   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.