Documentation Source Text

Hex Artifact Content
Login

Artifact aee2c2acd61ed692f4731750f90e79b51d825cc2b26832975c5e3ee068e904de:


0000: 3c 74 69 74 6c 65 3e 54 68 65 20 53 51 4c 69 74  <title>The SQLit
0010: 65 20 52 2a 54 72 65 65 20 4d 6f 64 75 6c 65 3c  e R*Tree Module<
0020: 2f 74 69 74 6c 65 3e 0a 3c 74 63 6c 3e 68 64 5f  /title>.<tcl>hd_
0030: 6b 65 79 77 6f 72 64 73 20 2a 72 74 72 65 65 20  keywords *rtree 
0040: 2a 52 54 52 45 45 20 7b 52 2d 54 72 65 65 20 65  *RTREE {R-Tree e
0050: 78 74 65 6e 73 69 6f 6e 7d 20 7b 52 2d 54 72 65  xtension} {R-Tre
0060: 65 73 7d 3c 2f 74 63 6c 3e 0a 3c 74 61 62 6c 65  es}</tcl>.<table
0070: 5f 6f 66 5f 63 6f 6e 74 65 6e 74 73 3e 0a 0a 3c  _of_contents>..<
0080: 68 31 3e 4f 76 65 72 76 69 65 77 3c 2f 68 31 3e  h1>Overview</h1>
0090: 0a 0a 3c 70 3e 0a 41 6e 20 5b 68 74 74 70 3a 2f  ..<p>.An [http:/
00a0: 2f 65 6e 2e 77 69 6b 69 70 65 64 69 61 2e 6f 72  /en.wikipedia.or
00b0: 67 2f 77 69 6b 69 2f 52 2d 74 72 65 65 20 7c 20  g/wiki/R-tree | 
00c0: 52 2d 54 72 65 65 5d 20 69 73 20 61 20 73 70 65  R-Tree] is a spe
00d0: 63 69 61 6c 0a 69 6e 64 65 78 20 74 68 61 74 20  cial.index that 
00e0: 69 73 20 64 65 73 69 67 6e 65 64 20 66 6f 72 20  is designed for 
00f0: 64 6f 69 6e 67 20 72 61 6e 67 65 20 71 75 65 72  doing range quer
0100: 69 65 73 2e 20 20 52 2d 54 72 65 65 73 20 61 72  ies.  R-Trees ar
0110: 65 20 6d 6f 73 74 20 63 6f 6d 6d 6f 6e 6c 79 0a  e most commonly.
0120: 75 73 65 64 20 69 6e 20 67 65 6f 73 70 61 74 69  used in geospati
0130: 61 6c 20 73 79 73 74 65 6d 73 20 77 68 65 72 65  al systems where
0140: 20 65 61 63 68 20 65 6e 74 72 79 20 69 73 20 61   each entry is a
0150: 20 72 65 63 74 61 6e 67 6c 65 20 77 69 74 68 20   rectangle with 
0160: 6d 69 6e 69 6d 75 6d 20 61 6e 64 0a 6d 61 78 69  minimum and.maxi
0170: 6d 75 6d 20 58 20 61 6e 64 20 59 20 63 6f 6f 72  mum X and Y coor
0180: 64 69 6e 61 74 65 73 2e 20 20 47 69 76 65 6e 20  dinates.  Given 
0190: 61 20 71 75 65 72 79 20 72 65 63 74 61 6e 67 6c  a query rectangl
01a0: 65 2c 20 61 6e 20 52 2d 54 72 65 65 20 69 73 20  e, an R-Tree is 
01b0: 61 62 6c 65 0a 74 6f 20 71 75 69 63 6b 6c 79 20  able.to quickly 
01c0: 66 69 6e 64 20 61 6c 6c 20 65 6e 74 72 69 65 73  find all entries
01d0: 20 74 68 61 74 20 61 72 65 20 63 6f 6e 74 61 69   that are contai
01e0: 6e 65 64 20 77 69 74 68 69 6e 20 74 68 65 20 71  ned within the q
01f0: 75 65 72 79 20 72 65 63 74 61 6e 67 6c 65 0a 6f  uery rectangle.o
0200: 72 20 77 68 69 63 68 20 6f 76 65 72 6c 61 70 20  r which overlap 
0210: 74 68 65 20 71 75 65 72 79 20 72 65 63 74 61 6e  the query rectan
0220: 67 6c 65 2e 20 20 54 68 69 73 20 69 64 65 61 20  gle.  This idea 
0230: 69 73 20 65 61 73 69 6c 79 20 65 78 74 65 6e 64  is easily extend
0240: 65 64 20 74 6f 0a 74 68 72 65 65 20 64 69 6d 65  ed to.three dime
0250: 6e 73 69 6f 6e 73 20 66 6f 72 20 75 73 65 20 69  nsions for use i
0260: 6e 20 43 41 44 20 73 79 73 74 65 6d 73 2e 20 20  n CAD systems.  
0270: 52 2d 54 72 65 65 73 20 61 6c 73 6f 20 66 69 6e  R-Trees also fin
0280: 64 20 75 73 65 20 69 6e 20 74 69 6d 65 2d 64 6f  d use in time-do
0290: 6d 61 69 6e 0a 72 61 6e 67 65 20 6c 6f 6f 6b 2d  main.range look-
02a0: 75 70 73 2e 20 20 46 6f 72 20 65 78 61 6d 70 6c  ups.  For exampl
02b0: 65 2c 20 73 75 70 70 6f 73 65 20 61 20 64 61 74  e, suppose a dat
02c0: 61 62 61 73 65 20 72 65 63 6f 72 64 73 20 74 68  abase records th
02d0: 65 20 73 74 61 72 74 69 6e 67 20 61 6e 64 0a 65  e starting and.e
02e0: 6e 64 69 6e 67 20 74 69 6d 65 73 20 66 6f 72 20  nding times for 
02f0: 61 20 6c 61 72 67 65 20 6e 75 6d 62 65 72 20 6f  a large number o
0300: 66 20 65 76 65 6e 74 73 2e 20 20 41 20 52 2d 54  f events.  A R-T
0310: 72 65 65 20 69 73 20 61 62 6c 65 20 74 6f 20 71  ree is able to q
0320: 75 69 63 6b 6c 79 0a 66 69 6e 64 20 61 6c 6c 20  uickly.find all 
0330: 65 76 65 6e 74 73 20 74 68 61 74 20 77 65 72 65  events that were
0340: 20 61 63 74 69 76 65 20 61 74 20 61 6e 79 20 74   active at any t
0350: 69 6d 65 20 64 75 72 69 6e 67 20 61 20 67 69 76  ime during a giv
0360: 65 6e 0a 74 69 6d 65 20 69 6e 74 65 72 76 61 6c  en.time interval
0370: 2c 20 6f 72 20 61 6c 6c 20 65 76 65 6e 74 73 20  , or all events 
0380: 74 68 61 74 20 73 74 61 72 74 65 64 20 64 75 72  that started dur
0390: 69 6e 67 20 61 20 70 61 72 74 69 63 75 6c 61 72  ing a particular
03a0: 20 74 69 6d 65 20 69 6e 74 65 72 76 61 6c 2c 0a   time interval,.
03b0: 6f 72 20 61 6c 6c 20 65 76 65 6e 74 73 20 74 68  or all events th
03c0: 61 74 20 62 6f 74 68 20 73 74 61 72 74 65 64 20  at both started 
03d0: 61 6e 64 20 65 6e 64 65 64 20 77 69 74 68 69 6e  and ended within
03e0: 20 61 20 67 69 76 65 6e 20 74 69 6d 65 20 69 6e   a given time in
03f0: 74 65 72 76 61 6c 2e 0a 41 6e 64 20 73 6f 20 66  terval..And so f
0400: 6f 72 74 68 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a  orth..</p>..<p>.
0410: 54 68 65 20 52 2d 54 72 65 65 20 63 6f 6e 63 65  The R-Tree conce
0420: 70 74 20 6f 72 69 67 69 6e 61 74 65 64 20 77 69  pt originated wi
0430: 74 68 20 0a 5b 68 74 74 70 3a 2f 2f 77 77 77 2e  th .[http://www.
0440: 62 61 79 6d 6f 6f 6e 2e 63 6f 6d 2f 7e 74 67 32  baymoon.com/~tg2
0450: 2f 20 7c 20 54 6f 6e 69 20 47 75 74 74 6d 61 6e  / | Toni Guttman
0460: 5d 3a 20 0a 3c 65 6d 3e 52 2d 54 72 65 65 73 3a  ]: .<em>R-Trees:
0470: 20 41 20 44 79 6e 61 6d 69 63 20 49 6e 64 65 78   A Dynamic Index
0480: 20 53 74 72 75 63 74 75 72 65 20 66 6f 72 20 53   Structure for S
0490: 70 61 74 69 61 6c 20 53 65 61 72 63 68 69 6e 67  patial Searching
04a0: 3c 2f 65 6d 3e 2c 0a 50 72 6f 63 2e 20 31 39 38  </em>,.Proc. 198
04b0: 34 20 41 43 4d 20 53 49 47 4d 4f 44 20 49 6e 74  4 ACM SIGMOD Int
04c0: 65 72 6e 61 74 69 6f 6e 61 6c 20 43 6f 6e 66 65  ernational Confe
04d0: 72 65 6e 63 65 20 6f 6e 20 4d 61 6e 61 67 65 6d  rence on Managem
04e0: 65 6e 74 20 6f 66 20 44 61 74 61 2c 0a 70 70 2e  ent of Data,.pp.
04f0: 20 34 37 2d 35 37 2e 0a 54 68 65 20 69 6d 70 6c   47-57..The impl
0500: 65 6d 65 6e 74 61 74 69 6f 6e 20 66 6f 75 6e 64  ementation found
0510: 20 69 6e 20 53 51 4c 69 74 65 20 69 73 20 61 20   in SQLite is a 
0520: 72 65 66 69 6e 65 6d 65 6e 74 20 6f 66 20 47 75  refinement of Gu
0530: 74 74 6d 61 6e 27 73 20 6f 72 69 67 69 6e 61 6c  ttman's original
0540: 0a 69 64 65 61 2c 20 63 6f 6d 6d 6f 6e 6c 79 20  .idea, commonly 
0550: 63 61 6c 6c 65 64 20 22 52 2a 54 72 65 65 73 22  called "R*Trees"
0560: 2c 20 74 68 61 74 20 77 61 73 20 64 65 73 63 72  , that was descr
0570: 69 62 65 64 20 62 79 0a 4e 6f 72 62 65 72 74 20  ibed by.Norbert 
0580: 42 65 63 6b 6d 61 6e 6e 2c 20 48 61 6e 73 2d 50  Beckmann, Hans-P
0590: 65 74 65 72 20 4b 72 69 65 67 65 6c 2c 20 52 61  eter Kriegel, Ra
05a0: 6c 66 20 53 63 68 6e 65 69 64 65 72 2c 20 42 65  lf Schneider, Be
05b0: 72 6e 68 61 72 64 20 53 65 65 67 65 72 3a 0a 3c  rnhard Seeger:.<
05c0: 65 6d 3e 54 68 65 20 52 2a 2d 54 72 65 65 3a 20  em>The R*-Tree: 
05d0: 41 6e 20 45 66 66 69 63 69 65 6e 74 20 61 6e 64  An Efficient and
05e0: 20 52 6f 62 75 73 74 20 41 63 63 65 73 73 20 4d   Robust Access M
05f0: 65 74 68 6f 64 20 66 6f 72 20 50 6f 69 6e 74 73  ethod for Points
0600: 0a 61 6e 64 20 52 65 63 74 61 6e 67 6c 65 73 2e  .and Rectangles.
0610: 3c 2f 65 6d 3e 20 53 49 47 4d 4f 44 20 43 6f 6e  </em> SIGMOD Con
0620: 66 65 72 65 6e 63 65 20 31 39 39 30 3a 20 33 32  ference 1990: 32
0630: 32 2d 33 33 31 2e 0a 3c 2f 70 3e 0a 0a 3c 68 31  2-331..</p>..<h1
0640: 3e 43 6f 6d 70 69 6c 69 6e 67 20 54 68 65 20 52  >Compiling The R
0650: 2a 54 72 65 65 20 4d 6f 64 75 6c 65 3c 2f 68 31  *Tree Module</h1
0660: 3e 0a 0a 3c 70 3e 0a 54 68 65 20 73 6f 75 72 63  >..<p>.The sourc
0670: 65 20 63 6f 64 65 20 74 6f 20 74 68 65 20 53 51  e code to the SQ
0680: 4c 69 74 65 20 52 2a 54 72 65 65 20 6d 6f 64 75  Lite R*Tree modu
0690: 6c 65 20 69 73 20 69 6e 63 6c 75 64 65 64 20 61  le is included a
06a0: 73 20 70 61 72 74 0a 6f 66 20 74 68 65 20 5b 61  s part.of the [a
06b0: 6d 61 6c 67 61 6d 61 74 69 6f 6e 5d 20 62 75 74  malgamation] but
06c0: 20 69 73 20 64 69 73 61 62 6c 65 64 20 62 79 20   is disabled by 
06d0: 64 65 66 61 75 6c 74 2e 20 20 54 6f 20 65 6e 61  default.  To ena
06e0: 62 6c 65 20 74 68 65 0a 52 2a 54 72 65 65 20 6d  ble the.R*Tree m
06f0: 6f 64 75 6c 65 2c 20 73 69 6d 70 6c 79 20 63 6f  odule, simply co
0700: 6d 70 69 6c 65 20 77 69 74 68 20 74 68 65 20 5b  mpile with the [
0710: 53 51 4c 49 54 45 5f 45 4e 41 42 4c 45 5f 52 54  SQLITE_ENABLE_RT
0720: 52 45 45 5d 20 0a 43 2d 70 72 65 70 72 6f 63 65  REE] .C-preproce
0730: 73 73 6f 72 20 6d 61 63 72 6f 20 64 65 66 69 6e  ssor macro defin
0740: 65 64 2e 20 20 57 69 74 68 20 6d 61 6e 79 20 63  ed.  With many c
0750: 6f 6d 70 69 6c 65 72 73 2c 20 74 68 69 73 20 69  ompilers, this i
0760: 73 20 61 63 63 6f 6d 70 6c 69 73 68 65 64 0a 62  s accomplished.b
0770: 79 20 61 64 64 69 6e 67 20 74 68 65 20 6f 70 74  y adding the opt
0780: 69 6f 6e 20 22 2d 44 53 51 4c 49 54 45 5f 45 4e  ion "-DSQLITE_EN
0790: 41 42 4c 45 5f 52 54 52 45 45 3d 31 22 20 74 6f  ABLE_RTREE=1" to
07a0: 20 74 68 65 20 63 6f 6d 70 69 6c 65 72 0a 63 6f   the compiler.co
07b0: 6d 6d 61 6e 64 2d 6c 69 6e 65 2e 0a 3c 2f 70 3e  mmand-line..</p>
07c0: 0a 0a 3c 68 31 3e 55 73 69 6e 67 20 74 68 65 20  ..<h1>Using the 
07d0: 52 2a 54 72 65 65 20 4d 6f 64 75 6c 65 3c 2f 68  R*Tree Module</h
07e0: 31 3e 0a 0a 3c 70 3e 0a 54 68 65 20 53 51 4c 69  1>..<p>.The SQLi
07f0: 74 65 20 52 2a 54 72 65 65 20 6d 6f 64 75 6c 65  te R*Tree module
0800: 20 69 73 20 69 6d 70 6c 65 6d 65 6e 74 65 64 20   is implemented 
0810: 61 73 20 61 0a 5b 73 71 6c 69 74 65 33 5f 63 72  as a.[sqlite3_cr
0820: 65 61 74 65 5f 6d 6f 64 75 6c 65 20 7c 20 76 69  eate_module | vi
0830: 72 74 75 61 6c 20 74 61 62 6c 65 5d 2e 20 20 5e  rtual table].  ^
0840: 45 61 63 68 20 52 2a 54 72 65 65 20 69 6e 64 65  Each R*Tree inde
0850: 78 20 69 73 20 61 0a 76 69 72 74 75 61 6c 20 74  x is a.virtual t
0860: 61 62 6c 65 20 77 69 74 68 20 61 6e 20 6f 64 64  able with an odd
0870: 20 6e 75 6d 62 65 72 20 6f 66 20 63 6f 6c 75 6d   number of colum
0880: 6e 73 20 62 65 74 77 65 65 6e 20 33 20 61 6e 64  ns between 3 and
0890: 20 31 31 2e 0a 5e 54 68 65 20 66 69 72 73 74 20   11..^The first 
08a0: 63 6f 6c 75 6d 6e 20 69 73 20 61 6c 77 61 79 73  column is always
08b0: 20 61 20 36 34 2d 62 69 74 20 73 69 67 6e 65 64   a 64-bit signed
08c0: 20 69 6e 74 65 67 65 72 20 70 72 69 6d 61 72 79   integer primary
08d0: 20 6b 65 79 2e 0a 5e 54 68 65 20 6f 74 68 65 72   key..^The other
08e0: 20 63 6f 6c 75 6d 6e 73 20 61 72 65 20 70 61 69   columns are pai
08f0: 72 73 2c 20 6f 6e 65 20 70 61 69 72 20 70 65 72  rs, one pair per
0900: 20 64 69 6d 65 6e 73 69 6f 6e 2c 20 63 6f 6e 74   dimension, cont
0910: 61 69 6e 69 6e 67 20 74 68 65 0a 6d 69 6e 69 6d  aining the.minim
0920: 75 6d 20 61 6e 64 20 6d 61 78 69 6d 75 6d 20 76  um and maximum v
0930: 61 6c 75 65 73 20 66 6f 72 20 74 68 61 74 20 64  alues for that d
0940: 69 6d 65 6e 73 69 6f 6e 2c 20 72 65 73 70 65 63  imension, respec
0950: 74 69 76 65 6c 79 2e 0a 5e 41 20 31 2d 64 69 6d  tively..^A 1-dim
0960: 65 6e 73 69 6f 6e 61 6c 20 52 2a 54 72 65 65 20  ensional R*Tree 
0970: 74 68 75 73 20 68 61 73 20 33 20 63 6f 6c 75 6d  thus has 3 colum
0980: 6e 73 2e 20 20 0a 5e 41 20 32 2d 64 69 6d 65 6e  ns.  .^A 2-dimen
0990: 73 69 6f 6e 61 6c 20 52 2a 54 72 65 65 20 68 61  sional R*Tree ha
09a0: 73 20 35 20 63 6f 6c 75 6d 6e 73 2e 0a 5e 41 20  s 5 columns..^A 
09b0: 33 2d 64 69 6d 65 6e 73 69 6f 6e 61 6c 20 52 2a  3-dimensional R*
09c0: 54 72 65 65 20 68 61 73 20 37 20 63 6f 6c 75 6d  Tree has 7 colum
09d0: 6e 73 2e 0a 5e 41 20 34 2d 64 69 6d 65 6e 73 69  ns..^A 4-dimensi
09e0: 6f 6e 61 6c 20 52 2a 54 72 65 65 20 68 61 73 20  onal R*Tree has 
09f0: 39 20 63 6f 6c 75 6d 6e 73 2e 0a 5e 41 6e 64 20  9 columns..^And 
0a00: 61 20 35 2d 64 69 6d 65 6e 73 69 6f 6e 61 6c 20  a 5-dimensional 
0a10: 52 2a 54 72 65 65 20 68 61 73 20 31 31 20 63 6f  R*Tree has 11 co
0a20: 6c 75 6d 6e 73 2e 20 20 5e 54 68 65 20 53 51 4c  lumns.  ^The SQL
0a30: 69 74 65 20 52 2a 54 72 65 65 20 69 6d 70 6c 65  ite R*Tree imple
0a40: 6d 65 6e 74 61 74 69 6f 6e 0a 64 6f 65 73 20 6e  mentation.does n
0a50: 6f 74 20 73 75 70 70 6f 72 74 20 52 2a 54 72 65  ot support R*Tre
0a60: 65 73 20 77 69 64 65 72 20 74 68 61 6e 20 35 20  es wider than 5 
0a70: 64 69 6d 65 6e 73 69 6f 6e 73 2e 0a 3c 2f 70 3e  dimensions..</p>
0a80: 0a 0a 3c 70 3e 0a 5e 54 68 65 20 66 69 72 73 74  ..<p>.^The first
0a90: 20 63 6f 6c 75 6d 6e 20 6f 66 20 61 6e 20 53 51   column of an SQ
0aa0: 4c 69 74 65 20 52 2a 54 72 65 65 20 69 73 20 73  Lite R*Tree is s
0ab0: 69 6d 69 6c 61 72 20 74 6f 20 61 6e 20 69 6e 74  imilar to an int
0ac0: 65 67 65 72 20 70 72 69 6d 61 72 79 20 0a 6b 65  eger primary .ke
0ad0: 79 20 63 6f 6c 75 6d 6e 20 6f 66 20 61 20 6e 6f  y column of a no
0ae0: 72 6d 61 6c 20 53 51 4c 69 74 65 20 74 61 62 6c  rmal SQLite tabl
0af0: 65 2e 20 49 74 20 6d 61 79 20 6f 6e 6c 79 20 73  e. It may only s
0b00: 74 6f 72 65 20 61 20 36 34 2d 62 69 74 20 73 69  tore a 64-bit si
0b10: 67 6e 65 64 0a 69 6e 74 65 67 65 72 20 76 61 6c  gned.integer val
0b20: 75 65 2e 20 49 6e 73 65 72 74 69 6e 67 20 61 20  ue. Inserting a 
0b30: 4e 55 4c 4c 20 76 61 6c 75 65 20 69 6e 74 6f 20  NULL value into 
0b40: 74 68 69 73 20 63 6f 6c 75 6d 6e 20 63 61 75 73  this column caus
0b50: 65 73 20 53 51 4c 69 74 65 0a 74 6f 20 61 75 74  es SQLite.to aut
0b60: 6f 6d 61 74 69 63 61 6c 6c 79 20 67 65 6e 65 72  omatically gener
0b70: 61 74 65 20 61 20 6e 65 77 20 75 6e 69 71 75 65  ate a new unique
0b80: 20 70 72 69 6d 61 72 79 20 6b 65 79 20 76 61 6c   primary key val
0b90: 75 65 2e 20 49 66 20 61 6e 20 61 74 74 65 6d 70  ue. If an attemp
0ba0: 74 0a 69 73 20 6d 61 64 65 20 74 6f 20 69 6e 73  t.is made to ins
0bb0: 65 72 74 20 61 6e 79 20 6f 74 68 65 72 20 6e 6f  ert any other no
0bc0: 6e 2d 69 6e 74 65 67 65 72 20 76 61 6c 75 65 20  n-integer value 
0bd0: 69 6e 74 6f 20 74 68 69 73 20 63 6f 6c 75 6d 6e  into this column
0be0: 2c 0a 74 68 65 20 72 2d 74 72 65 65 20 6d 6f 64  ,.the r-tree mod
0bf0: 75 6c 65 20 73 69 6c 65 6e 74 6c 79 20 63 6f 6e  ule silently con
0c00: 76 65 72 74 73 20 69 74 20 74 6f 20 61 6e 20 69  verts it to an i
0c10: 6e 74 65 67 65 72 20 62 65 66 6f 72 65 20 77 72  nteger before wr
0c20: 69 74 69 6e 67 20 69 74 0a 69 6e 74 6f 20 74 68  iting it.into th
0c30: 65 20 64 61 74 61 62 61 73 65 2e 0a 3c 70 3e 0a  e database..<p>.
0c40: 5e 54 68 65 20 6d 69 6e 2f 6d 61 78 2d 76 61 6c  ^The min/max-val
0c50: 75 65 20 70 61 69 72 20 63 6f 6c 75 6d 6e 73 20  ue pair columns 
0c60: 61 72 65 20 73 74 6f 72 65 64 20 61 73 20 33 32  are stored as 32
0c70: 2d 62 69 74 20 66 6c 6f 61 74 69 6e 67 20 70 6f  -bit floating po
0c80: 69 6e 74 20 76 61 6c 75 65 73 20 66 6f 72 0a 22  int values for."
0c90: 72 74 72 65 65 22 20 76 69 72 74 75 61 6c 20 74  rtree" virtual t
0ca0: 61 62 6c 65 73 20 6f 72 20 61 73 20 33 32 2d 62  ables or as 32-b
0cb0: 69 74 20 73 69 67 6e 65 64 20 69 6e 74 65 67 65  it signed intege
0cc0: 72 73 20 69 6e 20 22 72 74 72 65 65 5f 69 33 32  rs in "rtree_i32
0cd0: 22 20 76 69 72 74 75 61 6c 0a 74 61 62 6c 65 73  " virtual.tables
0ce0: 2e 20 20 5e 55 6e 6c 69 6b 65 20 72 65 67 75 6c  .  ^Unlike regul
0cf0: 61 72 20 53 51 4c 69 74 65 20 74 61 62 6c 65 73  ar SQLite tables
0d00: 20 77 68 69 63 68 20 63 61 6e 20 73 74 6f 72 65   which can store
0d10: 20 64 61 74 61 20 69 6e 20 61 20 76 61 72 69 65   data in a varie
0d20: 74 79 20 6f 66 0a 64 61 74 61 74 79 70 65 73 20  ty of.datatypes 
0d30: 61 6e 64 20 66 6f 72 6d 61 74 73 2c 20 74 68 65  and formats, the
0d40: 20 52 2a 54 72 65 65 20 72 69 67 69 64 6c 79 20   R*Tree rigidly 
0d50: 65 6e 66 6f 72 63 65 20 74 68 65 73 65 20 73 74  enforce these st
0d60: 6f 72 61 67 65 20 74 79 70 65 73 2e 20 0a 49 66  orage types. .If
0d70: 20 61 6e 79 20 6f 74 68 65 72 20 74 79 70 65 20   any other type 
0d80: 6f 66 20 76 61 6c 75 65 20 69 73 20 69 6e 73 65  of value is inse
0d90: 72 74 65 64 20 69 6e 74 6f 20 73 75 63 68 20 61  rted into such a
0da0: 20 63 6f 6c 75 6d 6e 2c 20 74 68 65 20 72 2d 74   column, the r-t
0db0: 72 65 65 0a 6d 6f 64 75 6c 65 20 73 69 6c 65 6e  ree.module silen
0dc0: 74 6c 79 20 63 6f 6e 76 65 72 74 73 20 69 74 20  tly converts it 
0dd0: 74 6f 20 74 68 65 20 72 65 71 75 69 72 65 64 20  to the required 
0de0: 74 79 70 65 20 62 65 66 6f 72 65 20 77 72 69 74  type before writ
0df0: 69 6e 67 20 74 68 65 0a 6e 65 77 20 72 65 63 6f  ing the.new reco
0e00: 72 64 20 74 6f 20 74 68 65 20 64 61 74 61 62 61  rd to the databa
0e10: 73 65 2e 0a 0a 3c 68 32 3e 43 72 65 61 74 69 6e  se...<h2>Creatin
0e20: 67 20 41 6e 20 52 2a 54 72 65 65 20 49 6e 64 65  g An R*Tree Inde
0e30: 78 3c 2f 68 32 3e 0a 0a 5e 28 3c 70 3e 0a 41 20  x</h2>..^(<p>.A 
0e40: 6e 65 77 20 52 2a 54 72 65 65 20 69 6e 64 65 78  new R*Tree index
0e50: 20 69 73 20 63 72 65 61 74 65 64 20 61 73 20 66   is created as f
0e60: 6f 6c 6c 6f 77 73 3a 0a 3c 2f 70 3e 0a 0a 3c 62  ollows:.</p>..<b
0e70: 6c 6f 63 6b 71 75 6f 74 65 3e 3c 70 72 65 3e 0a  lockquote><pre>.
0e80: 43 52 45 41 54 45 20 56 49 52 54 55 41 4c 20 54  CREATE VIRTUAL T
0e90: 41 42 4c 45 20 3c 65 6d 3e 26 6c 74 3b 6e 61 6d  ABLE <em>&lt;nam
0ea0: 65 26 67 74 3b 3c 2f 65 6d 3e 20 55 53 49 4e 47  e&gt;</em> USING
0eb0: 20 72 74 72 65 65 28 3c 65 6d 3e 26 6c 74 3b 63   rtree(<em>&lt;c
0ec0: 6f 6c 75 6d 6e 2d 6e 61 6d 65 73 26 67 74 3b 3c  olumn-names&gt;<
0ed0: 2f 65 6d 3e 29 3b 0a 3c 2f 70 72 65 3e 3c 2f 62  /em>);.</pre></b
0ee0: 6c 6f 63 6b 71 75 6f 74 65 3e 29 5e 0a 0a 3c 70  lockquote>)^..<p
0ef0: 3e 0a 54 68 65 20 3c 65 6d 3e 26 6c 74 3b 6e 61  >.The <em>&lt;na
0f00: 6d 65 26 67 74 3b 3c 2f 65 6d 3e 20 69 73 20 74  me&gt;</em> is t
0f10: 68 65 20 6e 61 6d 65 20 79 6f 75 72 20 61 70 70  he name your app
0f20: 6c 69 63 61 74 69 6f 6e 20 63 68 6f 6f 73 65 73  lication chooses
0f30: 20 66 6f 72 20 74 68 65 0a 52 2a 54 72 65 65 20   for the.R*Tree 
0f40: 69 6e 64 65 78 20 61 6e 64 20 3c 65 6d 3e 26 6c  index and <em>&l
0f50: 74 3b 63 6f 6c 75 6d 6e 2d 6e 61 6d 65 73 26 67  t;column-names&g
0f60: 74 3b 3c 2f 65 6d 3e 20 69 73 20 61 20 63 6f 6d  t;</em> is a com
0f70: 6d 61 20 73 65 70 61 72 61 74 65 64 20 6c 69 73  ma separated lis
0f80: 74 0a 6f 66 20 62 65 74 77 65 65 6e 20 33 20 61  t.of between 3 a
0f90: 6e 64 20 31 31 20 63 6f 6c 75 6d 6e 73 2e 0a 5e  nd 11 columns..^
0fa0: 28 54 68 65 20 76 69 72 74 75 61 6c 20 26 6c 74  (The virtual &lt
0fb0: 3b 6e 61 6d 65 26 67 74 3b 20 74 61 62 6c 65 20  ;name&gt; table 
0fc0: 63 72 65 61 74 65 73 20 74 68 72 65 65 20 22 73  creates three "s
0fd0: 68 61 64 6f 77 22 20 74 61 62 6c 65 73 20 74 6f  hadow" tables to
0fe0: 20 61 63 74 75 61 6c 6c 79 0a 73 74 6f 72 65 20   actually.store 
0ff0: 69 74 73 20 63 6f 6e 74 65 6e 74 2e 20 20 54 68  its content.  Th
1000: 65 20 6e 61 6d 65 73 20 6f 66 20 74 68 65 73 65  e names of these
1010: 20 73 68 61 64 6f 77 20 74 61 62 6c 65 73 20 61   shadow tables a
1020: 72 65 3a 0a 3c 2f 70 3e 0a 0a 3c 62 6c 6f 63 6b  re:.</p>..<block
1030: 71 75 6f 74 65 3e 0a 3c 65 6d 3e 26 6c 74 3b 6e  quote>.<em>&lt;n
1040: 61 6d 65 26 67 74 3b 3c 2f 65 6d 3e 3c 73 74 72  ame&gt;</em><str
1050: 6f 6e 67 3e 5f 6e 6f 64 65 3c 2f 73 74 72 6f 6e  ong>_node</stron
1060: 67 3e 3c 62 72 3e 0a 3c 65 6d 3e 26 6c 74 3b 6e  g><br>.<em>&lt;n
1070: 61 6d 65 26 67 74 3b 3c 2f 65 6d 3e 3c 73 74 72  ame&gt;</em><str
1080: 6f 6e 67 3e 5f 72 6f 77 69 64 3c 2f 73 74 72 6f  ong>_rowid</stro
1090: 6e 67 3e 3c 62 72 3e 0a 3c 65 6d 3e 26 6c 74 3b  ng><br>.<em>&lt;
10a0: 6e 61 6d 65 26 67 74 3b 3c 2f 65 6d 3e 3c 73 74  name&gt;</em><st
10b0: 72 6f 6e 67 3e 5f 70 61 72 65 6e 74 3c 2f 73 74  rong>_parent</st
10c0: 72 6f 6e 67 3e 0a 3c 2f 62 6c 6f 63 6b 71 75 6f  rong>.</blockquo
10d0: 74 65 3e 29 5e 0a 0a 3c 70 3e 0a 5e 54 68 65 20  te>)^..<p>.^The 
10e0: 73 68 61 64 6f 77 20 74 61 62 6c 65 73 20 61 72  shadow tables ar
10f0: 65 20 6f 72 64 69 6e 61 72 79 20 53 51 4c 69 74  e ordinary SQLit
1100: 65 20 64 61 74 61 20 74 61 62 6c 65 73 2e 20 20  e data tables.  
1110: 59 6f 75 20 63 61 6e 20 71 75 65 72 79 20 74 68  You can query th
1120: 65 6d 20 0a 64 69 72 65 63 74 6c 79 20 69 66 20  em .directly if 
1130: 79 6f 75 20 6c 69 6b 65 2c 20 74 68 6f 75 67 68  you like, though
1140: 20 74 68 69 73 20 75 6e 6c 69 6b 65 6c 79 20 74   this unlikely t
1150: 6f 20 72 65 76 65 61 6c 20 61 6e 79 74 68 69 6e  o reveal anythin
1160: 67 20 70 61 72 74 69 63 75 6c 61 72 6c 79 0a 75  g particularly.u
1170: 73 65 66 75 6c 2e 20 0a 5e 41 6e 64 20 79 6f 75  seful. .^And you
1180: 20 63 61 6e 20 5b 55 50 44 41 54 45 5d 2c 20 5b   can [UPDATE], [
1190: 44 45 4c 45 54 45 5d 2c 20 5b 49 4e 53 45 52 54  DELETE], [INSERT
11a0: 5d 20 6f 72 20 65 76 65 6e 20 5b 44 52 4f 50 20  ] or even [DROP 
11b0: 54 41 42 4c 45 20 7c 20 44 52 4f 50 5d 20 0a 74  TABLE | DROP] .t
11c0: 68 65 20 73 68 61 64 6f 77 20 74 61 62 6c 65 73  he shadow tables
11d0: 2c 20 74 68 6f 75 67 68 20 64 6f 69 6e 67 20 73  , though doing s
11e0: 6f 20 77 69 6c 6c 20 63 6f 72 72 75 70 74 20 79  o will corrupt y
11f0: 6f 75 72 20 52 2a 54 72 65 65 20 69 6e 64 65 78  our R*Tree index
1200: 2e 0a 53 6f 20 69 74 20 69 73 20 62 65 73 74 20  ..So it is best 
1210: 74 6f 20 73 69 6d 70 6c 79 20 69 67 6e 6f 72 65  to simply ignore
1220: 20 74 68 65 20 73 68 61 64 6f 77 20 74 61 62 6c   the shadow tabl
1230: 65 73 2e 20 20 52 65 63 6f 67 6e 69 7a 65 20 74  es.  Recognize t
1240: 68 61 74 20 74 68 65 79 0a 68 6f 6c 64 20 79 6f  hat they.hold yo
1250: 75 72 20 52 2a 54 72 65 65 20 69 6e 64 65 78 20  ur R*Tree index 
1260: 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 61 6e 64 20  information and 
1270: 6c 65 74 20 69 74 20 67 6f 20 61 73 20 74 68 61  let it go as tha
1280: 74 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a 5e 28 41  t..</p>..<p>.^(A
1290: 73 20 61 6e 20 65 78 61 6d 70 6c 65 2c 20 63 6f  s an example, co
12a0: 6e 73 69 64 65 72 20 63 72 65 61 74 69 6e 67 20  nsider creating 
12b0: 61 20 74 77 6f 2d 64 69 6d 65 6e 73 69 6f 6e 61  a two-dimensiona
12c0: 6c 20 52 2a 54 72 65 65 20 69 6e 64 65 78 20 66  l R*Tree index f
12d0: 6f 72 20 75 73 65 20 69 6e 20 0a 73 70 61 74 69  or use in .spati
12e0: 61 6c 20 71 75 65 72 69 65 73 3a 0a 3c 2f 70 3e  al queries:.</p>
12f0: 0a 0a 3c 62 6c 6f 63 6b 71 75 6f 74 65 3e 3c 70  ..<blockquote><p
1300: 72 65 3e 0a 43 52 45 41 54 45 20 56 49 52 54 55  re>.CREATE VIRTU
1310: 41 4c 20 54 41 42 4c 45 20 64 65 6d 6f 5f 69 6e  AL TABLE demo_in
1320: 64 65 78 20 55 53 49 4e 47 20 72 74 72 65 65 28  dex USING rtree(
1330: 0a 20 20 20 69 64 2c 20 20 20 20 20 20 20 20 20  .   id,         
1340: 20 20 20 20 20 2d 2d 20 49 6e 74 65 67 65 72 20       -- Integer 
1350: 70 72 69 6d 61 72 79 20 6b 65 79 0a 20 20 20 6d  primary key.   m
1360: 69 6e 58 2c 20 6d 61 78 58 2c 20 20 20 20 20 20  inX, maxX,      
1370: 2d 2d 20 4d 69 6e 69 6d 75 6d 20 61 6e 64 20 6d  -- Minimum and m
1380: 61 78 69 6d 75 6d 20 58 20 63 6f 6f 72 64 69 6e  aximum X coordin
1390: 61 74 65 0a 20 20 20 6d 69 6e 59 2c 20 6d 61 78  ate.   minY, max
13a0: 59 20 20 20 20 20 20 20 2d 2d 20 4d 69 6e 69 6d  Y       -- Minim
13b0: 75 6d 20 61 6e 64 20 6d 61 78 69 6d 75 6d 20 59  um and maximum Y
13c0: 20 63 6f 6f 72 64 69 6e 61 74 65 0a 29 3b 0a 3c   coordinate.);.<
13d0: 2f 70 72 65 3e 3c 2f 62 6c 6f 63 6b 71 75 6f 74  /pre></blockquot
13e0: 65 3e 29 5e 0a 0a 3c 68 32 3e 50 6f 70 75 6c 61  e>)^..<h2>Popula
13f0: 74 69 6e 67 20 41 6e 20 52 2a 54 72 65 65 20 49  ting An R*Tree I
1400: 6e 64 65 78 3c 2f 68 32 3e 0a 0a 3c 70 3e 0a 5e  ndex</h2>..<p>.^
1410: 54 68 65 20 75 73 75 61 6c 20 5b 49 4e 53 45 52  The usual [INSER
1420: 54 5d 2c 20 5b 55 50 44 41 54 45 5d 2c 20 61 6e  T], [UPDATE], an
1430: 64 20 5b 44 45 4c 45 54 45 5d 20 63 6f 6d 6d 61  d [DELETE] comma
1440: 6e 64 73 20 77 6f 72 6b 20 6f 6e 20 61 6e 20 52  nds work on an R
1450: 2a 54 72 65 65 0a 69 6e 64 65 78 20 6a 75 73 74  *Tree.index just
1460: 20 6c 69 6b 65 20 6f 6e 20 72 65 67 75 6c 61 72   like on regular
1470: 20 74 61 62 6c 65 73 2e 20 20 5e 28 53 6f 20 74   tables.  ^(So t
1480: 6f 20 69 6e 73 65 72 74 20 73 6f 6d 65 20 64 61  o insert some da
1490: 74 61 20 69 6e 74 6f 20 6f 75 72 20 73 61 6d 70  ta into our samp
14a0: 6c 65 0a 52 2a 54 72 65 65 20 69 6e 64 65 78 2c  le.R*Tree index,
14b0: 20 77 65 20 63 61 6e 20 64 6f 20 73 6f 6d 65 74   we can do somet
14c0: 68 69 6e 67 20 6c 69 6b 65 20 74 68 69 73 3a 0a  hing like this:.
14d0: 3c 2f 70 3e 0a 0a 3c 62 6c 6f 63 6b 71 75 6f 74  </p>..<blockquot
14e0: 65 3e 3c 70 72 65 3e 0a 49 4e 53 45 52 54 20 49  e><pre>.INSERT I
14f0: 4e 54 4f 20 64 65 6d 6f 5f 69 6e 64 65 78 20 56  NTO demo_index V
1500: 41 4c 55 45 53 28 0a 20 20 20 20 31 2c 20 20 20  ALUES(.    1,   
1510: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1520: 2d 2d 20 50 72 69 6d 61 72 79 20 6b 65 79 20 2d  -- Primary key -
1530: 2d 20 53 51 4c 69 74 65 2e 6f 72 67 20 68 65 61  - SQLite.org hea
1540: 64 71 75 61 72 74 65 72 73 0a 20 20 20 20 2d 38  dquarters.    -8
1550: 30 2e 37 37 34 39 2c 20 2d 38 30 2e 37 37 34 37  0.7749, -80.7747
1560: 2c 20 20 2d 2d 20 4c 6f 6e 67 69 74 75 64 65 20  ,  -- Longitude 
1570: 72 61 6e 67 65 0a 20 20 20 20 33 35 2e 33 37 37  range.    35.377
1580: 36 2c 20 33 35 2e 33 37 37 38 20 20 20 20 20 2d  6, 35.3778     -
1590: 2d 20 4c 61 74 69 74 75 64 65 20 72 61 6e 67 65  - Latitude range
15a0: 0a 29 3b 0a 49 4e 53 45 52 54 20 49 4e 54 4f 20  .);.INSERT INTO 
15b0: 64 65 6d 6f 5f 69 6e 64 65 78 20 56 41 4c 55 45  demo_index VALUE
15c0: 53 28 0a 20 20 20 20 32 2c 20 20 20 20 20 20 20  S(.    2,       
15d0: 20 20 20 20 20 20 20 20 20 20 20 20 2d 2d 20 4e              -- N
15e0: 43 20 31 32 74 68 20 43 6f 6e 67 72 65 73 73 69  C 12th Congressi
15f0: 6f 6e 61 6c 20 44 69 73 74 72 69 63 74 20 69 6e  onal District in
1600: 20 32 30 31 30 0a 20 20 20 20 2d 38 31 2e 30 2c   2010.    -81.0,
1610: 20 2d 37 39 2e 36 2c 0a 20 20 20 20 33 35 2e 30   -79.6,.    35.0
1620: 2c 20 33 36 2e 32 0a 29 3b 0a 3c 2f 70 72 65 3e  , 36.2.);.</pre>
1630: 3c 2f 62 6c 6f 63 6b 71 75 6f 74 65 3e 29 5e 0a  </blockquote>)^.
1640: 0a 3c 70 3e 0a 54 68 65 20 65 6e 74 72 69 65 73  .<p>.The entries
1650: 20 61 62 6f 76 65 20 6d 69 67 68 74 20 72 65 70   above might rep
1660: 72 65 73 65 6e 74 20 28 66 6f 72 20 65 78 61 6d  resent (for exam
1670: 70 6c 65 29 20 61 20 62 6f 75 6e 64 69 6e 67 20  ple) a bounding 
1680: 62 6f 78 20 61 72 6f 75 6e 64 0a 74 68 65 20 6d  box around.the m
1690: 61 69 6e 20 6f 66 66 69 63 65 20 66 6f 72 20 53  ain office for S
16a0: 51 4c 69 74 65 2e 6f 72 67 20 61 6e 64 20 62 6f  QLite.org and bo
16b0: 75 6e 64 69 6e 67 20 62 6f 78 20 61 72 6f 75 6e  unding box aroun
16c0: 64 20 74 68 65 0a 31 32 74 68 20 43 6f 6e 67 72  d the.12th Congr
16d0: 65 73 73 69 6f 6e 61 6c 20 44 69 73 74 72 69 63  essional Distric
16e0: 74 20 6f 66 20 4e 6f 72 74 68 20 43 61 72 6f 6c  t of North Carol
16f0: 69 6e 61 20 28 70 72 69 6f 72 20 74 6f 20 74 68  ina (prior to th
1700: 65 20 32 30 31 31 0a 72 65 64 69 73 74 72 69 63  e 2011.redistric
1710: 74 69 6e 67 29 20 69 6e 20 77 68 69 63 68 20 53  ting) in which S
1720: 51 4c 69 74 65 2e 6f 72 67 20 77 61 73 20 6c 6f  QLite.org was lo
1730: 63 61 74 65 64 2e 20 20 0a 3c 2f 70 3e 0a 0a 3c  cated.  .</p>..<
1740: 68 32 3e 51 75 65 72 79 69 6e 67 20 41 6e 20 52  h2>Querying An R
1750: 2a 54 72 65 65 20 49 6e 64 65 78 3c 2f 68 32 3e  *Tree Index</h2>
1760: 0a 0a 3c 70 3e 0a 5e 41 6e 79 20 76 61 6c 69 64  ..<p>.^Any valid
1770: 20 71 75 65 72 79 20 77 69 6c 6c 20 77 6f 72 6b   query will work
1780: 20 61 67 61 69 6e 73 74 20 61 6e 20 52 2a 54 72   against an R*Tr
1790: 65 65 20 69 6e 64 65 78 2e 20 20 42 75 74 20 74  ee index.  But t
17a0: 68 65 20 52 2a 54 72 65 65 0a 69 6d 70 6c 65 6d  he R*Tree.implem
17b0: 65 6e 74 61 74 69 6f 6e 20 69 73 20 64 65 73 69  entation is desi
17c0: 67 6e 65 64 20 74 6f 20 6d 61 6b 65 20 74 77 6f  gned to make two
17d0: 20 6b 69 6e 64 73 20 6f 66 20 71 75 65 72 69 65   kinds of querie
17e0: 73 20 65 73 70 65 63 69 61 6c 6c 79 0a 65 66 66  s especially.eff
17f0: 69 63 69 65 6e 74 2e 20 20 5e 28 46 69 72 73 74  icient.  ^(First
1800: 2c 20 71 75 65 72 69 65 73 20 61 67 61 69 6e 73  , queries agains
1810: 74 20 74 68 65 20 70 72 69 6d 61 72 79 20 6b 65  t the primary ke
1820: 79 20 61 72 65 20 65 66 66 69 63 69 65 6e 74 3a  y are efficient:
1830: 0a 3c 2f 70 3e 0a 0a 3c 62 6c 6f 63 6b 71 75 6f  .</p>..<blockquo
1840: 74 65 3e 3c 70 72 65 3e 0a 53 45 4c 45 43 54 20  te><pre>.SELECT 
1850: 2a 20 46 52 4f 4d 20 64 65 6d 6f 5f 69 6e 64 65  * FROM demo_inde
1860: 78 20 57 48 45 52 45 20 69 64 3d 31 3b 0a 3c 2f  x WHERE id=1;.</
1870: 70 72 65 3e 3c 2f 62 6c 6f 63 6b 71 75 6f 74 65  pre></blockquote
1880: 3e 29 5e 0a 0a 3c 70 3e 0a 4f 66 20 63 6f 75 72  >)^..<p>.Of cour
1890: 73 65 2c 20 61 6e 20 6f 72 64 69 6e 61 72 79 20  se, an ordinary 
18a0: 53 51 4c 69 74 65 20 74 61 62 6c 65 20 77 69 6c  SQLite table wil
18b0: 6c 20 61 6c 73 6f 20 64 6f 20 61 20 71 75 65 72  l also do a quer
18c0: 79 20 61 67 61 69 6e 73 74 20 69 74 73 0a 69 6e  y against its.in
18d0: 74 65 67 65 72 20 70 72 69 6d 61 72 79 20 6b 65  teger primary ke
18e0: 79 20 65 66 66 69 63 69 65 6e 74 6c 79 2c 20 73  y efficiently, s
18f0: 6f 20 74 68 65 20 70 72 65 76 69 6f 75 73 20 69  o the previous i
1900: 73 20 6e 6f 20 62 69 67 20 64 65 61 6c 2e 0a 54  s no big deal..T
1910: 68 65 20 72 65 61 6c 20 72 65 61 73 6f 6e 20 66  he real reason f
1920: 6f 72 20 75 73 69 6e 67 20 61 6e 20 52 2a 54 72  or using an R*Tr
1930: 65 65 20 69 73 20 73 6f 20 74 68 61 74 0a 79 6f  ee is so that.yo
1940: 75 20 63 61 6e 20 65 66 66 69 63 69 65 6e 74 6c  u can efficientl
1950: 79 20 64 6f 20 69 6e 65 71 75 61 6c 69 74 79 20  y do inequality 
1960: 71 75 65 72 69 65 73 20 61 67 61 69 6e 73 74 20  queries against 
1970: 74 68 65 20 63 6f 6f 72 64 69 6e 61 74 65 0a 72  the coordinate.r
1980: 61 6e 67 65 73 2e 20 20 5e 28 54 6f 20 66 69 6e  anges.  ^(To fin
1990: 64 20 61 6c 6c 20 65 6c 65 6d 65 6e 74 73 20 6f  d all elements o
19a0: 66 20 74 68 65 20 69 6e 64 65 78 20 74 68 61 74  f the index that
19b0: 20 61 72 65 20 63 6f 6e 74 61 69 6e 65 64 20 77   are contained w
19c0: 69 74 68 69 6e 0a 74 68 65 20 76 69 63 69 6e 69  ithin.the vicini
19d0: 74 79 20 6f 66 20 43 68 61 72 6c 6f 74 74 65 2c  ty of Charlotte,
19e0: 20 4e 6f 72 74 68 20 43 61 72 6f 6c 69 6e 61 2c   North Carolina,
19f0: 20 6f 6e 65 20 6d 69 67 68 74 20 64 6f 3a 0a 3c   one might do:.<
1a00: 2f 70 3e 0a 0a 3c 62 6c 6f 63 6b 71 75 6f 74 65  /p>..<blockquote
1a10: 3e 3c 70 72 65 3e 0a 53 45 4c 45 43 54 20 69 64  ><pre>.SELECT id
1a20: 20 46 52 4f 4d 20 64 65 6d 6f 5f 69 6e 64 65 78   FROM demo_index
1a30: 0a 20 57 48 45 52 45 20 6d 69 6e 58 26 67 74 3b  . WHERE minX&gt;
1a40: 3d 2d 38 31 2e 30 38 20 41 4e 44 20 6d 61 78 58  =-81.08 AND maxX
1a50: 26 6c 74 3b 3d 2d 38 30 2e 35 38 0a 20 20 20 41  &lt;=-80.58.   A
1a60: 4e 44 20 6d 69 6e 59 26 67 74 3b 3d 33 35 2e 30  ND minY&gt;=35.0
1a70: 30 20 20 41 4e 44 20 6d 61 78 59 26 6c 74 3b 3d  0  AND maxY&lt;=
1a80: 33 35 2e 34 34 3b 0a 3c 2f 70 72 65 3e 3c 2f 62  35.44;.</pre></b
1a90: 6c 6f 63 6b 71 75 6f 74 65 3e 29 5e 0a 0a 3c 70  lockquote>)^..<p
1aa0: 3e 0a 5e 54 68 65 20 71 75 65 72 79 20 61 62 6f  >.^The query abo
1ab0: 76 65 20 77 6f 75 6c 64 20 76 65 72 79 20 71 75  ve would very qu
1ac0: 69 63 6b 6c 79 20 6c 6f 63 61 74 65 20 74 68 65  ickly locate the
1ad0: 20 69 64 20 6f 66 20 31 20 65 76 65 6e 20 69 66   id of 1 even if
1ae0: 20 74 68 65 0a 52 2a 54 72 65 65 20 63 6f 6e 74   the.R*Tree cont
1af0: 61 69 6e 65 64 20 6d 69 6c 6c 69 6f 6e 73 20 6f  ained millions o
1b00: 66 20 65 6e 74 72 69 65 73 2e 20 20 54 68 65 20  f entries.  The 
1b10: 70 72 65 76 69 6f 75 73 20 69 73 20 61 6e 20 65  previous is an e
1b20: 78 61 6d 70 6c 65 0a 6f 66 20 61 20 22 63 6f 6e  xample.of a "con
1b30: 74 61 69 6e 65 64 2d 77 69 74 68 69 6e 22 20 71  tained-within" q
1b40: 75 65 72 79 2e 20 20 54 68 65 20 52 2a 54 72 65  uery.  The R*Tre
1b50: 65 20 61 6c 73 6f 20 73 75 70 70 6f 72 74 73 20  e also supports 
1b60: 22 6f 76 65 72 6c 61 70 70 69 6e 67 22 0a 71 75  "overlapping".qu
1b70: 65 72 69 65 73 2e 20 20 5e 28 46 6f 72 20 65 78  eries.  ^(For ex
1b80: 61 6d 70 6c 65 2c 20 74 6f 20 66 69 6e 64 20 61  ample, to find a
1b90: 6c 6c 20 62 6f 75 6e 64 69 6e 67 20 62 6f 78 65  ll bounding boxe
1ba0: 73 20 74 68 61 74 20 6f 76 65 72 6c 61 70 20 74  s that overlap t
1bb0: 68 65 0a 43 68 61 72 6c 6f 74 74 65 20 61 72 65  he.Charlotte are
1bc0: 61 3a 0a 3c 2f 70 3e 0a 0a 3c 62 6c 6f 63 6b 71  a:.</p>..<blockq
1bd0: 75 6f 74 65 3e 3c 70 72 65 3e 0a 53 45 4c 45 43  uote><pre>.SELEC
1be0: 54 20 69 64 20 46 52 4f 4d 20 64 65 6d 6f 5f 69  T id FROM demo_i
1bf0: 6e 64 65 78 0a 20 57 48 45 52 45 20 6d 61 78 58  ndex. WHERE maxX
1c00: 26 67 74 3b 3d 2d 38 31 2e 30 38 20 41 4e 44 20  &gt;=-81.08 AND 
1c10: 6d 69 6e 58 26 6c 74 3b 3d 2d 38 30 2e 35 38 0a  minX&lt;=-80.58.
1c20: 20 20 20 41 4e 44 20 6d 61 78 59 26 67 74 3b 3d     AND maxY&gt;=
1c30: 33 35 2e 30 30 20 20 41 4e 44 20 6d 69 6e 59 26  35.00  AND minY&
1c40: 6c 74 3b 3d 33 35 2e 34 34 3b 0a 3c 2f 70 72 65  lt;=35.44;.</pre
1c50: 3e 3c 2f 62 6c 6f 63 6b 71 75 6f 74 65 3e 29 5e  ></blockquote>)^
1c60: 0a 0a 3c 70 3e 0a 5e 28 54 68 69 73 20 73 65 63  ..<p>.^(This sec
1c70: 6f 6e 64 20 71 75 65 72 79 20 77 6f 75 6c 64 20  ond query would 
1c80: 66 69 6e 64 20 62 6f 74 68 20 65 6e 74 72 79 20  find both entry 
1c90: 31 20 28 74 68 65 20 53 51 4c 69 74 65 2e 6f 72  1 (the SQLite.or
1ca0: 67 20 6f 66 66 69 63 65 29 20 77 68 69 63 68 0a  g office) which.
1cb0: 69 73 20 65 6e 74 69 72 65 6c 79 20 63 6f 6e 74  is entirely cont
1cc0: 61 69 6e 65 64 20 77 69 74 68 69 6e 20 74 68 65  ained within the
1cd0: 20 71 75 65 72 79 20 62 6f 78 20 61 6e 64 20 61   query box and a
1ce0: 6c 73 6f 0a 74 68 65 20 31 32 74 68 20 43 6f 6e  lso.the 12th Con
1cf0: 67 72 65 73 73 69 6f 6e 61 6c 20 44 69 73 74 72  gressional Distr
1d00: 69 63 74 20 77 68 69 63 68 20 65 78 74 65 6e 64  ict which extend
1d10: 73 20 77 65 6c 6c 20 6f 75 74 73 69 64 65 20 74  s well outside t
1d20: 68 65 0a 71 75 65 72 79 20 62 6f 78 20 62 75 74  he.query box but
1d30: 20 73 74 69 6c 6c 20 6f 76 65 72 6c 61 70 73 20   still overlaps 
1d40: 74 68 65 20 71 75 65 72 79 20 62 6f 78 2e 29 5e  the query box.)^
1d50: 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a 5e 4e 6f 74 65  .</p>..<p>.^Note
1d60: 20 74 68 61 74 20 69 74 20 69 73 20 6e 6f 74 20   that it is not 
1d70: 6e 65 63 65 73 73 61 72 79 20 66 6f 72 20 61 6c  necessary for al
1d80: 6c 20 63 6f 6f 72 64 69 6e 61 74 65 73 20 69 6e  l coordinates in
1d90: 20 61 6e 20 52 2a 54 72 65 65 20 69 6e 64 65 78   an R*Tree index
1da0: 0a 74 6f 20 62 65 20 63 6f 6e 73 74 72 61 69 6e  .to be constrain
1db0: 65 64 20 69 6e 20 6f 72 64 65 72 20 66 6f 72 20  ed in order for 
1dc0: 74 68 65 20 69 6e 64 65 78 20 73 65 61 72 63 68  the index search
1dd0: 20 74 6f 20 62 65 20 65 66 66 69 63 69 65 6e 74   to be efficient
1de0: 2e 0a 5e 28 4f 6e 65 20 6d 69 67 68 74 2c 20 66  ..^(One might, f
1df0: 6f 72 20 65 78 61 6d 70 6c 65 2c 20 77 61 6e 74  or example, want
1e00: 20 74 6f 20 71 75 65 72 79 20 61 6c 6c 20 6f 62   to query all ob
1e10: 6a 65 63 74 73 20 74 68 61 74 20 6f 76 65 72 6c  jects that overl
1e20: 61 70 20 77 69 74 68 0a 74 68 65 20 33 35 74 68  ap with.the 35th
1e30: 20 70 61 72 61 6c 6c 65 6c 3a 0a 3c 2f 70 3e 0a   parallel:.</p>.
1e40: 0a 3c 62 6c 6f 63 6b 71 75 6f 74 65 3e 3c 70 72  .<blockquote><pr
1e50: 65 3e 0a 53 45 4c 45 43 54 20 69 64 20 46 52 4f  e>.SELECT id FRO
1e60: 4d 20 64 65 6d 6f 5f 69 6e 64 65 78 0a 20 57 48  M demo_index. WH
1e70: 45 52 45 20 6d 61 78 59 26 67 74 3b 3d 33 35 2e  ERE maxY&gt;=35.
1e80: 30 20 20 41 4e 44 20 6d 69 6e 59 26 6c 74 3b 3d  0  AND minY&lt;=
1e90: 33 35 2e 30 3b 0a 3c 2f 70 72 65 3e 3c 2f 62 6c  35.0;.</pre></bl
1ea0: 6f 63 6b 71 75 6f 74 65 3e 29 5e 0a 0a 3c 70 3e  ockquote>)^..<p>
1eb0: 0a 42 75 74 2c 20 67 65 6e 65 72 61 6c 6c 79 20  .But, generally 
1ec0: 73 70 65 61 6b 69 6e 67 2c 20 74 68 65 20 6d 6f  speaking, the mo
1ed0: 72 65 20 63 6f 6e 73 74 72 61 69 6e 74 73 20 74  re constraints t
1ee0: 68 61 74 20 74 68 65 20 52 2a 54 72 65 65 20 6d  hat the R*Tree m
1ef0: 6f 64 75 6c 65 0a 68 61 73 20 74 6f 20 77 6f 72  odule.has to wor
1f00: 6b 20 77 69 74 68 2c 20 61 6e 64 20 74 68 65 20  k with, and the 
1f10: 73 6d 61 6c 6c 65 72 20 74 68 65 20 62 6f 75 6e  smaller the boun
1f20: 64 69 6e 67 20 62 6f 78 2c 20 74 68 65 20 66 61  ding box, the fa
1f30: 73 74 65 72 20 74 68 65 0a 72 65 73 75 6c 74 73  ster the.results
1f40: 20 77 69 6c 6c 20 63 6f 6d 65 20 62 61 63 6b 2e   will come back.
1f50: 0a 3c 2f 70 3e 0a 0a 3c 68 32 3e 52 6f 75 6e 64  .</p>..<h2>Round
1f60: 6f 66 66 20 45 72 72 6f 72 3c 2f 68 32 3e 0a 0a  off Error</h2>..
1f70: 3c 70 3e 0a 42 79 20 64 65 66 61 75 6c 74 2c 20  <p>.By default, 
1f80: 63 6f 6f 72 64 69 6e 61 74 65 73 20 61 72 65 20  coordinates are 
1f90: 73 74 6f 72 65 64 20 69 6e 20 61 6e 20 52 2a 54  stored in an R*T
1fa0: 72 65 65 20 75 73 69 6e 67 20 33 32 2d 62 69 74  ree using 32-bit
1fb0: 20 66 6c 6f 61 74 69 6e 67 0a 70 6f 69 6e 74 20   floating.point 
1fc0: 76 61 6c 75 65 73 2e 20 20 57 68 65 6e 20 61 20  values.  When a 
1fd0: 63 6f 6f 72 64 69 6e 61 74 65 20 63 61 6e 6e 6f  coordinate canno
1fe0: 74 20 62 65 20 65 78 61 63 74 6c 79 20 72 65 70  t be exactly rep
1ff0: 72 65 73 65 6e 74 65 64 20 62 79 20 61 0a 33 32  resented by a.32
2000: 2d 62 69 74 20 66 6c 6f 61 74 69 6e 67 20 70 6f  -bit floating po
2010: 69 6e 74 20 6e 75 6d 62 65 72 2c 20 74 68 65 20  int number, the 
2020: 6c 6f 77 65 72 2d 62 6f 75 6e 64 20 63 6f 6f 72  lower-bound coor
2030: 64 69 6e 61 74 65 73 20 61 72 65 20 72 6f 75 6e  dinates are roun
2040: 64 65 64 20 64 6f 77 6e 0a 61 6e 64 20 74 68 65  ded down.and the
2050: 20 75 70 70 65 72 2d 62 6f 75 6e 64 20 63 6f 6f   upper-bound coo
2060: 72 64 69 6e 61 74 65 73 20 61 72 65 20 72 6f 75  rdinates are rou
2070: 6e 64 65 64 20 75 70 2e 20 20 54 68 75 73 2c 20  nded up.  Thus, 
2080: 62 6f 75 6e 64 69 6e 67 20 62 6f 78 65 73 20 6d  bounding boxes m
2090: 69 67 68 74 0a 62 65 20 73 6c 69 67 68 74 6c 79  ight.be slightly
20a0: 20 6c 61 72 67 65 72 20 74 68 61 6e 20 73 70 65   larger than spe
20b0: 63 69 66 69 65 64 2c 20 62 75 74 20 77 69 6c 6c  cified, but will
20c0: 20 6e 65 76 65 72 20 62 65 20 61 6e 79 20 73 6d   never be any sm
20d0: 61 6c 6c 65 72 2e 20 20 54 68 69 73 0a 69 73 20  aller.  This.is 
20e0: 65 78 61 63 74 6c 79 20 77 68 61 74 20 69 73 20  exactly what is 
20f0: 64 65 73 69 72 65 64 20 66 6f 72 20 64 6f 69 6e  desired for doin
2100: 67 20 74 68 65 20 6d 6f 72 65 20 63 6f 6d 6d 6f  g the more commo
2110: 6e 20 22 6f 76 65 72 6c 61 70 70 69 6e 67 22 20  n "overlapping" 
2120: 71 75 65 72 69 65 73 0a 77 68 65 72 65 20 74 68  queries.where th
2130: 65 20 61 70 70 6c 69 63 61 74 69 6f 6e 20 77 61  e application wa
2140: 6e 74 73 20 74 6f 20 66 69 6e 64 20 65 76 65 72  nts to find ever
2150: 79 20 65 6e 74 72 79 20 69 6e 20 74 68 65 20 52  y entry in the R
2160: 2a 54 72 65 65 20 74 68 61 74 20 6f 76 65 72 6c  *Tree that overl
2170: 61 70 73 0a 61 20 71 75 65 72 79 20 62 6f 75 6e  aps.a query boun
2180: 64 69 6e 67 20 62 6f 78 2e 20 20 52 6f 75 6e 64  ding box.  Round
2190: 69 6e 67 20 74 68 65 20 65 6e 74 72 79 20 62 6f  ing the entry bo
21a0: 75 6e 64 69 6e 67 20 62 6f 78 65 73 20 6f 75 74  unding boxes out
21b0: 77 61 72 64 20 6d 69 67 68 74 20 63 61 75 73 65  ward might cause
21c0: 20 61 0a 66 65 77 20 65 78 74 72 61 20 65 6e 74   a.few extra ent
21d0: 72 69 65 73 20 74 6f 20 61 70 70 65 61 72 73 20  ries to appears 
21e0: 69 6e 20 61 6e 20 6f 76 65 72 6c 61 70 70 69 6e  in an overlappin
21f0: 67 20 71 75 65 72 79 20 69 66 20 74 68 65 20 65  g query if the e
2200: 64 67 65 20 6f 66 20 74 68 65 0a 65 6e 74 72 79  dge of the.entry
2210: 20 62 6f 75 6e 64 69 6e 67 20 62 6f 78 20 63 6f   bounding box co
2220: 72 72 65 73 70 6f 6e 64 73 20 74 6f 20 61 6e 20  rresponds to an 
2230: 65 64 67 65 20 6f 66 20 74 68 65 20 71 75 65 72  edge of the quer
2240: 79 20 62 6f 75 6e 64 69 6e 67 20 62 6f 78 2e 20  y bounding box. 
2250: 20 42 75 74 0a 74 68 65 20 6f 76 65 72 6c 61 70   But.the overlap
2260: 70 69 6e 67 20 71 75 65 72 79 20 77 69 6c 6c 20  ping query will 
2270: 6e 65 76 65 72 20 6d 69 73 73 20 61 20 76 61 6c  never miss a val
2280: 69 64 20 74 61 62 6c 65 20 65 6e 74 72 79 2e 20  id table entry. 
2290: 20 0a 0a 3c 70 3e 48 6f 77 65 76 65 72 2c 20 66   ..<p>However, f
22a0: 6f 72 20 61 20 22 63 6f 6e 74 61 69 6e 65 64 2d  or a "contained-
22b0: 77 69 74 68 69 6e 22 20 73 74 79 6c 65 20 71 75  within" style qu
22c0: 65 72 79 2c 20 72 6f 75 6e 64 69 6e 67 20 74 68  ery, rounding th
22d0: 65 20 62 6f 75 6e 64 69 6e 67 0a 62 6f 78 65 73  e bounding.boxes
22e0: 20 6f 75 74 77 61 72 64 20 6d 69 67 68 74 20 63   outward might c
22f0: 61 75 73 65 20 73 6f 6d 65 20 65 6e 74 72 69 65  ause some entrie
2300: 73 20 74 6f 20 62 65 20 65 78 63 6c 75 64 65 64  s to be excluded
2310: 20 66 72 6f 6d 20 74 68 65 20 72 65 73 75 6c 74   from the result
2320: 20 73 65 74 0a 69 66 20 74 68 65 20 65 64 67 65   set.if the edge
2330: 20 6f 66 20 74 68 65 20 65 6e 74 72 79 20 62 6f   of the entry bo
2340: 75 6e 64 69 6e 67 20 62 6f 78 20 63 6f 72 72 65  unding box corre
2350: 73 70 6f 6e 64 73 20 74 6f 20 74 68 65 20 65 64  sponds to the ed
2360: 67 65 20 6f 66 20 74 68 65 20 71 75 65 72 79 0a  ge of the query.
2370: 62 6f 75 6e 64 69 6e 67 20 62 6f 78 2e 20 20 54  bounding box.  T
2380: 6f 20 67 75 61 72 64 20 61 67 61 69 6e 73 74 20  o guard against 
2390: 74 68 69 73 2c 20 61 70 70 6c 69 63 61 74 69 6f  this, applicatio
23a0: 6e 73 20 73 68 6f 75 6c 64 20 65 78 70 61 6e 64  ns should expand
23b0: 20 74 68 65 69 72 0a 63 6f 6e 74 61 69 6e 65 64   their.contained
23c0: 2d 77 69 74 68 69 6e 20 71 75 65 72 79 20 62 6f  -within query bo
23d0: 78 65 73 20 73 6c 69 67 68 74 6c 79 20 28 62 79  xes slightly (by
23e0: 20 30 2e 30 30 30 30 31 32 25 29 20 62 79 20 72   0.000012%) by r
23f0: 6f 75 6e 64 69 6e 67 20 64 6f 77 6e 20 74 68 65  ounding down the
2400: 0a 6c 6f 77 65 72 20 63 6f 6f 72 64 69 6e 61 74  .lower coordinat
2410: 65 73 20 61 6e 64 20 72 6f 75 6e 64 69 6e 67 20  es and rounding 
2420: 75 70 20 74 68 65 20 74 6f 70 20 63 6f 6f 72 64  up the top coord
2430: 69 6e 61 74 65 73 2c 20 69 6e 20 65 61 63 68 20  inates, in each 
2440: 64 69 6d 65 6e 73 69 6f 6e 2e 0a 0a 3c 68 31 3e  dimension...<h1>
2450: 55 73 69 6e 67 20 52 2a 54 72 65 65 73 20 45 66  Using R*Trees Ef
2460: 66 65 63 74 69 76 65 6c 79 3c 2f 68 31 3e 0a 0a  fectively</h1>..
2470: 3c 70 3e 0a 46 6f 72 20 53 51 4c 69 74 65 20 76  <p>.For SQLite v
2480: 65 72 73 69 6f 6e 73 20 70 72 69 6f 72 20 74 6f  ersions prior to
2490: 20 33 2e 32 34 2e 30 20 28 5b 64 61 74 65 6f 66   3.24.0 ([dateof
24a0: 3a 33 2e 32 34 2e 30 5d 29 2c 0a 74 68 65 20 6f  :3.24.0]),.the o
24b0: 6e 6c 79 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20  nly information 
24c0: 74 68 61 74 20 61 6e 20 52 2a 54 72 65 65 20 69  that an R*Tree i
24d0: 6e 64 65 78 20 73 74 6f 72 65 73 20 61 62 6f 75  ndex stores abou
24e0: 74 20 61 6e 20 6f 62 6a 65 63 74 20 69 73 0a 69  t an object is.i
24f0: 74 73 20 69 6e 74 65 67 65 72 20 49 44 20 61 6e  ts integer ID an
2500: 64 20 69 74 73 20 62 6f 75 6e 64 69 6e 67 20 62  d its bounding b
2510: 6f 78 2e 20 20 41 64 64 69 74 69 6f 6e 61 6c 20  ox.  Additional 
2520: 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 6e 65 65 64  information need
2530: 73 20 74 6f 0a 62 65 20 73 74 6f 72 65 64 20 69  s to.be stored i
2540: 6e 20 73 65 70 61 72 61 74 65 20 74 61 62 6c 65  n separate table
2550: 73 20 61 6e 64 20 72 65 6c 61 74 65 64 20 74 6f  s and related to
2560: 20 74 68 65 20 52 2a 54 72 65 65 20 69 6e 64 65   the R*Tree inde
2570: 78 20 75 73 69 6e 67 0a 74 68 65 20 70 72 69 6d  x using.the prim
2580: 61 72 79 20 6b 65 79 2e 20 20 5e 28 46 6f 72 20  ary key.  ^(For 
2590: 74 68 65 20 65 78 61 6d 70 6c 65 20 61 62 6f 76  the example abov
25a0: 65 2c 20 6f 6e 65 20 6d 69 67 68 74 20 63 72 65  e, one might cre
25b0: 61 74 65 20 61 6e 20 61 75 78 69 6c 69 61 72 79  ate an auxiliary
25c0: 0a 74 61 62 6c 65 20 61 73 20 66 6f 6c 6c 6f 77  .table as follow
25d0: 73 3a 0a 3c 2f 70 3e 0a 0a 3c 62 6c 6f 63 6b 71  s:.</p>..<blockq
25e0: 75 6f 74 65 3e 3c 70 72 65 3e 0a 43 52 45 41 54  uote><pre>.CREAT
25f0: 45 20 54 41 42 4c 45 20 64 65 6d 6f 5f 64 61 74  E TABLE demo_dat
2600: 61 28 0a 20 20 69 64 20 49 4e 54 45 47 45 52 20  a(.  id INTEGER 
2610: 50 52 49 4d 41 52 59 20 4b 45 59 2c 20 20 2d 2d  PRIMARY KEY,  --
2620: 20 70 72 69 6d 61 72 79 20 6b 65 79 0a 20 20 6f   primary key.  o
2630: 62 6a 6e 61 6d 65 20 54 45 58 54 2c 20 20 20 20  bjname TEXT,    
2640: 20 20 20 20 20 20 20 20 2d 2d 20 6e 61 6d 65 20          -- name 
2650: 6f 66 20 74 68 65 20 6f 62 6a 65 63 74 0a 20 20  of the object.  
2660: 6f 62 6a 74 79 70 65 20 54 45 58 54 2c 20 20 20  objtype TEXT,   
2670: 20 20 20 20 20 20 20 20 20 2d 2d 20 6f 62 6a 65           -- obje
2680: 63 74 20 74 79 70 65 0a 20 20 62 6f 75 6e 64 61  ct type.  bounda
2690: 72 79 20 42 4c 4f 42 20 20 20 20 20 20 20 20 20  ry BLOB         
26a0: 20 20 20 2d 2d 20 64 65 74 61 69 6c 65 64 20 62     -- detailed b
26b0: 6f 75 6e 64 61 72 79 20 6f 66 20 6f 62 6a 65 63  oundary of objec
26c0: 74 0a 29 3b 0a 3c 2f 70 72 65 3e 3c 2f 62 6c 6f  t.);.</pre></blo
26d0: 63 6b 71 75 6f 74 65 3e 29 5e 0a 0a 3c 70 3e 0a  ckquote>)^..<p>.
26e0: 49 6e 20 74 68 69 73 20 65 78 61 6d 70 6c 65 2c  In this example,
26f0: 20 74 68 65 20 64 65 6d 6f 5f 64 61 74 61 2e 62   the demo_data.b
2700: 6f 75 6e 64 61 72 79 20 66 69 65 6c 64 20 69 73  oundary field is
2710: 20 69 6e 74 65 6e 64 65 64 20 74 6f 20 68 6f 6c   intended to hol
2720: 64 20 73 6f 6d 65 0a 6b 69 6e 64 20 6f 66 20 62  d some.kind of b
2730: 69 6e 61 72 79 20 72 65 70 72 65 73 65 6e 74 61  inary representa
2740: 74 69 6f 6e 20 6f 66 20 74 68 65 20 70 72 65 63  tion of the prec
2750: 69 73 65 20 62 6f 75 6e 64 61 72 69 65 73 20 6f  ise boundaries o
2760: 66 20 74 68 65 20 6f 62 6a 65 63 74 2e 0a 54 68  f the object..Th
2770: 65 20 52 2a 54 72 65 65 20 69 6e 64 65 78 20 6f  e R*Tree index o
2780: 6e 6c 79 20 68 6f 6c 64 73 20 61 6e 20 61 78 69  nly holds an axi
2790: 73 2d 61 6c 69 67 6e 65 64 20 72 65 63 74 61 6e  s-aligned rectan
27a0: 67 75 6c 61 72 20 62 6f 75 6e 64 61 72 79 20 66  gular boundary f
27b0: 6f 72 20 74 68 65 0a 6f 62 6a 65 63 74 2e 20 20  or the.object.  
27c0: 54 68 65 20 52 2a 54 72 65 65 20 62 6f 75 6e 64  The R*Tree bound
27d0: 61 72 79 20 69 73 20 6a 75 73 74 20 61 6e 20 61  ary is just an a
27e0: 70 70 72 6f 78 69 6d 61 74 69 6f 6e 20 6f 66 20  pproximation of 
27f0: 74 68 65 20 74 72 75 65 20 6f 62 6a 65 63 74 0a  the true object.
2800: 62 6f 75 6e 64 61 72 79 2e 20 20 53 6f 20 77 68  boundary.  So wh
2810: 61 74 20 74 79 70 69 63 61 6c 6c 79 20 68 61 70  at typically hap
2820: 70 65 6e 73 20 69 73 20 74 68 61 74 20 74 68 65  pens is that the
2830: 20 52 2a 54 72 65 65 20 69 6e 64 65 78 20 69 73   R*Tree index is
2840: 20 75 73 65 64 20 74 6f 0a 6e 61 72 72 6f 77 20   used to.narrow 
2850: 61 20 73 65 61 72 63 68 20 64 6f 77 6e 20 74 6f  a search down to
2860: 20 61 20 6c 69 73 74 20 6f 66 20 63 61 6e 64 69   a list of candi
2870: 64 61 74 65 20 6f 62 6a 65 63 74 73 20 61 6e 64  date objects and
2880: 20 74 68 65 6e 20 6d 6f 72 65 20 64 65 74 61 69   then more detai
2890: 6c 65 64 0a 61 6e 64 20 65 78 70 65 6e 73 69 76  led.and expensiv
28a0: 65 20 63 6f 6d 70 75 74 61 74 69 6f 6e 73 20 61  e computations a
28b0: 72 65 20 64 6f 6e 65 20 6f 6e 20 65 61 63 68 20  re done on each 
28c0: 63 61 6e 64 69 64 61 74 65 20 74 6f 20 66 69 6e  candidate to fin
28d0: 64 20 69 66 20 74 68 65 0a 63 61 6e 64 69 64 61  d if the.candida
28e0: 74 65 20 74 72 75 6c 79 20 6d 65 65 74 73 20 74  te truly meets t
28f0: 68 65 20 73 65 61 72 63 68 20 63 72 69 74 65 72  he search criter
2900: 69 61 2e 0a 3c 2f 70 3e 0a 0a 3c 62 6c 6f 63 6b  ia..</p>..<block
2910: 71 75 6f 74 65 3e 3c 70 3e 0a 3c 73 74 72 6f 6e  quote><p>.<stron
2920: 67 3e 4b 65 79 20 50 6f 69 6e 74 3a 3c 2f 73 74  g>Key Point:</st
2930: 72 6f 6e 67 3e 0a 41 6e 20 52 2a 54 72 65 65 20  rong>.An R*Tree 
2940: 69 6e 64 65 78 20 64 6f 65 73 20 6e 6f 74 20 6e  index does not n
2950: 6f 72 6d 61 6c 6c 79 20 70 72 6f 76 69 64 65 20  ormally provide 
2960: 74 68 65 20 65 78 61 63 74 20 61 6e 73 77 65 72  the exact answer
2970: 20 62 75 74 20 6d 65 72 65 6c 79 0a 72 65 64 75   but merely.redu
2980: 63 65 73 20 74 68 65 20 73 65 74 20 6f 66 20 70  ces the set of p
2990: 6f 74 65 6e 74 69 61 6c 20 61 6e 73 77 65 72 73  otential answers
29a0: 20 66 72 6f 6d 20 6d 69 6c 6c 69 6f 6e 73 20 74   from millions t
29b0: 6f 20 64 6f 7a 65 6e 73 2e 0a 3c 2f 70 3e 3c 2f  o dozens..</p></
29c0: 62 6c 6f 63 6b 71 75 6f 74 65 3e 0a 0a 3c 70 3e  blockquote>..<p>
29d0: 0a 53 75 70 70 6f 73 65 20 74 68 65 20 64 65 6d  .Suppose the dem
29e0: 6f 5f 64 61 74 61 2e 62 6f 75 6e 64 61 72 79 20  o_data.boundary 
29f0: 66 69 65 6c 64 20 68 6f 6c 64 73 20 73 6f 6d 65  field holds some
2a00: 20 70 72 6f 70 72 69 65 74 61 72 79 20 64 61 74   proprietary dat
2a10: 61 20 64 65 73 63 72 69 70 74 69 6f 6e 0a 6f 66  a description.of
2a20: 20 61 20 63 6f 6d 70 6c 65 78 20 74 77 6f 2d 64   a complex two-d
2a30: 69 6d 65 6e 73 69 6f 6e 61 6c 20 62 6f 75 6e 64  imensional bound
2a40: 61 72 79 20 66 6f 72 20 61 6e 20 6f 62 6a 65 63  ary for an objec
2a50: 74 20 61 6e 64 20 73 75 70 70 6f 73 65 20 74 68  t and suppose th
2a60: 61 74 20 74 68 65 0a 61 70 70 6c 69 63 61 74 69  at the.applicati
2a70: 6f 6e 20 68 61 73 20 75 73 65 64 20 74 68 65 20  on has used the 
2a80: 5b 73 71 6c 69 74 65 33 5f 63 72 65 61 74 65 5f  [sqlite3_create_
2a90: 66 75 6e 63 74 69 6f 6e 28 29 5d 20 69 6e 74 65  function()] inte
2aa0: 72 66 61 63 65 20 74 6f 0a 63 72 65 61 74 65 64  rface to.created
2ab0: 20 61 70 70 6c 69 63 61 74 69 6f 6e 2d 64 65 66   application-def
2ac0: 69 6e 65 64 20 66 75 6e 63 74 69 6f 6e 73 20 22  ined functions "
2ad0: 63 6f 6e 74 61 69 6e 65 64 5f 69 6e 22 20 61 6e  contained_in" an
2ae0: 64 0a 22 6f 76 65 72 6c 61 70 73 22 20 61 63 63  d."overlaps" acc
2af0: 65 70 74 69 6e 67 20 74 77 6f 20 64 65 6d 6f 5f  epting two demo_
2b00: 64 61 74 61 2e 62 6f 75 6e 64 61 72 79 20 6f 62  data.boundary ob
2b10: 6a 65 63 74 73 20 61 6e 64 20 72 65 74 75 72 6e  jects and return
2b20: 20 74 72 75 65 20 6f 72 20 66 61 6c 73 65 2e 0a   true or false..
2b30: 4f 6e 65 20 6d 61 79 20 61 73 73 75 6d 65 20 74  One may assume t
2b40: 68 61 74 20 22 63 6f 6e 74 61 69 6e 65 64 5f 69  hat "contained_i
2b50: 6e 22 20 61 6e 64 20 22 6f 76 65 72 6c 61 70 73  n" and "overlaps
2b60: 22 20 61 72 65 20 72 65 6c 61 74 69 76 65 6c 79  " are relatively
2b70: 20 73 6c 6f 77 0a 66 75 6e 63 74 69 6f 6e 73 20   slow.functions 
2b80: 74 68 61 74 20 77 65 20 64 6f 20 6e 6f 74 20 77  that we do not w
2b90: 61 6e 74 20 74 6f 20 69 6e 76 6f 6b 65 20 74 6f  ant to invoke to
2ba0: 6f 20 66 72 65 71 75 65 6e 74 6c 79 2e 0a 5e 28  o frequently..^(
2bb0: 54 68 65 6e 20 61 6e 20 65 66 66 69 63 69 65 6e  Then an efficien
2bc0: 74 20 77 61 79 20 74 6f 20 66 69 6e 64 20 74 68  t way to find th
2bd0: 65 20 6e 61 6d 65 20 6f 66 20 61 6c 6c 20 6f 62  e name of all ob
2be0: 6a 65 63 74 73 20 6c 6f 63 61 74 65 64 20 77 69  jects located wi
2bf0: 74 68 69 6e 0a 74 68 65 20 4e 6f 72 74 68 20 43  thin.the North C
2c00: 61 72 6f 6c 69 6e 61 20 31 32 74 68 20 44 69 73  arolina 12th Dis
2c10: 74 72 69 63 74 2c 20 6f 6e 65 20 6d 61 79 20 62  trict, one may b
2c20: 65 20 74 6f 20 72 75 6e 20 61 20 71 75 65 72 79  e to run a query
2c30: 20 6c 69 6b 65 20 74 68 69 73 3a 0a 3c 2f 70 3e   like this:.</p>
2c40: 0a 0a 3c 61 20 6e 61 6d 65 3d 22 64 69 71 75 65  ..<a name="dique
2c50: 72 79 22 3e 3c 2f 61 3e 0a 3c 62 6c 6f 63 6b 71  ry"></a>.<blockq
2c60: 75 6f 74 65 3e 3c 70 72 65 3e 0a 53 45 4c 45 43  uote><pre>.SELEC
2c70: 54 20 6f 62 6a 6e 61 6d 65 20 46 52 4f 4d 20 64  T objname FROM d
2c80: 65 6d 6f 5f 64 61 74 61 2c 20 64 65 6d 6f 5f 69  emo_data, demo_i
2c90: 6e 64 65 78 0a 20 57 48 45 52 45 20 64 65 6d 6f  ndex. WHERE demo
2ca0: 5f 64 61 74 61 2e 69 64 3d 64 65 6d 6f 5f 69 6e  _data.id=demo_in
2cb0: 64 65 78 2e 69 64 0a 20 20 20 41 4e 44 20 63 6f  dex.id.   AND co
2cc0: 6e 74 61 69 6e 65 64 5f 69 6e 28 64 65 6d 6f 5f  ntained_in(demo_
2cd0: 64 61 74 61 2e 62 6f 75 6e 64 61 72 79 2c 20 3a  data.boundary, :
2ce0: 62 6f 75 6e 64 61 72 79 29 0a 20 20 20 41 4e 44  boundary).   AND
2cf0: 20 6d 69 6e 58 26 67 74 3b 3d 2d 38 31 2e 30 20   minX&gt;=-81.0 
2d00: 41 4e 44 20 6d 61 78 58 26 6c 74 3b 3d 2d 37 39  AND maxX&lt;=-79
2d10: 2e 36 0a 20 20 20 41 4e 44 20 6d 69 6e 59 26 67  .6.   AND minY&g
2d20: 74 3b 3d 33 35 2e 30 20 41 4e 44 20 6d 61 78 59  t;=35.0 AND maxY
2d30: 26 67 74 3b 3d 33 36 2e 32 3b 0a 3c 2f 70 72 65  &gt;=36.2;.</pre
2d40: 3e 3c 2f 62 6c 6f 63 6b 71 75 6f 74 65 3e 29 5e  ></blockquote>)^
2d50: 0a 0a 3c 70 3e 49 6e 20 74 68 65 20 71 75 65 72  ..<p>In the quer
2d60: 79 20 61 62 6f 76 65 2c 20 6f 6e 65 20 77 6f 75  y above, one wou
2d70: 6c 64 20 70 72 65 73 75 6d 61 62 6c 79 20 62 69  ld presumably bi
2d80: 6e 64 20 74 68 65 20 62 69 6e 61 72 79 20 42 4c  nd the binary BL
2d90: 4f 42 20 0a 64 65 73 63 72 69 70 74 69 6f 6e 20  OB .description 
2da0: 6f 66 20 74 68 65 20 70 72 65 63 69 73 65 20 62  of the precise b
2db0: 6f 75 6e 64 61 72 79 20 6f 66 20 74 68 65 20 31  oundary of the 1
2dc0: 32 74 68 20 64 69 73 74 72 69 63 74 20 74 6f 20  2th district to 
2dd0: 74 68 65 0a 22 3a 62 6f 75 6e 64 61 72 79 22 20  the.":boundary" 
2de0: 70 61 72 61 6d 65 74 65 72 2e 3c 2f 70 3e 0a 0a  parameter.</p>..
2df0: 3c 70 3e 4e 6f 74 69 63 65 20 68 6f 77 20 74 68  <p>Notice how th
2e00: 65 20 71 75 65 72 79 20 61 62 6f 76 65 20 77 6f  e query above wo
2e10: 72 6b 73 3a 20 20 54 68 65 20 52 2a 54 72 65 65  rks:  The R*Tree
2e20: 20 69 6e 64 65 78 20 72 75 6e 73 20 69 6e 20 74   index runs in t
2e30: 68 65 20 6f 75 74 65 72 0a 6c 6f 6f 70 20 74 6f  he outer.loop to
2e40: 20 66 69 6e 64 20 65 6e 74 72 69 65 73 20 74 68   find entries th
2e50: 61 74 20 61 72 65 20 63 6f 6e 74 61 69 6e 65 64  at are contained
2e60: 20 77 69 74 68 69 6e 20 74 68 65 20 62 6f 75 6e   within the boun
2e70: 64 69 6e 67 20 62 6f 78 0a 6f 66 20 6c 6f 6e 67  ding box.of long
2e80: 69 74 75 64 65 20 2d 38 31 2e 2e 2d 37 39 2e 36  itude -81..-79.6
2e90: 20 61 6e 64 20 6c 61 74 69 74 75 64 65 20 33 35   and latitude 35
2ea0: 2e 30 2e 2e 33 36 2e 32 2e 20 0a 46 6f 72 20 65  .0..36.2. .For e
2eb0: 61 63 68 20 6f 62 6a 65 63 74 20 69 64 65 6e 74  ach object ident
2ec0: 69 66 69 65 72 20 66 6f 75 6e 64 2c 20 53 51 4c  ifier found, SQL
2ed0: 69 74 65 20 6c 6f 6f 6b 73 20 75 70 0a 74 68 65  ite looks up.the
2ee0: 20 63 6f 72 72 65 73 70 6f 6e 64 69 6e 67 20 65   corresponding e
2ef0: 6e 74 72 79 20 69 6e 20 74 68 65 20 64 65 6d 6f  ntry in the demo
2f00: 5f 64 61 74 61 20 74 61 62 6c 65 2e 20 20 49 74  _data table.  It
2f10: 20 74 68 65 6e 20 75 73 65 73 20 74 68 65 20 62   then uses the b
2f20: 6f 75 6e 64 61 72 79 0a 66 69 65 6c 64 20 66 72  oundary.field fr
2f30: 6f 6d 20 74 68 65 20 64 65 6d 6f 5f 64 61 74 61  om the demo_data
2f40: 20 74 61 62 6c 65 20 61 73 20 61 20 70 61 72 61   table as a para
2f50: 6d 65 74 65 72 20 74 6f 20 74 68 65 20 63 6f 6e  meter to the con
2f60: 74 61 69 6e 65 64 5f 69 6e 28 29 0a 66 75 6e 63  tained_in().func
2f70: 74 69 6f 6e 20 61 6e 64 20 69 66 20 74 68 61 74  tion and if that
2f80: 20 66 75 6e 63 74 69 6f 6e 20 72 65 74 75 72 6e   function return
2f90: 73 20 74 72 75 65 2c 20 74 68 65 20 6f 62 6a 6e  s true, the objn
2fa0: 61 6d 65 20 66 69 65 6c 64 20 66 72 6f 6d 0a 74  ame field from.t
2fb0: 68 65 20 64 65 6d 6f 5f 64 61 74 61 20 74 61 62  he demo_data tab
2fc0: 6c 65 20 69 73 20 72 65 74 75 72 6e 65 64 20 61  le is returned a
2fd0: 73 20 74 68 65 20 6e 65 78 74 20 72 6f 77 20 6f  s the next row o
2fe0: 66 20 71 75 65 72 79 20 72 65 73 75 6c 74 2e 3c  f query result.<
2ff0: 2f 70 3e 0a 0a 3c 70 3e 4f 6e 65 20 77 6f 75 6c  /p>..<p>One woul
3000: 64 20 67 65 74 20 74 68 65 20 73 61 6d 65 20 61  d get the same a
3010: 6e 73 77 65 72 20 77 69 74 68 6f 75 74 20 74 68  nswer without th
3020: 65 20 75 73 65 20 6f 66 20 74 68 65 20 52 2a 54  e use of the R*T
3030: 72 65 65 20 69 6e 64 65 78 0a 75 73 69 6e 67 20  ree index.using 
3040: 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 73 69  the following si
3050: 6d 70 6c 65 72 20 71 75 65 72 79 3a 3c 2f 70 3e  mpler query:</p>
3060: 0a 0a 3c 62 6c 6f 63 6b 71 75 6f 74 65 3e 3c 70  ..<blockquote><p
3070: 72 65 3e 0a 53 45 4c 45 43 54 20 6f 62 6a 6e 61  re>.SELECT objna
3080: 6d 65 20 46 52 4f 4d 20 64 65 6d 6f 5f 64 61 74  me FROM demo_dat
3090: 61 0a 20 57 48 45 52 45 20 63 6f 6e 74 61 69 6e  a. WHERE contain
30a0: 65 64 5f 69 6e 28 64 65 6d 6f 5f 64 61 74 61 2e  ed_in(demo_data.
30b0: 62 6f 75 6e 64 61 72 79 2c 20 3a 62 6f 75 6e 64  boundary, :bound
30c0: 61 72 79 29 3b 0a 3c 2f 70 72 65 3e 3c 2f 62 6c  ary);.</pre></bl
30d0: 6f 63 6b 71 75 6f 74 65 3e 0a 0a 3c 70 3e 54 68  ockquote>..<p>Th
30e0: 65 20 70 72 6f 62 6c 65 6d 20 77 69 74 68 20 74  e problem with t
30f0: 68 69 73 20 6c 61 74 74 65 72 20 71 75 65 72 79  his latter query
3100: 20 69 73 20 74 68 61 74 20 69 74 20 6d 75 73 74   is that it must
3110: 20 61 70 70 6c 79 20 74 68 65 0a 63 6f 6e 74 61   apply the.conta
3120: 69 6e 65 64 5f 69 6e 28 29 20 66 75 6e 63 74 69  ined_in() functi
3130: 6f 6e 20 74 6f 20 6d 69 6c 6c 69 6f 6e 73 20 6f  on to millions o
3140: 66 20 65 6e 74 72 69 65 73 20 69 6e 20 74 68 65  f entries in the
3150: 20 64 65 6d 6f 5f 64 61 74 61 20 74 61 62 6c 65   demo_data table
3160: 2e 0a 54 68 65 20 75 73 65 20 6f 66 20 74 68 65  ..The use of the
3170: 20 52 2a 54 72 65 65 20 69 6e 20 74 68 65 20 70   R*Tree in the p
3180: 65 6e 75 6c 74 69 6d 61 74 65 20 71 75 65 72 79  enultimate query
3190: 20 72 65 64 75 63 65 73 20 74 68 65 20 6e 75 6d   reduces the num
31a0: 62 65 72 20 6f 66 0a 63 61 6c 6c 73 20 74 6f 20  ber of.calls to 
31b0: 63 6f 6e 74 61 69 6e 65 64 5f 69 6e 28 29 20 66  contained_in() f
31c0: 75 6e 63 74 69 6f 6e 20 74 6f 20 61 20 73 6d 61  unction to a sma
31d0: 6c 6c 20 73 75 62 73 65 74 20 6f 66 20 74 68 65  ll subset of the
31e0: 20 65 6e 74 69 72 65 20 74 61 62 6c 65 2e 0a 54   entire table..T
31f0: 68 65 20 52 2a 54 72 65 65 20 69 6e 64 65 78 20  he R*Tree index 
3200: 64 69 64 20 6e 6f 74 20 66 69 6e 64 20 74 68 65  did not find the
3210: 20 65 78 61 63 74 20 61 6e 73 77 65 72 20 69 74   exact answer it
3220: 73 65 6c 66 2c 20 69 74 20 6d 65 72 65 6c 79 0a  self, it merely.
3230: 6c 69 6d 69 74 65 64 20 74 68 65 20 73 65 61 72  limited the sear
3240: 63 68 20 73 70 61 63 65 2e 3c 2f 70 3e 0a 0a 3c  ch space.</p>..<
3250: 74 63 6c 3e 68 64 5f 66 72 61 67 6d 65 6e 74 20  tcl>hd_fragment 
3260: 7b 61 75 78 63 6f 6c 7d 20 7b 61 75 78 69 6c 69  {auxcol} {auxili
3270: 61 72 79 20 63 6f 6c 75 6d 6e 73 20 69 6e 20 72  ary columns in r
3280: 2d 74 72 65 65 20 74 61 62 6c 65 73 7d 3c 2f 74  -tree tables}</t
3290: 63 6c 3e 0a 3c 68 32 3e 41 75 78 69 6c 69 61 72  cl>.<h2>Auxiliar
32a0: 79 20 43 6f 6c 75 6d 6e 73 3c 2f 68 32 3e 0a 0a  y Columns</h2>..
32b0: 3c 70 3e 0a 42 65 67 69 6e 6e 69 6e 67 20 77 69  <p>.Beginning wi
32c0: 74 68 20 53 51 4c 69 74 65 20 76 65 72 73 69 6f  th SQLite versio
32d0: 6e 20 33 2e 32 34 2e 30 20 28 5b 64 61 74 65 6f  n 3.24.0 ([dateo
32e0: 66 3a 33 2e 32 34 2e 30 5d 29 2c 20 72 2d 74 72  f:3.24.0]), r-tr
32f0: 65 65 20 74 61 62 6c 65 73 0a 63 61 6e 20 68 61  ee tables.can ha
3300: 76 65 20 61 75 78 69 6c 69 61 72 79 20 63 6f 6c  ve auxiliary col
3310: 75 6d 6e 73 20 74 68 61 74 20 73 74 6f 72 65 20  umns that store 
3320: 61 72 62 69 74 72 61 72 79 20 64 61 74 61 2e 0a  arbitrary data..
3330: 41 75 78 69 6c 69 61 72 79 20 63 6f 6c 75 6d 6e  Auxiliary column
3340: 73 20 63 61 6e 20 62 65 20 75 73 65 64 20 69 6e  s can be used in
3350: 20 70 6c 61 63 65 20 6f 66 0a 73 65 63 6f 6e 64   place of.second
3360: 61 72 79 20 74 61 62 6c 65 73 20 73 75 63 68 20  ary tables such 
3370: 61 73 20 22 64 65 6d 6f 5f 64 61 74 61 22 2e 0a  as "demo_data"..
3380: 0a 3c 70 3e 0a 41 75 78 69 6c 69 61 72 79 20 63  .<p>.Auxiliary c
3390: 6f 6c 75 6d 6e 73 20 61 72 65 20 6d 61 72 6b 65  olumns are marke
33a0: 64 20 77 69 74 68 20 61 20 22 2b 22 20 73 79 6d  d with a "+" sym
33b0: 62 6f 6c 20 62 65 66 6f 72 65 20 74 68 65 20 63  bol before the c
33c0: 6f 6c 75 6d 6e 20 6e 61 6d 65 2e 0a 41 75 78 69  olumn name..Auxi
33d0: 6c 69 61 72 79 20 63 6f 6c 75 6d 6e 73 20 6d 75  liary columns mu
33e0: 73 74 20 63 6f 6d 65 20 61 66 74 65 72 20 61 6c  st come after al
33f0: 6c 20 6f 66 20 74 68 65 20 63 6f 6f 72 64 69 6e  l of the coordin
3400: 61 74 65 20 62 6f 75 6e 64 61 72 79 20 63 6f 6c  ate boundary col
3410: 75 6d 6e 73 2e 0a 54 68 65 72 65 20 69 73 20 61  umns..There is a
3420: 20 6c 69 6d 69 74 20 6f 66 20 6e 6f 20 6d 6f 72   limit of no mor
3430: 65 20 74 68 61 6e 20 31 30 30 20 61 75 78 69 6c  e than 100 auxil
3440: 69 61 72 79 20 63 6f 6c 75 6d 6e 73 2e 0a 54 68  iary columns..Th
3450: 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 65 78 61 6d  e following exam
3460: 70 6c 65 20 73 68 6f 77 73 20 61 6e 20 72 2d 74  ple shows an r-t
3470: 72 65 65 20 74 61 62 6c 65 20 77 69 74 68 20 61  ree table with a
3480: 75 78 69 6c 69 61 72 79 20 63 6f 6c 75 6d 6e 73  uxiliary columns
3490: 20 74 68 61 74 0a 69 73 20 65 71 75 69 76 61 6c   that.is equival
34a0: 65 6e 74 20 74 6f 20 74 68 65 20 74 77 6f 20 74  ent to the two t
34b0: 61 62 6c 65 73 20 22 64 65 6d 6f 5f 69 6e 64 65  ables "demo_inde
34c0: 78 22 20 61 6e 64 20 22 64 65 6d 6f 5f 64 61 74  x" and "demo_dat
34d0: 61 22 20 61 62 6f 76 65 3a 0a 0a 5e 28 3c 62 6c  a" above:..^(<bl
34e0: 6f 63 6b 71 75 6f 74 65 3e 3c 70 72 65 3e 0a 43  ockquote><pre>.C
34f0: 52 45 41 54 45 20 56 49 52 54 55 41 4c 20 54 41  REATE VIRTUAL TA
3500: 42 4c 45 20 64 65 6d 6f 5f 69 6e 64 65 78 32 20  BLE demo_index2 
3510: 55 53 49 4e 47 20 72 74 72 65 65 28 0a 20 20 20  USING rtree(.   
3520: 69 64 2c 20 20 20 20 20 20 20 20 20 20 20 20 20  id,             
3530: 20 2d 2d 20 49 6e 74 65 67 65 72 20 70 72 69 6d   -- Integer prim
3540: 61 72 79 20 6b 65 79 0a 20 20 20 6d 69 6e 58 2c  ary key.   minX,
3550: 20 6d 61 78 58 2c 20 20 20 20 20 20 2d 2d 20 4d   maxX,      -- M
3560: 69 6e 69 6d 75 6d 20 61 6e 64 20 6d 61 78 69 6d  inimum and maxim
3570: 75 6d 20 58 20 63 6f 6f 72 64 69 6e 61 74 65 0a  um X coordinate.
3580: 20 20 20 6d 69 6e 59 2c 20 6d 61 78 59 2c 20 20     minY, maxY,  
3590: 20 20 20 20 2d 2d 20 4d 69 6e 69 6d 75 6d 20 61      -- Minimum a
35a0: 6e 64 20 6d 61 78 69 6d 75 6d 20 59 20 63 6f 6f  nd maximum Y coo
35b0: 72 64 69 6e 61 74 65 0a 20 20 20 2b 6f 62 6a 6e  rdinate.   +objn
35c0: 61 6d 65 20 54 45 58 54 2c 20 20 20 2d 2d 20 6e  ame TEXT,   -- n
35d0: 61 6d 65 20 6f 66 20 74 68 65 20 6f 62 6a 65 63  ame of the objec
35e0: 74 0a 20 20 20 2b 6f 62 6a 74 79 70 65 20 54 45  t.   +objtype TE
35f0: 58 54 2c 20 20 20 2d 2d 20 6f 62 6a 65 63 74 20  XT,   -- object 
3600: 74 79 70 65 0a 20 20 20 2b 62 6f 75 6e 64 61 72  type.   +boundar
3610: 79 20 42 4c 4f 42 20 20 20 2d 2d 20 64 65 74 61  y BLOB   -- deta
3620: 69 6c 65 64 20 62 6f 75 6e 64 61 72 79 20 6f 66  iled boundary of
3630: 20 6f 62 6a 65 63 74 0a 29 3b 0a 3c 2f 70 72 65   object.);.</pre
3640: 3e 3c 2f 62 6c 6f 63 6b 71 75 6f 74 65 3e 29 5e  ></blockquote>)^
3650: 0a 0a 3c 70 3e 0a 42 79 20 63 6f 6d 62 69 6e 69  ..<p>.By combini
3660: 6e 67 20 6c 6f 63 61 74 69 6f 6e 20 64 61 74 61  ng location data
3670: 20 61 6e 64 20 72 65 6c 61 74 65 64 20 69 6e 66   and related inf
3680: 6f 72 6d 61 74 69 6f 6e 20 69 6e 74 6f 20 74 68  ormation into th
3690: 65 20 73 61 6d 65 0a 74 61 62 6c 65 2c 20 61 75  e same.table, au
36a0: 78 69 6c 69 61 72 79 20 63 6f 6c 75 6d 6e 73 20  xiliary columns 
36b0: 63 61 6e 20 70 72 6f 76 69 64 65 20 61 20 63 6c  can provide a cl
36c0: 65 61 6e 65 72 20 6d 6f 64 65 6c 0a 61 6e 64 20  eaner model.and 
36d0: 72 65 64 75 63 65 20 74 68 65 20 6e 65 65 64 20  reduce the need 
36e0: 74 6f 20 6a 6f 69 6e 73 2e 0a 46 6f 72 20 65 78  to joins..For ex
36f0: 61 6d 70 6c 65 2c 20 74 68 65 20 65 61 72 6c 69  ample, the earli
3700: 65 72 0a 3c 61 20 68 72 65 66 3d 22 23 64 69 71  er.<a href="#diq
3710: 75 65 72 79 22 3e 6a 6f 69 6e 20 62 65 74 77 65  uery">join betwe
3720: 65 6e 20 64 65 6d 6f 5f 69 6e 64 65 78 20 61 6e  en demo_index an
3730: 64 20 64 65 6d 6f 5f 64 61 74 61 3c 2f 61 3e 20  d demo_data</a> 
3740: 63 61 6e 20 6e 6f 77 0a 62 65 20 77 72 69 74 74  can now.be writt
3750: 65 6e 20 61 73 20 61 20 73 69 6d 70 6c 65 20 71  en as a simple q
3760: 75 65 72 79 2c 20 6c 69 6b 65 20 74 68 69 73 3a  uery, like this:
3770: 0a 0a 5e 28 3c 62 6c 6f 63 6b 71 75 6f 74 65 3e  ..^(<blockquote>
3780: 3c 70 72 65 3e 0a 53 45 4c 45 43 54 20 6f 62 6a  <pre>.SELECT obj
3790: 6e 61 6d 65 20 46 52 4f 4d 20 64 65 6d 6f 5f 69  name FROM demo_i
37a0: 6e 64 65 78 32 0a 20 57 48 45 52 45 20 63 6f 6e  ndex2. WHERE con
37b0: 74 61 69 6e 65 64 5f 69 6e 28 62 6f 75 6e 64 61  tained_in(bounda
37c0: 72 79 2c 20 3a 62 6f 75 6e 64 61 72 79 29 0a 20  ry, :boundary). 
37d0: 20 20 41 4e 44 20 6d 69 6e 58 26 67 74 3b 3d 2d    AND minX&gt;=-
37e0: 38 31 2e 30 20 41 4e 44 20 6d 61 78 58 26 6c 74  81.0 AND maxX&lt
37f0: 3b 3d 2d 37 39 2e 36 0a 20 20 20 41 4e 44 20 6d  ;=-79.6.   AND m
3800: 69 6e 59 26 67 74 3b 3d 33 35 2e 30 20 41 4e 44  inY&gt;=35.0 AND
3810: 20 6d 61 78 59 26 67 74 3b 3d 33 36 2e 32 3b 0a   maxY&gt;=36.2;.
3820: 3c 2f 70 72 65 3e 3c 2f 62 6c 6f 63 6b 71 75 6f  </pre></blockquo
3830: 74 65 3e 29 5e 0a 0a 3c 74 63 6c 3e 68 64 5f 66  te>)^..<tcl>hd_f
3840: 72 61 67 6d 65 6e 74 20 7b 69 6e 74 72 74 72 65  ragment {intrtre
3850: 65 7d 20 7b 69 6e 74 65 67 65 72 2d 76 61 6c 75  e} {integer-valu
3860: 65 64 20 72 2d 74 72 65 65 73 7d 3c 2f 74 63 6c  ed r-trees}</tcl
3870: 3e 0a 3c 68 31 3e 49 6e 74 65 67 65 72 2d 56 61  >.<h1>Integer-Va
3880: 6c 75 65 64 20 52 2d 54 72 65 65 73 3c 2f 68 31  lued R-Trees</h1
3890: 3e 0a 0a 3c 70 3e 0a 54 68 65 20 64 65 66 61 75  >..<p>.The defau
38a0: 6c 74 20 76 69 72 74 75 61 6c 20 74 61 62 6c 65  lt virtual table
38b0: 20 28 22 72 74 72 65 65 22 29 20 6e 6f 72 6d 61   ("rtree") norma
38c0: 6c 6c 79 20 73 74 6f 72 65 73 20 63 6f 6f 72 64  lly stores coord
38d0: 69 6e 61 74 65 73 20 61 73 0a 73 69 6e 67 6c 65  inates as.single
38e0: 2d 70 72 65 63 69 73 69 6f 6e 20 28 34 2d 62 79  -precision (4-by
38f0: 74 65 29 20 66 6c 6f 61 74 69 6e 67 20 70 6f 69  te) floating poi
3900: 6e 74 20 6e 75 6d 62 65 72 73 2e 20 20 49 66 20  nt numbers.  If 
3910: 69 6e 74 65 67 65 72 20 63 6f 6f 72 64 69 6e 61  integer coordina
3920: 74 65 73 0a 61 72 65 20 64 65 73 69 72 65 64 2c  tes.are desired,
3930: 20 64 65 63 6c 61 72 65 20 74 68 65 20 74 61 62   declare the tab
3940: 6c 65 20 75 73 69 6e 67 20 22 72 74 72 65 65 5f  le using "rtree_
3950: 69 33 32 22 20 69 6e 73 74 65 61 64 3a 0a 0a 3c  i32" instead:..<
3960: 62 6c 6f 63 6b 71 75 6f 74 65 3e 3c 70 72 65 3e  blockquote><pre>
3970: 0a 43 52 45 41 54 45 20 56 49 52 54 55 41 4c 20  .CREATE VIRTUAL 
3980: 54 41 42 4c 45 20 69 6e 74 72 74 72 65 65 20 55  TABLE intrtree U
3990: 53 49 4e 47 20 72 74 72 65 65 5f 69 33 32 28 69  SING rtree_i32(i
39a0: 64 2c 78 30 2c 78 31 2c 79 30 2c 79 31 2c 7a 30  d,x0,x1,y0,y1,z0
39b0: 2c 7a 31 29 3b 0a 3c 2f 70 72 65 3e 3c 2f 62 6c  ,z1);.</pre></bl
39c0: 6f 63 6b 71 75 6f 74 65 3e 0a 0a 3c 70 3e 0a 41  ockquote>..<p>.A
39d0: 6e 20 72 74 72 65 65 5f 69 33 32 20 73 74 6f 72  n rtree_i32 stor
39e0: 65 73 20 63 6f 6f 72 64 69 6e 61 74 65 73 20 61  es coordinates a
39f0: 73 20 33 32 2d 62 69 74 20 73 69 67 6e 65 64 20  s 32-bit signed 
3a00: 69 6e 74 65 67 65 72 73 2e 20 20 42 75 74 20 69  integers.  But i
3a10: 74 20 73 74 69 6c 6c 0a 75 73 69 6e 67 20 66 6c  t still.using fl
3a20: 6f 61 74 69 6e 67 20 70 6f 69 6e 74 20 63 6f 6d  oating point com
3a30: 70 75 74 61 74 69 6f 6e 73 20 69 6e 74 65 72 6e  putations intern
3a40: 61 6c 6c 79 20 61 73 20 70 61 72 74 20 6f 66 20  ally as part of 
3a50: 74 68 65 20 72 2d 74 72 65 65 20 61 6c 67 6f 72  the r-tree algor
3a60: 69 74 68 6d 2e 0a 0a 3c 74 63 6c 3e 68 64 5f 66  ithm...<tcl>hd_f
3a70: 72 61 67 6d 65 6e 74 20 7b 63 75 73 74 6f 6d 71  ragment {customq
3a80: 75 65 72 79 7d 20 7b 63 75 73 74 6f 6d 20 72 2d  uery} {custom r-
3a90: 74 72 65 65 20 71 75 65 72 69 65 73 7d 3c 2f 74  tree queries}</t
3aa0: 63 6c 3e 0a 3c 68 31 3e 43 75 73 74 6f 6d 20 52  cl>.<h1>Custom R
3ab0: 2d 54 72 65 65 20 51 75 65 72 69 65 73 3c 2f 68  -Tree Queries</h
3ac0: 31 3e 0a 0a 3c 70 3e 42 79 20 75 73 69 6e 67 20  1>..<p>By using 
3ad0: 73 74 61 6e 64 61 72 64 20 53 51 4c 20 65 78 70  standard SQL exp
3ae0: 72 65 73 73 69 6f 6e 73 20 69 6e 20 74 68 65 20  ressions in the 
3af0: 57 48 45 52 45 20 63 6c 61 75 73 65 20 6f 66 20  WHERE clause of 
3b00: 61 20 53 45 4c 45 43 54 20 71 75 65 72 79 2c 0a  a SELECT query,.
3b10: 61 20 70 72 6f 67 72 61 6d 6d 65 72 20 63 61 6e  a programmer can
3b20: 20 71 75 65 72 79 20 66 6f 72 20 61 6c 6c 20 52   query for all R
3b30: 2a 54 72 65 65 20 65 6e 74 72 69 65 73 20 74 68  *Tree entries th
3b40: 61 74 20 0a 69 6e 74 65 72 73 65 63 74 20 77 69  at .intersect wi
3b50: 74 68 20 6f 72 20 61 72 65 20 63 6f 6e 74 61 69  th or are contai
3b60: 6e 65 64 20 77 69 74 68 69 6e 20 61 20 70 61 72  ned within a par
3b70: 74 69 63 75 6c 61 72 20 62 6f 75 6e 64 69 6e 67  ticular bounding
3b80: 2d 62 6f 78 2e 0a 43 75 73 74 6f 6d 20 52 2a 54  -box..Custom R*T
3b90: 72 65 65 20 71 75 65 72 69 65 73 2c 20 75 73 69  ree queries, usi
3ba0: 6e 67 20 74 68 65 20 4d 41 54 43 48 0a 6f 70 65  ng the MATCH.ope
3bb0: 72 61 74 6f 72 20 69 6e 20 74 68 65 20 57 48 45  rator in the WHE
3bc0: 52 45 20 63 6c 61 75 73 65 20 6f 66 20 61 20 53  RE clause of a S
3bd0: 45 4c 45 43 54 2c 20 61 6c 6c 6f 77 20 74 68 65  ELECT, allow the
3be0: 20 70 72 6f 67 72 61 6d 6d 65 72 20 74 6f 20 71   programmer to q
3bf0: 75 65 72 79 20 66 6f 72 20 0a 74 68 65 20 73 65  uery for .the se
3c00: 74 20 6f 66 20 52 2a 54 72 65 65 20 65 6e 74 72  t of R*Tree entr
3c10: 69 65 73 20 74 68 61 74 20 69 6e 74 65 72 73 65  ies that interse
3c20: 63 74 20 61 6e 79 20 61 72 62 69 74 72 61 72 79  ct any arbitrary
3c30: 20 72 65 67 69 6f 6e 20 6f 72 20 73 68 61 70 65   region or shape
3c40: 2c 20 6e 6f 74 20 0a 6a 75 73 74 20 61 20 62 6f  , not .just a bo
3c50: 78 2e 20 20 54 68 69 73 20 63 61 70 61 62 69 6c  x.  This capabil
3c60: 69 74 79 20 69 73 20 75 73 65 66 75 6c 2c 20 66  ity is useful, f
3c70: 6f 72 20 65 78 61 6d 70 6c 65 2c 20 69 6e 20 63  or example, in c
3c80: 6f 6d 70 75 74 69 6e 67 20 74 68 65 20 0a 73 75  omputing the .su
3c90: 62 73 65 74 20 6f 66 20 6f 62 6a 65 63 74 73 20  bset of objects 
3ca0: 69 6e 20 74 68 65 20 52 2a 54 72 65 65 20 74 68  in the R*Tree th
3cb0: 61 74 20 61 72 65 20 76 69 73 69 62 6c 65 20 66  at are visible f
3cc0: 72 6f 6d 20 61 20 63 61 6d 65 72 61 20 70 6f 73  rom a camera pos
3cd0: 69 74 69 6f 6e 65 64 20 0a 69 6e 20 33 2d 44 20  itioned .in 3-D 
3ce0: 73 70 61 63 65 2e 0a 0a 3c 70 3e 52 65 67 69 6f  space...<p>Regio
3cf0: 6e 73 20 66 6f 72 20 63 75 73 74 6f 6d 20 52 2a  ns for custom R*
3d00: 54 72 65 65 20 71 75 65 72 69 65 73 20 61 72 65  Tree queries are
3d10: 20 64 65 66 69 6e 65 64 20 62 79 20 52 2a 54 72   defined by R*Tr
3d20: 65 65 20 67 65 6f 6d 65 74 72 79 20 63 61 6c 6c  ee geometry call
3d30: 62 61 63 6b 73 0a 69 6d 70 6c 65 6d 65 6e 74 65  backs.implemente
3d40: 64 20 62 79 20 74 68 65 20 61 70 70 6c 69 63 61  d by the applica
3d50: 74 69 6f 6e 20 61 6e 64 20 72 65 67 69 73 74 65  tion and registe
3d60: 72 65 64 20 77 69 74 68 20 53 51 4c 69 74 65 20  red with SQLite 
3d70: 76 69 61 20 61 20 63 61 6c 6c 20 74 6f 20 6f 6e  via a call to on
3d80: 65 0a 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69  e.of the followi
3d90: 6e 67 20 74 77 6f 20 41 50 49 73 3a 0a 0a 3c 62  ng two APIs:..<b
3da0: 6c 6f 63 6b 71 75 6f 74 65 3e 3c 70 72 65 3e 0a  lockquote><pre>.
3db0: 69 6e 74 20 73 71 6c 69 74 65 33 5f 72 74 72 65  int sqlite3_rtre
3dc0: 65 5f 71 75 65 72 79 5f 63 61 6c 6c 62 61 63 6b  e_query_callback
3dd0: 28 0a 20 20 73 71 6c 69 74 65 33 20 2a 64 62 2c  (.  sqlite3 *db,
3de0: 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 7a  .  const char *z
3df0: 51 75 65 72 79 46 75 6e 63 2c 0a 20 20 69 6e 74  QueryFunc,.  int
3e00: 20 28 2a 78 51 75 65 72 79 46 75 6e 63 29 28 73   (*xQueryFunc)(s
3e10: 71 6c 69 74 65 33 5f 72 74 72 65 65 5f 71 75 65  qlite3_rtree_que
3e20: 72 79 5f 69 6e 66 6f 2a 29 2c 0a 20 20 76 6f 69  ry_info*),.  voi
3e30: 64 20 2a 70 43 6f 6e 74 65 78 74 2c 0a 20 20 76  d *pContext,.  v
3e40: 6f 69 64 20 28 2a 78 44 65 73 74 72 75 63 74 6f  oid (*xDestructo
3e50: 72 29 28 76 6f 69 64 2a 29 0a 29 3b 0a 69 6e 74  r)(void*).);.int
3e60: 20 73 71 6c 69 74 65 33 5f 72 74 72 65 65 5f 67   sqlite3_rtree_g
3e70: 65 6f 6d 65 74 72 79 5f 63 61 6c 6c 62 61 63 6b  eometry_callback
3e80: 28 0a 20 20 73 71 6c 69 74 65 33 20 2a 64 62 2c  (.  sqlite3 *db,
3e90: 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 7a  .  const char *z
3ea0: 47 65 6f 6d 2c 0a 20 20 69 6e 74 20 28 2a 78 47  Geom,.  int (*xG
3eb0: 65 6f 6d 29 28 73 71 6c 69 74 65 33 5f 72 74 72  eom)(sqlite3_rtr
3ec0: 65 65 5f 67 65 6f 6d 65 74 72 79 20 2a 2c 20 69  ee_geometry *, i
3ed0: 6e 74 20 6e 43 6f 6f 72 64 2c 20 64 6f 75 62 6c  nt nCoord, doubl
3ee0: 65 20 2a 61 43 6f 6f 72 64 2c 20 69 6e 74 20 2a  e *aCoord, int *
3ef0: 70 52 65 73 29 2c 0a 20 20 76 6f 69 64 20 2a 70  pRes),.  void *p
3f00: 43 6f 6e 74 65 78 74 0a 29 3b 0a 3c 2f 70 72 65  Context.);.</pre
3f10: 3e 3c 2f 62 6c 6f 63 6b 71 75 6f 74 65 3e 0a 0a  ></blockquote>..
3f20: 3c 70 3e 54 68 65 20 73 71 6c 69 74 65 33 5f 72  <p>The sqlite3_r
3f30: 74 72 65 65 5f 71 75 65 72 79 5f 63 61 6c 6c 62  tree_query_callb
3f40: 61 63 6b 28 29 20 62 65 63 61 6d 65 20 61 76 61  ack() became ava
3f50: 69 6c 61 62 6c 65 20 77 69 74 68 20 53 51 4c 69  ilable with SQLi
3f60: 74 65 0a 5b 76 65 72 73 69 6f 6e 20 33 2e 38 2e  te.[version 3.8.
3f70: 35 5d 20 28 5b 64 61 74 65 6f 66 3a 33 2e 38 2e  5] ([dateof:3.8.
3f80: 35 5d 29 20 61 6e 64 20 69 73 20 74 68 65 20 70  5]) and is the p
3f90: 72 65 66 65 72 72 65 64 20 69 6e 74 65 72 66 61  referred interfa
3fa0: 63 65 2e 0a 54 68 65 20 73 71 6c 69 74 65 33 5f  ce..The sqlite3_
3fb0: 72 74 72 65 65 5f 67 65 6f 6d 65 74 72 79 5f 63  rtree_geometry_c
3fc0: 61 6c 6c 62 61 63 6b 28 29 20 69 73 20 61 6e 20  allback() is an 
3fd0: 6f 6c 64 65 72 20 61 6e 64 20 6c 65 73 73 20 66  older and less f
3fe0: 6c 65 78 69 62 6c 65 0a 69 6e 74 65 72 66 61 63  lexible.interfac
3ff0: 65 20 74 68 61 74 20 69 73 20 73 75 70 70 6f 72  e that is suppor
4000: 74 65 64 20 66 6f 72 20 62 61 63 6b 77 61 72 64  ted for backward
4010: 73 20 63 6f 6d 70 61 74 69 62 69 6c 69 74 79 2e  s compatibility.
4020: 0a 0a 3c 70 3e 5e 41 20 63 61 6c 6c 20 74 6f 20  ..<p>^A call to 
4030: 6f 6e 65 20 6f 66 20 74 68 65 20 61 62 6f 76 65  one of the above
4040: 20 41 50 49 73 20 63 72 65 61 74 65 73 20 61 20   APIs creates a 
4050: 6e 65 77 20 53 51 4c 20 66 75 6e 63 74 69 6f 6e  new SQL function
4060: 20 6e 61 6d 65 64 20 62 79 20 74 68 65 0a 73 65   named by the.se
4070: 63 6f 6e 64 20 70 61 72 61 6d 65 74 65 72 20 28  cond parameter (
4080: 7a 51 75 65 72 79 46 75 6e 63 20 6f 72 20 7a 47  zQueryFunc or zG
4090: 65 6f 6d 29 2e 20 20 5e 57 68 65 6e 20 74 68 61  eom).  ^When tha
40a0: 74 20 53 51 4c 20 66 75 6e 63 74 69 6f 6e 20 61  t SQL function a
40b0: 70 70 65 61 72 73 0a 6f 6e 20 74 68 65 20 72 69  ppears.on the ri
40c0: 67 68 74 2d 68 61 6e 64 20 73 69 64 65 20 6f 66  ght-hand side of
40d0: 20 74 68 65 20 4d 41 54 43 48 20 6f 70 65 72 61   the MATCH opera
40e0: 74 6f 72 20 61 6e 64 20 74 68 65 20 6c 65 66 74  tor and the left
40f0: 2d 68 61 6e 64 20 73 69 64 65 20 6f 66 20 74 68  -hand side of th
4100: 65 0a 4d 41 54 43 48 20 6f 70 65 72 61 74 6f 72  e.MATCH operator
4110: 20 69 73 20 61 6e 79 20 63 6f 6c 75 6d 6e 20 69   is any column i
4120: 6e 20 74 68 65 20 52 2a 54 72 65 65 20 76 69 72  n the R*Tree vir
4130: 74 75 61 6c 20 74 61 62 6c 65 2c 20 74 68 65 6e  tual table, then
4140: 20 74 68 65 20 63 61 6c 6c 62 61 63 6b 20 0a 64   the callback .d
4150: 65 66 69 6e 65 64 20 62 79 20 74 68 65 20 74 68  efined by the th
4160: 69 72 64 20 61 72 67 75 6d 65 6e 74 20 28 78 51  ird argument (xQ
4170: 75 65 72 79 46 75 6e 63 20 6f 72 20 78 47 65 6f  ueryFunc or xGeo
4180: 6d 29 20 69 73 20 69 6e 76 6f 6b 65 64 20 74 6f  m) is invoked to
4190: 20 64 65 74 65 72 6d 69 6e 65 0a 69 66 20 61 20   determine.if a 
41a0: 70 61 72 74 69 63 75 6c 61 72 20 6f 62 6a 65 63  particular objec
41b0: 74 20 6f 72 20 73 75 62 74 72 65 65 20 6f 76 65  t or subtree ove
41c0: 72 6c 61 70 73 20 74 68 65 20 64 65 73 69 72 65  rlaps the desire
41d0: 64 20 72 65 67 69 6f 6e 2e 0a 0a 3c 70 3e 5e 28  d region...<p>^(
41e0: 46 6f 72 20 65 78 61 6d 70 6c 65 2c 20 61 20 71  For example, a q
41f0: 75 65 72 79 20 6c 69 6b 65 20 74 68 65 20 66 6f  uery like the fo
4200: 6c 6c 6f 77 69 6e 67 20 6d 69 67 68 74 20 62 65  llowing might be
4210: 20 75 73 65 64 20 74 6f 20 66 69 6e 64 20 61 6c   used to find al
4220: 6c 0a 52 2a 54 72 65 65 20 65 6e 74 72 69 65 73  l.R*Tree entries
4230: 20 74 68 61 74 20 6f 76 65 72 6c 61 70 20 77 69   that overlap wi
4240: 74 68 20 61 20 63 69 72 63 6c 65 20 63 65 6e 74  th a circle cent
4250: 65 72 65 64 20 61 20 34 35 2e 33 2c 32 32 2e 39  ered a 45.3,22.9
4260: 20 77 69 74 68 20 61 0a 72 61 64 69 75 73 20 6f   with a.radius o
4270: 66 20 35 2e 30 3a 0a 0a 3c 62 6c 6f 63 6b 71 75  f 5.0:..<blockqu
4280: 6f 74 65 3e 3c 70 72 65 3e 0a 53 45 4c 45 43 54  ote><pre>.SELECT
4290: 20 69 64 20 46 52 4f 4d 20 64 65 6d 6f 5f 69 6e   id FROM demo_in
42a0: 64 65 78 20 57 48 45 52 45 20 69 64 20 4d 41 54  dex WHERE id MAT
42b0: 43 48 20 63 69 72 63 6c 65 28 34 35 2e 33 2c 20  CH circle(45.3, 
42c0: 32 32 2e 39 2c 20 35 2e 30 29 0a 3c 2f 62 6c 6f  22.9, 5.0).</blo
42d0: 63 6b 71 75 6f 74 65 3e 3c 2f 70 72 65 3e 29 5e  ckquote></pre>)^
42e0: 0a 0a 3c 70 3e 5e 54 68 65 20 53 51 4c 20 73 79  ..<p>^The SQL sy
42f0: 6e 74 61 78 20 66 6f 72 20 63 75 73 74 6f 6d 20  ntax for custom 
4300: 71 75 65 72 69 65 73 20 69 73 20 74 68 65 20 73  queries is the s
4310: 61 6d 65 20 72 65 67 61 72 64 6c 65 73 73 20 6f  ame regardless o
4320: 66 20 77 68 69 63 68 0a 69 6e 74 65 72 66 61 63  f which.interfac
4330: 65 2c 20 73 71 6c 69 74 65 33 5f 72 74 72 65 65  e, sqlite3_rtree
4340: 5f 67 65 6f 6d 65 74 72 79 5f 63 61 6c 6c 62 61  _geometry_callba
4350: 63 6b 28 29 20 6f 72 20 73 71 6c 69 74 65 33 5f  ck() or sqlite3_
4360: 72 74 72 65 65 5f 71 75 65 72 79 5f 63 61 6c 6c  rtree_query_call
4370: 62 61 63 6b 28 29 2c 0a 69 73 20 75 73 65 64 20  back(),.is used 
4380: 74 6f 20 72 65 67 69 73 74 65 72 20 74 68 65 20  to register the 
4390: 53 51 4c 20 66 75 6e 63 74 69 6f 6e 2e 20 20 48  SQL function.  H
43a0: 6f 77 65 76 65 72 2c 20 74 68 65 20 6e 65 77 65  owever, the newe
43b0: 72 20 71 75 65 72 79 2d 73 74 79 6c 65 0a 63 61  r query-style.ca
43c0: 6c 6c 62 61 63 6b 73 20 67 69 76 65 20 74 68 65  llbacks give the
43d0: 20 61 70 70 6c 69 63 61 74 69 6f 6e 20 67 72 65   application gre
43e0: 61 74 65 72 20 63 6f 6e 74 72 6f 6c 20 6f 76 65  ater control ove
43f0: 72 20 68 6f 77 20 74 68 65 20 71 75 65 72 79 20  r how the query 
4400: 70 72 6f 63 65 65 64 73 2e 0a 0a 3c 68 32 3e 54  proceeds...<h2>T
4410: 68 65 20 4c 65 67 61 63 79 20 78 47 65 6f 6d 20  he Legacy xGeom 
4420: 43 61 6c 6c 62 61 63 6b 3c 2f 68 32 3e 0a 0a 3c  Callback</h2>..<
4430: 70 3e 5e 54 68 65 20 6c 65 67 61 63 79 20 78 47  p>^The legacy xG
4440: 65 6f 6d 20 63 61 6c 6c 62 61 63 6b 20 69 73 20  eom callback is 
4450: 69 6e 76 6f 6b 65 64 20 77 69 74 68 20 66 6f 75  invoked with fou
4460: 72 20 61 72 67 75 6d 65 6e 74 73 2e 20 20 5e 54  r arguments.  ^T
4470: 68 65 20 66 69 72 73 74 0a 61 72 67 75 6d 65 6e  he first.argumen
4480: 74 20 69 73 20 61 20 70 6f 69 6e 74 65 72 20 74  t is a pointer t
4490: 6f 20 61 6e 20 73 71 6c 69 74 65 33 5f 72 74 72  o an sqlite3_rtr
44a0: 65 65 5f 67 65 6f 6d 65 74 72 79 20 73 74 72 75  ee_geometry stru
44b0: 63 74 75 72 65 20 77 68 69 63 68 20 70 72 6f 76  cture which prov
44c0: 69 64 65 73 0a 69 6e 66 6f 72 6d 61 74 69 6f 6e  ides.information
44d0: 20 61 62 6f 75 74 20 68 6f 77 20 74 68 65 20 53   about how the S
44e0: 51 4c 20 66 75 6e 63 74 69 6f 6e 20 77 61 73 20  QL function was 
44f0: 69 6e 76 6f 6b 65 64 2e 20 20 5e 54 68 65 20 73  invoked.  ^The s
4500: 65 63 6f 6e 64 20 61 72 67 75 6d 65 6e 74 0a 69  econd argument.i
4510: 73 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20  s the number of 
4520: 63 6f 6f 72 64 69 6e 61 74 65 73 20 69 6e 20 65  coordinates in e
4530: 61 63 68 20 72 2d 74 72 65 65 20 65 6e 74 72 79  ach r-tree entry
4540: 2c 20 61 6e 64 20 69 73 20 61 6c 77 61 79 73 20  , and is always 
4550: 74 68 65 20 73 61 6d 65 0a 66 6f 72 20 61 6e 79  the same.for any
4560: 20 67 69 76 65 6e 20 52 2a 54 72 65 65 2e 20 20   given R*Tree.  
4570: 5e 54 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 63  ^The number of c
4580: 6f 6f 72 64 69 6e 61 74 65 73 20 69 73 20 32 20  oordinates is 2 
4590: 66 6f 72 20 61 20 31 2d 64 69 6d 65 6e 73 69 6f  for a 1-dimensio
45a0: 6e 61 6c 20 52 2a 54 72 65 65 2c 0a 34 20 66 6f  nal R*Tree,.4 fo
45b0: 72 20 61 20 32 2d 64 69 6d 65 6e 73 69 6f 6e 61  r a 2-dimensiona
45c0: 6c 20 52 2a 54 72 65 65 2c 20 36 20 66 6f 72 20  l R*Tree, 6 for 
45d0: 61 20 33 2d 64 69 6d 65 6e 73 69 6f 6e 61 6c 20  a 3-dimensional 
45e0: 52 2a 54 72 65 65 2c 20 61 6e 64 20 73 6f 20 66  R*Tree, and so f
45f0: 6f 72 74 68 2e 0a 5e 54 68 65 20 74 68 69 72 64  orth..^The third
4600: 20 61 72 67 75 6d 65 6e 74 2c 20 61 43 6f 6f 72   argument, aCoor
4610: 64 5b 5d 2c 20 69 73 20 61 6e 20 61 72 72 61 79  d[], is an array
4620: 20 6f 66 20 6e 43 6f 6f 72 64 20 63 6f 6f 72 64   of nCoord coord
4630: 69 6e 61 74 65 73 20 74 68 61 74 20 64 65 66 69  inates that defi
4640: 6e 65 73 0a 61 20 62 6f 75 6e 64 69 6e 67 20 62  nes.a bounding b
4650: 6f 78 20 74 6f 20 62 65 20 74 65 73 74 65 64 2e  ox to be tested.
4660: 20 20 5e 54 68 65 20 6c 61 73 74 20 61 72 67 75    ^The last argu
4670: 6d 65 6e 74 20 69 73 20 61 20 70 6f 69 6e 74 65  ment is a pointe
4680: 72 20 69 6e 74 6f 20 77 68 69 63 68 20 0a 74 68  r into which .th
4690: 65 20 63 61 6c 6c 62 61 63 6b 20 72 65 73 75 6c  e callback resul
46a0: 74 20 73 68 6f 75 6c 64 20 62 65 20 77 72 69 74  t should be writ
46b0: 74 65 6e 2e 20 20 54 68 65 20 72 65 73 75 6c 74  ten.  The result
46c0: 20 69 73 20 7a 65 72 6f 0a 69 66 20 74 68 65 20   is zero.if the 
46d0: 62 6f 75 6e 64 69 6e 67 2d 62 6f 78 20 64 65 66  bounding-box def
46e0: 69 6e 65 64 20 62 79 20 61 43 6f 6f 72 64 5b 5d  ined by aCoord[]
46f0: 20 69 73 20 63 6f 6d 70 6c 65 74 65 6c 79 20 6f   is completely o
4700: 75 74 73 69 64 65 0a 74 68 65 20 72 65 67 69 6f  utside.the regio
4710: 6e 20 64 65 66 69 6e 65 64 20 62 79 20 74 68 65  n defined by the
4720: 20 78 47 65 6f 6d 20 63 61 6c 6c 62 61 63 6b 20   xGeom callback 
4730: 61 6e 64 20 74 68 65 20 72 65 73 75 6c 74 20 69  and the result i
4740: 73 20 6e 6f 6e 2d 7a 65 72 6f 20 69 66 0a 74 68  s non-zero if.th
4750: 65 20 62 6f 75 6e 64 69 6e 67 2d 62 6f 78 20 69  e bounding-box i
4760: 73 20 69 6e 73 69 64 65 20 6f 72 20 6f 76 65 72  s inside or over
4770: 6c 61 70 73 20 77 69 74 68 20 74 68 65 20 78 47  laps with the xG
4780: 65 6f 6d 20 72 65 67 69 6f 6e 2e 20 20 54 68 65  eom region.  The
4790: 20 78 47 65 6f 6d 0a 63 61 6c 6c 62 61 63 6b 20   xGeom.callback 
47a0: 73 68 6f 75 6c 64 20 6e 6f 72 6d 61 6c 6c 79 20  should normally 
47b0: 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b  return SQLITE_OK
47c0: 2e 20 20 5e 49 66 20 78 47 65 6f 6d 20 72 65 74  .  ^If xGeom ret
47d0: 75 72 6e 73 20 61 6e 79 74 68 69 6e 67 20 6f 74  urns anything ot
47e0: 68 65 72 0a 74 68 61 6e 20 53 51 4c 49 54 45 5f  her.than SQLITE_
47f0: 4f 4b 2c 20 74 68 65 6e 20 74 68 65 20 72 2d 74  OK, then the r-t
4800: 72 65 65 20 71 75 65 72 79 20 77 69 6c 6c 20 61  ree query will a
4810: 62 6f 72 74 20 77 69 74 68 20 61 6e 20 65 72 72  bort with an err
4820: 6f 72 2e 0a 0a 3c 70 3e 54 68 65 20 73 71 6c 69  or...<p>The sqli
4830: 74 65 33 5f 72 74 72 65 65 5f 67 65 6f 6d 65 74  te3_rtree_geomet
4840: 72 79 20 73 74 72 75 63 74 75 72 65 20 74 68 61  ry structure tha
4850: 74 20 74 68 65 20 66 69 72 73 74 20 61 72 67 75  t the first argu
4860: 6d 65 6e 74 20 74 6f 20 74 68 65 0a 78 47 65 6f  ment to the.xGeo
4870: 6d 20 63 61 6c 6c 62 61 63 6b 20 70 6f 69 6e 74  m callback point
4880: 73 20 74 6f 20 68 61 73 20 61 20 73 74 72 75 63  s to has a struc
4890: 74 75 72 65 20 73 68 6f 77 6e 20 62 65 6c 6f 77  ture shown below
48a0: 2e 20 20 5e 54 68 65 20 65 78 61 63 74 20 73 61  .  ^The exact sa
48b0: 6d 65 0a 73 71 6c 69 74 65 33 5f 72 74 72 65 65  me.sqlite3_rtree
48c0: 5f 67 65 6f 6d 65 74 72 79 0a 73 74 72 75 63 74  _geometry.struct
48d0: 75 72 65 20 69 73 20 75 73 65 64 20 66 6f 72 20  ure is used for 
48e0: 65 76 65 72 79 20 63 61 6c 6c 62 61 63 6b 20 66  every callback f
48f0: 6f 72 20 73 61 6d 65 20 4d 41 54 43 48 20 6f 70  or same MATCH op
4900: 65 72 61 74 6f 72 20 69 6e 20 74 68 65 20 73 61  erator in the sa
4910: 6d 65 0a 71 75 65 72 79 2e 20 20 5e 54 68 65 20  me.query.  ^The 
4920: 63 6f 6e 74 65 6e 74 73 20 6f 66 20 74 68 65 20  contents of the 
4930: 73 71 6c 69 74 65 33 5f 72 74 72 65 65 5f 67 65  sqlite3_rtree_ge
4940: 6f 6d 65 74 72 79 0a 73 74 72 75 63 74 75 72 65  ometry.structure
4950: 20 61 72 65 20 69 6e 69 74 69 61 6c 69 7a 65 64   are initialized
4960: 20 62 79 20 53 51 4c 69 74 65 20 62 75 74 20 61   by SQLite but a
4970: 72 65 0a 6e 6f 74 20 73 75 62 73 65 71 75 65 6e  re.not subsequen
4980: 74 6c 79 20 6d 6f 64 69 66 69 65 64 2e 20 20 54  tly modified.  T
4990: 68 65 20 63 61 6c 6c 62 61 63 6b 20 69 73 20 66  he callback is f
49a0: 72 65 65 20 74 6f 20 6d 61 6b 65 20 63 68 61 6e  ree to make chan
49b0: 67 65 73 20 74 6f 20 74 68 65 0a 70 55 73 65 72  ges to the.pUser
49c0: 20 61 6e 64 20 78 44 65 6c 55 73 65 72 20 65 6c   and xDelUser el
49d0: 65 6d 65 6e 74 73 20 6f 66 20 74 68 65 20 73 74  ements of the st
49e0: 72 75 63 74 75 72 65 20 69 66 20 64 65 73 69 72  ructure if desir
49f0: 65 64 2e 0a 0a 3c 62 6c 6f 63 6b 71 75 6f 74 65  ed...<blockquote
4a00: 3e 3c 70 72 65 3e 0a 74 79 70 65 64 65 66 20 73  ><pre>.typedef s
4a10: 74 72 75 63 74 20 73 71 6c 69 74 65 33 5f 72 74  truct sqlite3_rt
4a20: 72 65 65 5f 67 65 6f 6d 65 74 72 79 20 73 71 6c  ree_geometry sql
4a30: 69 74 65 33 5f 72 74 72 65 65 5f 67 65 6f 6d 65  ite3_rtree_geome
4a40: 74 72 79 3b 0a 73 74 72 75 63 74 20 73 71 6c 69  try;.struct sqli
4a50: 74 65 33 5f 72 74 72 65 65 5f 67 65 6f 6d 65 74  te3_rtree_geomet
4a60: 72 79 20 7b 0a 20 20 76 6f 69 64 20 2a 70 43 6f  ry {.  void *pCo
4a70: 6e 74 65 78 74 3b 20 20 20 20 20 20 20 20 20 20  ntext;          
4a80: 20 20 20 20 20 20 20 2f 2a 20 43 6f 70 79 20 6f         /* Copy o
4a90: 66 20 70 43 6f 6e 74 65 78 74 20 70 61 73 73 65  f pContext passe
4aa0: 64 20 74 6f 20 73 5f 72 5f 67 5f 63 28 29 20 2a  d to s_r_g_c() *
4ab0: 2f 0a 20 20 69 6e 74 20 6e 50 61 72 61 6d 3b 20  /.  int nParam; 
4ac0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
4ad0: 20 20 20 20 2f 2a 20 53 69 7a 65 20 6f 66 20 61      /* Size of a
4ae0: 72 72 61 79 20 61 50 61 72 61 6d 20 2a 2f 0a 20  rray aParam */. 
4af0: 20 64 6f 75 62 6c 65 20 2a 61 50 61 72 61 6d 3b   double *aParam;
4b00: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
4b10: 20 2f 2a 20 50 61 72 61 6d 65 74 65 72 73 20 70   /* Parameters p
4b20: 61 73 73 65 64 20 74 6f 20 53 51 4c 20 67 65 6f  assed to SQL geo
4b30: 6d 20 66 75 6e 63 74 69 6f 6e 20 2a 2f 0a 20 20  m function */.  
4b40: 76 6f 69 64 20 2a 70 55 73 65 72 3b 20 20 20 20  void *pUser;    
4b50: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
4b60: 2f 2a 20 43 61 6c 6c 62 61 63 6b 20 69 6d 70 6c  /* Callback impl
4b70: 65 6d 65 6e 74 61 74 69 6f 6e 20 75 73 65 72 20  ementation user 
4b80: 64 61 74 61 20 2a 2f 0a 20 20 76 6f 69 64 20 28  data */.  void (
4b90: 2a 78 44 65 6c 55 73 65 72 29 28 76 6f 69 64 20  *xDelUser)(void 
4ba0: 2a 29 3b 20 20 20 20 20 20 20 2f 2a 20 43 61 6c  *);       /* Cal
4bb0: 6c 65 64 20 62 79 20 53 51 4c 69 74 65 20 74 6f  led by SQLite to
4bc0: 20 63 6c 65 61 6e 20 75 70 20 70 55 73 65 72 20   clean up pUser 
4bd0: 2a 2f 0a 7d 3b 0a 3c 2f 70 72 65 3e 3c 2f 62 6c  */.};.</pre></bl
4be0: 6f 63 6b 71 75 6f 74 65 3e 0a 0a 3c 70 3e 5e 54  ockquote>..<p>^T
4bf0: 68 65 20 70 43 6f 6e 74 65 78 74 20 6d 65 6d 62  he pContext memb
4c00: 65 72 20 6f 66 20 74 68 65 20 73 71 6c 69 74 65  er of the sqlite
4c10: 33 5f 72 74 72 65 65 5f 67 65 6f 6d 65 74 72 79  3_rtree_geometry
4c20: 0a 73 74 72 75 63 74 75 72 65 20 69 73 20 61 6c  .structure is al
4c30: 77 61 79 73 20 73 65 74 20 74 6f 20 61 20 63 6f  ways set to a co
4c40: 70 79 20 6f 66 20 74 68 65 20 70 43 6f 6e 74 65  py of the pConte
4c50: 78 74 0a 61 72 67 75 6d 65 6e 74 20 70 61 73 73  xt.argument pass
4c60: 65 64 20 74 6f 20 73 71 6c 69 74 65 33 5f 72 74  ed to sqlite3_rt
4c70: 72 65 65 5f 67 65 6f 6d 65 74 72 79 5f 63 61 6c  ree_geometry_cal
4c80: 6c 62 61 63 6b 28 29 20 77 68 65 6e 20 74 68 65  lback() when the
4c90: 0a 63 61 6c 6c 62 61 63 6b 20 69 73 20 72 65 67  .callback is reg
4ca0: 69 73 74 65 72 65 64 2e 20 5e 54 68 65 20 61 50  istered. ^The aP
4cb0: 61 72 61 6d 5b 5d 20 61 72 72 61 79 20 28 73 69  aram[] array (si
4cc0: 7a 65 20 6e 50 61 72 61 6d 29 20 63 6f 6e 74 61  ze nParam) conta
4cd0: 69 6e 73 20 74 68 65 20 70 61 72 61 6d 65 74 65  ins the paramete
4ce0: 72 0a 76 61 6c 75 65 73 20 70 61 73 73 65 64 20  r.values passed 
4cf0: 74 6f 20 74 68 65 20 53 51 4c 20 66 75 6e 63 74  to the SQL funct
4d00: 69 6f 6e 20 6f 6e 20 74 68 65 20 72 69 67 68 74  ion on the right
4d10: 2d 68 61 6e 64 20 73 69 64 65 20 6f 66 20 74 68  -hand side of th
4d20: 65 20 4d 41 54 43 48 20 6f 70 65 72 61 74 6f 72  e MATCH operator
4d30: 2e 0a 49 6e 20 74 68 65 20 65 78 61 6d 70 6c 65  ..In the example
4d40: 20 22 63 69 72 63 6c 65 22 20 71 75 65 72 79 20   "circle" query 
4d50: 61 62 6f 76 65 2c 20 6e 50 61 72 61 6d 20 77 6f  above, nParam wo
4d60: 75 6c 64 20 62 65 20 73 65 74 20 74 6f 20 33 20  uld be set to 3 
4d70: 61 6e 64 20 74 68 65 20 61 50 61 72 61 6d 5b 5d  and the aParam[]
4d80: 0a 61 72 72 61 79 20 77 6f 75 6c 64 20 63 6f 6e  .array would con
4d90: 74 61 69 6e 20 74 68 65 20 74 68 72 65 65 20 76  tain the three v
4da0: 61 6c 75 65 73 20 34 35 2e 33 2c 20 32 32 2e 39  alues 45.3, 22.9
4db0: 20 61 6e 64 20 35 2e 30 2e 0a 0a 3c 70 3e 5e 54   and 5.0...<p>^T
4dc0: 68 65 20 70 55 73 65 72 20 61 6e 64 20 78 44 65  he pUser and xDe
4dd0: 6c 55 73 65 72 20 6d 65 6d 62 65 72 73 20 6f 66  lUser members of
4de0: 20 74 68 65 20 73 71 6c 69 74 65 33 5f 72 74 72   the sqlite3_rtr
4df0: 65 65 5f 67 65 6f 6d 65 74 72 79 20 73 74 72 75  ee_geometry stru
4e00: 63 74 75 72 65 20 61 72 65 0a 69 6e 69 74 69 61  cture are.initia
4e10: 6c 6c 79 20 73 65 74 20 74 6f 20 4e 55 4c 4c 2e  lly set to NULL.
4e20: 20 5e 54 68 65 20 70 55 73 65 72 20 76 61 72 69   ^The pUser vari
4e30: 61 62 6c 65 20 6d 61 79 20 62 65 20 73 65 74 20  able may be set 
4e40: 62 79 20 74 68 65 20 63 61 6c 6c 62 61 63 6b 0a  by the callback.
4e50: 69 6d 70 6c 65 6d 65 6e 74 61 74 69 6f 6e 20 74  implementation t
4e60: 6f 20 61 6e 79 20 61 72 62 69 74 72 61 72 79 20  o any arbitrary 
4e70: 76 61 6c 75 65 20 74 68 61 74 20 6d 61 79 20 62  value that may b
4e80: 65 20 75 73 65 66 75 6c 20 74 6f 20 73 75 62 73  e useful to subs
4e90: 65 71 75 65 6e 74 0a 69 6e 76 6f 63 61 74 69 6f  equent.invocatio
4ea0: 6e 73 20 6f 66 20 74 68 65 20 63 61 6c 6c 62 61  ns of the callba
4eb0: 63 6b 20 77 69 74 68 69 6e 20 74 68 65 20 73 61  ck within the sa
4ec0: 6d 65 20 71 75 65 72 79 20 28 66 6f 72 20 65 78  me query (for ex
4ed0: 61 6d 70 6c 65 2c 20 61 0a 70 6f 69 6e 74 65 72  ample, a.pointer
4ee0: 20 74 6f 20 61 20 63 6f 6d 70 6c 69 63 61 74 65   to a complicate
4ef0: 64 20 64 61 74 61 20 73 74 72 75 63 74 75 72 65  d data structure
4f00: 20 75 73 65 64 20 74 6f 20 74 65 73 74 20 66 6f   used to test fo
4f10: 72 20 72 65 67 69 6f 6e 20 69 6e 74 65 72 73 65  r region interse
4f20: 63 74 69 6f 6e 29 2e 0a 5e 49 66 20 74 68 65 20  ction)..^If the 
4f30: 78 44 65 6c 55 73 65 72 20 76 61 72 69 61 62 6c  xDelUser variabl
4f40: 65 20 69 73 20 73 65 74 20 74 6f 20 61 20 6e 6f  e is set to a no
4f50: 6e 2d 4e 55 4c 4c 20 76 61 6c 75 65 2c 20 74 68  n-NULL value, th
4f60: 65 6e 20 61 66 74 65 72 20 74 68 65 0a 71 75 65  en after the.que
4f70: 72 79 20 68 61 73 20 66 69 6e 69 73 68 65 64 20  ry has finished 
4f80: 72 75 6e 6e 69 6e 67 20 53 51 4c 69 74 65 20 61  running SQLite a
4f90: 75 74 6f 6d 61 74 69 63 61 6c 6c 79 20 69 6e 76  utomatically inv
4fa0: 6f 6b 65 73 20 69 74 20 77 69 74 68 20 74 68 65  okes it with the
4fb0: 0a 76 61 6c 75 65 20 6f 66 20 74 68 65 20 70 55  .value of the pU
4fc0: 73 65 72 20 76 61 72 69 61 62 6c 65 20 61 73 20  ser variable as 
4fd0: 74 68 65 20 6f 6e 6c 79 20 61 72 67 75 6d 65 6e  the only argumen
4fe0: 74 2e 20 49 6e 20 6f 74 68 65 72 20 77 6f 72 64  t. In other word
4ff0: 73 2c 20 78 44 65 6c 55 73 65 72 0a 6d 61 79 20  s, xDelUser.may 
5000: 62 65 20 73 65 74 20 74 6f 20 61 20 64 65 73 74  be set to a dest
5010: 72 75 63 74 6f 72 20 66 75 6e 63 74 69 6f 6e 20  ructor function 
5020: 66 6f 72 20 74 68 65 20 70 55 73 65 72 20 76 61  for the pUser va
5030: 6c 75 65 2e 0a 0a 3c 70 3e 5e 54 68 65 20 78 47  lue...<p>^The xG
5040: 65 6f 6d 20 63 61 6c 6c 62 61 63 6b 20 61 6c 77  eom callback alw
5050: 61 79 73 20 64 6f 65 73 20 61 20 64 65 70 74 68  ays does a depth
5060: 2d 66 69 72 73 74 20 73 65 61 72 63 68 20 6f 66  -first search of
5070: 20 74 68 65 20 72 2d 74 72 65 65 2e 0a 0a 3c 74   the r-tree...<t
5080: 63 6c 3e 68 64 5f 66 72 61 67 6d 65 6e 74 20 78  cl>hd_fragment x
5090: 71 75 65 72 79 20 7b 78 51 75 65 72 79 46 75 6e  query {xQueryFun
50a0: 63 20 52 2a 54 72 65 65 20 63 61 6c 6c 62 61 63  c R*Tree callbac
50b0: 6b 7d 20 7b 73 71 6c 69 74 65 33 5f 72 74 72 65  k} {sqlite3_rtre
50c0: 65 5f 71 75 65 72 79 5f 63 61 6c 6c 62 61 63 6b  e_query_callback
50d0: 7d 0a 3c 2f 74 63 6c 3e 0a 3c 68 32 3e 54 68 65  }.</tcl>.<h2>The
50e0: 20 4e 65 77 20 78 51 75 65 72 79 46 75 6e 63 20   New xQueryFunc 
50f0: 43 61 6c 6c 62 61 63 6b 3c 2f 68 32 3e 0a 0a 3c  Callback</h2>..<
5100: 70 3e 54 68 65 20 6e 65 77 65 72 20 78 51 75 65  p>The newer xQue
5110: 72 79 46 75 6e 63 20 63 61 6c 6c 62 61 63 6b 20  ryFunc callback 
5120: 72 65 63 65 69 76 65 73 20 6d 6f 72 65 20 69 6e  receives more in
5130: 66 6f 72 6d 61 74 69 6f 6e 20 66 72 6f 6d 20 74  formation from t
5140: 68 65 20 72 2d 74 72 65 65 0a 71 75 65 72 79 20  he r-tree.query 
5150: 65 6e 67 69 6e 65 20 6f 6e 20 65 61 63 68 20 63  engine on each c
5160: 61 6c 6c 2c 20 61 6e 64 20 69 74 20 73 65 6e 64  all, and it send
5170: 73 20 6d 6f 72 65 20 69 6e 66 6f 72 6d 61 74 69  s more informati
5180: 6f 6e 20 62 61 63 6b 20 74 6f 20 74 68 65 20 71  on back to the q
5190: 75 65 72 79 20 65 6e 67 69 6e 65 0a 62 65 66 6f  uery engine.befo
51a0: 72 65 20 69 74 20 72 65 74 75 72 6e 73 2e 0a 54  re it returns..T
51b0: 6f 20 68 65 6c 70 20 6b 65 65 70 20 74 68 65 20  o help keep the 
51c0: 69 6e 74 65 72 66 61 63 65 20 6d 61 6e 61 67 65  interface manage
51d0: 61 62 6c 65 2c 20 74 68 65 20 78 51 75 65 72 79  able, the xQuery
51e0: 46 75 6e 63 20 63 61 6c 6c 62 61 63 6b 20 73 65  Func callback se
51f0: 6e 64 73 20 61 6e 64 20 72 65 63 65 69 76 65 73  nds and receives
5200: 0a 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 66 72 6f  .information fro
5210: 6d 20 74 68 65 20 71 75 65 72 79 20 65 6e 67 69  m the query engi
5220: 6e 65 20 61 73 20 66 69 65 6c 64 73 20 69 6e 20  ne as fields in 
5230: 74 68 65 0a 73 71 6c 69 74 65 33 5f 72 74 72 65  the.sqlite3_rtre
5240: 65 5f 71 75 65 72 79 5f 69 6e 66 6f 20 73 74 72  e_query_info str
5250: 75 63 74 75 72 65 3a 0a 0a 3c 62 6c 6f 63 6b 71  ucture:..<blockq
5260: 75 6f 74 65 3e 3c 70 72 65 3e 0a 73 74 72 75 63  uote><pre>.struc
5270: 74 20 73 71 6c 69 74 65 33 5f 72 74 72 65 65 5f  t sqlite3_rtree_
5280: 71 75 65 72 79 5f 69 6e 66 6f 20 7b 0a 20 20 76  query_info {.  v
5290: 6f 69 64 20 2a 70 43 6f 6e 74 65 78 74 3b 20 20  oid *pContext;  
52a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
52b0: 20 2f 2a 20 70 43 6f 6e 74 65 78 74 20 66 72 6f   /* pContext fro
52c0: 6d 20 77 68 65 6e 20 66 75 6e 63 74 69 6f 6e 20  m when function 
52d0: 72 65 67 69 73 74 65 72 65 64 20 2a 2f 0a 20 20  registered */.  
52e0: 69 6e 74 20 6e 50 61 72 61 6d 3b 20 20 20 20 20  int nParam;     
52f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5300: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 66    /* Number of f
5310: 75 6e 63 74 69 6f 6e 20 70 61 72 61 6d 65 74 65  unction paramete
5320: 72 73 20 2a 2f 0a 20 20 73 71 6c 69 74 65 33 5f  rs */.  sqlite3_
5330: 72 74 72 65 65 5f 64 62 6c 20 2a 61 50 61 72 61  rtree_dbl *aPara
5340: 6d 3b 20 20 20 20 20 20 20 20 2f 2a 20 76 61 6c  m;        /* val
5350: 75 65 20 6f 66 20 66 75 6e 63 74 69 6f 6e 20 70  ue of function p
5360: 61 72 61 6d 65 74 65 72 73 20 2a 2f 0a 20 20 76  arameters */.  v
5370: 6f 69 64 20 2a 70 55 73 65 72 3b 20 20 20 20 20  oid *pUser;     
5380: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5390: 20 2f 2a 20 63 61 6c 6c 62 61 63 6b 20 63 61 6e   /* callback can
53a0: 20 75 73 65 20 74 68 69 73 2c 20 69 66 20 64 65   use this, if de
53b0: 73 69 72 65 64 20 2a 2f 0a 20 20 76 6f 69 64 20  sired */.  void 
53c0: 28 2a 78 44 65 6c 55 73 65 72 29 28 76 6f 69 64  (*xDelUser)(void
53d0: 2a 29 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20  *);          /* 
53e0: 66 75 6e 63 74 69 6f 6e 20 74 6f 20 66 72 65 65  function to free
53f0: 20 70 55 73 65 72 20 2a 2f 0a 20 20 73 71 6c 69   pUser */.  sqli
5400: 74 65 33 5f 72 74 72 65 65 5f 64 62 6c 20 2a 61  te3_rtree_dbl *a
5410: 43 6f 6f 72 64 3b 20 20 20 20 20 20 20 20 2f 2a  Coord;        /*
5420: 20 43 6f 6f 72 64 69 6e 61 74 65 73 20 6f 66 20   Coordinates of 
5430: 6e 6f 64 65 20 6f 72 20 65 6e 74 72 79 20 74 6f  node or entry to
5440: 20 63 68 65 63 6b 20 2a 2f 0a 20 20 75 6e 73 69   check */.  unsi
5450: 67 6e 65 64 20 69 6e 74 20 2a 61 6e 51 75 65 75  gned int *anQueu
5460: 65 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a  e;            /*
5470: 20 4e 75 6d 62 65 72 20 6f 66 20 70 65 6e 64 69   Number of pendi
5480: 6e 67 20 65 6e 74 72 69 65 73 20 69 6e 20 74 68  ng entries in th
5490: 65 20 71 75 65 75 65 20 2a 2f 0a 20 20 69 6e 74  e queue */.  int
54a0: 20 6e 43 6f 6f 72 64 3b 20 20 20 20 20 20 20 20   nCoord;        
54b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
54c0: 2a 20 4e 75 6d 62 65 72 20 6f 66 20 63 6f 6f 72  * Number of coor
54d0: 64 69 6e 61 74 65 73 20 2a 2f 0a 20 20 69 6e 74  dinates */.  int
54e0: 20 69 4c 65 76 65 6c 3b 20 20 20 20 20 20 20 20   iLevel;        
54f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
5500: 2a 20 4c 65 76 65 6c 20 6f 66 20 63 75 72 72 65  * Level of curre
5510: 6e 74 20 6e 6f 64 65 20 6f 72 20 65 6e 74 72 79  nt node or entry
5520: 20 2a 2f 0a 20 20 69 6e 74 20 6d 78 4c 65 76 65   */.  int mxLeve
5530: 6c 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  l;              
5540: 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 6c          /* The l
5550: 61 72 67 65 73 74 20 69 4c 65 76 65 6c 20 76 61  argest iLevel va
5560: 6c 75 65 20 69 6e 20 74 68 65 20 74 72 65 65 20  lue in the tree 
5570: 2a 2f 0a 20 20 73 71 6c 69 74 65 33 5f 69 6e 74  */.  sqlite3_int
5580: 36 34 20 69 52 6f 77 69 64 3b 20 20 20 20 20 20  64 iRowid;      
5590: 20 20 20 20 20 20 20 2f 2a 20 52 6f 77 69 64 20         /* Rowid 
55a0: 66 6f 72 20 63 75 72 72 65 6e 74 20 65 6e 74 72  for current entr
55b0: 79 20 2a 2f 0a 20 20 73 71 6c 69 74 65 33 5f 72  y */.  sqlite3_r
55c0: 74 72 65 65 5f 64 62 6c 20 72 50 61 72 65 6e 74  tree_dbl rParent
55d0: 53 63 6f 72 65 3b 20 20 20 2f 2a 20 53 63 6f 72  Score;   /* Scor
55e0: 65 20 6f 66 20 70 61 72 65 6e 74 20 6e 6f 64 65  e of parent node
55f0: 20 2a 2f 0a 20 20 69 6e 74 20 65 50 61 72 65 6e   */.  int eParen
5600: 74 57 69 74 68 69 6e 3b 20 20 20 20 20 20 20 20  tWithin;        
5610: 20 20 20 20 20 20 20 20 2f 2a 20 56 69 73 69 62          /* Visib
5620: 69 6c 69 74 79 20 6f 66 20 70 61 72 65 6e 74 20  ility of parent 
5630: 6e 6f 64 65 20 2a 2f 0a 20 20 69 6e 74 20 65 57  node */.  int eW
5640: 69 74 68 69 6e 3b 20 20 20 20 20 20 20 20 20 20  ithin;          
5650: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f              /* O
5660: 55 54 3a 20 56 69 73 69 62 6c 69 74 79 20 2a 2f  UT: Visiblity */
5670: 0a 20 20 73 71 6c 69 74 65 33 5f 72 74 72 65 65  .  sqlite3_rtree
5680: 5f 64 62 6c 20 72 53 63 6f 72 65 3b 20 20 20 20  _dbl rScore;    
5690: 20 20 20 20 20 2f 2a 20 4f 55 54 3a 20 57 72 69       /* OUT: Wri
56a0: 74 65 20 74 68 65 20 73 63 6f 72 65 20 68 65 72  te the score her
56b0: 65 20 2a 2f 0a 20 20 2f 2a 20 54 68 65 20 66 6f  e */.  /* The fo
56c0: 6c 6c 6f 77 69 6e 67 20 66 69 65 6c 64 73 20 61  llowing fields a
56d0: 72 65 20 6f 6e 6c 79 20 61 76 61 69 6c 61 62 6c  re only availabl
56e0: 65 20 69 6e 20 33 2e 38 2e 31 31 20 61 6e 64 20  e in 3.8.11 and 
56f0: 6c 61 74 65 72 20 2a 2f 0a 20 20 73 71 6c 69 74  later */.  sqlit
5700: 65 33 5f 76 61 6c 75 65 20 2a 2a 61 70 53 71 6c  e3_value **apSql
5710: 50 61 72 61 6d 3b 20 20 20 20 20 20 20 2f 2a 20  Param;       /* 
5720: 4f 72 69 67 69 6e 61 6c 20 53 51 4c 20 76 61 6c  Original SQL val
5730: 75 65 73 20 6f 66 20 70 61 72 61 6d 65 74 65 72  ues of parameter
5740: 73 20 2a 2f 0a 7d 3b 0a 3c 2f 70 72 65 3e 3c 2f  s */.};.</pre></
5750: 62 6c 6f 63 6b 71 75 6f 74 65 3e 0a 0a 3c 70 3e  blockquote>..<p>
5760: 54 68 65 20 66 69 72 73 74 20 66 69 76 65 20 66  The first five f
5770: 69 65 6c 64 73 20 6f 66 20 74 68 65 20 73 71 6c  ields of the sql
5780: 69 74 65 33 5f 72 74 72 65 65 5f 71 75 65 72 79  ite3_rtree_query
5790: 5f 69 6e 66 6f 20 73 74 72 75 63 74 75 72 65 20  _info structure 
57a0: 61 72 65 20 69 64 65 6e 74 69 63 61 6c 0a 74 6f  are identical.to
57b0: 20 74 68 65 20 73 71 6c 69 74 65 33 5f 72 74 72   the sqlite3_rtr
57c0: 65 65 5f 67 65 6f 6d 65 74 72 79 20 73 74 72 75  ee_geometry stru
57d0: 63 74 75 72 65 2c 20 61 6e 64 20 68 61 76 65 20  cture, and have 
57e0: 65 78 61 63 74 6c 79 20 74 68 65 20 73 61 6d 65  exactly the same
57f0: 20 6d 65 61 6e 69 6e 67 2e 0a 54 68 65 20 73 71   meaning..The sq
5800: 6c 69 74 65 33 5f 72 74 72 65 65 5f 71 75 65 72  lite3_rtree_quer
5810: 79 5f 69 6e 66 6f 20 73 74 72 75 63 74 75 72 65  y_info structure
5820: 20 61 6c 73 6f 20 63 6f 6e 74 61 69 6e 73 20 6e   also contains n
5830: 43 6f 6f 72 64 20 61 6e 64 20 61 43 6f 6f 72 64  Coord and aCoord
5840: 20 66 69 65 6c 64 73 20 0a 77 68 69 63 68 20 68   fields .which h
5850: 61 76 65 20 74 68 65 20 73 61 6d 65 20 6d 65 61  ave the same mea
5860: 6e 69 6e 67 20 61 73 20 74 68 65 20 70 61 72 61  ning as the para
5870: 6d 65 74 65 72 20 6f 66 20 74 68 65 20 73 61 6d  meter of the sam
5880: 65 20 6e 61 6d 65 20 69 6e 20 74 68 65 20 78 47  e name in the xG
5890: 65 6f 6d 20 63 61 6c 6c 62 61 63 6b 2e 0a 0a 3c  eom callback...<
58a0: 70 3e 54 68 65 20 78 51 75 65 72 79 46 75 6e 63  p>The xQueryFunc
58b0: 20 6d 75 73 74 20 73 65 74 20 74 68 65 20 65 57   must set the eW
58c0: 69 74 68 69 6e 20 66 69 65 6c 64 20 6f 66 20 73  ithin field of s
58d0: 71 6c 69 74 65 33 5f 72 74 72 65 65 5f 71 75 65  qlite3_rtree_que
58e0: 72 79 5f 69 6e 66 6f 20 74 6f 0a 6f 6e 65 20 6f  ry_info to.one o
58f0: 66 20 74 68 65 20 76 61 6c 75 65 73 20 4e 4f 54  f the values NOT
5900: 5f 57 49 54 48 49 4e 2c 20 50 41 52 54 4c 59 5f  _WITHIN, PARTLY_
5910: 57 49 54 48 49 4e 2c 20 6f 72 20 46 55 4c 4c 59  WITHIN, or FULLY
5920: 5f 57 49 54 48 49 4e 20 64 65 70 65 6e 64 69 6e  _WITHIN dependin
5930: 67 20 6f 6e 20 77 68 65 74 68 65 72 0a 6f 72 20  g on whether.or 
5940: 6e 6f 74 20 74 68 65 20 62 6f 75 6e 64 69 6e 67  not the bounding
5950: 20 62 6f 78 20 64 65 66 69 6e 65 64 20 62 79 20   box defined by 
5960: 61 43 6f 6f 72 64 5b 5d 20 69 73 20 63 6f 6d 70  aCoord[] is comp
5970: 6c 65 74 65 6c 79 20 6f 75 74 73 69 64 65 20 74  letely outside t
5980: 68 65 20 72 65 67 69 6f 6e 2c 0a 6f 76 65 72 6c  he region,.overl
5990: 61 70 73 20 74 68 65 20 72 65 67 69 6f 6e 2c 20  aps the region, 
59a0: 6f 72 20 69 73 20 63 6f 6d 70 6c 65 74 65 6c 79  or is completely
59b0: 20 69 6e 73 69 64 65 20 74 68 65 20 72 65 67 69   inside the regi
59c0: 6f 6e 2c 20 72 65 73 70 65 63 74 69 76 65 6c 79  on, respectively
59d0: 2e 20 20 49 6e 0a 61 64 64 69 74 69 6f 6e 2c 20  .  In.addition, 
59e0: 74 68 65 20 78 51 75 65 72 79 46 75 6e 63 20 6d  the xQueryFunc m
59f0: 75 73 74 20 73 65 74 20 74 68 65 20 72 53 63 6f  ust set the rSco
5a00: 72 65 20 66 69 65 6c 64 20 74 6f 20 61 20 6e 6f  re field to a no
5a10: 6e 2d 6e 65 67 61 74 69 76 65 20 76 61 6c 75 65  n-negative value
5a20: 20 74 68 61 74 0a 69 6e 64 69 63 61 74 65 73 20   that.indicates 
5a30: 74 68 65 20 6f 72 64 65 72 20 69 6e 20 77 68 69  the order in whi
5a40: 63 68 20 73 75 62 74 72 65 65 73 20 61 6e 64 20  ch subtrees and 
5a50: 65 6e 74 72 69 65 73 20 6f 66 20 74 68 65 20 71  entries of the q
5a60: 75 65 72 79 20 73 68 6f 75 6c 64 20 62 65 20 61  uery should be a
5a70: 6e 61 6c 79 7a 65 64 0a 61 6e 64 20 72 65 74 75  nalyzed.and retu
5a80: 72 6e 65 64 2e 20 20 5e 53 6d 61 6c 6c 65 72 20  rned.  ^Smaller 
5a90: 73 63 6f 72 65 73 20 61 72 65 20 70 72 6f 63 65  scores are proce
5aa0: 73 73 65 64 20 66 69 72 73 74 2e 0a 0a 3c 70 3e  ssed first...<p>
5ab0: 41 73 20 69 74 73 20 6e 61 6d 65 20 69 6d 70 6c  As its name impl
5ac0: 69 65 73 2c 20 61 6e 20 52 2a 54 72 65 65 20 69  ies, an R*Tree i
5ad0: 73 20 6f 72 67 61 6e 69 7a 65 64 20 61 73 20 61  s organized as a
5ae0: 20 74 72 65 65 2e 20 20 45 61 63 68 20 6e 6f 64   tree.  Each nod
5af0: 65 20 6f 66 20 74 68 65 0a 74 72 65 65 20 69 73  e of the.tree is
5b00: 20 61 20 62 6f 75 6e 64 69 6e 67 20 62 6f 78 2e   a bounding box.
5b10: 20 20 54 68 65 20 72 6f 6f 74 20 6f 66 20 74 68    The root of th
5b20: 65 20 74 72 65 65 20 69 73 20 61 20 62 6f 75 6e  e tree is a boun
5b30: 64 69 6e 67 20 62 6f 78 20 74 68 61 74 20 65 6e  ding box that en
5b40: 63 61 70 73 75 6c 61 74 65 73 0a 61 6c 6c 20 65  capsulates.all e
5b50: 6c 65 6d 65 6e 74 73 20 6f 66 20 74 68 65 20 74  lements of the t
5b60: 72 65 65 2e 20 20 42 65 6e 65 61 74 68 20 74 68  ree.  Beneath th
5b70: 65 20 72 6f 6f 74 20 61 72 65 20 61 20 6e 75 6d  e root are a num
5b80: 62 65 72 20 6f 66 20 73 75 62 74 72 65 65 73 20  ber of subtrees 
5b90: 28 74 79 70 69 63 61 6c 6c 79 0a 32 30 20 6f 72  (typically.20 or
5ba0: 20 6d 6f 72 65 29 20 65 61 63 68 20 77 69 74 68   more) each with
5bb0: 20 74 68 65 69 72 20 6f 77 6e 20 73 6d 61 6c 6c   their own small
5bc0: 65 72 20 62 6f 75 6e 64 69 6e 67 20 62 6f 78 65  er bounding boxe
5bd0: 73 20 61 6e 64 20 65 61 63 68 20 63 6f 6e 74 61  s and each conta
5be0: 69 6e 69 6e 67 20 73 6f 6d 65 0a 73 75 62 73 65  ining some.subse
5bf0: 74 20 6f 66 20 74 68 65 20 52 2a 54 72 65 65 20  t of the R*Tree 
5c00: 65 6e 74 72 69 65 73 2e 20 20 54 68 65 20 73 75  entries.  The su
5c10: 62 74 72 65 65 73 20 6d 61 79 20 68 61 76 65 20  btrees may have 
5c20: 73 75 62 2d 73 75 62 74 72 65 65 73 2c 20 61 6e  sub-subtrees, an
5c30: 64 20 73 6f 20 66 6f 72 74 68 0a 75 6e 74 69 6c  d so forth.until
5c40: 20 66 69 6e 61 6c 6c 79 20 6f 6e 65 20 72 65 61   finally one rea
5c50: 63 68 65 73 20 74 68 65 20 6c 65 61 76 65 73 20  ches the leaves 
5c60: 6f 66 20 74 68 65 20 74 72 65 65 20 77 68 69 63  of the tree whic
5c70: 68 20 61 72 65 20 74 68 65 20 61 63 74 75 61 6c  h are the actual
5c80: 20 52 2a 54 72 65 65 0a 65 6e 74 72 69 65 73 2e   R*Tree.entries.
5c90: 0a 0a 3c 70 3e 41 6e 20 52 2a 54 72 65 65 20 71  ..<p>An R*Tree q
5ca0: 75 65 72 79 20 69 73 20 69 6e 69 74 69 61 6c 69  uery is initiali
5cb0: 7a 65 64 20 62 79 20 6d 61 6b 69 6e 67 20 74 68  zed by making th
5cc0: 65 20 72 6f 6f 74 20 6e 6f 64 65 20 74 68 65 20  e root node the 
5cd0: 6f 6e 6c 79 20 65 6e 74 72 79 0a 69 6e 20 61 20  only entry.in a 
5ce0: 70 72 69 6f 72 69 74 79 20 71 75 65 75 65 20 73  priority queue s
5cf0: 6f 72 74 65 64 20 62 79 20 72 53 63 6f 72 65 2e  orted by rScore.
5d00: 0a 54 68 65 20 71 75 65 72 79 20 70 72 6f 63 65  .The query proce
5d10: 65 64 73 20 62 79 20 65 78 74 72 61 63 74 69 6e  eds by extractin
5d20: 67 20 74 68 65 20 65 6e 74 72 79 20 66 72 6f 6d  g the entry from
5d30: 20 74 68 65 20 70 72 69 6f 72 69 74 79 20 71 75   the priority qu
5d40: 65 75 65 20 74 68 61 74 20 68 61 73 0a 74 68 65  eue that has.the
5d50: 20 6c 6f 77 65 73 74 20 73 63 6f 72 65 2e 20 20   lowest score.  
5d60: 49 66 20 74 68 61 74 20 65 6e 74 72 79 20 69 73  If that entry is
5d70: 20 61 20 6c 65 61 66 20 28 6d 65 61 6e 69 6e 67   a leaf (meaning
5d80: 20 74 68 61 74 20 69 74 20 69 73 20 61 6e 20 61   that it is an a
5d90: 63 74 75 61 6c 0a 52 2a 54 72 65 65 20 65 6e 74  ctual.R*Tree ent
5da0: 72 79 20 61 6e 64 20 6e 6f 74 20 61 20 73 75 62  ry and not a sub
5db0: 74 72 65 65 29 20 74 68 65 6e 20 74 68 61 74 20  tree) then that 
5dc0: 65 6e 74 72 79 0a 69 73 20 72 65 74 75 72 6e 65  entry.is returne
5dd0: 64 20 61 73 20 6f 6e 65 20 72 6f 77 20 6f 66 20  d as one row of 
5de0: 74 68 65 20 71 75 65 72 79 20 72 65 73 75 6c 74  the query result
5df0: 2e 20 20 0a 49 66 20 74 68 65 20 65 78 74 72 61  .  .If the extra
5e00: 63 74 65 64 20 70 72 69 6f 72 69 74 79 20 71 75  cted priority qu
5e10: 65 75 65 20 65 6e 74 72 79 20 69 73 20 61 20 6e  eue entry is a n
5e20: 6f 64 65 20 28 61 20 73 75 62 74 72 65 65 29 2c  ode (a subtree),
5e30: 0a 74 68 65 6e 20 73 75 62 2d 73 75 62 74 72 65  .then sub-subtre
5e40: 65 73 20 6f 72 20 6c 65 61 76 65 73 20 63 6f 6e  es or leaves con
5e50: 74 61 69 6e 65 64 20 77 69 74 68 69 6e 20 74 68  tained within th
5e60: 61 74 20 65 6e 74 72 79 20 61 72 65 20 70 61 73  at entry are pas
5e70: 73 65 64 20 74 6f 20 74 68 65 0a 78 51 75 65 72  sed to the.xQuer
5e80: 79 46 75 6e 63 20 63 61 6c 6c 62 61 63 6b 2c 20  yFunc callback, 
5e90: 6f 6e 65 20 62 79 20 6f 6e 65 2e 20 20 54 68 6f  one by one.  Tho
5ea0: 73 65 20 73 75 62 65 6c 65 6d 65 6e 74 73 20 66  se subelements f
5eb0: 6f 72 20 77 68 69 63 68 20 74 68 65 20 78 51 75  or which the xQu
5ec0: 65 72 79 46 75 6e 63 0a 63 61 6c 6c 62 61 63 6b  eryFunc.callback
5ed0: 20 73 65 74 73 20 65 57 69 74 68 69 6e 20 74 6f   sets eWithin to
5ee0: 20 50 41 52 54 4c 59 5f 57 49 54 48 49 4e 20 6f   PARTLY_WITHIN o
5ef0: 72 20 46 55 4c 4c 59 5f 57 49 54 48 49 4e 20 61  r FULLY_WITHIN a
5f00: 72 65 20 61 64 64 65 64 20 74 6f 20 74 68 65 20  re added to the 
5f10: 70 72 69 6f 72 69 74 79 0a 71 75 65 75 65 20 75  priority.queue u
5f20: 73 69 6e 67 20 74 68 65 20 73 63 6f 72 65 20 73  sing the score s
5f30: 75 70 70 6c 69 65 64 20 62 79 20 74 68 65 20 63  upplied by the c
5f40: 61 6c 6c 62 61 63 6b 2e 20 20 53 75 62 65 6c 65  allback.  Subele
5f50: 6d 65 6e 74 73 20 74 68 61 74 20 72 65 74 75 72  ments that retur
5f60: 6e 0a 4e 4f 54 5f 57 49 54 48 49 4e 20 61 72 65  n.NOT_WITHIN are
5f70: 20 64 69 73 63 61 72 64 65 64 2e 20 20 54 68 65   discarded.  The
5f80: 20 71 75 65 72 79 20 72 75 6e 73 20 75 6e 74 69   query runs unti
5f90: 6c 20 74 68 65 20 70 72 69 6f 72 69 74 79 20 71  l the priority q
5fa0: 75 65 75 65 20 69 73 20 65 6d 70 74 79 2e 0a 0a  ueue is empty...
5fb0: 3c 70 3e 45 76 65 72 79 20 6c 65 61 66 20 65 6e  <p>Every leaf en
5fc0: 74 72 79 20 61 6e 64 20 6e 6f 64 65 20 28 73 75  try and node (su
5fd0: 62 74 72 65 65 29 20 77 69 74 68 69 6e 20 74 68  btree) within th
5fe0: 65 20 52 2a 54 72 65 65 20 68 61 73 20 61 6e 20  e R*Tree has an 
5ff0: 69 6e 74 65 67 65 72 20 22 6c 65 76 65 6c 22 2e  integer "level".
6000: 0a 5e 54 68 65 20 6c 65 61 76 65 73 20 68 61 76  .^The leaves hav
6010: 65 20 61 20 6c 65 76 65 6c 20 6f 66 20 30 2e 20  e a level of 0. 
6020: 20 54 68 65 20 66 69 72 73 74 20 63 6f 6e 74 61   The first conta
6030: 69 6e 69 6e 67 20 73 75 62 74 72 65 65 20 6f 66  ining subtree of
6040: 20 74 68 65 20 6c 65 61 76 65 73 20 68 61 73 0a   the leaves has.
6050: 61 20 6c 65 76 65 6c 20 6f 66 20 31 2e 20 20 54  a level of 1.  T
6060: 68 65 20 72 6f 6f 74 20 6f 66 20 74 68 65 20 52  he root of the R
6070: 2a 54 72 65 65 20 68 61 73 20 74 68 65 20 6c 61  *Tree has the la
6080: 72 67 65 73 74 20 6c 65 76 65 6c 20 76 61 6c 75  rgest level valu
6090: 65 2e 20 20 5e 54 68 65 0a 6d 78 4c 65 76 65 6c  e.  ^The.mxLevel
60a0: 20 65 6e 74 72 79 20 69 6e 20 74 68 65 20 73 71   entry in the sq
60b0: 6c 69 74 65 33 5f 72 74 72 65 65 5f 71 75 65 72  lite3_rtree_quer
60c0: 79 5f 69 6e 66 6f 20 73 74 72 75 63 74 75 72 65  y_info structure
60d0: 20 69 73 20 74 68 65 20 6c 65 76 65 6c 20 76 61   is the level va
60e0: 6c 75 65 20 66 6f 72 0a 74 68 65 20 72 6f 6f 74  lue for.the root
60f0: 20 6f 66 20 74 68 65 20 52 2a 54 72 65 65 2e 20   of the R*Tree. 
6100: 20 54 68 65 20 69 4c 65 76 65 6c 20 65 6e 74 72   The iLevel entr
6110: 79 20 69 6e 20 73 71 6c 69 74 65 33 5f 72 74 72  y in sqlite3_rtr
6120: 65 65 5f 71 75 65 72 79 5f 69 6e 66 6f 20 67 69  ee_query_info gi
6130: 76 65 73 20 74 68 65 0a 6c 65 76 65 6c 20 66 6f  ves the.level fo
6140: 72 20 74 68 65 20 6f 62 6a 65 63 74 20 62 65 69  r the object bei
6150: 6e 67 20 69 6e 74 65 72 72 6f 67 61 74 65 64 2e  ng interrogated.
6160: 0a 0a 3c 70 3e 5e 28 4d 6f 73 74 20 52 2a 54 72  ..<p>^(Most R*Tr
6170: 65 65 20 71 75 65 72 69 65 73 20 75 73 65 20 61  ee queries use a
6180: 20 64 65 70 74 68 2d 66 69 72 73 74 20 73 65 61   depth-first sea
6190: 72 63 68 2e 20 20 54 68 69 73 20 69 73 20 61 63  rch.  This is ac
61a0: 63 6f 6d 70 6c 69 73 68 65 64 20 62 79 20 73 65  complished by se
61b0: 74 74 69 6e 67 0a 74 68 65 20 72 53 63 6f 72 65  tting.the rScore
61c0: 20 65 71 75 61 6c 20 74 6f 20 69 4c 65 76 65 6c   equal to iLevel
61d0: 2e 29 5e 20 20 41 20 64 65 70 74 68 2d 66 69 72  .)^  A depth-fir
61e0: 73 74 20 73 65 61 72 63 68 20 69 73 20 75 73 75  st search is usu
61f0: 61 6c 6c 79 20 70 72 65 66 65 72 72 65 64 20 73  ally preferred s
6200: 69 6e 63 65 20 69 74 0a 6d 69 6e 69 6d 69 7a 65  ince it.minimize
6210: 73 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20  s the number of 
6220: 65 6c 65 6d 65 6e 74 73 20 69 6e 20 74 68 65 20  elements in the 
6230: 70 72 69 6f 72 69 74 79 20 71 75 65 75 65 2c 20  priority queue, 
6240: 77 68 69 63 68 20 72 65 64 75 63 65 73 20 6d 65  which reduces me
6250: 6d 6f 72 79 0a 72 65 71 75 69 72 65 6d 65 6e 74  mory.requirement
6260: 73 20 61 6e 64 20 73 70 65 65 64 73 20 70 72 6f  s and speeds pro
6270: 63 65 73 73 69 6e 67 2e 20 20 5e 48 6f 77 65 76  cessing.  ^Howev
6280: 65 72 2c 20 73 6f 6d 65 20 61 70 70 6c 69 63 61  er, some applica
6290: 74 69 6f 6e 20 6d 61 79 20 70 72 65 66 65 72 20  tion may prefer 
62a0: 61 0a 62 72 65 61 64 74 68 2d 66 69 72 73 74 20  a.breadth-first 
62b0: 73 65 61 72 63 68 2c 20 77 68 69 63 68 20 63 61  search, which ca
62c0: 6e 20 62 65 20 61 63 63 6f 6d 70 6c 69 73 68 65  n be accomplishe
62d0: 64 20 62 79 20 73 65 74 74 69 6e 67 20 72 53 63  d by setting rSc
62e0: 6f 72 65 20 74 6f 20 6d 78 4c 65 76 65 6c 2d 69  ore to mxLevel-i
62f0: 4c 65 76 65 6c 2e 0a 42 79 20 63 72 65 61 74 69  Level..By creati
6300: 6e 67 20 6d 6f 72 65 20 63 6f 6d 70 6c 65 78 20  ng more complex 
6310: 66 6f 72 6d 75 6c 61 73 20 66 6f 72 20 72 53 63  formulas for rSc
6320: 6f 72 65 2c 20 61 70 70 6c 69 63 61 74 69 6f 6e  ore, application
6330: 73 20 63 61 6e 20 65 78 65 72 63 69 73 65 0a 64  s can exercise.d
6340: 65 74 61 69 6c 65 64 20 63 6f 6e 74 72 6f 6c 20  etailed control 
6350: 6f 76 65 72 20 74 68 65 20 6f 72 64 65 72 20 69  over the order i
6360: 6e 20 77 68 69 63 68 20 73 75 62 74 72 65 65 20  n which subtree 
6370: 61 72 65 20 73 65 61 72 63 68 65 64 20 61 6e 64  are searched and
6380: 20 6c 65 61 66 0a 52 2a 54 72 65 65 20 65 6e 74   leaf.R*Tree ent
6390: 72 69 65 73 20 61 72 65 20 72 65 74 75 72 6e 65  ries are returne
63a0: 64 2e 20 20 46 6f 72 20 65 78 61 6d 70 6c 65 2c  d.  For example,
63b0: 20 69 6e 20 61 6e 20 61 70 70 6c 69 63 61 74 69   in an applicati
63c0: 6f 6e 20 77 69 74 68 20 6d 61 6e 79 0a 6d 69 6c  on with many.mil
63d0: 6c 69 6f 6e 73 20 6f 66 20 52 2a 54 72 65 65 20  lions of R*Tree 
63e0: 65 6e 74 72 69 65 73 2c 20 74 68 65 20 72 53 63  entries, the rSc
63f0: 6f 72 65 20 6d 69 67 68 74 20 62 65 20 61 72 72  ore might be arr
6400: 61 6e 67 65 64 20 73 6f 20 74 68 61 74 20 74 68  anged so that th
6410: 65 0a 6c 61 72 67 65 73 74 20 6f 72 20 6d 6f 73  e.largest or mos
6420: 74 20 73 69 67 6e 69 66 69 63 61 6e 74 20 65 6e  t significant en
6430: 74 72 69 65 73 20 61 72 65 20 72 65 74 75 72 6e  tries are return
6440: 65 64 20 66 69 72 73 74 2c 20 61 6c 6c 6f 77 69  ed first, allowi
6450: 6e 67 20 74 68 65 0a 61 70 70 6c 69 63 61 74 69  ng the.applicati
6460: 6f 6e 20 74 6f 20 64 69 73 70 6c 61 79 20 74 68  on to display th
6470: 65 20 6d 6f 73 74 20 69 6d 70 6f 72 74 61 6e 74  e most important
6480: 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 71 75 69   information qui
6490: 63 6b 6c 79 2c 20 61 6e 64 0a 66 69 6c 6c 69 6e  ckly, and.fillin
64a0: 67 20 69 6e 20 73 6d 61 6c 6c 65 72 20 61 6e 64  g in smaller and
64b0: 20 6c 65 73 73 20 69 6d 70 6f 72 74 61 6e 74 20   less important 
64c0: 64 65 74 61 69 6c 73 20 61 73 20 74 68 65 79 20  details as they 
64d0: 62 65 63 6f 6d 65 20 61 76 61 69 6c 61 62 6c 65  become available
64e0: 2e 0a 0a 3c 70 3e 4f 74 68 65 72 20 69 6e 66 6f  ...<p>Other info
64f0: 72 6d 61 74 69 6f 6e 20 66 69 65 6c 64 73 20 6f  rmation fields o
6500: 66 20 74 68 65 20 73 71 6c 69 74 65 33 5f 72 74  f the sqlite3_rt
6510: 72 65 65 5f 71 75 65 72 79 5f 69 6e 66 6f 20 73  ree_query_info s
6520: 74 72 75 63 74 75 72 65 20 61 72 65 0a 61 76 61  tructure are.ava
6530: 69 6c 61 62 6c 65 20 66 6f 72 20 75 73 65 20 62  ilable for use b
6540: 79 20 74 68 65 20 78 51 75 65 72 79 46 75 6e 63  y the xQueryFunc
6550: 20 63 61 6c 6c 62 61 63 6b 2c 20 69 66 20 64 65   callback, if de
6560: 73 69 72 65 64 2e 20 20 5e 28 54 68 65 20 69 52  sired.  ^(The iR
6570: 6f 77 69 64 20 66 69 65 6c 64 0a 69 73 20 74 68  owid field.is th
6580: 65 20 72 6f 77 69 64 20 28 74 68 65 20 66 69 72  e rowid (the fir
6590: 73 74 20 6f 66 20 74 68 65 20 33 20 74 6f 20 31  st of the 3 to 1
65a0: 31 20 63 6f 6c 75 6d 6e 73 20 69 6e 20 74 68 65  1 columns in the
65b0: 20 52 2a 54 72 65 65 29 20 66 6f 72 20 74 68 65   R*Tree) for the
65c0: 20 65 6c 65 6d 65 6e 74 0a 62 65 69 6e 67 20 63   element.being c
65d0: 6f 6e 73 69 64 65 72 65 64 2e 20 20 69 52 6f 77  onsidered.  iRow
65e0: 69 64 20 69 73 20 6f 6e 6c 79 20 76 61 6c 69 64  id is only valid
65f0: 20 66 6f 72 20 6c 65 61 76 65 73 2e 29 5e 20 20   for leaves.)^  
6600: 5e 54 68 65 20 65 50 61 72 65 6e 74 57 69 74 68  ^The eParentWith
6610: 69 6e 20 61 6e 64 0a 72 50 61 72 65 6e 74 53 63  in and.rParentSc
6620: 6f 72 65 20 76 61 6c 75 65 73 20 61 72 65 20 63  ore values are c
6630: 6f 70 69 65 73 20 6f 66 20 74 68 65 20 65 57 69  opies of the eWi
6640: 74 68 69 6e 20 61 6e 64 20 72 53 63 6f 72 65 20  thin and rScore 
6650: 76 61 6c 75 65 73 20 66 72 6f 6d 20 74 68 65 0a  values from the.
6660: 63 6f 6e 74 61 69 6e 69 6e 67 20 73 75 62 74 72  containing subtr
6670: 65 65 20 6f 66 20 74 68 65 20 63 75 72 72 65 6e  ee of the curren
6680: 74 20 72 6f 77 2e 20 20 5e 54 68 65 20 61 6e 51  t row.  ^The anQ
6690: 75 65 75 65 20 66 69 65 6c 64 20 69 73 20 61 6e  ueue field is an
66a0: 20 61 72 72 61 79 0a 6f 66 20 6d 78 4c 65 76 65   array.of mxLeve
66b0: 6c 2b 31 20 75 6e 73 69 67 6e 65 64 20 69 6e 74  l+1 unsigned int
66c0: 65 67 65 72 73 20 74 68 61 74 20 74 65 6c 6c 20  egers that tell 
66d0: 74 68 65 20 63 75 72 72 65 6e 74 20 6e 75 6d 62  the current numb
66e0: 65 72 20 6f 66 20 65 6c 65 6d 65 6e 74 73 20 69  er of elements i
66f0: 6e 0a 74 68 65 20 70 72 69 6f 72 69 74 79 20 71  n.the priority q
6700: 75 65 75 65 20 61 74 20 65 61 63 68 20 6c 65 76  ueue at each lev
6710: 65 6c 2e 0a 0a 3c 68 32 3e 41 64 64 69 74 69 6f  el...<h2>Additio
6720: 6e 61 6c 20 43 6f 6e 73 69 64 65 72 61 74 69 6f  nal Consideratio
6730: 6e 73 20 66 6f 72 20 43 75 73 74 6f 6d 20 51 75  ns for Custom Qu
6740: 65 72 69 65 73 3c 2f 68 32 3e 0a 0a 3c 70 3e 0a  eries</h2>..<p>.
6750: 5e 54 68 65 20 4d 41 54 43 48 20 6f 70 65 72 61  ^The MATCH opera
6760: 74 6f 72 20 6f 66 20 61 20 63 75 73 74 6f 6d 20  tor of a custom 
6770: 52 2a 54 72 65 65 20 71 75 65 72 79 20 66 75 6e  R*Tree query fun
6780: 63 74 69 6f 6e 20 6d 75 73 74 20 62 65 20 61 20  ction must be a 
6790: 74 6f 70 2d 6c 65 76 65 6c 0a 41 4e 44 2d 63 6f  top-level.AND-co
67a0: 6e 6e 65 63 74 65 64 20 74 65 72 6d 20 6f 66 20  nnected term of 
67b0: 74 68 65 20 57 48 45 52 45 20 63 6c 61 75 73 65  the WHERE clause
67c0: 2c 20 6f 72 20 65 6c 73 65 20 69 74 20 77 69 6c  , or else it wil
67d0: 6c 20 6e 6f 74 20 62 65 20 75 73 61 62 6c 65 0a  l not be usable.
67e0: 62 79 20 74 68 65 20 52 2a 54 72 65 65 20 71 75  by the R*Tree qu
67f0: 65 72 79 20 6f 70 74 69 6d 69 7a 65 72 20 61 6e  ery optimizer an
6800: 64 20 74 68 65 20 71 75 65 72 79 20 77 69 6c 6c  d the query will
6810: 20 6e 6f 74 20 62 65 20 72 75 6e 6e 61 62 6c 65   not be runnable
6820: 2e 0a 5e 49 66 20 74 68 65 20 4d 41 54 43 48 20  ..^If the MATCH 
6830: 6f 70 65 72 61 74 6f 72 20 69 73 20 63 6f 6e 6e  operator is conn
6840: 65 63 74 65 64 20 74 6f 20 6f 74 68 65 72 20 74  ected to other t
6850: 65 72 6d 73 20 6f 66 20 74 68 65 20 57 48 45 52  erms of the WHER
6860: 45 20 63 6c 61 75 73 65 20 0a 76 69 61 20 61 6e  E clause .via an
6870: 20 4f 52 20 6f 70 65 72 61 74 6f 72 2c 20 66 6f   OR operator, fo
6880: 72 20 65 78 61 6d 70 6c 65 2c 20 74 68 65 20 71  r example, the q
6890: 75 65 72 79 20 77 69 6c 6c 20 66 61 69 6c 20 77  uery will fail w
68a0: 69 74 68 20 61 6e 20 65 72 72 6f 72 2e 0a 0a 3c  ith an error...<
68b0: 70 3e 0a 5e 54 77 6f 20 6f 72 20 6d 6f 72 65 20  p>.^Two or more 
68c0: 4d 41 54 43 48 20 6f 70 65 72 61 74 6f 72 73 20  MATCH operators 
68d0: 61 72 65 20 61 6c 6c 6f 77 65 64 20 69 6e 20 74  are allowed in t
68e0: 68 65 20 73 61 6d 65 20 57 48 45 52 45 20 63 6c  he same WHERE cl
68f0: 61 75 73 65 2c 20 61 73 20 6c 6f 6e 67 0a 61 73  ause, as long.as
6900: 20 74 68 65 79 20 61 72 65 20 63 6f 6e 6e 65 63   they are connec
6910: 74 65 64 20 62 79 20 41 4e 44 20 6f 70 65 72 61  ted by AND opera
6920: 74 6f 72 73 2e 20 20 48 6f 77 65 76 65 72 2c 0a  tors.  However,.
6930: 74 68 65 20 52 2a 54 72 65 65 20 71 75 65 72 79  the R*Tree query
6940: 20 65 6e 67 69 6e 65 20 6f 6e 6c 79 20 63 6f 6e   engine only con
6950: 74 61 69 6e 73 20 61 20 73 69 6e 67 6c 65 20 70  tains a single p
6960: 72 69 6f 72 69 74 79 20 71 75 65 75 65 2e 20 20  riority queue.  
6970: 5e 54 68 65 20 70 72 69 6f 72 69 74 79 0a 61 73  ^The priority.as
6980: 73 69 67 6e 65 64 20 74 6f 20 65 61 63 68 20 6e  signed to each n
6990: 6f 64 65 20 69 6e 20 74 68 65 20 73 65 61 72 63  ode in the searc
69a0: 68 20 69 73 20 74 68 65 20 6c 6f 77 65 73 74 20  h is the lowest 
69b0: 70 72 69 6f 72 69 74 79 20 72 65 74 75 72 6e 65  priority returne
69c0: 64 20 62 79 20 61 6e 79 0a 6f 66 20 74 68 65 20  d by any.of the 
69d0: 4d 41 54 43 48 20 6f 70 65 72 61 74 6f 72 73 2e  MATCH operators.
69e0: 0a 0a 3c 68 31 3e 49 6d 70 6c 65 6d 65 6e 74 61  ..<h1>Implementa
69f0: 74 69 6f 6e 20 44 65 74 61 69 6c 73 3c 2f 68 31  tion Details</h1
6a00: 3e 0a 0a 3c 70 3e 0a 54 68 65 20 66 6f 6c 6c 6f  >..<p>.The follo
6a10: 77 69 6e 67 20 73 65 63 74 69 6f 6e 73 20 64 65  wing sections de
6a20: 73 63 72 69 62 65 20 73 6f 6d 65 20 6c 6f 77 2d  scribe some low-
6a30: 6c 65 76 65 6c 20 64 65 74 61 69 6c 73 20 6f 66  level details of
6a40: 20 74 68 65 20 52 2a 54 72 65 65 20 69 6d 70 6c   the R*Tree impl
6a50: 65 6d 65 6e 74 61 74 69 6f 6e 2c 0a 74 68 61 74  ementation,.that
6a60: 20 6d 69 67 68 74 20 62 65 20 75 73 65 66 75 6c   might be useful
6a70: 20 66 6f 72 20 74 72 6f 75 62 6c 65 2d 73 68 6f   for trouble-sho
6a80: 6f 74 69 6e 67 20 6f 72 20 70 65 72 66 6f 72 6d  oting or perform
6a90: 61 6e 63 65 20 61 6e 61 6c 79 73 69 73 2e 0a 0a  ance analysis...
6aa0: 3c 68 32 3e 53 68 61 64 6f 77 20 54 61 62 6c 65  <h2>Shadow Table
6ab0: 73 3c 2f 68 32 3e 0a 0a 3c 70 3e 54 68 65 20 63  s</h2>..<p>The c
6ac0: 6f 6e 74 65 6e 74 20 6f 66 20 61 6e 20 52 2a 54  ontent of an R*T
6ad0: 72 65 65 20 69 6e 64 65 78 20 69 73 20 61 63 74  ree index is act
6ae0: 75 61 6c 6c 79 20 73 74 6f 72 65 64 20 69 6e 20  ually stored in 
6af0: 74 68 72 65 65 20 6f 72 64 69 6e 61 72 79 0a 53  three ordinary.S
6b00: 51 4c 69 74 65 20 74 61 62 6c 65 73 20 77 69 74  QLite tables wit
6b10: 68 20 6e 61 6d 65 73 20 64 65 72 69 76 65 64 20  h names derived 
6b20: 66 72 6f 6d 20 74 68 65 20 6e 61 6d 65 20 6f 66  from the name of
6b30: 20 74 68 65 20 52 2a 54 72 65 65 2e 20 20 54 68   the R*Tree.  Th
6b40: 65 73 65 0a 74 68 72 65 65 20 74 61 62 6c 65 73  ese.three tables
6b50: 20 61 72 65 20 63 61 6c 6c 65 64 20 22 73 68 61   are called "sha
6b60: 64 6f 77 20 74 61 62 6c 65 73 22 2e 20 20 54 68  dow tables".  Th
6b70: 69 73 20 69 73 20 74 68 65 69 72 20 73 63 68 65  is is their sche
6b80: 6d 61 3a 0a 0a 3c 63 6f 64 65 62 6c 6f 63 6b 3e  ma:..<codeblock>
6b90: 0a 43 52 45 41 54 45 20 54 41 42 4c 45 20 25 5f  .CREATE TABLE %_
6ba0: 6e 6f 64 65 28 6e 6f 64 65 6e 6f 20 49 4e 54 45  node(nodeno INTE
6bb0: 47 45 52 20 50 52 49 4d 41 52 59 20 4b 45 59 2c  GER PRIMARY KEY,
6bc0: 20 64 61 74 61 20 42 4c 4f 42 29 0a 43 52 45 41   data BLOB).CREA
6bd0: 54 45 20 54 41 42 4c 45 20 25 5f 70 61 72 65 6e  TE TABLE %_paren
6be0: 74 28 6e 6f 64 65 6e 6f 20 49 4e 54 45 47 45 52  t(nodeno INTEGER
6bf0: 20 50 52 49 4d 41 52 59 20 4b 45 59 2c 20 70 61   PRIMARY KEY, pa
6c00: 72 65 6e 74 6e 6f 64 65 20 49 4e 54 45 47 45 52  rentnode INTEGER
6c10: 29 0a 43 52 45 41 54 45 20 54 41 42 4c 45 20 25  ).CREATE TABLE %
6c20: 5f 72 6f 77 69 64 28 72 6f 77 69 64 20 49 4e 54  _rowid(rowid INT
6c30: 45 47 45 52 20 50 52 49 4d 41 52 59 20 4b 45 59  EGER PRIMARY KEY
6c40: 2c 20 6e 6f 64 65 6e 6f 20 49 4e 54 45 47 45 52  , nodeno INTEGER
6c50: 29 0a 3c 2f 63 6f 64 65 62 6c 6f 63 6b 3e 0a 0a  ).</codeblock>..
6c60: 3c 70 3e 54 68 65 20 22 25 22 20 69 6e 20 74 68  <p>The "%" in th
6c70: 65 20 6e 61 6d 65 20 6f 66 20 65 61 63 68 20 73  e name of each s
6c80: 68 61 64 6f 77 20 74 61 62 6c 65 20 69 73 20 72  hadow table is r
6c90: 65 70 6c 61 63 65 64 20 62 79 20 74 68 65 20 6e  eplaced by the n
6ca0: 61 6d 65 20 6f 66 20 74 68 65 0a 52 2a 54 72 65  ame of the.R*Tre
6cb0: 65 20 76 69 72 74 75 61 6c 20 74 61 62 6c 65 2e  e virtual table.
6cc0: 20 20 53 6f 2c 20 69 66 20 74 68 65 20 6e 61 6d    So, if the nam
6cd0: 65 20 6f 66 20 74 68 65 20 52 2a 54 72 65 65 20  e of the R*Tree 
6ce0: 74 61 62 6c 65 20 69 73 20 22 78 79 7a 22 20 74  table is "xyz" t
6cf0: 68 65 6e 0a 74 68 65 20 74 68 72 65 65 20 73 68  hen.the three sh
6d00: 61 64 6f 77 20 74 61 62 6c 65 73 20 77 6f 75 6c  adow tables woul
6d10: 64 20 62 65 20 22 78 79 7a 5f 6e 6f 64 65 22 2c  d be "xyz_node",
6d20: 20 22 78 79 7a 5f 70 61 72 65 6e 74 22 2c 20 61   "xyz_parent", a
6d30: 6e 64 20 22 78 79 7a 5f 72 6f 77 69 64 22 2e 0a  nd "xyz_rowid"..
6d40: 0a 3c 70 3e 54 68 65 72 65 20 69 73 20 6f 6e 65  .<p>There is one
6d50: 20 65 6e 74 72 79 20 69 6e 20 74 68 65 20 25 5f   entry in the %_
6d60: 6e 6f 64 65 20 74 61 62 6c 65 20 66 6f 72 20 65  node table for e
6d70: 61 63 68 20 52 2a 54 72 65 65 20 6e 6f 64 65 2e  ach R*Tree node.
6d80: 20 20 41 6e 0a 52 2a 54 72 65 65 20 6e 6f 64 65    An.R*Tree node
6d90: 20 63 6f 6e 73 69 73 74 73 20 6f 66 20 6f 6e 65   consists of one
6da0: 20 6f 72 20 6d 6f 72 65 20 65 6e 74 72 69 65 73   or more entries
6db0: 20 74 68 61 74 20 61 72 65 20 70 72 6f 78 69 6d   that are proxim
6dc0: 61 74 65 20 74 6f 20 6f 6e 65 20 61 6e 6f 74 68  ate to one anoth
6dd0: 65 72 2e 0a 54 68 65 20 6e 6f 64 65 73 20 6f 66  er..The nodes of
6de0: 20 61 6e 20 52 2a 54 72 65 65 20 66 6f 72 20 61   an R*Tree for a
6df0: 20 74 72 65 65 2e 20 20 41 6c 6c 20 6e 6f 64 65   tree.  All node
6e00: 73 20 6f 74 68 65 72 20 74 68 61 6e 20 74 68 65  s other than the
6e10: 20 72 6f 6f 74 20 68 61 76 65 20 61 6e 0a 65 6e   root have an.en
6e20: 74 72 79 20 69 6e 20 74 68 65 20 25 5f 70 61 72  try in the %_par
6e30: 65 6e 74 20 73 68 61 64 6f 77 20 74 61 62 6c 65  ent shadow table
6e40: 20 74 68 61 74 20 69 64 65 6e 74 69 66 69 65 73   that identifies
6e50: 20 74 68 65 20 70 61 72 65 6e 74 20 6e 6f 64 65   the parent node
6e60: 2e 0a 45 61 63 68 20 65 6e 74 72 79 20 69 6e 20  ..Each entry in 
6e70: 61 6e 20 52 2a 54 72 65 65 20 68 61 73 20 61 20  an R*Tree has a 
6e80: 72 6f 77 69 64 2e 20 20 54 68 65 20 25 5f 72 6f  rowid.  The %_ro
6e90: 77 69 64 20 73 68 61 64 6f 77 20 74 61 62 6c 65  wid shadow table
6ea0: 20 6d 61 70 73 20 65 6e 74 72 79 0a 72 6f 77 69   maps entry.rowi
6eb0: 64 73 20 74 6f 20 74 68 65 20 6e 6f 64 65 20 74  ds to the node t
6ec0: 68 61 74 20 63 6f 6e 74 61 69 6e 73 20 74 68 61  hat contains tha
6ed0: 74 20 65 6e 74 72 79 2e 0a 0a 3c 74 63 6c 3e 68  t entry...<tcl>h
6ee0: 64 5f 66 72 61 67 6d 65 6e 74 20 72 74 72 65 65  d_fragment rtree
6ef0: 63 68 65 63 6b 20 72 74 72 65 65 63 68 65 63 6b  check rtreecheck
6f00: 28 29 3c 2f 74 63 6c 3e 0a 3c 68 32 3e 49 6e 74  ()</tcl>.<h2>Int
6f10: 65 67 72 69 74 79 20 43 68 65 63 6b 20 75 73 69  egrity Check usi
6f20: 6e 67 20 74 68 65 20 72 74 72 65 65 63 68 65 63  ng the rtreechec
6f30: 6b 28 29 20 53 51 4c 20 66 75 6e 63 74 69 6f 6e  k() SQL function
6f40: 3c 2f 68 32 3e 0a 0a 3c 70 3e 54 68 65 20 73 63  </h2>..<p>The sc
6f50: 61 6c 61 72 20 53 51 4c 20 66 75 6e 63 74 69 6f  alar SQL functio
6f60: 6e 20 72 74 72 65 65 63 68 65 63 6b 28 52 29 20  n rtreecheck(R) 
6f70: 6f 72 20 72 74 72 65 65 63 68 65 63 6b 28 53 2c  or rtreecheck(S,
6f80: 52 29 20 72 75 6e 73 20 61 6e 0a 69 6e 74 65 67  R) runs an.integ
6f90: 72 69 74 79 20 63 68 65 63 6b 20 6f 6e 20 74 68  rity check on th
6fa0: 65 20 72 74 72 65 65 20 74 61 62 6c 65 20 6e 61  e rtree table na
6fb0: 6d 65 64 20 52 20 63 6f 6e 74 61 69 6e 65 64 20  med R contained 
6fc0: 77 69 74 68 69 6e 20 64 61 74 61 62 61 73 65 20  within database 
6fd0: 53 2e 0a 54 68 65 20 66 75 6e 63 74 69 6f 6e 20  S..The function 
6fe0: 72 65 74 75 72 6e 73 20 61 20 68 75 6d 61 6e 2d  returns a human-
6ff0: 6c 61 6e 67 75 61 67 65 20 64 65 73 63 72 69 70  language descrip
7000: 74 69 6f 6e 20 6f 66 20 61 6e 79 20 70 72 6f 62  tion of any prob
7010: 6c 65 6d 73 20 66 6f 75 6e 64 2c 0a 6f 72 20 74  lems found,.or t
7020: 68 65 20 73 74 72 69 6e 67 20 27 6f 6b 27 20 69  he string 'ok' i
7030: 66 20 65 76 65 72 79 74 68 69 6e 67 20 69 73 20  f everything is 
7040: 6f 6b 2e 20 20 52 75 6e 6e 69 6e 67 20 72 74 72  ok.  Running rtr
7050: 65 65 63 68 65 63 6b 28 29 20 6f 6e 20 61 6e 20  eecheck() on an 
7060: 52 2a 54 72 65 65 0a 76 69 72 74 75 61 6c 20 74  R*Tree.virtual t
7070: 61 62 6c 65 20 69 73 20 73 69 6d 69 6c 61 72 20  able is similar 
7080: 74 6f 20 72 75 6e 6e 69 6e 67 20 5b 50 52 41 47  to running [PRAG
7090: 4d 41 20 69 6e 74 65 67 72 69 74 79 5f 63 68 65  MA integrity_che
70a0: 63 6b 5d 20 6f 6e 20 61 0a 64 61 74 61 62 61 73  ck] on a.databas
70b0: 65 2e 0a 0a 3c 70 3e 45 78 61 6d 70 6c 65 3a 20  e...<p>Example: 
70c0: 54 6f 20 76 65 72 69 66 79 20 74 68 61 74 20 61  To verify that a
70d0: 6e 20 52 2a 54 72 65 65 20 6e 61 6d 65 64 20 22  n R*Tree named "
70e0: 64 65 6d 6f 5f 69 6e 64 65 78 22 20 69 73 20 77  demo_index" is w
70f0: 65 6c 6c 2d 66 6f 72 6d 65 64 0a 61 6e 64 20 69  ell-formed.and i
7100: 6e 74 65 72 6e 61 6c 6c 79 20 63 6f 6e 73 69 73  nternally consis
7110: 74 65 6e 74 2c 20 72 75 6e 3a 0a 0a 3c 63 6f 64  tent, run:..<cod
7120: 65 62 6c 6f 63 6b 3e 0a 53 45 4c 45 43 54 20 72  eblock>.SELECT r
7130: 74 72 65 65 63 68 65 63 6b 28 27 64 65 6d 6f 5f  treecheck('demo_
7140: 69 6e 64 65 78 27 29 3b 0a 3c 2f 63 6f 64 65 62  index');.</codeb
7150: 6c 6f 63 6b 3e 0a 0a 3c 70 3e 54 68 65 20 72 74  lock>..<p>The rt
7160: 72 65 65 63 68 65 63 6b 28 29 20 66 75 6e 63 74  reecheck() funct
7170: 69 6f 6e 20 70 65 72 66 6f 72 6d 73 20 74 68 65  ion performs the
7180: 20 66 6f 6c 6c 6f 77 69 6e 67 20 63 68 65 63 6b   following check
7190: 73 3a 0a 0a 3c 6f 6c 3e 0a 3c 6c 69 3e 3c 70 3e  s:..<ol>.<li><p>
71a0: 0a 46 6f 72 20 65 61 63 68 20 63 65 6c 6c 20 69  .For each cell i
71b0: 6e 20 74 68 65 20 72 2d 74 72 65 65 20 73 74 72  n the r-tree str
71c0: 75 63 74 75 72 65 20 28 25 5f 6e 6f 64 65 20 74  ucture (%_node t
71d0: 61 62 6c 65 29 2c 20 74 68 61 74 3a 0a 3c 6f 6c  able), that:.<ol
71e0: 20 74 79 70 65 3d 61 3e 0a 3c 6c 69 3e 3c 70 3e   type=a>.<li><p>
71f0: 20 66 6f 72 20 65 61 63 68 20 64 69 6d 65 6e 73   for each dimens
7200: 69 6f 6e 2c 20 28 63 6f 6f 72 64 31 20 26 6c 74  ion, (coord1 &lt
7210: 3b 3d 20 63 6f 6f 72 64 32 29 2e 0a 3c 6c 69 3e  ;= coord2)..<li>
7220: 3c 70 3e 20 75 6e 6c 65 73 73 20 74 68 65 20 63  <p> unless the c
7230: 65 6c 6c 20 69 73 20 6f 6e 20 74 68 65 20 72 6f  ell is on the ro
7240: 6f 74 20 6e 6f 64 65 2c 20 74 68 61 74 20 74 68  ot node, that th
7250: 65 20 63 65 6c 6c 20 69 73 20 62 6f 75 6e 64 65  e cell is bounde
7260: 64 0a 20 20 20 20 20 20 20 20 62 79 20 74 68 65  d.        by the
7270: 20 70 61 72 65 6e 74 20 63 65 6c 6c 20 6f 6e 20   parent cell on 
7280: 74 68 65 20 70 61 72 65 6e 74 20 6e 6f 64 65 2e  the parent node.
7290: 0a 3c 6c 69 3e 3c 70 3e 20 66 6f 72 20 6c 65 61  .<li><p> for lea
72a0: 66 20 6e 6f 64 65 73 2c 20 74 68 61 74 20 74 68  f nodes, that th
72b0: 65 72 65 20 69 73 20 61 6e 20 65 6e 74 72 79 20  ere is an entry 
72c0: 69 6e 20 74 68 65 20 25 5f 72 6f 77 69 64 20 0a  in the %_rowid .
72d0: 20 20 20 20 20 20 20 20 74 61 62 6c 65 20 63 6f          table co
72e0: 72 72 65 73 70 6f 6e 64 69 6e 67 20 74 6f 20 74  rresponding to t
72f0: 68 65 20 63 65 6c 6c 27 73 20 72 6f 77 69 64 20  he cell's rowid 
7300: 76 61 6c 75 65 20 74 68 61 74 20 0a 20 20 20 20  value that .    
7310: 20 20 20 20 70 6f 69 6e 74 73 20 74 6f 20 74 68      points to th
7320: 65 20 63 6f 72 72 65 63 74 20 6e 6f 64 65 2e 0a  e correct node..
7330: 3c 6c 69 3e 3c 70 3e 20 66 6f 72 20 63 65 6c 6c  <li><p> for cell
7340: 73 20 6f 6e 20 6e 6f 6e 2d 6c 65 61 66 20 6e 6f  s on non-leaf no
7350: 64 65 73 2c 20 74 68 61 74 20 74 68 65 72 65 20  des, that there 
7360: 69 73 20 61 6e 20 65 6e 74 72 79 20 69 6e 20 74  is an entry in t
7370: 68 65 20 0a 20 20 20 20 20 20 20 20 25 5f 70 61  he .        %_pa
7380: 72 65 6e 74 20 74 61 62 6c 65 20 6d 61 70 70 69  rent table mappi
7390: 6e 67 20 66 72 6f 6d 20 74 68 65 20 63 65 6c 6c  ng from the cell
73a0: 27 73 20 63 68 69 6c 64 20 6e 6f 64 65 20 74 6f  's child node to
73b0: 20 74 68 65 0a 20 20 20 20 20 20 20 20 6e 6f 64   the.        nod
73c0: 65 20 74 68 61 74 20 69 74 20 72 65 73 69 64 65  e that it reside
73d0: 73 20 6f 6e 2e 0a 3c 2f 6f 6c 3e 0a 3c 6c 69 3e  s on..</ol>.<li>
73e0: 3c 70 3e 0a 54 68 61 74 20 74 68 65 72 65 20 61  <p>.That there a
73f0: 72 65 20 74 68 65 20 73 61 6d 65 20 6e 75 6d 62  re the same numb
7400: 65 72 20 6f 66 20 65 6e 74 72 69 65 73 20 69 6e  er of entries in
7410: 20 74 68 65 20 25 5f 72 6f 77 69 64 20 74 61 62   the %_rowid tab
7420: 6c 65 0a 61 73 20 74 68 65 72 65 20 61 72 65 20  le.as there are 
7430: 6c 65 61 66 20 63 65 6c 6c 73 20 69 6e 20 74 68  leaf cells in th
7440: 65 20 72 2d 74 72 65 65 20 73 74 72 75 63 74 75  e r-tree structu
7450: 72 65 2c 20 61 6e 64 20 74 68 61 74 20 74 68 65  re, and that the
7460: 72 65 0a 69 73 20 61 20 6c 65 61 66 20 63 65 6c  re.is a leaf cel
7470: 6c 20 74 68 61 74 20 63 6f 72 72 65 73 70 6f 6e  l that correspon
7480: 64 73 20 74 6f 20 65 61 63 68 20 65 6e 74 72 79  ds to each entry
7490: 20 69 6e 20 74 68 65 20 25 5f 72 6f 77 69 64 20   in the %_rowid 
74a0: 74 61 62 6c 65 2e 0a 3c 6c 69 3e 3c 70 3e 0a 54  table..<li><p>.T
74b0: 68 61 74 20 74 68 65 72 65 20 61 72 65 20 74 68  hat there are th
74c0: 65 20 73 61 6d 65 20 6e 75 6d 62 65 72 20 6f 66  e same number of
74d0: 20 65 6e 74 72 69 65 73 20 69 6e 20 74 68 65 20   entries in the 
74e0: 25 5f 70 61 72 65 6e 74 20 74 61 62 6c 65 0a 61  %_parent table.a
74f0: 73 20 74 68 65 72 65 20 61 72 65 20 6e 6f 6e 2d  s there are non-
7500: 6c 65 61 66 20 63 65 6c 6c 73 20 69 6e 20 74 68  leaf cells in th
7510: 65 20 72 2d 74 72 65 65 20 73 74 72 75 63 74 75  e r-tree structu
7520: 72 65 2c 20 61 6e 64 20 74 68 61 74 20 0a 74 68  re, and that .th
7530: 65 72 65 20 69 73 20 61 20 6e 6f 6e 2d 6c 65 61  ere is a non-lea
7540: 66 20 63 65 6c 6c 20 74 68 61 74 20 63 6f 72 72  f cell that corr
7550: 65 73 70 6f 6e 64 73 20 74 6f 20 65 61 63 68 20  esponds to each 
7560: 65 6e 74 72 79 20 69 6e 20 74 68 65 20 0a 25 5f  entry in the .%_
7570: 70 61 72 65 6e 74 20 74 61 62 6c 65 2e 0a 3c 2f  parent table..</
7580: 6f 6c 3e 0a                                      ol>.