/ Hex Artifact Content
Login

Artifact 6315c0d73ebf0ec40dedb5aa0e942bc8b54e3761:


0000: 0a 54 68 69 73 20 64 69 72 65 63 74 6f 72 79 20  .This directory 
0010: 63 6f 6e 74 61 69 6e 73 20 61 6e 20 53 51 4c 69  contains an SQLi
0020: 74 65 20 65 78 74 65 6e 73 69 6f 6e 20 74 68 61  te extension tha
0030: 74 20 69 6d 70 6c 65 6d 65 6e 74 73 20 61 20 76  t implements a v
0040: 69 72 74 75 61 6c 20 0a 74 61 62 6c 65 20 74 79  irtual .table ty
0050: 70 65 20 74 68 61 74 20 61 6c 6c 6f 77 73 20 75  pe that allows u
0060: 73 65 72 73 20 74 6f 20 63 72 65 61 74 65 2c 20  sers to create, 
0070: 71 75 65 72 79 20 61 6e 64 20 6d 61 6e 69 70 75  query and manipu
0080: 6c 61 74 65 20 72 2d 74 72 65 65 5b 31 5d 20 0a  late r-tree[1] .
0090: 64 61 74 61 20 73 74 72 75 63 74 75 72 65 73 20  data structures 
00a0: 69 6e 73 69 64 65 20 6f 66 20 53 51 4c 69 74 65  inside of SQLite
00b0: 20 64 61 74 61 62 61 73 65 73 2e 20 55 73 65 72   databases. User
00c0: 73 20 63 72 65 61 74 65 2c 20 70 6f 70 75 6c 61  s create, popula
00d0: 74 65 20 0a 61 6e 64 20 71 75 65 72 79 20 72 2d  te .and query r-
00e0: 74 72 65 65 20 73 74 72 75 63 74 75 72 65 73 20  tree structures 
00f0: 75 73 69 6e 67 20 6f 72 64 69 6e 61 72 79 20 53  using ordinary S
0100: 51 4c 20 73 74 61 74 65 6d 65 6e 74 73 2e 0a 0a  QL statements...
0110: 20 20 20 20 31 2e 20 20 53 51 4c 20 49 6e 74 65      1.  SQL Inte
0120: 72 66 61 63 65 0a 0a 20 20 20 20 20 20 20 20 31  rface..        1
0130: 2e 31 20 20 54 61 62 6c 65 20 43 72 65 61 74 69  .1  Table Creati
0140: 6f 6e 0a 20 20 20 20 20 20 20 20 31 2e 32 20 20  on.        1.2  
0150: 44 61 74 61 20 4d 61 6e 69 70 75 6c 61 74 69 6f  Data Manipulatio
0160: 6e 0a 20 20 20 20 20 20 20 20 31 2e 33 20 20 44  n.        1.3  D
0170: 61 74 61 20 51 75 65 72 79 69 6e 67 0a 20 20 20  ata Querying.   
0180: 20 20 20 20 20 31 2e 34 20 20 49 6e 74 72 6f 73       1.4  Intros
0190: 70 65 63 74 69 6f 6e 20 61 6e 64 20 41 6e 61 6c  pection and Anal
01a0: 79 73 69 73 0a 0a 20 20 20 20 32 2e 20 20 43 6f  ysis..    2.  Co
01b0: 6d 70 69 6c 61 74 69 6f 6e 20 61 6e 64 20 44 65  mpilation and De
01c0: 70 6c 6f 79 6d 65 6e 74 0a 0a 20 20 20 20 33 2e  ployment..    3.
01d0: 20 20 52 65 66 65 72 65 6e 63 65 73 0a 0a 0a 31    References...1
01e0: 2e 20 53 51 4c 20 49 4e 54 45 52 46 41 43 45 0a  . SQL INTERFACE.
01f0: 0a 20 20 31 2e 31 20 54 61 62 6c 65 20 43 72 65  .  1.1 Table Cre
0200: 61 74 69 6f 6e 2e 0a 0a 20 20 20 20 41 6c 6c 20  ation...    All 
0210: 72 2d 74 72 65 65 20 76 69 72 74 75 61 6c 20 74  r-tree virtual t
0220: 61 62 6c 65 73 20 68 61 76 65 20 61 6e 20 6f 64  ables have an od
0230: 64 20 6e 75 6d 62 65 72 20 6f 66 20 63 6f 6c 75  d number of colu
0240: 6d 6e 73 20 62 65 74 77 65 65 6e 0a 20 20 20 20  mns between.    
0250: 33 20 61 6e 64 20 31 31 2e 20 55 6e 6c 69 6b 65  3 and 11. Unlike
0260: 20 72 65 67 75 6c 61 72 20 53 51 4c 69 74 65 20   regular SQLite 
0270: 74 61 62 6c 65 73 2c 20 72 2d 74 72 65 65 20 74  tables, r-tree t
0280: 61 62 6c 65 73 20 61 72 65 20 73 74 72 6f 6e 67  ables are strong
0290: 6c 79 20 0a 20 20 20 20 74 79 70 65 64 2e 20 0a  ly .    typed. .
02a0: 0a 20 20 20 20 54 68 65 20 6c 65 66 74 6d 6f 73  .    The leftmos
02b0: 74 20 63 6f 6c 75 6d 6e 20 69 73 20 61 6c 77 61  t column is alwa
02c0: 79 73 20 74 68 65 20 70 69 6d 61 72 79 20 6b 65  ys the pimary ke
02d0: 79 20 61 6e 64 20 63 6f 6e 74 61 69 6e 73 20 36  y and contains 6
02e0: 34 2d 62 69 74 20 0a 20 20 20 20 69 6e 74 65 67  4-bit .    integ
02f0: 65 72 20 76 61 6c 75 65 73 2e 20 45 61 63 68 20  er values. Each 
0300: 73 75 62 73 65 71 75 65 6e 74 20 63 6f 6c 75 6d  subsequent colum
0310: 6e 20 63 6f 6e 74 61 69 6e 73 20 61 20 33 32 2d  n contains a 32-
0320: 62 69 74 20 72 65 61 6c 0a 20 20 20 20 76 61 6c  bit real.    val
0330: 75 65 2e 20 46 6f 72 20 65 61 63 68 20 70 61 69  ue. For each pai
0340: 72 20 6f 66 20 72 65 61 6c 20 76 61 6c 75 65 73  r of real values
0350: 2c 20 74 68 65 20 66 69 72 73 74 20 28 6c 65 66  , the first (lef
0360: 74 6d 6f 73 74 29 20 6d 75 73 74 20 62 65 20 0a  tmost) must be .
0370: 20 20 20 20 6c 65 73 73 20 74 68 61 6e 20 6f 72      less than or
0380: 20 65 71 75 61 6c 20 74 6f 20 74 68 65 20 73 65   equal to the se
0390: 63 6f 6e 64 2e 20 52 2d 74 72 65 65 20 74 61 62  cond. R-tree tab
03a0: 6c 65 73 20 6d 61 79 20 62 65 20 0a 20 20 20 20  les may be .    
03b0: 63 6f 6e 73 74 72 75 63 74 65 64 20 75 73 69 6e  constructed usin
03c0: 67 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20  g the following 
03d0: 73 79 6e 74 61 78 3a 0a 0a 20 20 20 20 20 20 43  syntax:..      C
03e0: 52 45 41 54 45 20 56 49 52 54 55 41 4c 20 54 41  REATE VIRTUAL TA
03f0: 42 4c 45 20 3c 6e 61 6d 65 3e 20 55 53 49 4e 47  BLE <name> USING
0400: 20 72 74 72 65 65 28 3c 63 6f 6c 75 6d 6e 2d 6e   rtree(<column-n
0410: 61 6d 65 73 3e 29 0a 0a 20 20 20 20 46 6f 72 20  ames>)..    For 
0420: 65 78 61 6d 70 6c 65 3a 0a 0a 20 20 20 20 20 20  example:..      
0430: 43 52 45 41 54 45 20 56 49 52 54 55 41 4c 20 54  CREATE VIRTUAL T
0440: 41 42 4c 45 20 62 6f 78 65 73 20 55 53 49 4e 47  ABLE boxes USING
0450: 20 72 74 72 65 65 28 62 6f 78 6e 6f 2c 20 78 6d   rtree(boxno, xm
0460: 69 6e 2c 20 78 6d 61 78 2c 20 79 6d 69 6e 2c 20  in, xmax, ymin, 
0470: 79 6d 61 78 29 3b 0a 20 20 20 20 20 20 49 4e 53  ymax);.      INS
0480: 45 52 54 20 49 4e 54 4f 20 62 6f 78 65 73 20 56  ERT INTO boxes V
0490: 41 4c 55 45 53 28 31 2c 20 31 2e 30 2c 20 33 2e  ALUES(1, 1.0, 3.
04a0: 30 2c 20 32 2e 30 2c 20 34 2e 30 29 3b 0a 0a 20  0, 2.0, 4.0);.. 
04b0: 20 20 20 43 6f 6e 73 74 72 75 63 74 69 6e 67 20     Constructing 
04c0: 61 20 76 69 72 74 75 61 6c 20 72 2d 74 72 65 65  a virtual r-tree
04d0: 20 74 61 62 6c 65 20 3c 6e 61 6d 65 3e 20 63 72   table <name> cr
04e0: 65 61 74 65 73 20 74 68 65 20 66 6f 6c 6c 6f 77  eates the follow
04f0: 69 6e 67 20 74 68 72 65 65 0a 20 20 20 20 72 65  ing three.    re
0500: 61 6c 20 74 61 62 6c 65 73 20 69 6e 20 74 68 65  al tables in the
0510: 20 64 61 74 61 62 61 73 65 20 74 6f 20 73 74 6f   database to sto
0520: 72 65 20 74 68 65 20 64 61 74 61 20 73 74 72 75  re the data stru
0530: 63 74 75 72 65 3a 0a 0a 20 20 20 20 20 20 3c 6e  cture:..      <n
0540: 61 6d 65 3e 5f 6e 6f 64 65 0a 20 20 20 20 20 20  ame>_node.      
0550: 3c 6e 61 6d 65 3e 5f 72 6f 77 69 64 0a 20 20 20  <name>_rowid.   
0560: 20 20 20 3c 6e 61 6d 65 3e 5f 70 61 72 65 6e 74     <name>_parent
0570: 0a 0a 20 20 20 20 44 72 6f 70 70 69 6e 67 20 6f  ..    Dropping o
0580: 72 20 6d 6f 64 69 66 79 69 6e 67 20 74 68 65 20  r modifying the 
0590: 63 6f 6e 74 65 6e 74 73 20 6f 66 20 74 68 65 73  contents of thes
05a0: 65 20 74 61 62 6c 65 73 20 64 69 72 65 63 74 6c  e tables directl
05b0: 79 20 77 69 6c 6c 0a 20 20 20 20 63 6f 72 72 75  y will.    corru
05c0: 70 74 20 74 68 65 20 72 2d 74 72 65 65 20 73 74  pt the r-tree st
05d0: 72 75 63 74 75 72 65 2e 20 54 6f 20 64 65 6c 65  ructure. To dele
05e0: 74 65 20 61 6e 20 72 2d 74 72 65 65 20 66 72 6f  te an r-tree fro
05f0: 6d 20 61 20 64 61 74 61 62 61 73 65 2c 0a 20 20  m a database,.  
0600: 20 20 75 73 65 20 61 20 72 65 67 75 6c 61 72 20    use a regular 
0610: 44 52 4f 50 20 54 41 42 4c 45 20 73 74 61 74 65  DROP TABLE state
0620: 6d 65 6e 74 3a 0a 0a 20 20 20 20 20 20 44 52 4f  ment:..      DRO
0630: 50 20 54 41 42 4c 45 20 3c 6e 61 6d 65 3e 3b 0a  P TABLE <name>;.
0640: 0a 20 20 20 20 44 72 6f 70 70 69 6e 67 20 74 68  .    Dropping th
0650: 65 20 6d 61 69 6e 20 72 2d 74 72 65 65 20 74 61  e main r-tree ta
0660: 62 6c 65 20 61 75 74 6f 6d 61 74 69 63 61 6c 6c  ble automaticall
0670: 79 20 64 72 6f 70 73 20 74 68 65 20 61 75 74 6f  y drops the auto
0680: 6d 61 74 69 63 61 6c 6c 79 0a 20 20 20 20 63 72  matically.    cr
0690: 65 61 74 65 64 20 74 61 62 6c 65 73 2e 20 0a 0a  eated tables. ..
06a0: 20 20 31 2e 32 20 44 61 74 61 20 4d 61 6e 69 70    1.2 Data Manip
06b0: 75 6c 61 74 69 6f 6e 20 28 49 4e 53 45 52 54 2c  ulation (INSERT,
06c0: 20 55 50 44 41 54 45 2c 20 44 45 4c 45 54 45 29   UPDATE, DELETE)
06d0: 2e 0a 0a 20 20 20 20 54 68 65 20 75 73 75 61 6c  ...    The usual
06e0: 20 49 4e 53 45 52 54 2c 20 55 50 44 41 54 45 20   INSERT, UPDATE 
06f0: 6f 72 20 44 45 4c 45 54 45 20 73 79 6e 74 61 78  or DELETE syntax
0700: 20 69 73 20 75 73 65 64 20 74 6f 20 6d 61 6e 69   is used to mani
0710: 70 75 6c 61 74 65 20 64 61 74 61 0a 20 20 20 20  pulate data.    
0720: 73 74 6f 72 65 64 20 69 6e 20 61 6e 20 72 2d 74  stored in an r-t
0730: 72 65 65 20 74 61 62 6c 65 2e 20 50 6c 65 61 73  ree table. Pleas
0740: 65 20 6e 6f 74 65 20 74 68 65 20 66 6f 6c 6c 6f  e note the follo
0750: 77 69 6e 67 3a 0a 0a 20 20 20 20 20 20 2a 20 49  wing:..      * I
0760: 6e 73 65 72 74 69 6e 67 20 61 20 4e 55 4c 4c 20  nserting a NULL 
0770: 76 61 6c 75 65 20 69 6e 74 6f 20 74 68 65 20 70  value into the p
0780: 72 69 6d 61 72 79 20 6b 65 79 20 63 6f 6c 75 6d  rimary key colum
0790: 6e 20 68 61 73 20 74 68 65 0a 20 20 20 20 20 20  n has the.      
07a0: 20 20 73 61 6d 65 20 65 66 66 65 63 74 20 61 73    same effect as
07b0: 20 69 6e 73 65 72 74 69 6e 67 20 61 20 4e 55 4c   inserting a NUL
07c0: 4c 20 69 6e 74 6f 20 61 6e 20 49 4e 54 45 47 45  L into an INTEGE
07d0: 52 20 50 52 49 4d 41 52 59 20 4b 45 59 0a 20 20  R PRIMARY KEY.  
07e0: 20 20 20 20 20 20 63 6f 6c 75 6d 6e 20 6f 66 20        column of 
07f0: 61 20 72 65 67 75 6c 61 72 20 74 61 62 6c 65 2e  a regular table.
0800: 20 54 68 65 20 73 79 73 74 65 6d 20 61 75 74 6f   The system auto
0810: 6d 61 74 69 63 61 6c 6c 79 20 61 73 73 69 67 6e  matically assign
0820: 73 0a 20 20 20 20 20 20 20 20 61 6e 20 75 6e 75  s.        an unu
0830: 73 65 64 20 69 6e 74 65 67 65 72 20 6b 65 79 20  sed integer key 
0840: 76 61 6c 75 65 20 74 6f 20 74 68 65 20 6e 65 77  value to the new
0850: 20 72 65 63 6f 72 64 2e 20 55 73 75 61 6c 6c 79   record. Usually
0860: 2c 20 74 68 69 73 0a 20 20 20 20 20 20 20 20 69  , this.        i
0870: 73 20 6f 6e 65 20 67 72 65 61 74 65 72 20 74 68  s one greater th
0880: 61 6e 20 74 68 65 20 6c 61 72 67 65 73 74 20 70  an the largest p
0890: 72 69 6d 61 72 79 20 6b 65 79 20 76 61 6c 75 65  rimary key value
08a0: 20 63 75 72 72 65 6e 74 6c 79 0a 20 20 20 20 20   currently.     
08b0: 20 20 20 70 72 65 73 65 6e 74 20 69 6e 20 74 68     present in th
08c0: 65 20 74 61 62 6c 65 2e 0a 0a 20 20 20 20 20 20  e table...      
08d0: 2a 20 41 74 74 65 6d 70 74 69 6e 67 20 74 6f 20  * Attempting to 
08e0: 69 6e 73 65 72 74 20 61 20 64 75 70 6c 69 63 61  insert a duplica
08f0: 74 65 20 70 72 69 6d 61 72 79 20 6b 65 79 20 76  te primary key v
0900: 61 6c 75 65 20 66 61 69 6c 73 20 77 69 74 68 0a  alue fails with.
0910: 20 20 20 20 20 20 20 20 61 6e 20 53 51 4c 49 54          an SQLIT
0920: 45 5f 43 4f 4e 53 54 52 41 49 4e 54 20 65 72 72  E_CONSTRAINT err
0930: 6f 72 2e 0a 0a 20 20 20 20 20 20 2a 20 41 74 74  or...      * Att
0940: 65 6d 70 74 69 6e 67 20 74 6f 20 69 6e 73 65 72  empting to inser
0950: 74 20 6f 72 20 6d 6f 64 69 66 79 20 61 20 72 65  t or modify a re
0960: 63 6f 72 64 20 73 75 63 68 20 74 68 61 74 20 74  cord such that t
0970: 68 65 20 76 61 6c 75 65 0a 20 20 20 20 20 20 20  he value.       
0980: 20 73 74 6f 72 65 64 20 69 6e 20 74 68 65 20 28   stored in the (
0990: 4e 2a 32 29 74 68 20 63 6f 6c 75 6d 6e 20 69 73  N*2)th column is
09a0: 20 67 72 65 61 74 65 72 20 74 68 61 6e 20 74 68   greater than th
09b0: 61 74 20 73 74 6f 72 65 64 20 69 6e 0a 20 20 20  at stored in.   
09c0: 20 20 20 20 20 74 68 65 20 28 4e 2a 32 2b 31 29       the (N*2+1)
09d0: 74 68 20 63 6f 6c 75 6d 6e 20 66 61 69 6c 73 20  th column fails 
09e0: 77 69 74 68 20 61 6e 20 53 51 4c 49 54 45 5f 43  with an SQLITE_C
09f0: 4f 4e 53 54 52 41 49 4e 54 20 65 72 72 6f 72 2e  ONSTRAINT error.
0a00: 0a 0a 20 20 20 20 20 20 2a 20 57 68 65 6e 20 61  ..      * When a
0a10: 20 72 65 63 6f 72 64 20 69 73 20 69 6e 73 65 72   record is inser
0a20: 74 65 64 2c 20 76 61 6c 75 65 73 20 61 72 65 20  ted, values are 
0a30: 61 6c 77 61 79 73 20 63 6f 6e 76 65 72 74 65 64  always converted
0a40: 20 74 6f 20 0a 20 20 20 20 20 20 20 20 74 68 65   to .        the
0a50: 20 72 65 71 75 69 72 65 64 20 74 79 70 65 20 28   required type (
0a60: 36 34 2d 62 69 74 20 69 6e 74 65 67 65 72 20 6f  64-bit integer o
0a70: 72 20 33 32 2d 62 69 74 20 72 65 61 6c 29 20 61  r 32-bit real) a
0a80: 73 20 69 66 20 74 68 65 79 0a 20 20 20 20 20 20  s if they.      
0a90: 20 20 77 65 72 65 20 70 61 72 74 20 6f 66 20 61    were part of a
0aa0: 6e 20 53 51 4c 20 43 41 53 54 20 65 78 70 72 65  n SQL CAST expre
0ab0: 73 73 69 6f 6e 2e 20 4e 6f 6e 2d 6e 75 6d 65 72  ssion. Non-numer
0ac0: 69 63 20 73 74 72 69 6e 67 73 20 61 72 65 0a 20  ic strings are. 
0ad0: 20 20 20 20 20 20 20 63 6f 6e 76 65 72 74 65 64         converted
0ae0: 20 74 6f 20 7a 65 72 6f 2e 0a 0a 20 20 31 2e 33   to zero...  1.3
0af0: 20 51 75 65 72 69 65 73 2e 0a 0a 20 20 20 20 52   Queries...    R
0b00: 2d 74 72 65 65 20 74 61 62 6c 65 73 20 6d 61 79  -tree tables may
0b10: 20 62 65 20 71 75 65 72 69 65 64 20 75 73 69 6e   be queried usin
0b20: 67 20 61 6c 6c 20 6f 66 20 74 68 65 20 73 61 6d  g all of the sam
0b30: 65 20 53 51 4c 20 73 79 6e 74 61 78 20 73 75 70  e SQL syntax sup
0b40: 70 6f 72 74 65 64 0a 20 20 20 20 62 79 20 72 65  ported.    by re
0b50: 67 75 6c 61 72 20 74 61 62 6c 65 73 2e 20 48 6f  gular tables. Ho
0b60: 77 65 76 65 72 2c 20 73 6f 6d 65 20 71 75 65 72  wever, some quer
0b70: 79 20 70 61 74 74 65 72 6e 73 20 61 72 65 20 6d  y patterns are m
0b80: 6f 72 65 20 65 66 66 69 63 69 65 6e 74 0a 20 20  ore efficient.  
0b90: 20 20 74 68 61 6e 20 6f 74 68 65 72 73 2e 0a 0a    than others...
0ba0: 20 20 20 20 52 2d 74 72 65 65 73 20 73 75 70 70      R-trees supp
0bb0: 6f 72 74 20 66 61 73 74 20 6c 6f 6f 6b 75 70 20  ort fast lookup 
0bc0: 62 79 20 70 72 69 6d 61 72 79 20 6b 65 79 20 76  by primary key v
0bd0: 61 6c 75 65 20 28 4f 28 6c 6f 67 4e 29 2c 20 6c  alue (O(logN), l
0be0: 69 6b 65 20 0a 20 20 20 20 72 65 67 75 6c 61 72  ike .    regular
0bf0: 20 74 61 62 6c 65 73 29 2e 0a 0a 20 20 20 20 41   tables)...    A
0c00: 6e 79 20 63 6f 6d 62 69 6e 61 74 69 6f 6e 20 6f  ny combination o
0c10: 66 20 65 71 75 61 6c 69 74 79 20 61 6e 64 20 72  f equality and r
0c20: 61 6e 67 65 20 28 3c 2c 20 3c 3d 2c 20 3e 2c 20  ange (<, <=, >, 
0c30: 3e 3d 29 20 63 6f 6e 73 74 72 61 69 6e 74 73 0a  >=) constraints.
0c40: 20 20 20 20 6f 6e 20 73 70 61 74 69 61 6c 20 64      on spatial d
0c50: 61 74 61 20 63 6f 6c 75 6d 6e 73 20 6d 61 79 20  ata columns may 
0c60: 62 65 20 75 73 65 64 20 74 6f 20 6f 70 74 69 6d  be used to optim
0c70: 69 7a 65 20 6f 74 68 65 72 20 71 75 65 72 69 65  ize other querie
0c80: 73 2e 20 54 68 69 73 0a 20 20 20 20 69 73 20 74  s. This.    is t
0c90: 68 65 20 6b 65 79 20 61 64 76 61 6e 74 61 67 65  he key advantage
0ca0: 20 74 6f 20 75 73 69 6e 67 20 72 2d 74 72 65 65   to using r-tree
0cb0: 20 74 61 62 6c 65 73 20 69 6e 73 74 65 61 64 20   tables instead 
0cc0: 6f 66 20 63 72 65 61 74 69 6e 67 20 0a 20 20 20  of creating .   
0cd0: 20 69 6e 64 69 63 65 73 20 6f 6e 20 72 65 67 75   indices on regu
0ce0: 6c 61 72 20 74 61 62 6c 65 73 2e 0a 0a 20 20 31  lar tables...  1
0cf0: 2e 34 20 49 6e 74 72 6f 73 70 65 63 74 69 6f 6e  .4 Introspection
0d00: 20 61 6e 64 20 41 6e 61 6c 79 73 69 73 2e 0a 0a   and Analysis...
0d10: 20 20 20 20 54 4f 44 4f 3a 20 44 65 73 63 72 69      TODO: Descri
0d20: 62 65 20 72 74 72 65 65 6e 6f 64 65 28 29 20 61  be rtreenode() a
0d30: 6e 64 20 72 74 72 65 65 64 65 70 74 68 28 29 20  nd rtreedepth() 
0d40: 66 75 6e 63 74 69 6f 6e 73 2e 0a 0a 0a 32 2e 20  functions....2. 
0d50: 43 4f 4d 50 49 4c 41 54 49 4f 4e 20 41 4e 44 20  COMPILATION AND 
0d60: 55 53 41 47 45 0a 0a 20 20 54 68 65 20 65 61 73  USAGE..  The eas
0d70: 69 65 73 74 20 77 61 79 20 74 6f 20 63 6f 6d 70  iest way to comp
0d80: 69 6c 65 20 61 6e 64 20 75 73 65 20 74 68 65 20  ile and use the 
0d90: 52 54 52 45 45 20 65 78 74 65 6e 73 69 6f 6e 20  RTREE extension 
0da0: 69 73 20 74 6f 20 62 75 69 6c 64 0a 20 20 61 6e  is to build.  an
0db0: 64 20 75 73 65 20 69 74 20 61 73 20 61 20 64 79  d use it as a dy
0dc0: 6e 61 6d 69 63 61 6c 6c 79 20 6c 6f 61 64 61 62  namically loadab
0dd0: 6c 65 20 53 51 4c 69 74 65 20 65 78 74 65 6e 73  le SQLite extens
0de0: 69 6f 6e 2e 20 54 6f 20 64 6f 20 74 68 69 73 0a  ion. To do this.
0df0: 20 20 75 73 69 6e 67 20 67 63 63 20 6f 6e 20 2a    using gcc on *
0e00: 6e 69 78 3a 0a 0a 20 20 20 20 67 63 63 20 2d 73  nix:..    gcc -s
0e10: 68 61 72 65 64 20 72 74 72 65 65 2e 63 20 2d 6f  hared rtree.c -o
0e20: 20 6c 69 62 53 71 6c 69 74 65 52 74 72 65 65 2e   libSqliteRtree.
0e30: 73 6f 0a 0a 20 20 59 6f 75 20 6d 61 79 20 6e 65  so..  You may ne
0e40: 65 64 20 74 6f 20 61 64 64 20 22 2d 49 22 20 66  ed to add "-I" f
0e50: 6c 61 67 73 20 73 6f 20 74 68 61 74 20 67 63 63  lags so that gcc
0e60: 20 63 61 6e 20 66 69 6e 64 20 73 71 6c 69 74 65   can find sqlite
0e70: 33 65 78 74 2e 68 0a 20 20 61 6e 64 20 73 71 6c  3ext.h.  and sql
0e80: 69 74 65 33 2e 68 2e 20 54 68 65 20 72 65 73 75  ite3.h. The resu
0e90: 6c 74 69 6e 67 20 73 68 61 72 65 64 20 6c 69 62  lting shared lib
0ea0: 2c 20 6c 69 62 53 71 6c 69 74 65 52 74 72 65 65  , libSqliteRtree
0eb0: 2e 73 6f 2c 20 6d 61 79 20 62 65 0a 20 20 6c 6f  .so, may be.  lo
0ec0: 61 64 65 64 20 69 6e 74 6f 20 73 71 6c 69 74 65  aded into sqlite
0ed0: 20 69 6e 20 74 68 65 20 73 61 6d 65 20 77 61 79   in the same way
0ee0: 20 61 73 20 61 6e 79 20 6f 74 68 65 72 20 64 79   as any other dy
0ef0: 6e 61 6d 69 63 6c 79 20 6c 6f 61 64 61 62 6c 65  namicly loadable
0f00: 0a 20 20 65 78 74 65 6e 73 69 6f 6e 2e 0a 0a 0a  .  extension....
0f10: 33 2e 20 52 45 46 45 52 45 4e 43 45 53 0a 0a 20  3. REFERENCES.. 
0f20: 20 5b 31 5d 20 20 41 74 6f 6e 69 6e 20 47 75 74   [1]  Atonin Gut
0f30: 74 6d 61 6e 2c 20 22 52 2d 74 72 65 65 73 20 2d  tman, "R-trees -
0f40: 20 41 20 44 79 6e 61 6d 69 63 20 49 6e 64 65 78   A Dynamic Index
0f50: 20 53 74 72 75 63 74 75 72 65 20 46 6f 72 20 53   Structure For S
0f60: 70 61 74 69 61 6c 20 0a 20 20 20 20 20 20 20 53  patial .       S
0f70: 65 61 72 63 68 69 6e 67 22 2c 20 55 6e 69 76 65  earching", Unive
0f80: 72 73 69 74 79 20 6f 66 20 43 61 6c 69 66 6f 72  rsity of Califor
0f90: 6e 69 61 20 42 65 72 6b 65 6c 65 79 2c 20 31 39  nia Berkeley, 19
0fa0: 38 34 2e 0a 0a 20 20 5b 32 5d 20 20 4e 6f 72 62  84...  [2]  Norb
0fb0: 65 72 74 20 42 65 63 6b 6d 61 6e 6e 2c 20 48 61  ert Beckmann, Ha
0fc0: 6e 73 2d 50 65 74 65 72 20 4b 72 69 65 67 65 6c  ns-Peter Kriegel
0fd0: 2c 20 52 61 6c 66 20 53 63 68 6e 65 69 64 65 72  , Ralf Schneider
0fe0: 2c 20 42 65 72 6e 68 61 72 64 20 53 65 65 67 65  , Bernhard Seege
0ff0: 72 2c 0a 20 20 20 20 20 20 20 22 54 68 65 20 52  r,.       "The R
1000: 2a 2d 74 72 65 65 3a 20 41 6e 20 45 66 66 69 63  *-tree: An Effic
1010: 69 65 6e 74 20 61 6e 64 20 52 6f 62 75 73 74 20  ient and Robust 
1020: 41 63 63 65 73 73 20 4d 65 74 68 6f 64 20 66 6f  Access Method fo
1030: 72 20 50 6f 69 6e 74 73 20 61 6e 64 0a 20 20 20  r Points and.   
1040: 20 20 20 20 52 65 63 74 61 6e 67 6c 65 73 22 2c      Rectangles",
1050: 20 55 6e 69 76 65 72 73 69 74 61 65 74 20 42 72   Universitaet Br
1060: 65 6d 65 6e 2c 20 31 39 39 30 2e 0a              emen, 1990..