Documentation Source Text

Hex Artifact Content
Login

Artifact 1b8fcf3a9f701eb69c07bc1ba8fbfaa32a10c99c:


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 68 31 20 61 6c  es}</tcl>.<h1 al
0070: 69 67 6e 3d 22 63 65 6e 74 65 72 22 3e 54 68 65  ign="center">The
0080: 20 53 51 4c 69 74 65 20 52 2a 54 72 65 65 20 4d   SQLite R*Tree M
0090: 6f 64 75 6c 65 3c 2f 68 31 3e 0a 0a 3c 68 32 3e  odule</h1>..<h2>
00a0: 31 2e 30 20 4f 76 65 72 76 69 65 77 3c 2f 68 32  1.0 Overview</h2
00b0: 3e 0a 0a 3c 70 3e 0a 41 6e 20 5b 68 74 74 70 3a  >..<p>.An [http:
00c0: 2f 2f 65 6e 2e 77 69 6b 69 70 65 64 69 61 2e 6f  //en.wikipedia.o
00d0: 72 67 2f 77 69 6b 69 2f 52 2d 74 72 65 65 20 7c  rg/wiki/R-tree |
00e0: 20 52 2d 54 72 65 65 5d 20 69 73 20 61 20 73 70   R-Tree] is a sp
00f0: 65 63 69 61 6c 0a 69 6e 64 65 78 20 74 68 61 74  ecial.index that
0100: 20 69 73 20 64 65 73 69 67 6e 65 64 20 66 6f 72   is designed for
0110: 20 64 6f 69 6e 67 20 72 61 6e 67 65 20 71 75 65   doing range que
0120: 72 69 65 73 2e 20 20 52 2d 54 72 65 65 73 20 61  ries.  R-Trees a
0130: 72 65 20 6d 6f 73 74 20 63 6f 6d 6d 6f 6e 6c 79  re most commonly
0140: 0a 75 73 65 64 20 69 6e 20 67 65 6f 73 70 61 74  .used in geospat
0150: 69 61 6c 20 73 79 73 74 65 6d 73 20 77 68 65 72  ial systems wher
0160: 65 20 65 61 63 68 20 65 6e 74 72 79 20 69 73 20  e each entry is 
0170: 61 20 72 65 63 74 61 6e 67 6c 65 20 77 69 74 68  a rectangle with
0180: 20 6d 69 6e 69 6d 75 6d 20 61 6e 64 0a 6d 61 78   minimum and.max
0190: 69 6d 75 6d 20 58 20 61 6e 64 20 59 20 63 6f 6f  imum X and Y coo
01a0: 72 64 69 6e 61 74 65 73 2e 20 20 47 69 76 65 6e  rdinates.  Given
01b0: 20 61 20 71 75 65 72 79 20 72 65 63 74 61 6e 67   a query rectang
01c0: 6c 65 2c 20 61 6e 20 52 2d 54 72 65 65 20 69 73  le, an R-Tree is
01d0: 20 61 62 6c 65 0a 74 6f 20 71 75 69 63 6b 6c 79   able.to quickly
01e0: 20 66 69 6e 64 20 61 6c 6c 20 65 6e 74 72 69 65   find all entrie
01f0: 73 20 74 68 61 74 20 61 72 65 20 63 6f 6e 74 61  s that are conta
0200: 69 6e 65 64 20 77 69 74 68 69 6e 20 74 68 65 20  ined within the 
0210: 71 75 65 72 79 20 72 65 63 74 61 6e 67 6c 65 0a  query rectangle.
0220: 6f 72 20 77 68 69 63 68 20 6f 76 65 72 6c 61 70  or which overlap
0230: 20 74 68 65 20 71 75 65 72 79 20 72 65 63 74 61   the query recta
0240: 6e 67 6c 65 2e 20 20 54 68 69 73 20 69 64 65 61  ngle.  This idea
0250: 20 69 73 20 65 61 73 69 6c 79 20 65 78 74 65 6e   is easily exten
0260: 64 65 64 20 74 6f 0a 74 68 72 65 65 20 64 69 6d  ded to.three dim
0270: 65 6e 73 69 6f 6e 73 20 66 6f 72 20 75 73 65 20  ensions for use 
0280: 69 6e 20 43 41 44 20 73 79 73 74 65 6d 73 2e 20  in CAD systems. 
0290: 20 52 2d 54 72 65 65 73 20 61 6c 73 6f 20 66 69   R-Trees also fi
02a0: 6e 64 20 75 73 65 20 69 6e 20 74 69 6d 65 2d 64  nd use in time-d
02b0: 6f 6d 61 69 6e 0a 72 61 6e 67 65 20 6c 6f 6f 6b  omain.range look
02c0: 2d 75 70 73 2e 20 20 46 6f 72 20 65 78 61 6d 70  -ups.  For examp
02d0: 6c 65 2c 20 73 75 70 70 6f 73 65 20 61 20 64 61  le, suppose a da
02e0: 74 61 62 61 73 65 20 72 65 63 6f 72 64 73 20 74  tabase records t
02f0: 68 65 20 73 74 61 72 74 69 6e 67 20 61 6e 64 0a  he starting and.
0300: 65 6e 64 69 6e 67 20 74 69 6d 65 73 20 66 6f 72  ending times for
0310: 20 61 20 6c 61 72 67 65 20 6e 75 6d 62 65 72 20   a large number 
0320: 6f 66 20 65 76 65 6e 74 73 2e 20 20 41 20 52 2d  of events.  A R-
0330: 54 72 65 65 20 69 73 20 61 62 6c 65 20 74 6f 20  Tree is able to 
0340: 71 75 69 63 6b 6c 79 0a 66 69 6e 64 20 61 6c 6c  quickly.find all
0350: 20 65 76 65 6e 74 73 20 74 68 61 74 20 77 65 72   events that wer
0360: 65 20 61 63 74 69 76 65 20 61 74 20 61 6e 79 20  e active at any 
0370: 74 69 6d 65 20 64 75 72 69 6e 67 20 61 20 67 69  time during a gi
0380: 76 65 6e 0a 74 69 6d 65 20 69 6e 74 65 72 76 61  ven.time interva
0390: 6c 2c 20 6f 72 20 61 6c 6c 20 65 76 65 6e 74 73  l, or all events
03a0: 20 74 68 61 74 20 73 74 61 72 74 65 64 20 64 75   that started du
03b0: 72 69 6e 67 20 61 20 70 61 72 74 69 63 75 6c 61  ring a particula
03c0: 72 20 74 69 6d 65 20 69 6e 74 65 72 76 61 6c 2c  r time interval,
03d0: 0a 6f 72 20 61 6c 6c 20 65 76 65 6e 74 73 20 74  .or all events t
03e0: 68 61 74 20 62 6f 74 68 20 73 74 61 72 74 65 64  hat both started
03f0: 20 61 6e 64 20 65 6e 64 65 64 20 77 69 74 68 69   and ended withi
0400: 6e 20 61 20 67 69 76 65 6e 20 74 69 6d 65 20 69  n a given time i
0410: 6e 74 65 72 76 61 6c 2e 0a 41 6e 64 20 73 6f 20  nterval..And so 
0420: 66 6f 72 74 68 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e  forth..</p>..<p>
0430: 0a 54 68 65 20 52 2d 54 72 65 65 20 63 6f 6e 63  .The R-Tree conc
0440: 65 70 74 20 6f 72 69 67 69 6e 61 74 65 64 20 77  ept originated w
0450: 69 74 68 20 0a 5b 68 74 74 70 3a 2f 2f 77 77 77  ith .[http://www
0460: 2e 62 61 79 6d 6f 6f 6e 2e 63 6f 6d 2f 7e 74 67  .baymoon.com/~tg
0470: 32 2f 20 7c 20 54 6f 6e 69 20 47 75 74 74 6d 61  2/ | Toni Guttma
0480: 6e 5d 3a 20 0a 3c 65 6d 3e 52 2d 54 72 65 65 73  n]: .<em>R-Trees
0490: 3a 20 41 20 44 79 6e 61 6d 69 63 20 49 6e 64 65  : A Dynamic Inde
04a0: 78 20 53 74 72 75 63 74 75 72 65 20 66 6f 72 20  x Structure for 
04b0: 53 70 61 74 69 61 6c 20 53 65 61 72 63 68 69 6e  Spatial Searchin
04c0: 67 3c 2f 65 6d 3e 2c 0a 50 72 6f 63 2e 20 31 39  g</em>,.Proc. 19
04d0: 38 34 20 41 43 4d 20 53 49 47 4d 4f 44 20 49 6e  84 ACM SIGMOD In
04e0: 74 65 72 6e 61 74 69 6f 6e 61 6c 20 43 6f 6e 66  ternational Conf
04f0: 65 72 65 6e 63 65 20 6f 6e 20 4d 61 6e 61 67 65  erence on Manage
0500: 6d 65 6e 74 20 6f 66 20 44 61 74 61 2c 0a 70 70  ment of Data,.pp
0510: 2e 20 34 37 2d 35 37 2e 0a 54 68 65 20 69 6d 70  . 47-57..The imp
0520: 6c 65 6d 65 6e 74 61 74 69 6f 6e 20 66 6f 75 6e  lementation foun
0530: 64 20 69 6e 20 53 51 4c 69 74 65 20 69 73 20 61  d in SQLite is a
0540: 20 72 65 66 69 6e 65 6d 65 6e 74 20 6f 66 20 47   refinement of G
0550: 75 74 74 6d 61 6e 27 73 20 6f 72 69 67 69 6e 61  uttman's origina
0560: 6c 0a 69 64 65 61 2c 20 63 6f 6d 6d 6f 6e 6c 79  l.idea, commonly
0570: 20 63 61 6c 6c 65 64 20 22 52 2a 54 72 65 65 73   called "R*Trees
0580: 22 2c 20 74 68 61 74 20 77 61 73 20 64 65 73 63  ", that was desc
0590: 72 69 62 65 64 20 62 79 0a 4e 6f 72 62 65 72 74  ribed by.Norbert
05a0: 20 42 65 63 6b 6d 61 6e 6e 2c 20 48 61 6e 73 2d   Beckmann, Hans-
05b0: 50 65 74 65 72 20 4b 72 69 65 67 65 6c 2c 20 52  Peter Kriegel, R
05c0: 61 6c 66 20 53 63 68 6e 65 69 64 65 72 2c 20 42  alf Schneider, B
05d0: 65 72 6e 68 61 72 64 20 53 65 65 67 65 72 3a 0a  ernhard Seeger:.
05e0: 3c 65 6d 3e 54 68 65 20 52 2a 2d 54 72 65 65 3a  <em>The R*-Tree:
05f0: 20 41 6e 20 45 66 66 69 63 69 65 6e 74 20 61 6e   An Efficient an
0600: 64 20 52 6f 62 75 73 74 20 41 63 63 65 73 73 20  d Robust Access 
0610: 4d 65 74 68 6f 64 20 66 6f 72 20 50 6f 69 6e 74  Method for Point
0620: 73 0a 61 6e 64 20 52 65 63 74 61 6e 67 6c 65 73  s.and Rectangles
0630: 2e 3c 2f 65 6d 3e 20 53 49 47 4d 4f 44 20 43 6f  .</em> SIGMOD Co
0640: 6e 66 65 72 65 6e 63 65 20 31 39 39 30 3a 20 33  nference 1990: 3
0650: 32 32 2d 33 33 31 2e 0a 3c 2f 70 3e 0a 0a 3c 68  22-331..</p>..<h
0660: 32 3e 32 2e 30 20 43 6f 6d 70 69 6c 69 6e 67 20  2>2.0 Compiling 
0670: 54 68 65 20 52 2a 54 72 65 65 20 4d 6f 64 75 6c  The R*Tree Modul
0680: 65 3c 2f 68 32 3e 0a 0a 3c 70 3e 0a 54 68 65 20  e</h2>..<p>.The 
0690: 73 6f 75 72 63 65 20 63 6f 64 65 20 74 6f 20 74  source code to t
06a0: 68 65 20 53 51 4c 69 74 65 20 52 2a 54 72 65 65  he SQLite R*Tree
06b0: 20 6d 6f 64 75 6c 65 20 69 73 20 69 6e 63 6c 75   module is inclu
06c0: 64 65 64 20 61 73 20 70 61 72 74 0a 6f 66 20 74  ded as part.of t
06d0: 68 65 20 5b 61 6d 61 6c 67 61 6d 61 74 69 6f 6e  he [amalgamation
06e0: 5d 20 62 75 74 20 69 73 20 64 69 73 61 62 6c 65  ] but is disable
06f0: 64 20 62 79 20 64 65 66 61 75 6c 74 2e 20 20 54  d by default.  T
0700: 6f 20 65 6e 61 62 6c 65 20 74 68 65 0a 52 2a 54  o enable the.R*T
0710: 72 65 65 20 6d 6f 64 75 6c 65 2c 20 73 69 6d 70  ree module, simp
0720: 6c 79 20 63 6f 6d 70 69 6c 65 20 77 69 74 68 20  ly compile with 
0730: 74 68 65 20 5b 53 51 4c 49 54 45 5f 45 4e 41 42  the [SQLITE_ENAB
0740: 4c 45 5f 52 54 52 45 45 5d 20 0a 43 2d 70 72 65  LE_RTREE] .C-pre
0750: 70 72 6f 63 65 73 73 6f 72 20 6d 61 63 72 6f 20  processor macro 
0760: 64 65 66 69 6e 65 64 2e 20 20 57 69 74 68 20 6d  defined.  With m
0770: 61 6e 79 20 63 6f 6d 70 69 6c 65 72 73 2c 20 74  any compilers, t
0780: 68 69 73 20 69 73 20 61 63 63 6f 6d 70 6c 69 73  his is accomplis
0790: 68 65 64 0a 62 79 20 61 64 64 69 6e 67 20 74 68  hed.by adding th
07a0: 65 20 6f 70 74 69 6f 6e 20 22 2d 44 53 51 4c 49  e option "-DSQLI
07b0: 54 45 5f 45 4e 41 42 4c 45 5f 52 54 52 45 45 3d  TE_ENABLE_RTREE=
07c0: 31 22 20 74 6f 20 74 68 65 20 63 6f 6d 70 69 6c  1" to the compil
07d0: 65 72 0a 63 6f 6d 6d 61 6e 64 2d 6c 69 6e 65 2e  er.command-line.
07e0: 0a 3c 2f 70 3e 0a 0a 3c 68 32 3e 33 2e 30 20 55  .</p>..<h2>3.0 U
07f0: 73 69 6e 67 20 74 68 65 20 52 2a 54 72 65 65 20  sing the R*Tree 
0800: 4d 6f 64 75 6c 65 3c 2f 68 32 3e 0a 0a 3c 70 3e  Module</h2>..<p>
0810: 0a 54 68 65 20 53 51 4c 69 74 65 20 52 2a 54 72  .The SQLite R*Tr
0820: 65 65 20 6d 6f 64 75 6c 65 20 69 73 20 69 6d 70  ee module is imp
0830: 6c 65 6d 65 6e 74 65 64 20 61 73 20 61 0a 5b 73  lemented as a.[s
0840: 71 6c 69 74 65 33 5f 63 72 65 61 74 65 5f 6d 6f  qlite3_create_mo
0850: 64 75 6c 65 20 7c 20 76 69 72 74 75 61 6c 20 74  dule | virtual t
0860: 61 62 6c 65 5d 2e 20 20 5e 45 61 63 68 20 52 2a  able].  ^Each R*
0870: 54 72 65 65 20 69 6e 64 65 78 20 69 73 20 61 0a  Tree index is a.
0880: 76 69 72 74 75 61 6c 20 74 61 62 6c 65 20 77 69  virtual table wi
0890: 74 68 20 61 6e 20 6f 64 64 20 6e 75 6d 62 65 72  th an odd number
08a0: 20 6f 66 20 63 6f 6c 75 6d 6e 73 20 62 65 74 77   of columns betw
08b0: 65 65 6e 20 33 20 61 6e 64 20 31 31 2e 0a 5e 54  een 3 and 11..^T
08c0: 68 65 20 66 69 72 73 74 20 63 6f 6c 75 6d 6e 20  he first column 
08d0: 69 73 20 61 6c 77 61 79 73 20 61 20 36 34 2d 62  is always a 64-b
08e0: 69 74 20 73 69 67 6e 65 64 20 69 6e 74 65 67 65  it signed intege
08f0: 72 20 70 72 69 6d 61 72 79 20 6b 65 79 2e 0a 5e  r primary key..^
0900: 54 68 65 20 6f 74 68 65 72 20 63 6f 6c 75 6d 6e  The other column
0910: 73 20 61 72 65 20 70 61 69 72 73 2c 20 6f 6e 65  s are pairs, one
0920: 20 70 61 69 72 20 70 65 72 20 64 69 6d 65 6e 73   pair per dimens
0930: 69 6f 6e 2c 20 63 6f 6e 74 61 69 6e 69 6e 67 20  ion, containing 
0940: 74 68 65 0a 6d 69 6e 69 6d 75 6d 20 61 6e 64 20  the.minimum and 
0950: 6d 61 78 69 6d 75 6d 20 76 61 6c 75 65 73 20 66  maximum values f
0960: 6f 72 20 74 68 61 74 20 64 69 6d 65 6e 73 69 6f  or that dimensio
0970: 6e 2c 20 72 65 73 70 65 63 74 69 76 65 6c 79 2e  n, respectively.
0980: 0a 5e 41 20 31 2d 64 69 6d 65 6e 73 69 6f 6e 61  .^A 1-dimensiona
0990: 6c 20 52 2a 54 72 65 65 20 74 68 75 73 20 68 61  l R*Tree thus ha
09a0: 73 20 33 20 63 6f 6c 75 6d 6e 73 2e 20 20 0a 5e  s 3 columns.  .^
09b0: 41 20 32 2d 64 69 6d 65 6e 73 69 6f 6e 61 6c 20  A 2-dimensional 
09c0: 52 2a 54 72 65 65 20 68 61 73 20 35 20 63 6f 6c  R*Tree has 5 col
09d0: 75 6d 6e 73 2e 0a 5e 41 20 33 2d 64 69 6d 65 6e  umns..^A 3-dimen
09e0: 73 69 6f 6e 61 6c 20 52 2a 54 72 65 65 20 68 61  sional R*Tree ha
09f0: 73 20 37 20 63 6f 6c 75 6d 6e 73 2e 0a 5e 41 20  s 7 columns..^A 
0a00: 34 2d 64 69 6d 65 6e 73 69 6f 6e 61 6c 20 52 2a  4-dimensional R*
0a10: 54 72 65 65 20 68 61 73 20 39 20 63 6f 6c 75 6d  Tree has 9 colum
0a20: 6e 73 2e 0a 5e 41 6e 64 20 61 20 35 2d 64 69 6d  ns..^And a 5-dim
0a30: 65 6e 73 69 6f 6e 61 6c 20 52 2a 54 72 65 65 20  ensional R*Tree 
0a40: 68 61 73 20 31 31 20 63 6f 6c 75 6d 6e 73 2e 20  has 11 columns. 
0a50: 20 5e 54 68 65 20 53 51 4c 69 74 65 20 52 2a 54   ^The SQLite R*T
0a60: 72 65 65 20 69 6d 70 6c 65 6d 65 6e 74 61 74 69  ree implementati
0a70: 6f 6e 0a 64 6f 65 73 20 6e 6f 74 20 73 75 70 70  on.does not supp
0a80: 6f 72 74 20 52 2a 54 72 65 65 73 20 77 69 64 65  ort R*Trees wide
0a90: 72 20 74 68 61 6e 20 35 20 64 69 6d 65 6e 73 69  r than 5 dimensi
0aa0: 6f 6e 73 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a 5e  ons..</p>..<p>.^
0ab0: 54 68 65 20 66 69 72 73 74 20 63 6f 6c 75 6d 6e  The first column
0ac0: 20 6f 66 20 61 6e 20 53 51 4c 69 74 65 20 52 2a   of an SQLite R*
0ad0: 54 72 65 65 20 6d 75 73 74 20 61 6c 77 61 79 73  Tree must always
0ae0: 20 62 65 20 61 6e 20 69 6e 74 65 67 65 72 0a 70   be an integer.p
0af0: 72 69 6d 61 72 79 20 6b 65 79 2e 0a 5e 54 68 65  rimary key..^The
0b00: 20 6d 69 6e 2f 6d 61 78 2d 76 61 6c 75 65 20 70   min/max-value p
0b10: 61 69 72 20 63 6f 6c 75 6d 6e 73 20 61 72 65 20  air columns are 
0b20: 73 74 6f 72 65 64 20 61 73 0a 33 32 2d 62 69 74  stored as.32-bit
0b30: 20 66 6c 6f 61 74 69 6e 67 20 70 6f 69 6e 74 20   floating point 
0b40: 76 61 6c 75 65 73 20 66 6f 72 20 22 72 74 72 65  values for "rtre
0b50: 65 22 20 76 69 72 74 75 61 6c 20 74 61 62 6c 65  e" virtual table
0b60: 73 20 6f 72 20 61 73 0a 33 32 2d 62 69 74 20 73  s or as.32-bit s
0b70: 69 67 6e 65 64 20 69 6e 74 65 67 65 72 73 20 69  igned integers i
0b80: 6e 20 22 72 74 72 65 65 5f 69 33 32 22 20 76 69  n "rtree_i32" vi
0b90: 72 74 75 61 6c 20 74 61 62 6c 65 73 2e 0a 5e 55  rtual tables..^U
0ba0: 6e 6c 69 6b 65 20 72 65 67 75 6c 61 72 20 53 51  nlike regular SQ
0bb0: 4c 69 74 65 20 74 61 62 6c 65 73 20 77 68 69 63  Lite tables whic
0bc0: 68 0a 63 61 6e 20 73 74 6f 72 65 20 64 61 74 61  h.can store data
0bd0: 20 69 6e 20 61 20 76 61 72 69 65 74 79 20 6f 66   in a variety of
0be0: 20 64 61 74 61 74 79 70 65 73 20 61 6e 64 20 66   datatypes and f
0bf0: 6f 72 6d 61 74 73 2c 20 74 68 65 20 52 2a 54 72  ormats, the R*Tr
0c00: 65 65 0a 69 6e 64 69 63 65 73 20 72 69 67 69 64  ee.indices rigid
0c10: 6c 79 20 65 6e 66 6f 72 63 65 20 74 68 65 73 65  ly enforce these
0c20: 20 73 74 6f 72 61 67 65 20 74 79 70 65 73 2e 20   storage types. 
0c30: 20 5e 41 74 74 65 6d 70 74 73 20 74 6f 20 69 6e   ^Attempts to in
0c40: 73 65 72 74 0a 73 6f 6d 65 74 68 69 6e 67 20 6f  sert.something o
0c50: 74 68 65 72 20 74 68 61 6e 20 61 6e 20 69 6e 74  ther than an int
0c60: 65 67 65 72 20 69 6e 74 6f 20 74 68 65 20 66 69  eger into the fi
0c70: 72 73 74 20 63 6f 6c 75 6d 6e 2c 20 6f 72 20 73  rst column, or s
0c80: 6f 6d 65 74 68 69 6e 67 0a 6f 74 68 65 72 20 74  omething.other t
0c90: 68 61 6e 20 61 20 6e 75 6d 65 72 69 63 20 76 61  han a numeric va
0ca0: 6c 75 65 20 69 6e 74 6f 20 74 68 65 20 6f 74 68  lue into the oth
0cb0: 65 72 20 63 6f 6c 75 6d 6e 73 2c 20 77 69 6c 6c  er columns, will
0cc0: 20 72 65 73 75 6c 74 0a 69 6e 20 61 6e 20 65 72   result.in an er
0cd0: 72 6f 72 2e 0a 3c 2f 70 3e 0a 0a 3c 68 33 3e 33  ror..</p>..<h3>3
0ce0: 2e 31 20 43 72 65 61 74 69 6e 67 20 41 6e 20 52  .1 Creating An R
0cf0: 2a 54 72 65 65 20 49 6e 64 65 78 3c 2f 68 33 3e  *Tree Index</h3>
0d00: 0a 0a 5e 28 3c 70 3e 0a 41 20 6e 65 77 20 52 2a  ..^(<p>.A new R*
0d10: 54 72 65 65 20 69 6e 64 65 78 20 69 73 20 63 72  Tree index is cr
0d20: 65 61 74 65 64 20 61 73 20 66 6f 6c 6c 6f 77 73  eated as follows
0d30: 3a 0a 3c 2f 70 3e 0a 0a 3c 62 6c 6f 63 6b 71 75  :.</p>..<blockqu
0d40: 6f 74 65 3e 3c 70 72 65 3e 0a 43 52 45 41 54 45  ote><pre>.CREATE
0d50: 20 56 49 52 54 55 41 4c 20 54 41 42 4c 45 20 3c   VIRTUAL TABLE <
0d60: 65 6d 3e 26 6c 74 3b 6e 61 6d 65 26 67 74 3b 3c  em>&lt;name&gt;<
0d70: 2f 65 6d 3e 20 55 53 49 4e 47 20 72 74 72 65 65  /em> USING rtree
0d80: 28 3c 65 6d 3e 26 6c 74 3b 63 6f 6c 75 6d 6e 2d  (<em>&lt;column-
0d90: 6e 61 6d 65 73 26 67 74 3b 3c 2f 65 6d 3e 29 3b  names&gt;</em>);
0da0: 0a 3c 2f 70 72 65 3e 3c 2f 62 6c 6f 63 6b 71 75  .</pre></blockqu
0db0: 6f 74 65 3e 29 5e 0a 0a 3c 70 3e 0a 54 68 65 20  ote>)^..<p>.The 
0dc0: 3c 65 6d 3e 26 6c 74 3b 6e 61 6d 65 26 67 74 3b  <em>&lt;name&gt;
0dd0: 3c 2f 65 6d 3e 20 69 73 20 74 68 65 20 6e 61 6d  </em> is the nam
0de0: 65 20 79 6f 75 72 20 61 70 70 6c 69 63 61 74 69  e your applicati
0df0: 6f 6e 20 63 68 6f 6f 73 65 73 20 66 6f 72 20 74  on chooses for t
0e00: 68 65 0a 52 2a 54 72 65 65 20 69 6e 64 65 78 20  he.R*Tree index 
0e10: 61 6e 64 20 3c 65 6d 3e 26 6c 74 3b 63 6f 6c 75  and <em>&lt;colu
0e20: 6d 6e 2d 6e 61 6d 65 73 26 67 74 3b 3c 2f 65 6d  mn-names&gt;</em
0e30: 3e 20 69 73 20 61 20 63 6f 6d 6d 61 20 73 65 70  > is a comma sep
0e40: 61 72 61 74 65 64 20 6c 69 73 74 0a 6f 66 20 62  arated list.of b
0e50: 65 74 77 65 65 6e 20 33 20 61 6e 64 20 31 31 20  etween 3 and 11 
0e60: 63 6f 6c 75 6d 6e 73 2e 0a 5e 28 54 68 65 20 76  columns..^(The v
0e70: 69 72 74 75 61 6c 20 26 6c 74 3b 6e 61 6d 65 26  irtual &lt;name&
0e80: 67 74 3b 20 74 61 62 6c 65 20 63 72 65 61 74 65  gt; table create
0e90: 73 20 74 68 72 65 65 20 22 73 68 61 64 6f 77 22  s three "shadow"
0ea0: 20 74 61 62 6c 65 73 20 74 6f 20 61 63 74 75 61   tables to actua
0eb0: 6c 6c 79 0a 73 74 6f 72 65 20 69 74 73 20 63 6f  lly.store its co
0ec0: 6e 74 65 6e 74 2e 20 20 54 68 65 20 6e 61 6d 65  ntent.  The name
0ed0: 73 20 6f 66 20 74 68 65 73 65 20 73 68 61 64 6f  s of these shado
0ee0: 77 20 74 61 62 6c 65 73 20 61 72 65 3a 0a 3c 2f  w tables are:.</
0ef0: 70 3e 0a 0a 3c 62 6c 6f 63 6b 71 75 6f 74 65 3e  p>..<blockquote>
0f00: 0a 3c 65 6d 3e 26 6c 74 3b 6e 61 6d 65 26 67 74  .<em>&lt;name&gt
0f10: 3b 3c 2f 65 6d 3e 3c 73 74 72 6f 6e 67 3e 5f 6e  ;</em><strong>_n
0f20: 6f 64 65 3c 2f 73 74 72 6f 6e 67 3e 3c 62 72 3e  ode</strong><br>
0f30: 0a 3c 65 6d 3e 26 6c 74 3b 6e 61 6d 65 26 67 74  .<em>&lt;name&gt
0f40: 3b 3c 2f 65 6d 3e 3c 73 74 72 6f 6e 67 3e 5f 72  ;</em><strong>_r
0f50: 6f 77 69 64 3c 2f 73 74 72 6f 6e 67 3e 3c 62 72  owid</strong><br
0f60: 3e 0a 3c 65 6d 3e 26 6c 74 3b 6e 61 6d 65 26 67  >.<em>&lt;name&g
0f70: 74 3b 3c 2f 65 6d 3e 3c 73 74 72 6f 6e 67 3e 5f  t;</em><strong>_
0f80: 70 61 72 65 6e 74 3c 2f 73 74 72 6f 6e 67 3e 0a  parent</strong>.
0f90: 3c 2f 62 6c 6f 63 6b 71 75 6f 74 65 3e 29 5e 0a  </blockquote>)^.
0fa0: 0a 3c 70 3e 0a 5e 54 68 65 20 73 68 61 64 6f 77  .<p>.^The shadow
0fb0: 20 74 61 62 6c 65 73 20 61 72 65 20 6f 72 64 69   tables are ordi
0fc0: 6e 61 72 79 20 53 51 4c 69 74 65 20 64 61 74 61  nary SQLite data
0fd0: 20 74 61 62 6c 65 73 2e 20 20 59 6f 75 20 63 61   tables.  You ca
0fe0: 6e 20 71 75 65 72 79 20 74 68 65 6d 20 0a 64 69  n query them .di
0ff0: 72 65 63 74 6c 79 20 69 66 20 79 6f 75 20 6c 69  rectly if you li
1000: 6b 65 2c 20 74 68 6f 75 67 68 20 74 68 69 73 20  ke, though this 
1010: 75 6e 6c 69 6b 65 6c 79 20 74 6f 20 72 65 76 65  unlikely to reve
1020: 61 6c 20 61 6e 79 74 68 69 6e 67 20 70 61 72 74  al anything part
1030: 69 63 75 6c 61 72 6c 79 0a 75 73 65 66 75 6c 2e  icularly.useful.
1040: 20 0a 5e 41 6e 64 20 79 6f 75 20 63 61 6e 20 5b   .^And you can [
1050: 55 50 44 41 54 45 5d 2c 20 5b 44 45 4c 45 54 45  UPDATE], [DELETE
1060: 5d 2c 20 5b 49 4e 53 45 52 54 5d 20 6f 72 20 65  ], [INSERT] or e
1070: 76 65 6e 20 5b 44 52 4f 50 20 54 41 42 4c 45 20  ven [DROP TABLE 
1080: 7c 20 44 52 4f 50 5d 20 0a 74 68 65 20 73 68 61  | DROP] .the sha
1090: 64 6f 77 20 74 61 62 6c 65 73 2c 20 74 68 6f 75  dow tables, thou
10a0: 67 68 20 64 6f 69 6e 67 20 73 6f 20 77 69 6c 6c  gh doing so will
10b0: 20 63 6f 72 72 75 70 74 20 79 6f 75 72 20 52 2a   corrupt your R*
10c0: 54 72 65 65 20 69 6e 64 65 78 2e 0a 53 6f 20 69  Tree index..So i
10d0: 74 20 69 73 20 62 65 73 74 20 74 6f 20 73 69 6d  t is best to sim
10e0: 70 6c 79 20 69 67 6e 6f 72 65 20 74 68 65 20 73  ply ignore the s
10f0: 68 61 64 6f 77 20 74 61 62 6c 65 73 2e 20 20 52  hadow tables.  R
1100: 65 63 6f 67 6e 69 7a 65 20 74 68 61 74 20 74 68  ecognize that th
1110: 65 79 0a 68 6f 6c 64 20 79 6f 75 72 20 52 2a 54  ey.hold your R*T
1120: 72 65 65 20 69 6e 64 65 78 20 69 6e 66 6f 72 6d  ree index inform
1130: 61 74 69 6f 6e 20 61 6e 64 20 6c 65 74 20 69 74  ation and let it
1140: 20 67 6f 20 61 73 20 74 68 61 74 2e 0a 3c 2f 70   go as that..</p
1150: 3e 0a 0a 3c 70 3e 0a 5e 28 41 73 20 61 6e 20 65  >..<p>.^(As an e
1160: 78 61 6d 70 6c 65 2c 20 63 6f 6e 73 69 64 65 72  xample, consider
1170: 20 63 72 65 61 74 69 6e 67 20 61 20 74 77 6f 2d   creating a two-
1180: 64 69 6d 65 6e 73 69 6f 6e 61 6c 20 52 2a 54 72  dimensional R*Tr
1190: 65 65 20 69 6e 64 65 78 20 66 6f 72 20 75 73 65  ee index for use
11a0: 20 69 6e 20 0a 73 70 61 74 69 61 6c 20 71 75 65   in .spatial que
11b0: 72 69 65 73 3a 0a 3c 2f 70 3e 0a 0a 3c 62 6c 6f  ries:.</p>..<blo
11c0: 63 6b 71 75 6f 74 65 3e 3c 70 72 65 3e 0a 43 52  ckquote><pre>.CR
11d0: 45 41 54 45 20 56 49 52 54 55 41 4c 20 54 41 42  EATE VIRTUAL TAB
11e0: 4c 45 20 64 65 6d 6f 5f 69 6e 64 65 78 20 55 53  LE demo_index US
11f0: 49 4e 47 20 72 74 72 65 65 28 0a 20 20 20 69 64  ING rtree(.   id
1200: 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2d  ,              -
1210: 2d 20 49 6e 74 65 67 65 72 20 70 72 69 6d 61 72  - Integer primar
1220: 79 20 6b 65 79 0a 20 20 20 6d 69 6e 58 2c 20 6d  y key.   minX, m
1230: 61 78 58 2c 20 20 20 20 20 20 2d 2d 20 4d 69 6e  axX,      -- Min
1240: 69 6d 75 6d 20 61 6e 64 20 6d 61 78 69 6d 75 6d  imum and maximum
1250: 20 58 20 63 6f 6f 72 64 69 6e 61 74 65 0a 20 20   X coordinate.  
1260: 20 6d 69 6e 59 2c 20 6d 61 78 59 20 20 20 20 20   minY, maxY     
1270: 20 20 2d 2d 20 4d 69 6e 69 6d 75 6d 20 61 6e 64    -- Minimum and
1280: 20 6d 61 78 69 6d 75 6d 20 59 20 63 6f 6f 72 64   maximum Y coord
1290: 69 6e 61 74 65 0a 29 3b 0a 3c 2f 70 72 65 3e 3c  inate.);.</pre><
12a0: 2f 62 6c 6f 63 6b 71 75 6f 74 65 3e 29 5e 0a 0a  /blockquote>)^..
12b0: 3c 68 33 3e 33 2e 32 20 50 6f 70 75 6c 61 74 69  <h3>3.2 Populati
12c0: 6e 67 20 41 6e 20 52 2a 54 72 65 65 20 49 6e 64  ng An R*Tree Ind
12d0: 65 78 3c 2f 68 33 3e 0a 0a 3c 70 3e 0a 5e 54 68  ex</h3>..<p>.^Th
12e0: 65 20 75 73 75 61 6c 20 5b 49 4e 53 45 52 54 5d  e usual [INSERT]
12f0: 2c 20 5b 55 50 44 41 54 45 5d 2c 20 61 6e 64 20  , [UPDATE], and 
1300: 5b 44 45 4c 45 54 45 5d 20 63 6f 6d 6d 61 6e 64  [DELETE] command
1310: 73 20 77 6f 72 6b 20 6f 6e 20 61 6e 20 52 2a 54  s work on an R*T
1320: 72 65 65 0a 69 6e 64 65 78 20 6a 75 73 74 20 6c  ree.index just l
1330: 69 6b 65 20 6f 6e 20 72 65 67 75 6c 61 72 20 74  ike on regular t
1340: 61 62 6c 65 73 2e 20 20 5e 28 53 6f 20 74 6f 20  ables.  ^(So to 
1350: 69 6e 73 65 72 74 20 73 6f 6d 65 20 64 61 74 61  insert some data
1360: 20 69 6e 74 6f 20 6f 75 72 20 73 61 6d 70 6c 65   into our sample
1370: 0a 52 2a 54 72 65 65 20 69 6e 64 65 78 2c 20 77  .R*Tree index, w
1380: 65 20 63 61 6e 20 64 6f 20 73 6f 6d 65 74 68 69  e can do somethi
1390: 6e 67 20 6c 69 6b 65 20 74 68 69 73 3a 0a 3c 2f  ng like this:.</
13a0: 70 3e 0a 0a 3c 62 6c 6f 63 6b 71 75 6f 74 65 3e  p>..<blockquote>
13b0: 3c 70 72 65 3e 0a 49 4e 53 45 52 54 20 49 4e 54  <pre>.INSERT INT
13c0: 4f 20 64 65 6d 6f 5f 69 6e 64 65 78 20 56 41 4c  O demo_index VAL
13d0: 55 45 53 28 0a 20 20 20 20 31 2c 20 20 20 20 20  UES(.    1,     
13e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2d 2d                --
13f0: 20 50 72 69 6d 61 72 79 20 6b 65 79 20 2d 2d 20   Primary key -- 
1400: 53 51 4c 69 74 65 2e 6f 72 67 20 68 65 61 64 71  SQLite.org headq
1410: 75 61 72 74 65 72 73 0a 20 20 20 20 2d 38 30 2e  uarters.    -80.
1420: 37 37 34 39 2c 20 2d 38 30 2e 37 37 34 37 2c 20  7749, -80.7747, 
1430: 20 2d 2d 20 4c 6f 6e 67 69 74 75 64 65 20 72 61   -- Longitude ra
1440: 6e 67 65 0a 20 20 20 20 33 35 2e 33 37 37 36 2c  nge.    35.3776,
1450: 20 33 35 2e 33 37 37 38 20 20 20 20 20 2d 2d 20   35.3778     -- 
1460: 4c 61 74 69 74 75 64 65 20 72 61 6e 67 65 0a 29  Latitude range.)
1470: 3b 0a 49 4e 53 45 52 54 20 49 4e 54 4f 20 64 65  ;.INSERT INTO de
1480: 6d 6f 5f 69 6e 64 65 78 20 56 41 4c 55 45 53 28  mo_index VALUES(
1490: 0a 20 20 20 20 32 2c 20 20 20 20 20 20 20 20 20  .    2,         
14a0: 20 20 20 20 20 20 20 20 20 20 2d 2d 20 4e 43 20            -- NC 
14b0: 31 32 74 68 20 43 6f 6e 67 72 65 73 73 69 6f 6e  12th Congression
14c0: 61 6c 20 44 69 73 74 72 69 63 74 20 69 6e 20 32  al District in 2
14d0: 30 31 30 0a 20 20 20 20 2d 38 31 2e 30 2c 20 2d  010.    -81.0, -
14e0: 37 39 2e 36 2c 0a 20 20 20 20 33 35 2e 30 2c 20  79.6,.    35.0, 
14f0: 33 36 2e 32 0a 29 3b 0a 3c 2f 70 72 65 3e 3c 2f  36.2.);.</pre></
1500: 62 6c 6f 63 6b 71 75 6f 74 65 3e 29 5e 0a 0a 3c  blockquote>)^..<
1510: 70 3e 0a 54 68 65 20 65 6e 74 72 69 65 73 20 61  p>.The entries a
1520: 62 6f 76 65 20 6d 69 67 68 74 20 72 65 70 72 65  bove might repre
1530: 73 65 6e 74 20 28 66 6f 72 20 65 78 61 6d 70 6c  sent (for exampl
1540: 65 29 20 61 20 62 6f 75 6e 64 69 6e 67 20 62 6f  e) a bounding bo
1550: 78 20 61 72 6f 75 6e 64 0a 74 68 65 20 6d 61 69  x around.the mai
1560: 6e 20 6f 66 66 69 63 65 20 66 6f 72 20 53 51 4c  n office for SQL
1570: 69 74 65 2e 6f 72 67 20 61 6e 64 20 62 6f 75 6e  ite.org and boun
1580: 64 69 6e 67 20 62 6f 78 20 61 72 6f 75 6e 64 20  ding box around 
1590: 74 68 65 0a 31 32 74 68 20 43 6f 6e 67 72 65 73  the.12th Congres
15a0: 73 69 6f 6e 61 6c 20 44 69 73 74 72 69 63 74 20  sional District 
15b0: 6f 66 20 4e 6f 72 74 68 20 43 61 72 6f 6c 69 6e  of North Carolin
15c0: 61 20 28 70 72 69 6f 72 20 74 6f 20 74 68 65 20  a (prior to the 
15d0: 32 30 31 31 0a 72 65 64 69 73 74 72 69 63 74 69  2011.redistricti
15e0: 6e 67 29 20 69 6e 20 77 68 69 63 68 20 53 51 4c  ng) in which SQL
15f0: 69 74 65 2e 6f 72 67 20 77 61 73 20 6c 6f 63 61  ite.org was loca
1600: 74 65 64 2e 20 20 0a 3c 2f 70 3e 0a 0a 3c 68 33  ted.  .</p>..<h3
1610: 3e 33 2e 33 20 51 75 65 72 79 69 6e 67 20 41 6e  >3.3 Querying An
1620: 20 52 2a 54 72 65 65 20 49 6e 64 65 78 3c 2f 68   R*Tree Index</h
1630: 33 3e 0a 0a 3c 70 3e 0a 5e 41 6e 79 20 76 61 6c  3>..<p>.^Any val
1640: 69 64 20 71 75 65 72 79 20 77 69 6c 6c 20 77 6f  id query will wo
1650: 72 6b 20 61 67 61 69 6e 73 74 20 61 6e 20 52 2a  rk against an R*
1660: 54 72 65 65 20 69 6e 64 65 78 2e 20 20 42 75 74  Tree index.  But
1670: 20 74 68 65 20 52 2a 54 72 65 65 0a 69 6d 70 6c   the R*Tree.impl
1680: 65 6d 65 6e 74 61 74 69 6f 6e 20 69 73 20 64 65  ementation is de
1690: 73 69 67 6e 65 64 20 74 6f 20 6d 61 6b 65 20 74  signed to make t
16a0: 77 6f 20 6b 69 6e 64 73 20 6f 66 20 71 75 65 72  wo kinds of quer
16b0: 69 65 73 20 65 73 70 65 63 69 61 6c 6c 79 0a 65  ies especially.e
16c0: 66 66 69 63 69 65 6e 74 2e 20 20 5e 28 46 69 72  fficient.  ^(Fir
16d0: 73 74 2c 20 71 75 65 72 69 65 73 20 61 67 61 69  st, queries agai
16e0: 6e 73 74 20 74 68 65 20 70 72 69 6d 61 72 79 20  nst the primary 
16f0: 6b 65 79 20 61 72 65 20 65 66 66 69 63 69 65 6e  key are efficien
1700: 74 3a 0a 3c 2f 70 3e 0a 0a 3c 62 6c 6f 63 6b 71  t:.</p>..<blockq
1710: 75 6f 74 65 3e 3c 70 72 65 3e 0a 53 45 4c 45 43  uote><pre>.SELEC
1720: 54 20 2a 20 46 52 4f 4d 20 64 65 6d 6f 5f 69 6e  T * FROM demo_in
1730: 64 65 78 20 57 48 45 52 45 20 69 64 3d 31 3b 0a  dex WHERE id=1;.
1740: 3c 2f 70 72 65 3e 3c 2f 62 6c 6f 63 6b 71 75 6f  </pre></blockquo
1750: 74 65 3e 29 5e 0a 0a 3c 70 3e 0a 4f 66 20 63 6f  te>)^..<p>.Of co
1760: 75 72 73 65 2c 20 61 6e 20 6f 72 64 69 6e 61 72  urse, an ordinar
1770: 79 20 53 51 4c 69 74 65 20 74 61 62 6c 65 20 77  y SQLite table w
1780: 69 6c 6c 20 61 6c 73 6f 20 64 6f 20 61 20 71 75  ill also do a qu
1790: 65 72 79 20 61 67 61 69 6e 73 74 20 69 74 73 0a  ery against its.
17a0: 69 6e 74 65 67 65 72 20 70 72 69 6d 61 72 79 20  integer primary 
17b0: 6b 65 79 20 65 66 66 69 63 69 65 6e 74 6c 79 2c  key efficiently,
17c0: 20 73 6f 20 74 68 65 20 70 72 65 76 69 6f 75 73   so the previous
17d0: 20 69 73 20 6e 6f 20 62 69 67 20 64 65 61 6c 2e   is no big deal.
17e0: 0a 54 68 65 20 72 65 61 6c 20 72 65 61 73 6f 6e  .The real reason
17f0: 20 66 6f 72 20 75 73 69 6e 67 20 61 6e 20 52 2a   for using an R*
1800: 54 72 65 65 20 69 73 20 73 6f 20 74 68 61 74 0a  Tree is so that.
1810: 79 6f 75 20 63 61 6e 20 65 66 66 69 63 69 65 6e  you can efficien
1820: 74 6c 79 20 64 6f 20 69 6e 65 71 75 61 6c 69 74  tly do inequalit
1830: 79 20 71 75 65 72 69 65 73 20 61 67 61 69 6e 73  y queries agains
1840: 74 20 74 68 65 20 63 6f 6f 72 64 69 6e 61 74 65  t the coordinate
1850: 0a 72 61 6e 67 65 73 2e 20 20 5e 28 54 6f 20 66  .ranges.  ^(To f
1860: 69 6e 64 20 61 6c 6c 20 65 6c 65 6d 65 6e 74 73  ind all elements
1870: 20 6f 66 20 74 68 65 20 69 6e 64 65 78 20 74 68   of the index th
1880: 61 74 20 61 72 65 20 63 6f 6e 74 61 69 6e 65 64  at are contained
1890: 20 77 69 74 68 69 6e 0a 74 68 65 20 76 69 63 69   within.the vici
18a0: 6e 69 74 79 20 6f 66 20 43 68 61 72 6c 6f 74 74  nity of Charlott
18b0: 65 2c 20 4e 6f 72 74 68 20 43 61 72 6f 6c 69 6e  e, North Carolin
18c0: 61 2c 20 6f 6e 65 20 6d 69 67 68 74 20 64 6f 3a  a, one might do:
18d0: 0a 3c 2f 70 3e 0a 0a 3c 62 6c 6f 63 6b 71 75 6f  .</p>..<blockquo
18e0: 74 65 3e 3c 70 72 65 3e 0a 53 45 4c 45 43 54 20  te><pre>.SELECT 
18f0: 69 64 20 46 52 4f 4d 20 64 65 6d 6f 5f 69 6e 64  id FROM demo_ind
1900: 65 78 0a 20 57 48 45 52 45 20 6d 69 6e 58 3e 3d  ex. WHERE minX>=
1910: 2d 38 31 2e 30 38 20 41 4e 44 20 6d 61 78 58 3c  -81.08 AND maxX<
1920: 3d 2d 38 30 2e 35 38 0a 20 20 20 41 4e 44 20 6d  =-80.58.   AND m
1930: 69 6e 59 3e 3d 33 35 2e 30 30 20 20 41 4e 44 20  inY>=35.00  AND 
1940: 6d 61 78 59 3c 3d 33 35 2e 34 34 3b 0a 3c 2f 70  maxY<=35.44;.</p
1950: 72 65 3e 3c 2f 62 6c 6f 63 6b 71 75 6f 74 65 3e  re></blockquote>
1960: 29 5e 0a 0a 3c 70 3e 0a 5e 54 68 65 20 71 75 65  )^..<p>.^The que
1970: 72 79 20 61 62 6f 76 65 20 77 6f 75 6c 64 20 76  ry above would v
1980: 65 72 79 20 71 75 69 63 6b 6c 79 20 6c 6f 63 61  ery quickly loca
1990: 74 65 20 74 68 65 20 69 64 20 6f 66 20 31 20 65  te the id of 1 e
19a0: 76 65 6e 20 69 66 20 74 68 65 0a 52 2a 54 72 65  ven if the.R*Tre
19b0: 65 20 63 6f 6e 74 61 69 6e 65 64 20 6d 69 6c 6c  e contained mill
19c0: 69 6f 6e 73 20 6f 66 20 65 6e 74 72 69 65 73 2e  ions of entries.
19d0: 20 20 54 68 65 20 70 72 65 76 69 6f 75 73 20 69    The previous i
19e0: 73 20 61 6e 20 65 78 61 6d 70 6c 65 0a 6f 66 20  s an example.of 
19f0: 61 20 22 63 6f 6e 74 61 69 6e 65 64 2d 77 69 74  a "contained-wit
1a00: 68 69 6e 22 20 71 75 65 72 79 2e 20 20 54 68 65  hin" query.  The
1a10: 20 52 2a 54 72 65 65 20 61 6c 73 6f 20 73 75 70   R*Tree also sup
1a20: 70 6f 72 74 73 20 22 6f 76 65 72 6c 61 70 70 69  ports "overlappi
1a30: 6e 67 22 0a 71 75 65 72 69 65 73 2e 20 20 5e 28  ng".queries.  ^(
1a40: 46 6f 72 20 65 78 61 6d 70 6c 65 2c 20 74 6f 20  For example, to 
1a50: 66 69 6e 64 20 61 6c 6c 20 62 6f 75 6e 64 69 6e  find all boundin
1a60: 67 20 62 6f 78 65 73 20 74 68 61 74 20 6f 76 65  g boxes that ove
1a70: 72 6c 61 70 20 74 68 65 0a 43 68 61 72 6c 6f 74  rlap the.Charlot
1a80: 74 65 20 61 72 65 61 3a 0a 3c 2f 70 3e 0a 0a 3c  te area:.</p>..<
1a90: 62 6c 6f 63 6b 71 75 6f 74 65 3e 3c 70 72 65 3e  blockquote><pre>
1aa0: 0a 53 45 4c 45 43 54 20 69 64 20 46 52 4f 4d 20  .SELECT id FROM 
1ab0: 64 65 6d 6f 5f 69 6e 64 65 78 0a 20 57 48 45 52  demo_index. WHER
1ac0: 45 20 6d 61 78 58 3e 3d 2d 38 31 2e 30 38 20 41  E maxX>=-81.08 A
1ad0: 4e 44 20 6d 69 6e 58 3c 3d 2d 38 30 2e 35 38 0a  ND minX<=-80.58.
1ae0: 20 20 20 41 4e 44 20 6d 61 78 59 3e 3d 33 35 2e     AND maxY>=35.
1af0: 30 30 20 20 41 4e 44 20 6d 69 6e 59 3c 3d 33 35  00  AND minY<=35
1b00: 2e 34 34 3b 0a 3c 2f 70 72 65 3e 3c 2f 62 6c 6f  .44;.</pre></blo
1b10: 63 6b 71 75 6f 74 65 3e 29 5e 0a 0a 3c 70 3e 0a  ckquote>)^..<p>.
1b20: 5e 28 54 68 69 73 20 73 65 63 6f 6e 64 20 71 75  ^(This second qu
1b30: 65 72 79 20 77 6f 75 6c 64 20 66 69 6e 64 20 62  ery would find b
1b40: 6f 74 68 20 65 6e 74 72 79 20 31 20 28 74 68 65  oth entry 1 (the
1b50: 20 53 51 4c 69 74 65 2e 6f 72 67 20 6f 66 66 69   SQLite.org offi
1b60: 63 65 29 20 77 68 69 63 68 0a 69 73 20 65 6e 74  ce) which.is ent
1b70: 69 72 65 6c 79 20 63 6f 6e 74 61 69 6e 65 64 20  irely contained 
1b80: 77 69 74 68 69 6e 20 74 68 65 20 71 75 65 72 79  within the query
1b90: 20 62 6f 78 20 61 6e 64 20 61 6c 73 6f 0a 74 68   box and also.th
1ba0: 65 20 31 32 74 68 20 43 6f 6e 67 72 65 73 73 69  e 12th Congressi
1bb0: 6f 6e 61 6c 20 44 69 73 74 72 69 63 74 20 77 68  onal District wh
1bc0: 69 63 68 20 65 78 74 65 6e 64 73 20 77 65 6c 6c  ich extends well
1bd0: 20 6f 75 74 73 69 64 65 20 74 68 65 0a 71 75 65   outside the.que
1be0: 72 79 20 62 6f 78 20 62 75 74 20 73 74 69 6c 6c  ry box but still
1bf0: 20 6f 76 65 72 6c 61 70 73 20 74 68 65 20 71 75   overlaps the qu
1c00: 65 72 79 20 62 6f 78 2e 29 5e 0a 3c 2f 70 3e 0a  ery box.)^.</p>.
1c10: 0a 3c 70 3e 0a 5e 4e 6f 74 65 20 74 68 61 74 20  .<p>.^Note that 
1c20: 69 74 20 69 73 20 6e 6f 74 20 6e 65 63 65 73 73  it is not necess
1c30: 61 72 79 20 66 6f 72 20 61 6c 6c 20 63 6f 6f 72  ary for all coor
1c40: 64 69 6e 61 74 65 73 20 69 6e 20 61 6e 20 52 2a  dinates in an R*
1c50: 54 72 65 65 20 69 6e 64 65 78 0a 74 6f 20 62 65  Tree index.to be
1c60: 20 63 6f 6e 73 74 72 61 69 6e 65 64 20 69 6e 20   constrained in 
1c70: 6f 72 64 65 72 20 66 6f 72 20 74 68 65 20 69 6e  order for the in
1c80: 64 65 78 20 73 65 61 72 63 68 20 74 6f 20 62 65  dex search to be
1c90: 20 65 66 66 69 63 69 65 6e 74 2e 0a 5e 28 4f 6e   efficient..^(On
1ca0: 65 20 6d 69 67 68 74 2c 20 66 6f 72 20 65 78 61  e might, for exa
1cb0: 6d 70 6c 65 2c 20 77 61 6e 74 20 74 6f 20 71 75  mple, want to qu
1cc0: 65 72 79 20 61 6c 6c 20 6f 62 6a 65 63 74 73 20  ery all objects 
1cd0: 74 68 61 74 20 6f 76 65 72 6c 61 70 20 77 69 74  that overlap wit
1ce0: 68 0a 74 68 65 20 33 35 74 68 20 70 61 72 61 6c  h.the 35th paral
1cf0: 6c 65 6c 3a 0a 3c 2f 70 3e 0a 0a 3c 62 6c 6f 63  lel:.</p>..<bloc
1d00: 6b 71 75 6f 74 65 3e 3c 70 72 65 3e 0a 53 45 4c  kquote><pre>.SEL
1d10: 45 43 54 20 69 64 20 46 52 4f 4d 20 64 65 6d 6f  ECT id FROM demo
1d20: 5f 69 6e 64 65 78 0a 20 57 48 45 52 45 20 6d 61  _index. WHERE ma
1d30: 78 59 3e 3d 33 35 2e 30 20 20 41 4e 44 20 6d 69  xY>=35.0  AND mi
1d40: 6e 59 3c 3d 33 35 2e 30 3b 0a 3c 2f 70 72 65 3e  nY<=35.0;.</pre>
1d50: 3c 2f 62 6c 6f 63 6b 71 75 6f 74 65 3e 29 5e 0a  </blockquote>)^.
1d60: 0a 3c 70 3e 0a 42 75 74 2c 20 67 65 6e 65 72 61  .<p>.But, genera
1d70: 6c 6c 79 20 73 70 65 61 6b 69 6e 67 2c 20 74 68  lly speaking, th
1d80: 65 20 6d 6f 72 65 20 63 6f 6e 73 74 72 61 69 6e  e more constrain
1d90: 74 73 20 74 68 61 74 20 74 68 65 20 52 2a 54 72  ts that the R*Tr
1da0: 65 65 20 6d 6f 64 75 6c 65 0a 68 61 73 20 74 6f  ee module.has to
1db0: 20 77 6f 72 6b 20 77 69 74 68 2c 20 61 6e 64 20   work with, and 
1dc0: 74 68 65 20 73 6d 61 6c 6c 65 72 20 74 68 65 20  the smaller the 
1dd0: 62 6f 75 6e 64 69 6e 67 20 62 6f 78 2c 20 74 68  bounding box, th
1de0: 65 20 66 61 73 74 65 72 20 74 68 65 0a 72 65 73  e faster the.res
1df0: 75 6c 74 73 20 77 69 6c 6c 20 63 6f 6d 65 20 62  ults will come b
1e00: 61 63 6b 2e 0a 3c 2f 70 3e 0a 0a 3c 68 33 3e 33  ack..</p>..<h3>3
1e10: 2e 33 20 52 6f 75 6e 64 6f 66 66 20 45 72 72 6f  .3 Roundoff Erro
1e20: 72 3c 2f 68 33 3e 0a 0a 3c 70 3e 0a 42 79 20 64  r</h3>..<p>.By d
1e30: 65 66 61 75 6c 74 2c 20 63 6f 6f 72 64 69 6e 61  efault, coordina
1e40: 74 65 73 20 61 72 65 20 73 74 6f 72 65 64 20 69  tes are stored i
1e50: 6e 20 61 6e 20 52 2a 54 72 65 65 20 75 73 69 6e  n an R*Tree usin
1e60: 67 20 33 32 2d 62 69 74 20 66 6c 6f 61 74 69 6e  g 32-bit floatin
1e70: 67 0a 70 6f 69 6e 74 20 76 61 6c 75 65 73 2e 20  g.point values. 
1e80: 20 57 68 65 6e 20 61 20 63 6f 6f 72 64 69 6e 61   When a coordina
1e90: 74 65 20 63 61 6e 6e 6f 74 20 62 65 20 65 78 61  te cannot be exa
1ea0: 63 74 6c 79 20 72 65 70 72 65 73 65 6e 74 65 64  ctly represented
1eb0: 20 62 79 20 61 0a 33 32 2d 62 69 74 20 66 6c 6f   by a.32-bit flo
1ec0: 61 74 69 6e 67 20 70 6f 69 6e 74 20 6e 75 6d 62  ating point numb
1ed0: 65 72 2c 20 74 68 65 20 6c 6f 77 65 72 2d 62 6f  er, the lower-bo
1ee0: 75 6e 64 20 63 6f 6f 72 64 69 6e 61 74 65 73 20  und coordinates 
1ef0: 61 72 65 20 72 6f 75 6e 64 65 64 20 64 6f 77 6e  are rounded down
1f00: 0a 61 6e 64 20 74 68 65 20 75 70 70 65 72 2d 62  .and the upper-b
1f10: 6f 75 6e 64 20 63 6f 6f 72 64 69 6e 61 74 65 73  ound coordinates
1f20: 20 61 72 65 20 72 6f 75 6e 64 65 64 20 75 70 2e   are rounded up.
1f30: 20 20 54 68 75 73 2c 20 62 6f 75 6e 64 69 6e 67    Thus, bounding
1f40: 20 62 6f 78 65 73 20 6d 69 67 68 74 0a 62 65 20   boxes might.be 
1f50: 73 6c 69 67 68 74 6c 79 20 6c 61 72 67 65 72 20  slightly larger 
1f60: 74 68 61 6e 20 73 70 65 63 69 66 69 65 64 2c 20  than specified, 
1f70: 62 75 74 20 77 69 6c 6c 20 6e 65 76 65 72 20 62  but will never b
1f80: 65 20 61 6e 79 20 73 6d 61 6c 6c 65 72 2e 20 20  e any smaller.  
1f90: 54 68 69 73 0a 69 73 20 65 78 61 63 74 6c 79 20  This.is exactly 
1fa0: 77 68 61 74 20 69 73 20 64 65 73 69 72 65 64 20  what is desired 
1fb0: 66 6f 72 20 64 6f 69 6e 67 20 74 68 65 20 6d 6f  for doing the mo
1fc0: 72 65 20 63 6f 6d 6d 6f 6e 20 22 6f 76 65 72 6c  re common "overl
1fd0: 61 70 70 69 6e 67 22 20 71 75 65 72 69 65 73 0a  apping" queries.
1fe0: 77 68 65 72 65 20 74 68 65 20 61 70 70 6c 69 63  where the applic
1ff0: 61 74 69 6f 6e 20 77 61 6e 74 73 20 74 6f 20 66  ation wants to f
2000: 69 6e 64 20 65 76 65 72 79 20 65 6e 74 72 79 20  ind every entry 
2010: 69 6e 20 74 68 65 20 52 2a 54 72 65 65 20 74 68  in the R*Tree th
2020: 61 74 20 6f 76 65 72 6c 61 70 73 0a 61 20 71 75  at overlaps.a qu
2030: 65 72 79 20 62 6f 75 6e 64 69 6e 67 20 62 6f 78  ery bounding box
2040: 2e 20 20 52 6f 75 6e 64 69 6e 67 20 74 68 65 20  .  Rounding the 
2050: 65 6e 74 72 79 20 62 6f 75 6e 64 69 6e 67 20 62  entry bounding b
2060: 6f 78 65 73 20 6f 75 74 77 61 72 64 20 6d 69 67  oxes outward mig
2070: 68 74 20 63 61 75 73 65 20 61 0a 66 65 77 20 65  ht cause a.few e
2080: 78 74 72 61 20 65 6e 74 72 69 65 73 20 74 6f 20  xtra entries to 
2090: 61 70 70 65 61 72 73 20 69 6e 20 61 6e 20 6f 76  appears in an ov
20a0: 65 72 6c 61 70 70 69 6e 67 20 71 75 65 72 79 20  erlapping query 
20b0: 69 66 20 74 68 65 20 65 64 67 65 20 6f 66 20 74  if the edge of t
20c0: 68 65 0a 65 6e 74 72 79 20 62 6f 75 6e 64 69 6e  he.entry boundin
20d0: 67 20 62 6f 78 20 63 6f 72 72 65 73 70 6f 6e 64  g box correspond
20e0: 73 20 74 6f 20 61 6e 20 65 64 67 65 20 6f 66 20  s to an edge of 
20f0: 74 68 65 20 71 75 65 72 79 20 62 6f 75 6e 64 69  the query boundi
2100: 6e 67 20 62 6f 78 2e 20 20 42 75 74 0a 74 68 65  ng box.  But.the
2110: 20 6f 76 65 72 6c 61 70 70 69 6e 67 20 71 75 65   overlapping que
2120: 72 79 20 77 69 6c 6c 20 6e 65 76 65 72 20 6d 69  ry will never mi
2130: 73 73 20 61 20 76 61 6c 69 64 20 74 61 62 6c 65  ss a valid table
2140: 20 65 6e 74 72 79 2e 20 20 0a 0a 3c 70 3e 48 6f   entry.  ..<p>Ho
2150: 77 65 76 65 72 2c 20 66 6f 72 20 61 20 22 63 6f  wever, for a "co
2160: 6e 74 61 69 6e 65 64 2d 77 69 74 68 69 6e 22 20  ntained-within" 
2170: 73 74 79 6c 65 20 71 75 65 72 79 2c 20 72 6f 75  style query, rou
2180: 6e 64 69 6e 67 20 74 68 65 20 62 6f 75 6e 64 69  nding the boundi
2190: 6e 67 0a 62 6f 78 65 73 20 6f 75 74 77 61 72 64  ng.boxes outward
21a0: 20 6d 69 67 68 74 20 63 61 75 73 65 20 73 6f 6d   might cause som
21b0: 65 20 65 6e 74 72 69 65 73 20 74 6f 20 62 65 20  e entries to be 
21c0: 65 78 63 6c 75 64 65 64 20 66 72 6f 6d 20 74 68  excluded from th
21d0: 65 20 72 65 73 75 6c 74 20 73 65 74 0a 69 66 20  e result set.if 
21e0: 74 68 65 20 65 64 67 65 20 6f 66 20 74 68 65 20  the edge of the 
21f0: 65 6e 74 72 79 20 62 6f 75 6e 64 69 6e 67 20 62  entry bounding b
2200: 6f 78 20 63 6f 72 72 65 73 70 6f 6e 64 73 20 74  ox corresponds t
2210: 6f 20 74 68 65 20 65 64 67 65 20 6f 66 20 74 68  o the edge of th
2220: 65 20 71 75 65 72 79 0a 62 6f 75 6e 64 69 6e 67  e query.bounding
2230: 20 62 6f 78 2e 20 20 54 6f 20 67 75 61 72 64 20   box.  To guard 
2240: 61 67 61 69 6e 73 74 20 74 68 69 73 2c 20 61 70  against this, ap
2250: 70 6c 69 63 61 74 69 6f 6e 73 20 73 68 6f 75 6c  plications shoul
2260: 64 20 65 78 70 61 6e 64 20 74 68 65 69 72 0a 63  d expand their.c
2270: 6f 6e 74 61 69 6e 65 64 2d 77 69 74 68 69 6e 20  ontained-within 
2280: 71 75 65 72 79 20 62 6f 78 65 73 20 73 6c 69 67  query boxes slig
2290: 68 74 6c 79 20 28 62 79 20 30 2e 30 30 30 30 31  htly (by 0.00001
22a0: 32 25 29 20 62 79 20 72 6f 75 6e 64 69 6e 67 20  2%) by rounding 
22b0: 64 6f 77 6e 20 74 68 65 0a 6c 6f 77 65 72 20 63  down the.lower c
22c0: 6f 6f 72 64 69 6e 61 74 65 73 20 61 6e 64 20 72  oordinates and r
22d0: 6f 75 6e 64 69 6e 67 20 75 70 20 74 68 65 20 74  ounding up the t
22e0: 6f 70 20 63 6f 6f 72 64 69 6e 61 74 65 73 2c 20  op coordinates, 
22f0: 69 6e 20 65 61 63 68 20 64 69 6d 65 6e 73 69 6f  in each dimensio
2300: 6e 2e 0a 0a 3c 68 32 3e 34 2e 30 20 55 73 69 6e  n...<h2>4.0 Usin
2310: 67 20 52 2a 54 72 65 65 73 20 45 66 66 65 63 74  g R*Trees Effect
2320: 69 76 65 6c 79 3c 2f 68 32 3e 0a 0a 3c 70 3e 0a  ively</h2>..<p>.
2330: 54 68 65 20 6f 6e 6c 79 20 69 6e 66 6f 72 6d 61  The only informa
2340: 74 69 6f 6e 20 74 68 61 74 20 61 6e 20 52 2a 54  tion that an R*T
2350: 72 65 65 20 69 6e 64 65 78 20 73 74 6f 72 65 73  ree index stores
2360: 20 61 62 6f 75 74 20 61 6e 20 6f 62 6a 65 63 74   about an object
2370: 20 69 73 0a 69 74 73 20 69 6e 74 65 67 65 72 20   is.its integer 
2380: 49 44 20 61 6e 64 20 69 74 73 20 62 6f 75 6e 64  ID and its bound
2390: 69 6e 67 20 62 6f 78 2e 20 20 41 64 64 69 74 69  ing box.  Additi
23a0: 6f 6e 61 6c 20 69 6e 66 6f 72 6d 61 74 69 6f 6e  onal information
23b0: 20 6e 65 65 64 73 20 74 6f 0a 62 65 20 73 74 6f   needs to.be sto
23c0: 72 65 64 20 69 6e 20 73 65 70 61 72 61 74 65 20  red in separate 
23d0: 74 61 62 6c 65 73 20 61 6e 64 20 72 65 6c 61 74  tables and relat
23e0: 65 64 20 74 6f 20 74 68 65 20 52 2a 54 72 65 65  ed to the R*Tree
23f0: 20 69 6e 64 65 78 20 75 73 69 6e 67 0a 74 68 65   index using.the
2400: 20 70 72 69 6d 61 72 79 20 6b 65 79 2e 20 20 5e   primary key.  ^
2410: 28 46 6f 72 20 74 68 65 20 65 78 61 6d 70 6c 65  (For the example
2420: 20 61 62 6f 76 65 2c 20 6f 6e 65 20 6d 69 67 68   above, one migh
2430: 74 20 63 72 65 61 74 65 20 61 6e 20 61 75 78 69  t create an auxi
2440: 6c 69 61 72 79 0a 74 61 62 6c 65 20 61 73 20 66  liary.table as f
2450: 6f 6c 6c 6f 77 73 3a 0a 3c 2f 70 3e 0a 0a 3c 62  ollows:.</p>..<b
2460: 6c 6f 63 6b 71 75 6f 74 65 3e 3c 70 72 65 3e 0a  lockquote><pre>.
2470: 43 52 45 41 54 45 20 54 41 42 4c 45 20 64 65 6d  CREATE TABLE dem
2480: 6f 5f 64 61 74 61 28 0a 20 20 69 64 20 49 4e 54  o_data(.  id INT
2490: 45 47 45 52 20 50 52 49 4d 41 52 59 20 4b 45 59  EGER PRIMARY KEY
24a0: 2c 20 20 2d 2d 20 70 72 69 6d 61 72 79 20 6b 65  ,  -- primary ke
24b0: 79 0a 20 20 6f 62 6a 6e 61 6d 65 20 54 45 58 54  y.  objname TEXT
24c0: 2c 20 20 20 20 20 20 20 20 20 20 20 20 2d 2d 20  ,            -- 
24d0: 6e 61 6d 65 20 6f 66 20 74 68 65 20 6f 62 6a 65  name of the obje
24e0: 63 74 0a 20 20 6f 62 6a 74 79 70 65 20 54 45 58  ct.  objtype TEX
24f0: 54 2c 20 20 20 20 20 20 20 20 20 20 20 20 2d 2d  T,            --
2500: 20 6f 62 6a 65 63 74 20 74 79 70 65 0a 20 20 62   object type.  b
2510: 6f 75 6e 64 61 72 79 20 42 4c 4f 42 20 20 20 20  oundary BLOB    
2520: 20 20 20 20 20 20 20 20 2d 2d 20 64 65 74 61 69          -- detai
2530: 6c 65 64 20 62 6f 75 6e 64 61 72 79 20 6f 66 20  led boundary of 
2540: 6f 62 6a 65 63 74 0a 29 3b 0a 3c 2f 70 72 65 3e  object.);.</pre>
2550: 3c 2f 62 6c 6f 63 6b 71 75 6f 74 65 3e 29 5e 0a  </blockquote>)^.
2560: 0a 3c 70 3e 0a 49 6e 20 74 68 69 73 20 65 78 61  .<p>.In this exa
2570: 6d 70 6c 65 2c 20 74 68 65 20 64 65 6d 6f 5f 64  mple, the demo_d
2580: 61 74 61 2e 62 6f 75 6e 64 61 72 79 20 66 69 65  ata.boundary fie
2590: 6c 64 20 69 73 20 69 6e 74 65 6e 64 65 64 20 74  ld is intended t
25a0: 6f 20 68 6f 6c 64 20 73 6f 6d 65 0a 6b 69 6e 64  o hold some.kind
25b0: 20 6f 66 20 62 69 6e 61 72 79 20 72 65 70 72 65   of binary repre
25c0: 73 65 6e 74 61 74 69 6f 6e 20 6f 66 20 74 68 65  sentation of the
25d0: 20 70 72 65 63 69 73 65 20 62 6f 75 6e 64 61 72   precise boundar
25e0: 69 65 73 20 6f 66 20 74 68 65 20 6f 62 6a 65 63  ies of the objec
25f0: 74 2e 0a 54 68 65 20 52 2a 54 72 65 65 20 69 6e  t..The R*Tree in
2600: 64 65 78 20 6f 6e 6c 79 20 68 6f 6c 64 73 20 61  dex only holds a
2610: 6e 20 61 78 69 73 2d 61 6c 69 67 6e 65 64 20 72  n axis-aligned r
2620: 65 63 74 61 6e 67 75 6c 61 72 20 62 6f 75 6e 64  ectangular bound
2630: 61 72 79 20 66 6f 72 20 74 68 65 0a 6f 62 6a 65  ary for the.obje
2640: 63 74 2e 20 20 54 68 65 20 52 2a 54 72 65 65 20  ct.  The R*Tree 
2650: 62 6f 75 6e 64 61 72 79 20 69 73 20 6a 75 73 74  boundary is just
2660: 20 61 6e 20 61 70 70 72 6f 78 69 6d 61 74 69 6f   an approximatio
2670: 6e 20 6f 66 20 74 68 65 20 74 72 75 65 20 6f 62  n of the true ob
2680: 6a 65 63 74 0a 62 6f 75 6e 64 61 72 79 2e 20 20  ject.boundary.  
2690: 53 6f 20 77 68 61 74 20 74 79 70 69 63 61 6c 6c  So what typicall
26a0: 79 20 68 61 70 70 65 6e 73 20 69 73 20 74 68 61  y happens is tha
26b0: 74 20 74 68 65 20 52 2a 54 72 65 65 20 69 6e 64  t the R*Tree ind
26c0: 65 78 20 69 73 20 75 73 65 64 20 74 6f 0a 6e 61  ex is used to.na
26d0: 72 72 6f 77 20 61 20 73 65 61 72 63 68 20 64 6f  rrow a search do
26e0: 77 6e 20 74 6f 20 61 20 6c 69 73 74 20 6f 66 20  wn to a list of 
26f0: 63 61 6e 64 69 64 61 74 65 20 6f 62 6a 65 63 74  candidate object
2700: 73 20 61 6e 64 20 74 68 65 6e 20 6d 6f 72 65 20  s and then more 
2710: 64 65 74 61 69 6c 65 64 0a 61 6e 64 20 65 78 70  detailed.and exp
2720: 65 6e 73 69 76 65 20 63 6f 6d 70 75 74 61 74 69  ensive computati
2730: 6f 6e 73 20 61 72 65 20 64 6f 6e 65 20 6f 6e 20  ons are done on 
2740: 65 61 63 68 20 63 61 6e 64 69 64 61 74 65 20 74  each candidate t
2750: 6f 20 66 69 6e 64 20 69 66 20 74 68 65 0a 63 61  o find if the.ca
2760: 6e 64 69 64 61 74 65 20 74 72 75 6c 79 20 6d 65  ndidate truly me
2770: 65 74 73 20 74 68 65 20 73 65 61 72 63 68 20 63  ets the search c
2780: 72 69 74 65 72 69 61 2e 0a 3c 2f 70 3e 0a 0a 3c  riteria..</p>..<
2790: 62 6c 6f 63 6b 71 75 6f 74 65 3e 3c 70 3e 0a 3c  blockquote><p>.<
27a0: 73 74 72 6f 6e 67 3e 4b 65 79 20 50 6f 69 6e 74  strong>Key Point
27b0: 3a 3c 2f 73 74 72 6f 6e 67 3e 0a 41 6e 20 52 2a  :</strong>.An R*
27c0: 54 72 65 65 20 69 6e 64 65 78 20 64 6f 65 73 20  Tree index does 
27d0: 6e 6f 74 20 6e 6f 72 6d 61 6c 6c 79 20 70 72 6f  not normally pro
27e0: 76 69 64 65 20 74 68 65 20 65 78 61 63 74 20 61  vide the exact a
27f0: 6e 73 77 65 72 20 62 75 74 20 6d 65 72 65 6c 79  nswer but merely
2800: 0a 72 65 64 75 63 65 73 20 74 68 65 20 73 65 74  .reduces the set
2810: 20 6f 66 20 70 6f 74 65 6e 74 69 61 6c 20 61 6e   of potential an
2820: 73 77 65 72 73 20 66 72 6f 6d 20 6d 69 6c 6c 69  swers from milli
2830: 6f 6e 73 20 74 6f 20 64 6f 7a 65 6e 73 2e 0a 3c  ons to dozens..<
2840: 2f 70 3e 3c 2f 62 6c 6f 63 6b 71 75 6f 74 65 3e  /p></blockquote>
2850: 0a 0a 3c 70 3e 0a 53 75 70 70 6f 73 65 20 74 68  ..<p>.Suppose th
2860: 65 20 64 65 6d 6f 5f 64 61 74 61 2e 62 6f 75 6e  e demo_data.boun
2870: 64 61 72 79 20 66 69 65 6c 64 20 68 6f 6c 64 73  dary field holds
2880: 20 73 6f 6d 65 20 70 72 6f 70 72 69 65 74 61 72   some proprietar
2890: 79 20 64 61 74 61 20 64 65 73 63 72 69 70 74 69  y data descripti
28a0: 6f 6e 0a 6f 66 20 61 20 63 6f 6d 70 6c 65 78 20  on.of a complex 
28b0: 74 77 6f 2d 64 69 6d 65 6e 73 69 6f 6e 61 6c 20  two-dimensional 
28c0: 62 6f 75 6e 64 61 72 79 20 66 6f 72 20 61 6e 20  boundary for an 
28d0: 6f 62 6a 65 63 74 20 61 6e 64 20 73 75 70 70 6f  object and suppo
28e0: 73 65 20 74 68 61 74 20 74 68 65 0a 61 70 70 6c  se that the.appl
28f0: 69 63 61 74 69 6f 6e 20 68 61 73 20 75 73 65 64  ication has used
2900: 20 74 68 65 20 5b 73 71 6c 69 74 65 33 5f 63 72   the [sqlite3_cr
2910: 65 61 74 65 5f 66 75 6e 63 74 69 6f 6e 28 29 5d  eate_function()]
2920: 20 69 6e 74 65 72 66 61 63 65 20 74 6f 0a 63 72   interface to.cr
2930: 65 61 74 65 64 20 61 70 70 6c 69 63 61 74 69 6f  eated applicatio
2940: 6e 2d 64 65 66 69 6e 65 64 20 66 75 6e 63 74 69  n-defined functi
2950: 6f 6e 73 20 22 63 6f 6e 74 61 69 6e 65 64 5f 69  ons "contained_i
2960: 6e 22 20 61 6e 64 0a 22 6f 76 65 72 6c 61 70 73  n" and."overlaps
2970: 22 20 61 63 63 65 70 74 69 6e 67 20 74 77 6f 20  " accepting two 
2980: 64 65 6d 6f 5f 64 61 74 61 2e 62 6f 75 6e 64 61  demo_data.bounda
2990: 72 79 20 6f 62 6a 65 63 74 73 20 61 6e 64 20 72  ry objects and r
29a0: 65 74 75 72 6e 20 74 72 75 65 20 6f 72 20 66 61  eturn true or fa
29b0: 6c 73 65 2e 0a 4f 6e 65 20 6d 61 79 20 61 73 73  lse..One may ass
29c0: 75 6d 65 20 74 68 61 74 20 22 63 6f 6e 74 61 69  ume that "contai
29d0: 6e 65 64 5f 69 6e 22 20 61 6e 64 20 22 6f 76 65  ned_in" and "ove
29e0: 72 6c 61 70 73 22 20 61 72 65 20 72 65 6c 61 74  rlaps" are relat
29f0: 69 76 65 6c 79 20 73 6c 6f 77 0a 66 75 6e 63 74  ively slow.funct
2a00: 69 6f 6e 73 20 74 68 61 74 20 77 65 20 64 6f 20  ions that we do 
2a10: 6e 6f 74 20 77 61 6e 74 20 74 6f 20 69 6e 76 6f  not want to invo
2a20: 6b 65 20 74 6f 6f 20 66 72 65 71 75 65 6e 74 6c  ke too frequentl
2a30: 79 2e 0a 5e 28 54 68 65 6e 20 61 6e 20 65 66 66  y..^(Then an eff
2a40: 69 63 69 65 6e 74 20 77 61 79 20 74 6f 20 66 69  icient way to fi
2a50: 6e 64 20 74 68 65 20 6e 61 6d 65 20 6f 66 20 61  nd the name of a
2a60: 6c 6c 20 6f 62 6a 65 63 74 73 20 6c 6f 63 61 74  ll objects locat
2a70: 65 64 20 77 69 74 68 69 6e 0a 74 68 65 20 4e 6f  ed within.the No
2a80: 72 74 68 20 43 61 72 6f 6c 69 6e 61 20 31 32 74  rth Carolina 12t
2a90: 68 20 44 69 73 74 72 69 63 74 2c 20 6f 6e 65 20  h District, one 
2aa0: 6d 61 79 20 62 65 20 74 6f 20 72 75 6e 20 61 20  may be to run a 
2ab0: 71 75 65 72 79 20 6c 69 6b 65 20 74 68 69 73 3a  query like this:
2ac0: 0a 3c 2f 70 3e 0a 0a 3c 62 6c 6f 63 6b 71 75 6f  .</p>..<blockquo
2ad0: 74 65 3e 3c 70 72 65 3e 0a 53 45 4c 45 43 54 20  te><pre>.SELECT 
2ae0: 6f 62 6a 6e 61 6d 65 20 46 52 4f 4d 20 64 65 6d  objname FROM dem
2af0: 6f 5f 64 61 74 61 2c 20 64 65 6d 6f 5f 69 6e 64  o_data, demo_ind
2b00: 65 78 0a 20 57 48 45 52 45 20 64 65 6d 6f 5f 64  ex. WHERE demo_d
2b10: 61 74 61 2e 69 64 3d 64 65 6d 6f 5f 69 6e 64 65  ata.id=demo_inde
2b20: 78 2e 69 64 0a 20 20 20 41 4e 44 20 63 6f 6e 74  x.id.   AND cont
2b30: 61 69 6e 65 64 5f 69 6e 28 64 65 6d 6f 5f 64 61  ained_in(demo_da
2b40: 74 61 2e 62 6f 75 6e 64 61 72 79 2c 20 3a 62 6f  ta.boundary, :bo
2b50: 75 6e 64 61 72 79 29 0a 20 20 20 41 4e 44 20 6d  undary).   AND m
2b60: 69 6e 58 3e 3d 2d 38 31 2e 30 20 41 4e 44 20 6d  inX>=-81.0 AND m
2b70: 61 78 58 3c 3d 2d 37 39 2e 36 0a 20 20 20 41 4e  axX<=-79.6.   AN
2b80: 44 20 6d 69 6e 59 3e 3d 33 35 2e 30 20 41 4e 44  D minY>=35.0 AND
2b90: 20 6d 61 78 59 3c 3d 33 36 2e 32 3b 0a 3c 2f 70   maxY<=36.2;.</p
2ba0: 72 65 3e 3c 2f 62 6c 6f 63 6b 71 75 6f 74 65 3e  re></blockquote>
2bb0: 29 5e 0a 0a 3c 70 3e 49 6e 20 74 68 65 20 71 75  )^..<p>In the qu
2bc0: 65 72 79 20 61 62 6f 76 65 2c 20 6f 6e 65 20 77  ery above, one w
2bd0: 6f 75 6c 64 20 70 72 65 73 75 6d 61 62 6c 79 20  ould presumably 
2be0: 62 69 6e 64 20 74 68 65 20 62 69 6e 61 72 79 20  bind the binary 
2bf0: 42 4c 4f 42 20 0a 64 65 73 63 72 69 70 74 69 6f  BLOB .descriptio
2c00: 6e 20 6f 66 20 74 68 65 20 70 72 65 63 69 73 65  n of the precise
2c10: 20 62 6f 75 6e 64 61 72 79 20 6f 66 20 74 68 65   boundary of the
2c20: 20 31 32 74 68 20 64 69 73 74 72 69 63 74 20 74   12th district t
2c30: 6f 20 74 68 65 0a 22 3a 62 6f 75 6e 64 61 72 79  o the.":boundary
2c40: 22 20 70 61 72 61 6d 65 74 65 72 2e 3c 2f 70 3e  " parameter.</p>
2c50: 0a 0a 3c 70 3e 4e 6f 74 69 63 65 20 68 6f 77 20  ..<p>Notice how 
2c60: 74 68 65 20 71 75 65 72 79 20 61 62 6f 76 65 20  the query above 
2c70: 77 6f 72 6b 73 3a 20 20 54 68 65 20 52 2a 54 72  works:  The R*Tr
2c80: 65 65 20 69 6e 64 65 78 20 72 75 6e 73 20 69 6e  ee index runs in
2c90: 20 74 68 65 20 6f 75 74 65 72 0a 6c 6f 6f 70 20   the outer.loop 
2ca0: 74 6f 20 66 69 6e 64 20 65 6e 74 72 69 65 73 20  to find entries 
2cb0: 74 68 61 74 20 61 72 65 20 63 6f 6e 74 61 69 6e  that are contain
2cc0: 65 64 20 77 69 74 68 69 6e 20 74 68 65 20 62 6f  ed within the bo
2cd0: 75 6e 64 69 6e 67 20 62 6f 78 0a 6f 66 20 6c 6f  unding box.of lo
2ce0: 6e 67 69 74 75 64 65 20 2d 38 31 2e 2e 2d 37 39  ngitude -81..-79
2cf0: 2e 36 20 61 6e 64 20 6c 61 74 69 74 75 64 65 20  .6 and latitude 
2d00: 33 35 2e 30 2e 2e 33 36 2e 32 2e 20 0a 46 6f 72  35.0..36.2. .For
2d10: 20 65 61 63 68 20 6f 62 6a 65 63 74 20 69 64 65   each object ide
2d20: 6e 74 69 66 69 65 72 20 66 6f 75 6e 64 2c 20 53  ntifier found, S
2d30: 51 4c 69 74 65 20 6c 6f 6f 6b 73 20 75 70 0a 74  QLite looks up.t
2d40: 68 65 20 63 6f 72 72 65 73 70 6f 6e 64 69 6e 67  he corresponding
2d50: 20 65 6e 74 72 79 20 69 6e 20 74 68 65 20 64 65   entry in the de
2d60: 6d 6f 5f 64 61 74 61 20 74 61 62 6c 65 2e 20 20  mo_data table.  
2d70: 49 74 20 74 68 65 6e 20 75 73 65 73 20 74 68 65  It then uses the
2d80: 20 62 6f 75 6e 64 61 72 79 0a 66 69 65 6c 64 20   boundary.field 
2d90: 66 72 6f 6d 20 74 68 65 20 64 65 6d 6f 5f 64 61  from the demo_da
2da0: 74 61 20 74 61 62 6c 65 20 61 73 20 61 20 70 61  ta table as a pa
2db0: 72 61 6d 65 74 65 72 20 74 6f 20 74 68 65 20 63  rameter to the c
2dc0: 6f 6e 74 61 69 6e 65 64 5f 69 6e 28 29 0a 66 75  ontained_in().fu
2dd0: 6e 63 74 69 6f 6e 20 61 6e 64 20 69 66 20 74 68  nction and if th
2de0: 61 74 20 66 75 6e 63 74 69 6f 6e 20 72 65 74 75  at function retu
2df0: 72 6e 73 20 74 72 75 65 2c 20 74 68 65 20 6f 62  rns true, the ob
2e00: 6a 6e 61 6d 65 20 66 69 65 6c 64 20 66 72 6f 6d  jname field from
2e10: 0a 74 68 65 20 64 65 6d 6f 5f 64 61 74 61 20 74  .the demo_data t
2e20: 61 62 6c 65 20 69 73 20 72 65 74 75 72 6e 65 64  able is returned
2e30: 20 61 73 20 74 68 65 20 6e 65 78 74 20 72 6f 77   as the next row
2e40: 20 6f 66 20 71 75 65 72 79 20 72 65 73 75 6c 74   of query result
2e50: 2e 3c 2f 70 3e 0a 0a 3c 70 3e 4f 6e 65 20 77 6f  .</p>..<p>One wo
2e60: 75 6c 64 20 67 65 74 20 74 68 65 20 73 61 6d 65  uld get the same
2e70: 20 61 6e 73 77 65 72 20 77 69 74 68 6f 75 74 20   answer without 
2e80: 74 68 65 20 75 73 65 20 6f 66 20 74 68 65 20 52  the use of the R
2e90: 2a 54 72 65 65 20 69 6e 64 65 78 0a 75 73 69 6e  *Tree index.usin
2ea0: 67 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20  g the following 
2eb0: 73 69 6d 70 6c 65 72 20 71 75 65 72 79 3a 3c 2f  simpler query:</
2ec0: 70 3e 0a 0a 3c 62 6c 6f 63 6b 71 75 6f 74 65 3e  p>..<blockquote>
2ed0: 3c 70 72 65 3e 0a 53 45 4c 45 43 54 20 6f 62 6a  <pre>.SELECT obj
2ee0: 6e 61 6d 65 20 46 52 4f 4d 20 64 65 6d 6f 5f 64  name FROM demo_d
2ef0: 61 74 61 0a 20 57 48 45 52 45 20 63 6f 6e 74 61  ata. WHERE conta
2f00: 69 6e 65 64 5f 69 6e 28 64 65 6d 6f 5f 64 61 74  ined_in(demo_dat
2f10: 61 2e 62 6f 75 6e 64 61 72 79 2c 20 3a 62 6f 75  a.boundary, :bou
2f20: 6e 64 61 72 79 29 3b 0a 3c 2f 70 72 65 3e 3c 2f  ndary);.</pre></
2f30: 62 6c 6f 63 6b 71 75 6f 74 65 3e 0a 0a 3c 70 3e  blockquote>..<p>
2f40: 54 68 65 20 70 72 6f 62 6c 65 6d 20 77 69 74 68  The problem with
2f50: 20 74 68 69 73 20 6c 61 74 74 65 72 20 71 75 65   this latter que
2f60: 72 79 20 69 73 20 74 68 61 74 20 69 74 20 6d 75  ry is that it mu
2f70: 73 74 20 61 70 70 6c 79 20 74 68 65 0a 63 6f 6e  st apply the.con
2f80: 74 61 69 6e 65 64 5f 69 6e 28 29 20 66 75 6e 63  tained_in() func
2f90: 74 69 6f 6e 20 74 6f 20 6d 69 6c 6c 69 6f 6e 73  tion to millions
2fa0: 20 6f 66 20 65 6e 74 72 69 65 73 20 69 6e 20 74   of entries in 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 2e 0a 54 68 65 20 75 73 65 20 6f 66 20 74  le..The use of t
2fd0: 68 65 20 52 2a 54 72 65 65 20 69 6e 20 74 68 65  he R*Tree in the
2fe0: 20 70 65 6e 75 6c 74 69 6d 61 74 65 20 71 75 65   penultimate que
2ff0: 72 79 20 72 65 64 75 63 65 73 20 74 68 65 20 6e  ry reduces the n
3000: 75 6d 62 65 72 20 6f 66 0a 63 61 6c 6c 73 20 74  umber of.calls t
3010: 6f 20 63 6f 6e 74 61 69 6e 65 64 5f 69 6e 28 29  o contained_in()
3020: 20 66 75 6e 63 74 69 6f 6e 20 74 6f 20 61 20 73   function to a s
3030: 6d 61 6c 6c 20 73 75 62 73 65 74 20 6f 66 20 74  mall subset of t
3040: 68 65 20 65 6e 74 69 72 65 20 74 61 62 6c 65 2e  he entire table.
3050: 0a 54 68 65 20 52 2a 54 72 65 65 20 69 6e 64 65  .The R*Tree inde
3060: 78 20 64 69 64 20 6e 6f 74 20 66 69 6e 64 20 74  x did not find t
3070: 68 65 20 65 78 61 63 74 20 61 6e 73 77 65 72 20  he exact answer 
3080: 69 74 73 65 6c 66 2c 20 69 74 20 6d 65 72 65 6c  itself, it merel
3090: 79 0a 6c 69 6d 69 74 65 64 20 74 68 65 20 73 65  y.limited the se
30a0: 61 72 63 68 20 73 70 61 63 65 2e 3c 2f 70 3e 0a  arch space.</p>.
30b0: 0a 3c 74 63 6c 3e 68 64 5f 66 72 61 67 6d 65 6e  .<tcl>hd_fragmen
30c0: 74 20 7b 69 6e 74 72 74 72 65 65 7d 20 7b 69 6e  t {intrtree} {in
30d0: 74 65 67 65 72 2d 76 61 6c 75 65 64 20 72 2d 74  teger-valued r-t
30e0: 72 65 65 73 7d 3c 2f 74 63 6c 3e 0a 3c 68 32 3e  rees}</tcl>.<h2>
30f0: 35 2e 30 20 49 6e 74 65 67 65 72 2d 56 61 6c 75  5.0 Integer-Valu
3100: 65 64 20 52 2d 54 72 65 65 73 3c 2f 68 32 3e 0a  ed R-Trees</h2>.
3110: 0a 3c 70 3e 0a 54 68 65 20 64 65 66 61 75 6c 74  .<p>.The default
3120: 20 76 69 72 74 75 61 6c 20 74 61 62 6c 65 20 28   virtual table (
3130: 22 72 74 72 65 65 22 29 20 6e 6f 72 6d 61 6c 6c  "rtree") normall
3140: 79 20 73 74 6f 72 65 73 20 63 6f 6f 72 64 69 6e  y stores coordin
3150: 61 74 65 73 20 61 73 0a 73 69 6e 67 6c 65 2d 70  ates as.single-p
3160: 72 65 63 69 73 69 6f 6e 20 28 34 2d 62 79 74 65  recision (4-byte
3170: 29 20 66 6c 6f 61 74 69 6e 67 20 70 6f 69 6e 74  ) floating point
3180: 20 6e 75 6d 62 65 72 73 2e 20 20 49 66 20 69 6e   numbers.  If in
3190: 74 65 67 65 72 20 63 6f 6f 72 64 69 6e 61 74 65  teger coordinate
31a0: 73 0a 61 72 65 20 64 65 73 69 72 65 64 2c 20 64  s.are desired, d
31b0: 65 63 6c 61 72 65 20 74 68 65 20 74 61 62 6c 65  eclare the table
31c0: 20 75 73 69 6e 67 20 22 72 74 72 65 65 5f 69 33   using "rtree_i3
31d0: 32 22 20 69 6e 73 74 65 61 64 3a 0a 0a 3c 62 6c  2" instead:..<bl
31e0: 6f 63 6b 71 75 6f 74 65 3e 3c 70 72 65 3e 0a 43  ockquote><pre>.C
31f0: 52 45 41 54 45 20 56 49 52 54 55 41 4c 20 54 41  REATE VIRTUAL TA
3200: 42 4c 45 20 69 6e 74 72 74 72 65 65 20 55 53 49  BLE intrtree USI
3210: 4e 47 20 72 74 72 65 65 5f 69 33 32 28 69 64 2c  NG rtree_i32(id,
3220: 78 30 2c 78 31 2c 79 30 2c 79 31 2c 7a 30 2c 7a  x0,x1,y0,y1,z0,z
3230: 31 29 3b 0a 3c 2f 70 72 65 3e 3c 2f 62 6c 6f 63  1);.</pre></bloc
3240: 6b 71 75 6f 74 65 3e 0a 0a 3c 70 3e 0a 41 6e 20  kquote>..<p>.An 
3250: 72 74 72 65 65 5f 69 33 32 20 73 74 6f 72 65 73  rtree_i32 stores
3260: 20 63 6f 6f 72 64 69 6e 61 74 65 73 20 61 73 20   coordinates as 
3270: 33 32 2d 62 69 74 20 73 69 67 6e 65 64 20 69 6e  32-bit signed in
3280: 74 65 67 65 72 73 2e 20 20 42 75 74 20 69 74 20  tegers.  But it 
3290: 73 74 69 6c 6c 0a 75 73 69 6e 67 20 66 6c 6f 61  still.using floa
32a0: 74 69 6e 67 20 70 6f 69 6e 74 20 63 6f 6d 70 75  ting point compu
32b0: 74 61 74 69 6f 6e 73 20 69 6e 74 65 72 6e 61 6c  tations internal
32c0: 6c 79 20 61 73 20 70 61 72 74 20 6f 66 20 74 68  ly as part of th
32d0: 65 20 72 2d 74 72 65 65 20 61 6c 67 6f 72 69 74  e r-tree algorit
32e0: 68 6d 2e 0a 46 6f 72 20 61 70 70 6c 69 63 61 74  hm..For applicat
32f0: 69 6f 6e 73 20 72 75 6e 6e 69 6e 67 20 6f 6e 20  ions running on 
3300: 70 72 6f 63 65 73 73 6f 72 73 20 77 69 74 68 6f  processors witho
3310: 75 74 20 68 61 72 64 77 61 72 65 20 66 6c 6f 61  ut hardware floa
3320: 74 69 6e 67 20 70 6f 69 6e 74 2c 0a 69 74 20 6d  ting point,.it m
3330: 69 67 68 74 20 62 65 20 64 65 73 69 72 61 62 6c  ight be desirabl
3340: 65 20 74 6f 20 68 61 76 65 20 61 20 70 75 72 65  e to have a pure
3350: 20 69 6e 74 65 67 65 72 20 69 6d 70 6c 65 6d 65   integer impleme
3360: 6e 74 61 74 69 6f 6e 20 6f 66 20 72 2d 74 72 65  ntation of r-tre
3370: 65 73 2e 0a 54 68 69 73 20 69 73 20 61 63 63 6f  es..This is acco
3380: 6d 70 6c 69 73 68 65 64 20 62 79 20 63 6f 6d 70  mplished by comp
3390: 69 6c 69 6e 67 20 77 69 74 68 20 74 68 65 20 5b  iling with the [
33a0: 53 51 4c 49 54 45 5f 52 54 52 45 45 5f 49 4e 54  SQLITE_RTREE_INT
33b0: 5f 4f 4e 4c 59 5d 20 6f 70 74 69 6f 6e 2e 0a 57  _ONLY] option..W
33c0: 68 65 6e 20 53 51 4c 49 54 45 5f 52 54 52 45 45  hen SQLITE_RTREE
33d0: 5f 49 4e 54 5f 4f 4e 4c 59 20 69 73 20 75 73 65  _INT_ONLY is use
33e0: 64 2c 20 62 6f 74 68 20 74 68 65 20 22 72 74 72  d, both the "rtr
33f0: 65 65 22 20 61 6e 64 20 74 68 65 20 22 72 74 72  ee" and the "rtr
3400: 65 65 5f 69 33 32 22 0a 76 69 72 74 75 61 6c 20  ee_i32".virtual 
3410: 74 61 62 6c 65 73 20 73 74 6f 72 65 20 33 32 2d  tables store 32-
3420: 62 69 74 20 69 6e 74 65 67 65 72 73 20 61 6e 64  bit integers and
3430: 20 6f 6e 6c 79 20 69 6e 74 65 67 65 72 20 76 61   only integer va
3440: 6c 75 65 73 20 61 72 65 20 75 73 65 64 20 66 6f  lues are used fo
3450: 72 0a 69 6e 74 65 72 6e 61 6c 20 63 6f 6d 70 75  r.internal compu
3460: 74 61 74 69 6f 6e 73 2e 0a 0a 3c 74 63 6c 3e 68  tations...<tcl>h
3470: 64 5f 66 72 61 67 6d 65 6e 74 20 7b 63 75 73 74  d_fragment {cust
3480: 6f 6d 71 75 65 72 79 7d 20 7b 63 75 73 74 6f 6d  omquery} {custom
3490: 20 72 2d 74 72 65 65 20 71 75 65 72 69 65 73 7d   r-tree queries}
34a0: 3c 2f 74 63 6c 3e 0a 3c 68 32 3e 36 2e 30 20 43  </tcl>.<h2>6.0 C
34b0: 75 73 74 6f 6d 20 52 2d 54 72 65 65 20 51 75 65  ustom R-Tree Que
34c0: 72 69 65 73 3c 2f 68 32 3e 0a 0a 3c 70 3e 42 79  ries</h2>..<p>By
34d0: 20 75 73 69 6e 67 20 73 74 61 6e 64 61 72 64 20   using standard 
34e0: 53 51 4c 20 65 78 70 72 65 73 73 69 6f 6e 73 20  SQL expressions 
34f0: 69 6e 20 74 68 65 20 57 48 45 52 45 20 63 6c 61  in the WHERE cla
3500: 75 73 65 20 6f 66 20 61 20 53 45 4c 45 43 54 20  use of a SELECT 
3510: 71 75 65 72 79 2c 0a 61 20 70 72 6f 67 72 61 6d  query,.a program
3520: 6d 65 72 20 63 61 6e 20 71 75 65 72 79 20 66 6f  mer can query fo
3530: 72 20 61 6c 6c 20 52 2a 54 72 65 65 20 65 6e 74  r all R*Tree ent
3540: 72 69 65 73 20 74 68 61 74 20 68 61 76 65 20 61  ries that have a
3550: 20 73 70 61 74 69 61 6c 20 72 65 6c 61 74 69 6f   spatial relatio
3560: 6e 73 68 69 70 0a 28 74 68 65 79 20 69 6e 74 65  nship.(they inte
3570: 72 73 65 63 74 20 77 69 74 68 20 6f 72 20 61 72  rsect with or ar
3580: 65 20 63 6f 6e 74 61 69 6e 65 64 20 77 69 74 68  e contained with
3590: 69 6e 29 20 61 20 70 61 72 74 69 63 75 6c 61 72  in) a particular
35a0: 20 62 6f 75 6e 64 69 6e 67 2d 62 6f 78 2e 0a 43   bounding-box..C
35b0: 75 73 74 6f 6d 20 52 2a 54 72 65 65 20 71 75 65  ustom R*Tree que
35c0: 72 69 65 73 2c 20 75 73 69 6e 67 20 74 68 65 20  ries, using the 
35d0: 4d 41 54 43 48 0a 6f 70 65 72 61 74 6f 72 20 69  MATCH.operator i
35e0: 6e 20 74 68 65 20 57 48 45 52 45 20 63 6c 61 75  n the WHERE clau
35f0: 73 65 20 6f 66 20 61 20 53 45 4c 45 43 54 2c 20  se of a SELECT, 
3600: 61 6c 6c 6f 77 20 74 68 65 20 70 72 6f 67 72 61  allow the progra
3610: 6d 6d 65 72 20 74 6f 20 71 75 65 72 79 20 66 6f  mmer to query fo
3620: 72 20 0a 74 68 65 20 73 65 74 20 6f 66 20 52 2a  r .the set of R*
3630: 54 72 65 65 20 65 6e 74 72 69 65 73 20 74 68 61  Tree entries tha
3640: 74 20 69 6e 74 65 72 73 65 63 74 20 61 6e 79 20  t intersect any 
3650: 61 72 62 69 74 72 61 72 79 20 72 65 67 69 6f 6e  arbitrary region
3660: 20 6f 72 20 73 68 61 70 65 2c 20 6e 6f 74 20 0a   or shape, not .
3670: 6a 75 73 74 20 61 20 62 6f 78 2e 20 20 54 68 69  just a box.  Thi
3680: 73 20 63 61 70 61 62 69 6c 69 74 79 20 69 73 20  s capability is 
3690: 75 73 65 66 75 6c 2c 20 66 6f 72 20 65 78 61 6d  useful, for exam
36a0: 70 6c 65 2c 20 69 6e 20 63 6f 6d 70 75 74 69 6e  ple, in computin
36b0: 67 20 74 68 65 20 0a 73 75 62 73 65 74 20 6f 66  g the .subset of
36c0: 20 6f 62 6a 65 63 74 73 20 69 6e 20 74 68 65 20   objects in the 
36d0: 52 2a 54 72 65 65 20 74 68 61 74 20 61 72 65 20  R*Tree that are 
36e0: 76 69 73 69 62 6c 65 20 66 72 6f 6d 20 61 20 63  visible from a c
36f0: 61 6d 65 72 61 20 70 6f 73 69 74 69 6f 6e 65 64  amera positioned
3700: 20 0a 69 6e 20 33 2d 44 20 73 70 61 63 65 2e 0a   .in 3-D space..
3710: 0a 3c 70 3e 52 65 67 69 6f 6e 73 20 66 6f 72 20  .<p>Regions for 
3720: 63 75 73 74 6f 6d 20 52 2a 54 72 65 65 20 71 75  custom R*Tree qu
3730: 65 72 69 65 73 20 61 72 65 20 64 65 66 69 6e 65  eries are define
3740: 64 20 62 79 20 52 2a 54 72 65 65 20 67 65 6f 6d  d by R*Tree geom
3750: 65 74 72 79 20 63 61 6c 6c 62 61 63 6b 73 0a 69  etry callbacks.i
3760: 6d 70 6c 65 6d 65 6e 74 65 64 20 62 79 20 74 68  mplemented by th
3770: 65 20 61 70 70 6c 69 63 61 74 69 6f 6e 20 61 6e  e application an
3780: 64 20 72 65 67 69 73 74 65 72 65 64 20 77 69 74  d registered wit
3790: 68 20 53 51 4c 69 74 65 20 76 69 61 20 61 20 63  h SQLite via a c
37a0: 61 6c 6c 20 74 6f 20 6f 6e 65 0a 6f 66 20 74 68  all to one.of th
37b0: 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 74 77 6f 20  e following two 
37c0: 41 50 49 73 3a 0a 0a 3c 62 6c 6f 63 6b 71 75 6f  APIs:..<blockquo
37d0: 74 65 3e 3c 70 72 65 3e 0a 69 6e 74 20 73 71 6c  te><pre>.int sql
37e0: 69 74 65 33 5f 72 74 72 65 65 5f 71 75 65 72 79  ite3_rtree_query
37f0: 5f 63 61 6c 6c 62 61 63 6b 28 0a 20 20 73 71 6c  _callback(.  sql
3800: 69 74 65 33 20 2a 64 62 2c 0a 20 20 63 6f 6e 73  ite3 *db,.  cons
3810: 74 20 63 68 61 72 20 2a 7a 51 75 65 72 79 46 75  t char *zQueryFu
3820: 6e 63 2c 0a 20 20 69 6e 74 20 28 2a 78 51 75 65  nc,.  int (*xQue
3830: 72 79 46 75 6e 63 29 28 73 71 6c 69 74 65 33 5f  ryFunc)(sqlite3_
3840: 72 74 72 65 65 5f 71 75 65 72 79 5f 69 6e 66 6f  rtree_query_info
3850: 2a 29 2c 0a 20 20 76 6f 69 64 20 2a 70 43 6f 6e  *),.  void *pCon
3860: 74 65 78 74 2c 0a 20 20 76 6f 69 64 20 28 2a 78  text,.  void (*x
3870: 44 65 73 74 72 75 63 74 6f 72 29 28 76 6f 69 64  Destructor)(void
3880: 2a 29 0a 29 3b 0a 69 6e 74 20 73 71 6c 69 74 65  *).);.int sqlite
3890: 33 5f 72 74 72 65 65 5f 67 65 6f 6d 65 74 72 79  3_rtree_geometry
38a0: 5f 63 61 6c 6c 62 61 63 6b 28 0a 20 20 73 71 6c  _callback(.  sql
38b0: 69 74 65 33 20 2a 64 62 2c 0a 20 20 63 6f 6e 73  ite3 *db,.  cons
38c0: 74 20 63 68 61 72 20 2a 7a 47 65 6f 6d 2c 0a 20  t char *zGeom,. 
38d0: 20 69 6e 74 20 28 2a 78 47 65 6f 6d 29 28 73 71   int (*xGeom)(sq
38e0: 6c 69 74 65 33 5f 72 74 72 65 65 5f 67 65 6f 6d  lite3_rtree_geom
38f0: 65 74 72 79 20 2a 2c 20 69 6e 74 20 6e 43 6f 6f  etry *, int nCoo
3900: 72 64 2c 20 64 6f 75 62 6c 65 20 2a 61 43 6f 6f  rd, double *aCoo
3910: 72 64 2c 20 69 6e 74 20 2a 70 52 65 73 29 2c 0a  rd, int *pRes),.
3920: 20 20 76 6f 69 64 20 2a 70 43 6f 6e 74 65 78 74    void *pContext
3930: 0a 29 3b 0a 3c 2f 70 72 65 3e 3c 2f 62 6c 6f 63  .);.</pre></bloc
3940: 6b 71 75 6f 74 65 3e 0a 0a 3c 70 3e 54 68 65 20  kquote>..<p>The 
3950: 73 71 6c 69 74 65 33 5f 72 74 72 65 65 5f 71 75  sqlite3_rtree_qu
3960: 65 72 79 5f 63 61 6c 6c 62 61 63 6b 28 29 20 62  ery_callback() b
3970: 65 63 61 6d 65 20 61 76 61 69 6c 61 62 6c 65 20  ecame available 
3980: 77 69 74 68 20 53 51 4c 69 74 65 0a 5b 76 65 72  with SQLite.[ver
3990: 73 69 6f 6e 20 33 2e 38 2e 35 5d 20 61 6e 64 20  sion 3.8.5] and 
39a0: 69 73 20 74 68 65 20 70 72 65 66 65 72 72 65 64  is the preferred
39b0: 20 69 6e 74 65 72 66 61 63 65 2e 0a 54 68 65 20   interface..The 
39c0: 73 71 6c 69 74 65 33 5f 72 74 72 65 65 5f 67 65  sqlite3_rtree_ge
39d0: 6f 6d 65 74 72 79 5f 63 61 6c 6c 62 61 63 6b 28  ometry_callback(
39e0: 29 20 69 73 20 61 6e 20 6f 6c 64 65 72 20 61 6e  ) is an older an
39f0: 64 20 6c 65 73 73 20 66 6c 65 78 69 62 6c 65 0a  d less flexible.
3a00: 69 6e 74 65 72 66 61 63 65 20 74 68 61 74 20 69  interface that i
3a10: 73 20 73 75 70 70 6f 72 74 65 64 20 66 6f 72 20  s supported for 
3a20: 62 61 63 6b 77 61 72 64 73 20 63 6f 6d 70 61 74  backwards compat
3a30: 69 62 69 6c 69 74 79 2e 0a 0a 3c 70 3e 5e 41 20  ibility...<p>^A 
3a40: 63 61 6c 6c 20 74 6f 20 6f 6e 65 20 6f 66 20 74  call to one of t
3a50: 68 65 20 61 62 6f 76 65 20 41 50 49 73 20 63 72  he above APIs cr
3a60: 65 61 74 65 73 20 61 20 6e 65 77 20 53 51 4c 20  eates a new SQL 
3a70: 66 75 6e 63 74 69 6f 6e 20 6e 61 6d 65 64 20 62  function named b
3a80: 79 20 74 68 65 0a 73 65 63 6f 6e 64 20 70 61 72  y the.second par
3a90: 61 6d 65 74 65 72 20 28 7a 51 75 65 72 79 46 75  ameter (zQueryFu
3aa0: 6e 63 20 6f 72 20 7a 47 65 6f 6d 29 2e 20 20 5e  nc or zGeom).  ^
3ab0: 57 68 65 6e 20 74 68 61 74 20 53 51 4c 20 66 75  When that SQL fu
3ac0: 6e 63 74 69 6f 6e 20 61 70 70 65 61 72 73 0a 6f  nction appears.o
3ad0: 6e 20 74 68 65 20 72 69 67 68 74 2d 68 61 6e 64  n the right-hand
3ae0: 20 73 69 64 65 20 6f 66 20 74 68 65 20 4d 41 54   side of the MAT
3af0: 43 48 20 6f 70 65 72 61 74 6f 72 20 61 6e 64 20  CH operator and 
3b00: 74 68 65 20 6c 65 66 74 2d 68 61 6e 64 20 73 69  the left-hand si
3b10: 64 65 20 6f 66 20 74 68 65 0a 4d 41 54 43 48 20  de of the.MATCH 
3b20: 6f 70 65 72 61 74 6f 72 20 69 73 20 61 6e 79 20  operator is any 
3b30: 63 6f 6c 75 6d 6e 20 69 6e 20 74 68 65 20 52 2a  column in the R*
3b40: 54 72 65 65 20 76 69 72 74 75 61 6c 20 74 61 62  Tree virtual tab
3b50: 6c 65 2c 20 74 68 65 6e 20 74 68 65 20 63 61 6c  le, then the cal
3b60: 6c 62 61 63 6b 20 0a 64 65 66 69 6e 65 64 20 62  lback .defined b
3b70: 79 20 74 68 65 20 74 68 69 72 64 20 61 72 67 75  y the third argu
3b80: 6d 65 6e 74 20 28 78 51 75 65 72 79 46 75 6e 63  ment (xQueryFunc
3b90: 20 6f 72 20 78 47 65 6f 6d 29 20 69 73 20 69 6e   or xGeom) is in
3ba0: 76 6f 6b 65 64 20 74 6f 20 64 65 74 65 72 6d 69  voked to determi
3bb0: 6e 65 0a 69 66 20 61 20 70 61 72 74 69 63 75 6c  ne.if a particul
3bc0: 61 72 20 6f 62 6a 65 63 74 20 6f 72 20 73 75 62  ar object or sub
3bd0: 74 72 65 65 20 6f 76 65 72 6c 61 70 73 20 74 68  tree overlaps th
3be0: 65 20 64 65 73 69 72 65 64 20 72 65 67 69 6f 6e  e desired region
3bf0: 2e 0a 0a 3c 70 3e 5e 28 46 6f 72 20 65 78 61 6d  ...<p>^(For exam
3c00: 70 6c 65 2c 20 61 20 71 75 65 72 79 20 6c 69 6b  ple, a query lik
3c10: 65 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20  e the following 
3c20: 6d 69 67 68 74 20 62 65 20 75 73 65 64 20 74 6f  might be used to
3c30: 20 66 69 6e 64 20 61 6c 6c 0a 52 2a 54 72 65 65   find all.R*Tree
3c40: 20 65 6e 74 72 69 65 73 20 74 68 61 74 20 6f 76   entries that ov
3c50: 65 72 6c 61 70 20 77 69 74 68 20 61 20 63 69 72  erlap with a cir
3c60: 63 6c 65 20 63 65 6e 74 65 72 65 64 20 61 20 34  cle centered a 4
3c70: 35 2e 33 2c 32 32 2e 39 20 77 69 74 68 20 61 0a  5.3,22.9 with a.
3c80: 72 61 64 69 75 73 20 6f 66 20 35 2e 30 3a 0a 0a  radius of 5.0:..
3c90: 3c 62 6c 6f 63 6b 71 75 6f 74 65 3e 3c 70 72 65  <blockquote><pre
3ca0: 3e 0a 53 45 4c 45 43 54 20 69 64 20 46 52 4f 4d  >.SELECT id FROM
3cb0: 20 64 65 6d 6f 5f 69 6e 64 65 78 20 57 48 45 52   demo_index WHER
3cc0: 45 20 69 64 20 4d 41 54 43 48 20 63 69 72 63 6c  E id MATCH circl
3cd0: 65 28 34 35 2e 33 2c 20 32 32 2e 39 2c 20 35 2e  e(45.3, 22.9, 5.
3ce0: 30 29 0a 3c 2f 62 6c 6f 63 6b 71 75 6f 74 65 3e  0).</blockquote>
3cf0: 3c 2f 70 72 65 3e 29 5e 0a 0a 3c 70 3e 5e 54 68  </pre>)^..<p>^Th
3d00: 65 20 53 51 4c 20 73 79 6e 74 61 78 20 66 6f 72  e SQL syntax for
3d10: 20 63 75 73 74 6f 6d 20 71 75 65 72 69 65 73 20   custom queries 
3d20: 69 73 20 74 68 65 20 73 61 6d 65 20 72 65 67 61  is the same rega
3d30: 72 64 6c 65 73 73 20 6f 66 20 77 68 69 63 68 0a  rdless of which.
3d40: 69 6e 74 65 72 66 61 63 65 2c 20 73 71 6c 69 74  interface, sqlit
3d50: 65 33 5f 72 74 72 65 65 5f 67 65 6f 6d 65 74 72  e3_rtree_geometr
3d60: 79 5f 63 61 6c 6c 62 61 63 6b 28 29 20 6f 72 20  y_callback() or 
3d70: 73 71 6c 69 74 65 33 5f 72 74 72 65 65 5f 71 75  sqlite3_rtree_qu
3d80: 65 72 79 5f 63 61 6c 6c 62 61 63 6b 28 29 2c 0a  ery_callback(),.
3d90: 69 73 20 75 73 65 64 20 74 6f 20 72 65 67 69 73  is used to regis
3da0: 74 65 72 20 74 68 65 20 53 51 4c 20 66 75 6e 63  ter the SQL func
3db0: 74 69 6f 6e 2e 20 20 48 6f 77 65 76 65 72 2c 20  tion.  However, 
3dc0: 74 68 65 20 6e 65 77 65 72 20 71 75 65 72 79 2d  the newer query-
3dd0: 73 74 79 6c 65 0a 63 61 6c 6c 62 61 63 6b 73 20  style.callbacks 
3de0: 67 69 76 65 20 74 68 65 20 61 70 70 6c 69 63 61  give the applica
3df0: 74 69 6f 6e 20 67 72 65 61 74 65 72 20 63 6f 6e  tion greater con
3e00: 74 72 6f 6c 20 6f 76 65 72 20 68 6f 77 20 74 68  trol over how th
3e10: 65 20 71 75 65 72 79 20 70 72 6f 63 65 65 64 73  e query proceeds
3e20: 2e 0a 0a 3c 68 33 3e 36 2e 31 20 54 68 65 20 4c  ...<h3>6.1 The L
3e30: 65 67 61 63 79 20 78 47 65 6f 6d 20 43 61 6c 6c  egacy xGeom Call
3e40: 62 61 63 6b 3c 2f 68 33 3e 0a 0a 3c 70 3e 5e 54  back</h3>..<p>^T
3e50: 68 65 20 6c 65 67 61 63 79 20 78 47 65 6f 6d 20  he legacy xGeom 
3e60: 63 61 6c 6c 62 61 63 6b 20 69 73 20 69 6e 76 6f  callback is invo
3e70: 6b 65 64 20 77 69 74 68 20 66 6f 75 72 20 61 72  ked with four ar
3e80: 67 75 6d 65 6e 74 73 2e 20 20 5e 54 68 65 20 66  guments.  ^The f
3e90: 69 72 73 74 0a 61 72 67 75 6d 65 6e 74 20 69 73  irst.argument is
3ea0: 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 61 6e   a pointer to an
3eb0: 20 73 71 6c 69 74 65 33 5f 72 74 72 65 65 5f 67   sqlite3_rtree_g
3ec0: 65 6f 6d 65 74 72 79 20 73 74 72 75 63 74 75 72  eometry structur
3ed0: 65 20 77 68 69 63 68 20 70 72 6f 76 69 64 65 73  e which provides
3ee0: 0a 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 61 62 6f  .information abo
3ef0: 75 74 20 68 6f 77 20 74 68 65 20 53 51 4c 20 66  ut how the SQL f
3f00: 75 6e 63 74 69 6f 6e 20 77 61 73 20 69 6e 76 6f  unction was invo
3f10: 6b 65 64 2e 20 20 5e 54 68 65 20 73 65 63 6f 6e  ked.  ^The secon
3f20: 64 20 61 72 67 75 6d 65 6e 74 0a 69 73 20 74 68  d argument.is th
3f30: 65 20 6e 75 6d 62 65 72 20 6f 66 20 63 6f 6f 72  e number of coor
3f40: 64 69 6e 61 74 65 73 20 69 6e 20 65 61 63 68 20  dinates in each 
3f50: 72 2d 74 72 65 65 20 65 6e 74 72 79 2c 20 61 6e  r-tree entry, an
3f60: 64 20 69 73 20 61 6c 77 61 79 73 20 74 68 65 20  d is always the 
3f70: 73 61 6d 65 0a 66 6f 72 20 61 6e 79 20 67 69 76  same.for any giv
3f80: 65 6e 20 52 2a 54 72 65 65 2e 20 20 5e 54 68 65  en R*Tree.  ^The
3f90: 20 6e 75 6d 62 65 72 20 6f 66 20 63 6f 6f 72 64   number of coord
3fa0: 69 6e 61 74 65 73 20 69 73 20 32 20 66 6f 72 20  inates is 2 for 
3fb0: 61 20 31 2d 64 69 6d 65 6e 73 69 6f 6e 61 6c 20  a 1-dimensional 
3fc0: 52 2a 54 72 65 65 2c 0a 34 20 66 6f 72 20 61 20  R*Tree,.4 for a 
3fd0: 32 2d 64 69 6d 65 6e 73 69 6f 6e 61 6c 20 52 2a  2-dimensional R*
3fe0: 54 72 65 65 2c 20 36 20 66 6f 72 20 61 20 33 2d  Tree, 6 for a 3-
3ff0: 64 69 6d 65 6e 73 69 6f 6e 61 6c 20 52 2a 54 72  dimensional R*Tr
4000: 65 65 2c 20 61 6e 64 20 73 6f 20 66 6f 72 74 68  ee, and so forth
4010: 2e 0a 5e 54 68 65 20 74 68 69 72 64 20 61 72 67  ..^The third arg
4020: 75 6d 65 6e 74 2c 20 61 43 6f 6f 72 64 5b 5d 2c  ument, aCoord[],
4030: 20 69 73 20 61 6e 20 61 72 72 61 79 20 6f 66 20   is an array of 
4040: 6e 43 6f 6f 72 64 20 63 6f 6f 72 64 69 6e 61 74  nCoord coordinat
4050: 65 73 20 74 68 61 74 20 64 65 66 69 6e 65 73 0a  es that defines.
4060: 61 20 62 6f 75 6e 64 69 6e 67 20 62 6f 78 20 74  a bounding box t
4070: 6f 20 62 65 20 74 65 73 74 65 64 2e 20 20 5e 54  o be tested.  ^T
4080: 68 65 20 6c 61 73 74 20 61 72 67 75 6d 65 6e 74  he last argument
4090: 20 69 73 20 61 20 70 6f 69 6e 74 65 72 20 69 6e   is a pointer in
40a0: 74 6f 20 77 68 69 63 68 20 0a 74 68 65 20 63 61  to which .the ca
40b0: 6c 6c 62 61 63 6b 20 72 65 73 75 6c 74 20 73 68  llback result sh
40c0: 6f 75 6c 64 20 62 65 20 77 72 69 74 74 65 6e 2e  ould be written.
40d0: 20 20 54 68 65 20 72 65 73 75 6c 74 20 69 73 20    The result is 
40e0: 7a 65 72 6f 0a 69 66 20 74 68 65 20 62 6f 75 6e  zero.if the boun
40f0: 64 69 6e 67 2d 62 6f 78 20 64 65 66 69 6e 65 64  ding-box defined
4100: 20 62 79 20 61 43 6f 6f 72 64 5b 5d 20 69 73 20   by aCoord[] is 
4110: 63 6f 6d 70 6c 65 74 65 6c 79 20 6f 75 74 73 69  completely outsi
4120: 64 65 0a 74 68 65 20 72 65 67 69 6f 6e 20 64 65  de.the region de
4130: 66 69 6e 65 64 20 62 79 20 74 68 65 20 78 47 65  fined by the xGe
4140: 6f 6d 20 63 61 6c 6c 62 61 63 6b 20 61 6e 64 20  om callback and 
4150: 74 68 65 20 72 65 73 75 6c 74 20 69 73 20 6e 6f  the result is no
4160: 6e 2d 7a 65 72 6f 20 69 66 0a 74 68 65 20 62 6f  n-zero if.the bo
4170: 75 6e 64 69 6e 67 2d 62 6f 78 20 69 73 20 69 6e  unding-box is in
4180: 73 69 64 65 20 6f 72 20 6f 76 65 72 6c 61 70 73  side or overlaps
4190: 20 77 69 74 68 20 74 68 65 20 78 47 65 6f 6d 20   with the xGeom 
41a0: 72 65 67 69 6f 6e 2e 20 20 54 68 65 20 78 47 65  region.  The xGe
41b0: 6f 6d 0a 63 61 6c 6c 62 61 63 6b 20 73 68 6f 75  om.callback shou
41c0: 6c 64 20 6e 6f 72 6d 61 6c 6c 79 20 72 65 74 75  ld normally retu
41d0: 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 2e 20 20 5e  rn SQLITE_OK.  ^
41e0: 49 66 20 78 47 65 6f 6d 20 72 65 74 75 72 6e 73  If xGeom returns
41f0: 20 61 6e 79 74 68 69 6e 67 20 6f 74 68 65 72 0a   anything other.
4200: 74 68 61 6e 20 53 51 4c 49 54 45 5f 4f 4b 2c 20  than SQLITE_OK, 
4210: 74 68 65 6e 20 74 68 65 20 72 2d 74 72 65 65 20  then the r-tree 
4220: 71 75 65 72 79 20 77 69 6c 6c 20 61 62 6f 72 74  query will abort
4230: 20 77 69 74 68 20 61 6e 20 65 72 72 6f 72 2e 0a   with an error..
4240: 0a 3c 70 3e 54 68 65 20 73 71 6c 69 74 65 33 5f  .<p>The sqlite3_
4250: 72 74 72 65 65 5f 67 65 6f 6d 65 74 72 79 20 73  rtree_geometry s
4260: 74 72 75 63 74 75 72 65 20 74 68 61 74 20 74 68  tructure that th
4270: 65 20 66 69 72 73 74 20 61 72 67 75 6d 65 6e 74  e first argument
4280: 20 74 6f 20 74 68 65 0a 78 47 65 6f 6d 20 63 61   to the.xGeom ca
4290: 6c 6c 62 61 63 6b 20 70 6f 69 6e 74 73 20 74 6f  llback points to
42a0: 20 68 61 73 20 61 20 73 74 72 75 63 74 75 72 65   has a structure
42b0: 20 73 68 6f 77 6e 20 62 65 6c 6f 77 2e 20 20 5e   shown below.  ^
42c0: 54 68 65 20 65 78 61 63 74 20 73 61 6d 65 0a 73  The exact same.s
42d0: 71 6c 69 74 65 33 5f 72 74 72 65 65 5f 67 65 6f  qlite3_rtree_geo
42e0: 6d 65 74 72 79 0a 73 74 72 75 63 74 75 72 65 20  metry.structure 
42f0: 69 73 20 75 73 65 64 20 66 6f 72 20 65 76 65 72  is used for ever
4300: 79 20 63 61 6c 6c 62 61 63 6b 20 66 6f 72 20 73  y callback for s
4310: 61 6d 65 20 4d 41 54 43 48 20 6f 70 65 72 61 74  ame MATCH operat
4320: 6f 72 20 69 6e 20 74 68 65 20 73 61 6d 65 0a 71  or in the same.q
4330: 75 65 72 79 2e 20 20 5e 54 68 65 20 63 6f 6e 74  uery.  ^The cont
4340: 65 6e 74 73 20 6f 66 20 74 68 65 20 73 71 6c 69  ents of the sqli
4350: 74 65 33 5f 72 74 72 65 65 5f 67 65 6f 6d 65 74  te3_rtree_geomet
4360: 72 79 0a 73 74 72 75 63 74 75 72 65 20 61 72 65  ry.structure are
4370: 20 69 6e 69 74 69 61 6c 69 7a 65 64 20 62 79 20   initialized by 
4380: 53 51 4c 69 74 65 20 62 75 74 20 61 72 65 0a 6e  SQLite but are.n
4390: 6f 74 20 73 75 62 73 65 71 75 65 6e 74 6c 79 20  ot subsequently 
43a0: 6d 6f 64 69 66 69 65 64 2e 20 20 54 68 65 20 63  modified.  The c
43b0: 61 6c 6c 62 61 63 6b 20 69 73 20 66 72 65 65 20  allback is free 
43c0: 74 6f 20 6d 61 6b 65 20 63 68 61 6e 67 65 73 20  to make changes 
43d0: 74 6f 20 74 68 65 0a 70 55 73 65 72 20 61 6e 64  to the.pUser and
43e0: 20 78 44 65 6c 55 73 65 72 20 65 6c 65 6d 65 6e   xDelUser elemen
43f0: 74 73 20 6f 66 20 74 68 65 20 73 74 72 75 63 74  ts of the struct
4400: 75 72 65 20 69 66 20 64 65 73 69 72 65 64 2e 0a  ure if desired..
4410: 0a 3c 62 6c 6f 63 6b 71 75 6f 74 65 3e 3c 70 72  .<blockquote><pr
4420: 65 3e 0a 74 79 70 65 64 65 66 20 73 74 72 75 63  e>.typedef struc
4430: 74 20 73 71 6c 69 74 65 33 5f 72 74 72 65 65 5f  t sqlite3_rtree_
4440: 67 65 6f 6d 65 74 72 79 20 73 71 6c 69 74 65 33  geometry sqlite3
4450: 5f 72 74 72 65 65 5f 67 65 6f 6d 65 74 72 79 3b  _rtree_geometry;
4460: 0a 73 74 72 75 63 74 20 73 71 6c 69 74 65 33 5f  .struct sqlite3_
4470: 72 74 72 65 65 5f 67 65 6f 6d 65 74 72 79 20 7b  rtree_geometry {
4480: 0a 20 20 76 6f 69 64 20 2a 70 43 6f 6e 74 65 78  .  void *pContex
4490: 74 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  t;              
44a0: 20 20 20 2f 2a 20 43 6f 70 79 20 6f 66 20 70 43     /* Copy of pC
44b0: 6f 6e 74 65 78 74 20 70 61 73 73 65 64 20 74 6f  ontext passed to
44c0: 20 73 5f 72 5f 67 5f 63 28 29 20 2a 2f 0a 20 20   s_r_g_c() */.  
44d0: 69 6e 74 20 6e 50 61 72 61 6d 3b 20 20 20 20 20  int nParam;     
44e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
44f0: 2f 2a 20 53 69 7a 65 20 6f 66 20 61 72 72 61 79  /* Size of array
4500: 20 61 50 61 72 61 6d 20 2a 2f 0a 20 20 64 6f 75   aParam */.  dou
4510: 62 6c 65 20 2a 61 50 61 72 61 6d 3b 20 20 20 20  ble *aParam;    
4520: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
4530: 50 61 72 61 6d 65 74 65 72 73 20 70 61 73 73 65  Parameters passe
4540: 64 20 74 6f 20 53 51 4c 20 67 65 6f 6d 20 66 75  d to SQL geom fu
4550: 6e 63 74 69 6f 6e 20 2a 2f 0a 20 20 76 6f 69 64  nction */.  void
4560: 20 2a 70 55 73 65 72 3b 20 20 20 20 20 20 20 20   *pUser;        
4570: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43              /* C
4580: 61 6c 6c 62 61 63 6b 20 69 6d 70 6c 65 6d 65 6e  allback implemen
4590: 74 61 74 69 6f 6e 20 75 73 65 72 20 64 61 74 61  tation user data
45a0: 20 2a 2f 0a 20 20 76 6f 69 64 20 28 2a 78 44 65   */.  void (*xDe
45b0: 6c 55 73 65 72 29 28 76 6f 69 64 20 2a 29 3b 20  lUser)(void *); 
45c0: 20 20 20 20 20 20 2f 2a 20 43 61 6c 6c 65 64 20        /* Called 
45d0: 62 79 20 53 51 4c 69 74 65 20 74 6f 20 63 6c 65  by SQLite to cle
45e0: 61 6e 20 75 70 20 70 55 73 65 72 20 2a 2f 0a 7d  an up pUser */.}
45f0: 3b 0a 3c 2f 70 72 65 3e 3c 2f 62 6c 6f 63 6b 71  ;.</pre></blockq
4600: 75 6f 74 65 3e 0a 0a 3c 70 3e 5e 54 68 65 20 70  uote>..<p>^The p
4610: 43 6f 6e 74 65 78 74 20 6d 65 6d 62 65 72 20 6f  Context member o
4620: 66 20 74 68 65 20 73 71 6c 69 74 65 33 5f 72 74  f the sqlite3_rt
4630: 72 65 65 5f 67 65 6f 6d 65 74 72 79 0a 73 74 72  ree_geometry.str
4640: 75 63 74 75 72 65 20 69 73 20 61 6c 77 61 79 73  ucture is always
4650: 20 73 65 74 20 74 6f 20 61 20 63 6f 70 79 20 6f   set to a copy o
4660: 66 20 74 68 65 20 70 43 6f 6e 74 65 78 74 0a 61  f the pContext.a
4670: 72 67 75 6d 65 6e 74 20 70 61 73 73 65 64 20 74  rgument passed t
4680: 6f 20 73 71 6c 69 74 65 33 5f 72 74 72 65 65 5f  o sqlite3_rtree_
4690: 67 65 6f 6d 65 74 72 79 5f 63 61 6c 6c 62 61 63  geometry_callbac
46a0: 6b 28 29 20 77 68 65 6e 20 74 68 65 0a 63 61 6c  k() when the.cal
46b0: 6c 62 61 63 6b 20 69 73 20 72 65 67 69 73 74 65  lback is registe
46c0: 72 65 64 2e 20 5e 54 68 65 20 61 50 61 72 61 6d  red. ^The aParam
46d0: 5b 5d 20 61 72 72 61 79 20 28 73 69 7a 65 20 6e  [] array (size n
46e0: 50 61 72 61 6d 29 20 63 6f 6e 74 61 69 6e 73 20  Param) contains 
46f0: 74 68 65 20 70 61 72 61 6d 65 74 65 72 0a 76 61  the parameter.va
4700: 6c 75 65 73 20 70 61 73 73 65 64 20 74 6f 20 74  lues passed to t
4710: 68 65 20 53 51 4c 20 66 75 6e 63 74 69 6f 6e 20  he SQL function 
4720: 6f 6e 20 74 68 65 20 72 69 67 68 74 2d 68 61 6e  on the right-han
4730: 64 20 73 69 64 65 20 6f 66 20 74 68 65 20 4d 41  d side of the MA
4740: 54 43 48 20 6f 70 65 72 61 74 6f 72 2e 0a 49 6e  TCH operator..In
4750: 20 74 68 65 20 65 78 61 6d 70 6c 65 20 22 63 69   the example "ci
4760: 72 63 6c 65 22 20 71 75 65 72 79 20 61 62 6f 76  rcle" query abov
4770: 65 2c 20 6e 50 61 72 61 6d 20 77 6f 75 6c 64 20  e, nParam would 
4780: 62 65 20 73 65 74 20 74 6f 20 33 20 61 6e 64 20  be set to 3 and 
4790: 74 68 65 20 61 50 61 72 61 6d 5b 5d 0a 61 72 72  the aParam[].arr
47a0: 61 79 20 77 6f 75 6c 64 20 63 6f 6e 74 61 69 6e  ay would contain
47b0: 20 74 68 65 20 74 68 72 65 65 20 76 61 6c 75 65   the three value
47c0: 73 20 34 35 2e 33 2c 20 32 32 2e 39 20 61 6e 64  s 45.3, 22.9 and
47d0: 20 35 2e 30 2e 0a 0a 3c 70 3e 5e 54 68 65 20 70   5.0...<p>^The p
47e0: 55 73 65 72 20 61 6e 64 20 78 44 65 6c 55 73 65  User and xDelUse
47f0: 72 20 6d 65 6d 62 65 72 73 20 6f 66 20 74 68 65  r members of the
4800: 20 73 71 6c 69 74 65 33 5f 72 74 72 65 65 5f 67   sqlite3_rtree_g
4810: 65 6f 6d 65 74 72 79 20 73 74 72 75 63 74 75 72  eometry structur
4820: 65 20 61 72 65 0a 69 6e 69 74 69 61 6c 6c 79 20  e are.initially 
4830: 73 65 74 20 74 6f 20 4e 55 4c 4c 2e 20 5e 54 68  set to NULL. ^Th
4840: 65 20 70 55 73 65 72 20 76 61 72 69 61 62 6c 65  e pUser variable
4850: 20 6d 61 79 20 62 65 20 73 65 74 20 62 79 20 74   may be set by t
4860: 68 65 20 63 61 6c 6c 62 61 63 6b 0a 69 6d 70 6c  he callback.impl
4870: 65 6d 65 6e 74 61 74 69 6f 6e 20 74 6f 20 61 6e  ementation to an
4880: 79 20 61 72 62 69 74 72 61 72 79 20 76 61 6c 75  y arbitrary valu
4890: 65 20 74 68 61 74 20 6d 61 79 20 62 65 20 75 73  e that may be us
48a0: 65 66 75 6c 20 74 6f 20 73 75 62 73 65 71 75 65  eful to subseque
48b0: 6e 74 0a 69 6e 76 6f 63 61 74 69 6f 6e 73 20 6f  nt.invocations o
48c0: 66 20 74 68 65 20 63 61 6c 6c 62 61 63 6b 20 77  f the callback w
48d0: 69 74 68 69 6e 20 74 68 65 20 73 61 6d 65 20 71  ithin the same q
48e0: 75 65 72 79 20 28 66 6f 72 20 65 78 61 6d 70 6c  uery (for exampl
48f0: 65 2c 20 61 0a 70 6f 69 6e 74 65 72 20 74 6f 20  e, a.pointer to 
4900: 61 20 63 6f 6d 70 6c 69 63 61 74 65 64 20 64 61  a complicated da
4910: 74 61 20 73 74 72 75 63 74 75 72 65 20 75 73 65  ta structure use
4920: 64 20 74 6f 20 74 65 73 74 20 66 6f 72 20 72 65  d to test for re
4930: 67 69 6f 6e 20 69 6e 74 65 72 73 65 63 74 69 6f  gion intersectio
4940: 6e 29 2e 0a 5e 49 66 20 74 68 65 20 78 44 65 6c  n)..^If the xDel
4950: 55 73 65 72 20 76 61 72 69 61 62 6c 65 20 69 73  User variable is
4960: 20 73 65 74 20 74 6f 20 61 20 6e 6f 6e 2d 4e 55   set to a non-NU
4970: 4c 4c 20 76 61 6c 75 65 2c 20 74 68 65 6e 20 61  LL value, then a
4980: 66 74 65 72 20 74 68 65 0a 71 75 65 72 79 20 68  fter the.query h
4990: 61 73 20 66 69 6e 69 73 68 65 64 20 72 75 6e 6e  as finished runn
49a0: 69 6e 67 20 53 51 4c 69 74 65 20 61 75 74 6f 6d  ing SQLite autom
49b0: 61 74 69 63 61 6c 6c 79 20 69 6e 76 6f 6b 65 73  atically invokes
49c0: 20 69 74 20 77 69 74 68 20 74 68 65 0a 76 61 6c   it with the.val
49d0: 75 65 20 6f 66 20 74 68 65 20 70 55 73 65 72 20  ue of the pUser 
49e0: 76 61 72 69 61 62 6c 65 20 61 73 20 74 68 65 20  variable as the 
49f0: 6f 6e 6c 79 20 61 72 67 75 6d 65 6e 74 2e 20 49  only argument. I
4a00: 6e 20 6f 74 68 65 72 20 77 6f 72 64 73 2c 20 78  n other words, x
4a10: 44 65 6c 55 73 65 72 0a 6d 61 79 20 62 65 20 73  DelUser.may be s
4a20: 65 74 20 74 6f 20 61 20 64 65 73 74 72 75 63 74  et to a destruct
4a30: 6f 72 20 66 75 6e 63 74 69 6f 6e 20 66 6f 72 20  or function for 
4a40: 74 68 65 20 70 55 73 65 72 20 76 61 6c 75 65 2e  the pUser value.
4a50: 0a 0a 3c 70 3e 5e 54 68 65 20 78 47 65 6f 6d 20  ..<p>^The xGeom 
4a60: 63 61 6c 6c 62 61 63 6b 20 61 6c 77 61 79 73 20  callback always 
4a70: 64 6f 65 73 20 61 20 64 65 70 74 68 2d 66 69 72  does a depth-fir
4a80: 73 74 20 73 65 61 72 63 68 20 6f 66 20 74 68 65  st search of the
4a90: 20 72 2d 74 72 65 65 2e 0a 0a 3c 74 63 6c 3e 68   r-tree...<tcl>h
4aa0: 64 5f 66 72 61 67 6d 65 6e 74 20 78 71 75 65 72  d_fragment xquer
4ab0: 79 20 7b 78 51 75 65 72 79 46 75 6e 63 20 52 2a  y {xQueryFunc R*
4ac0: 54 72 65 65 20 63 61 6c 6c 62 61 63 6b 7d 20 7b  Tree callback} {
4ad0: 73 71 6c 69 74 65 33 5f 72 74 72 65 65 5f 71 75  sqlite3_rtree_qu
4ae0: 65 72 79 5f 63 61 6c 6c 62 61 63 6b 7d 0a 3c 2f  ery_callback}.</
4af0: 74 63 6c 3e 0a 3c 68 33 3e 36 2e 32 20 54 68 65  tcl>.<h3>6.2 The
4b00: 20 4e 65 77 20 78 51 75 65 72 79 46 75 6e 63 20   New xQueryFunc 
4b10: 43 61 6c 6c 62 61 63 6b 3c 2f 68 33 3e 0a 0a 3c  Callback</h3>..<
4b20: 70 3e 54 68 65 20 6e 65 77 65 72 20 78 51 75 65  p>The newer xQue
4b30: 72 79 46 75 6e 63 20 63 61 6c 6c 62 61 63 6b 20  ryFunc callback 
4b40: 72 65 63 65 69 76 65 73 20 6d 6f 72 65 20 69 6e  receives more in
4b50: 66 6f 72 6d 61 74 69 6f 6e 20 66 72 6f 6d 20 74  formation from t
4b60: 68 65 20 72 2d 74 72 65 65 0a 71 75 65 72 79 20  he r-tree.query 
4b70: 65 6e 67 69 6e 65 20 6f 6e 20 65 61 63 68 20 63  engine on each c
4b80: 61 6c 6c 2c 20 61 6e 64 20 69 74 20 73 65 6e 64  all, and it send
4b90: 73 20 6d 6f 72 65 20 69 6e 66 6f 72 6d 61 74 69  s more informati
4ba0: 6f 6e 20 62 61 63 6b 20 74 6f 20 74 68 65 20 71  on back to the q
4bb0: 75 65 72 79 20 65 6e 67 69 6e 65 0a 62 65 66 6f  uery engine.befo
4bc0: 72 65 20 69 74 20 72 65 74 75 72 6e 73 2e 0a 54  re it returns..T
4bd0: 6f 20 68 65 6c 70 20 6b 65 65 70 20 74 68 65 20  o help keep the 
4be0: 69 6e 74 65 72 66 61 63 65 20 6d 61 6e 61 67 65  interface manage
4bf0: 61 62 6c 65 2c 20 74 68 65 20 78 51 75 65 72 79  able, the xQuery
4c00: 46 75 6e 63 20 63 61 6c 6c 62 61 63 6b 20 73 65  Func callback se
4c10: 6e 64 73 20 61 6e 64 20 72 65 63 65 69 76 65 73  nds and receives
4c20: 0a 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 66 72 6f  .information fro
4c30: 6d 20 74 68 65 20 71 75 65 72 79 20 65 6e 67 69  m the query engi
4c40: 6e 65 20 61 73 20 66 69 65 6c 64 73 20 69 6e 20  ne as fields in 
4c50: 74 68 65 0a 73 71 6c 69 74 65 33 5f 72 74 72 65  the.sqlite3_rtre
4c60: 65 5f 71 75 65 72 79 5f 69 6e 66 6f 20 73 74 72  e_query_info str
4c70: 75 63 74 75 72 65 3a 0a 0a 3c 62 6c 6f 63 6b 71  ucture:..<blockq
4c80: 75 6f 74 65 3e 3c 70 72 65 3e 0a 73 74 72 75 63  uote><pre>.struc
4c90: 74 20 73 71 6c 69 74 65 33 5f 72 74 72 65 65 5f  t sqlite3_rtree_
4ca0: 71 75 65 72 79 5f 69 6e 66 6f 20 7b 0a 20 20 76  query_info {.  v
4cb0: 6f 69 64 20 2a 70 43 6f 6e 74 65 78 74 3b 20 20  oid *pContext;  
4cc0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
4cd0: 20 2f 2a 20 70 43 6f 6e 74 65 78 74 20 66 72 6f   /* pContext fro
4ce0: 6d 20 77 68 65 6e 20 66 75 6e 63 74 69 6f 6e 20  m when function 
4cf0: 72 65 67 69 73 74 65 72 65 64 20 2a 2f 0a 20 20  registered */.  
4d00: 69 6e 74 20 6e 50 61 72 61 6d 3b 20 20 20 20 20  int nParam;     
4d10: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
4d20: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 66    /* Number of f
4d30: 75 6e 63 74 69 6f 6e 20 70 61 72 61 6d 65 74 65  unction paramete
4d40: 72 73 20 2a 2f 0a 20 20 73 71 6c 69 74 65 33 5f  rs */.  sqlite3_
4d50: 72 74 72 65 65 5f 64 62 6c 20 2a 61 50 61 72 61  rtree_dbl *aPara
4d60: 6d 3b 20 20 20 20 20 20 20 20 2f 2a 20 76 61 6c  m;        /* val
4d70: 75 65 20 6f 66 20 66 75 6e 63 74 69 6f 6e 20 70  ue of function p
4d80: 61 72 61 6d 65 74 65 72 73 20 2a 2f 0a 20 20 76  arameters */.  v
4d90: 6f 69 64 20 2a 70 55 73 65 72 3b 20 20 20 20 20  oid *pUser;     
4da0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
4db0: 20 2f 2a 20 63 61 6c 6c 62 61 63 6b 20 63 61 6e   /* callback can
4dc0: 20 75 73 65 20 74 68 69 73 2c 20 69 66 20 64 65   use this, if de
4dd0: 73 69 72 65 64 20 2a 2f 0a 20 20 76 6f 69 64 20  sired */.  void 
4de0: 28 2a 78 44 65 6c 55 73 65 72 29 28 76 6f 69 64  (*xDelUser)(void
4df0: 2a 29 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20  *);          /* 
4e00: 66 75 6e 63 74 69 6f 6e 20 74 6f 20 66 72 65 65  function to free
4e10: 20 70 55 73 65 72 20 2a 2f 0a 20 20 73 71 6c 69   pUser */.  sqli
4e20: 74 65 33 5f 72 74 72 65 65 5f 64 62 6c 20 2a 61  te3_rtree_dbl *a
4e30: 43 6f 6f 72 64 3b 20 20 20 20 20 20 20 20 2f 2a  Coord;        /*
4e40: 20 43 6f 6f 72 64 69 6e 61 74 65 73 20 6f 66 20   Coordinates of 
4e50: 6e 6f 64 65 20 6f 72 20 65 6e 74 72 79 20 74 6f  node or entry to
4e60: 20 63 68 65 63 6b 20 2a 2f 0a 20 20 75 6e 73 69   check */.  unsi
4e70: 67 6e 65 64 20 69 6e 74 20 2a 61 6e 51 75 65 75  gned int *anQueu
4e80: 65 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a  e;            /*
4e90: 20 4e 75 6d 62 65 72 20 6f 66 20 70 65 6e 64 69   Number of pendi
4ea0: 6e 67 20 65 6e 74 72 69 65 73 20 69 6e 20 74 68  ng entries in th
4eb0: 65 20 71 75 65 75 65 20 2a 2f 0a 20 20 69 6e 74  e queue */.  int
4ec0: 20 6e 43 6f 6f 72 64 3b 20 20 20 20 20 20 20 20   nCoord;        
4ed0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
4ee0: 2a 20 4e 75 6d 62 65 72 20 6f 66 20 63 6f 6f 72  * Number of coor
4ef0: 64 69 6e 61 74 65 73 20 2a 2f 0a 20 20 69 6e 74  dinates */.  int
4f00: 20 69 4c 65 76 65 6c 3b 20 20 20 20 20 20 20 20   iLevel;        
4f10: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
4f20: 2a 20 4c 65 76 65 6c 20 6f 66 20 63 75 72 72 65  * Level of curre
4f30: 6e 74 20 6e 6f 64 65 20 6f 72 20 65 6e 74 72 79  nt node or entry
4f40: 20 2a 2f 0a 20 20 69 6e 74 20 6d 78 4c 65 76 65   */.  int mxLeve
4f50: 6c 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  l;              
4f60: 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 6c          /* The l
4f70: 61 72 67 65 73 74 20 69 4c 65 76 65 6c 20 76 61  argest iLevel va
4f80: 6c 75 65 20 69 6e 20 74 68 65 20 74 72 65 65 20  lue in the tree 
4f90: 2a 2f 0a 20 20 73 71 6c 69 74 65 33 5f 69 6e 74  */.  sqlite3_int
4fa0: 36 34 20 69 52 6f 77 69 64 3b 20 20 20 20 20 20  64 iRowid;      
4fb0: 20 20 20 20 20 20 20 2f 2a 20 52 6f 77 69 64 20         /* Rowid 
4fc0: 66 6f 72 20 63 75 72 72 65 6e 74 20 65 6e 74 72  for current entr
4fd0: 79 20 2a 2f 0a 20 20 73 71 6c 69 74 65 33 5f 72  y */.  sqlite3_r
4fe0: 74 72 65 65 5f 64 62 6c 20 72 50 61 72 65 6e 74  tree_dbl rParent
4ff0: 53 63 6f 72 65 3b 20 20 20 2f 2a 20 53 63 6f 72  Score;   /* Scor
5000: 65 20 6f 66 20 70 61 72 65 6e 74 20 6e 6f 64 65  e of parent node
5010: 20 2a 2f 0a 20 20 69 6e 74 20 65 50 61 72 65 6e   */.  int eParen
5020: 74 57 69 74 68 69 6e 3b 20 20 20 20 20 20 20 20  tWithin;        
5030: 20 20 20 20 20 20 20 20 2f 2a 20 56 69 73 69 62          /* Visib
5040: 69 6c 69 74 79 20 6f 66 20 70 61 72 65 6e 74 20  ility of parent 
5050: 6e 6f 64 65 20 2a 2f 0a 20 20 69 6e 74 20 65 57  node */.  int eW
5060: 69 74 68 69 6e 3b 20 20 20 20 20 20 20 20 20 20  ithin;          
5070: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f              /* O
5080: 55 54 3a 20 56 69 73 69 62 6c 69 74 79 20 2a 2f  UT: Visiblity */
5090: 0a 20 20 73 71 6c 69 74 65 33 5f 72 74 72 65 65  .  sqlite3_rtree
50a0: 5f 64 62 6c 20 72 53 63 6f 72 65 3b 20 20 20 20  _dbl rScore;    
50b0: 20 20 20 20 20 2f 2a 20 4f 55 54 3a 20 57 72 69       /* OUT: Wri
50c0: 74 65 20 74 68 65 20 73 63 6f 72 65 20 68 65 72  te the score her
50d0: 65 20 2a 2f 0a 7d 3b 0a 3c 2f 70 72 65 3e 3c 2f  e */.};.</pre></
50e0: 62 6c 6f 63 6b 71 75 6f 74 65 3e 0a 0a 3c 70 3e  blockquote>..<p>
50f0: 54 68 65 20 66 69 72 73 74 20 66 69 76 65 20 66  The first five f
5100: 69 65 6c 64 73 20 6f 66 20 74 68 65 20 73 71 6c  ields of the sql
5110: 69 74 65 33 5f 72 74 72 65 65 5f 71 75 65 72 79  ite3_rtree_query
5120: 5f 69 6e 66 6f 20 73 74 72 75 63 74 75 72 65 20  _info structure 
5130: 61 72 65 20 69 64 65 6e 74 69 63 61 6c 0a 74 6f  are identical.to
5140: 20 74 68 65 20 73 71 6c 69 74 65 33 5f 72 74 72   the sqlite3_rtr
5150: 65 65 5f 67 65 6f 6d 65 74 72 79 20 73 74 72 75  ee_geometry stru
5160: 63 74 75 72 65 2c 20 61 6e 64 20 68 61 76 65 20  cture, and have 
5170: 65 78 61 63 74 6c 79 20 74 68 65 20 73 61 6d 65  exactly the same
5180: 20 6d 65 61 6e 69 6e 67 2e 0a 54 68 65 20 73 71   meaning..The sq
5190: 6c 69 74 65 33 5f 72 74 72 65 65 5f 71 75 65 72  lite3_rtree_quer
51a0: 79 5f 69 6e 66 6f 20 73 74 72 75 63 74 75 72 65  y_info structure
51b0: 20 61 6c 73 6f 20 63 6f 6e 74 61 69 6e 73 20 6e   also contains n
51c0: 43 6f 6f 72 64 20 61 6e 64 20 61 43 6f 6f 72 64  Coord and aCoord
51d0: 20 66 69 65 6c 64 73 20 0a 77 68 69 63 68 20 68   fields .which h
51e0: 61 76 65 20 74 68 65 20 73 61 6d 65 20 6d 65 61  ave the same mea
51f0: 6e 69 6e 67 20 61 73 20 74 68 65 20 70 61 72 61  ning as the para
5200: 6d 65 74 65 72 20 6f 66 20 74 68 65 20 73 61 6d  meter of the sam
5210: 65 20 6e 61 6d 65 20 69 6e 20 74 68 65 20 78 47  e name in the xG
5220: 65 6f 6d 20 63 61 6c 6c 62 61 63 6b 2e 0a 0a 3c  eom callback...<
5230: 70 3e 54 68 65 20 78 51 75 65 72 79 46 75 6e 63  p>The xQueryFunc
5240: 20 6d 75 73 74 20 73 65 74 20 74 68 65 20 65 57   must set the eW
5250: 69 74 68 69 6e 20 66 69 65 6c 64 20 6f 66 20 73  ithin field of s
5260: 71 6c 69 74 65 33 5f 72 74 72 65 65 5f 71 75 65  qlite3_rtree_que
5270: 72 79 5f 69 6e 66 6f 20 74 6f 0a 6f 6e 20 6f 66  ry_info to.on of
5280: 20 74 68 65 20 76 61 6c 75 65 73 20 4e 4f 54 5f   the values NOT_
5290: 57 49 54 48 49 4e 2c 20 50 41 52 54 4c 59 5f 57  WITHIN, PARTLY_W
52a0: 49 54 48 49 4e 2c 20 6f 72 20 46 55 4c 4c 59 5f  ITHIN, or FULLY_
52b0: 57 49 54 48 49 4e 20 64 65 70 65 6e 64 69 6e 67  WITHIN depending
52c0: 20 6f 6e 20 77 68 65 74 68 65 72 0a 6f 72 20 6e   on whether.or n
52d0: 6f 74 20 74 68 65 20 62 6f 75 6e 64 69 6e 67 20  ot the bounding 
52e0: 62 6f 78 20 64 65 66 69 6e 65 64 20 62 79 20 61  box defined by a
52f0: 43 6f 6f 72 64 5b 5d 20 69 73 20 63 6f 6d 70 6c  Coord[] is compl
5300: 65 74 65 6c 79 20 6f 75 74 73 69 64 65 20 74 68  etely outside th
5310: 65 20 72 65 67 69 6f 6e 2c 0a 6f 76 65 72 6c 61  e region,.overla
5320: 70 73 20 74 68 65 20 72 65 67 69 6f 6e 2c 20 6f  ps the region, o
5330: 72 20 69 73 20 63 6f 6d 70 6c 65 74 65 6c 79 20  r is completely 
5340: 69 6e 73 69 64 65 20 74 68 65 20 72 65 67 69 6f  inside the regio
5350: 6e 2c 20 72 65 73 70 65 63 74 69 76 65 6c 79 2e  n, respectively.
5360: 20 20 49 6e 0a 61 64 64 69 74 69 6f 6e 2c 20 74    In.addition, t
5370: 68 65 20 78 51 75 65 72 79 46 75 6e 63 20 6d 75  he xQueryFunc mu
5380: 73 74 20 73 65 74 20 74 68 65 20 72 53 63 6f 72  st set the rScor
5390: 65 20 66 69 65 6c 64 20 74 6f 20 61 20 6e 6f 6e  e field to a non
53a0: 2d 6e 65 67 61 74 69 76 65 20 76 61 6c 75 65 20  -negative value 
53b0: 74 68 61 74 0a 69 6e 64 69 63 61 74 65 73 20 74  that.indicates t
53c0: 68 65 20 6f 72 64 65 72 20 69 6e 20 77 68 69 63  he order in whic
53d0: 68 20 73 75 62 74 72 65 65 73 20 61 6e 64 20 65  h subtrees and e
53e0: 6e 74 72 69 65 73 20 6f 66 20 74 68 65 20 71 75  ntries of the qu
53f0: 65 72 79 20 73 68 6f 75 6c 64 20 62 65 20 61 6e  ery should be an
5400: 61 6c 79 7a 65 64 0a 61 6e 64 20 72 65 74 75 72  alyzed.and retur
5410: 6e 65 64 2e 20 20 5e 53 6d 61 6c 6c 65 72 20 73  ned.  ^Smaller s
5420: 63 6f 72 65 73 20 61 72 65 20 70 72 6f 63 65 73  cores are proces
5430: 73 65 64 20 66 69 72 73 74 2e 0a 0a 3c 70 3e 41  sed first...<p>A
5440: 73 20 69 74 73 20 6e 61 6d 65 20 69 6d 70 6c 69  s its name impli
5450: 65 73 2c 20 61 6e 20 52 2a 54 72 65 65 20 69 73  es, an R*Tree is
5460: 20 6f 72 67 61 6e 69 7a 65 64 20 61 73 20 61 20   organized as a 
5470: 74 72 65 65 2e 20 20 45 61 63 68 20 6e 6f 64 65  tree.  Each node
5480: 20 6f 66 20 74 68 65 0a 74 72 65 65 20 69 73 20   of the.tree is 
5490: 61 20 62 6f 75 6e 64 69 6e 67 20 62 6f 78 2e 20  a bounding box. 
54a0: 20 54 68 65 20 72 6f 6f 74 20 6f 66 20 74 68 65   The root of the
54b0: 20 74 72 65 65 20 69 73 20 61 20 62 6f 75 6e 64   tree is a bound
54c0: 69 6e 67 20 62 6f 78 20 74 68 61 74 20 65 6e 63  ing box that enc
54d0: 61 70 73 75 6c 61 74 65 73 0a 61 6c 6c 20 65 6c  apsulates.all el
54e0: 65 6d 65 6e 74 73 20 6f 66 20 74 68 65 20 74 72  ements of the tr
54f0: 65 65 2e 20 20 42 65 6e 65 61 74 68 20 74 68 65  ee.  Beneath the
5500: 20 72 6f 6f 74 20 61 72 65 20 61 20 6e 75 6d 62   root are a numb
5510: 65 72 20 6f 66 20 73 75 62 74 72 65 65 73 20 28  er of subtrees (
5520: 74 79 70 69 63 61 6c 6c 79 0a 32 30 20 6f 72 20  typically.20 or 
5530: 6d 6f 72 65 29 20 65 61 63 68 20 77 69 74 68 20  more) each with 
5540: 74 68 65 69 72 20 6f 77 6e 20 73 6d 61 6c 6c 65  their own smalle
5550: 72 20 62 6f 75 6e 64 69 6e 67 20 62 6f 78 65 73  r bounding boxes
5560: 20 61 6e 64 20 65 61 63 68 20 63 6f 6e 74 61 69   and each contai
5570: 6e 69 6e 67 20 73 6f 6d 65 0a 73 75 62 73 65 74  ning some.subset
5580: 20 6f 66 20 74 68 65 20 52 2a 54 72 65 65 20 65   of the R*Tree e
5590: 6e 74 72 69 65 73 2e 20 20 54 68 65 20 73 75 62  ntries.  The sub
55a0: 74 72 65 65 73 20 6d 61 79 20 68 61 76 65 20 73  trees may have s
55b0: 75 62 2d 73 75 62 74 72 65 65 73 2c 20 61 6e 64  ub-subtrees, and
55c0: 20 73 6f 20 66 6f 72 74 68 0a 75 6e 74 69 6c 20   so forth.until 
55d0: 66 69 6e 61 6c 6c 79 20 6f 6e 65 20 72 65 61 63  finally one reac
55e0: 68 65 73 20 74 68 65 20 6c 65 61 76 65 73 20 6f  hes the leaves o
55f0: 66 20 74 68 65 20 74 72 65 65 20 77 68 69 63 68  f the tree which
5600: 20 61 72 65 20 74 68 65 20 61 63 74 75 61 6c 20   are the actual 
5610: 52 2a 54 72 65 65 0a 65 6e 74 72 69 65 73 2e 0a  R*Tree.entries..
5620: 0a 3c 70 3e 41 6e 20 52 2a 54 72 65 65 20 71 75  .<p>An R*Tree qu
5630: 65 72 79 20 69 73 20 69 6e 69 74 69 61 6c 69 7a  ery is initializ
5640: 65 64 20 62 79 20 6d 61 6b 69 6e 67 20 74 68 65  ed by making the
5650: 20 72 6f 6f 74 20 6e 6f 64 65 20 74 68 65 20 6f   root node the o
5660: 6e 6c 79 20 65 6e 74 72 79 0a 69 6e 20 61 20 70  nly entry.in a p
5670: 72 69 6f 72 69 74 79 20 71 75 65 75 65 20 73 6f  riority queue so
5680: 72 74 65 64 20 62 79 20 72 53 63 6f 72 65 2e 0a  rted by rScore..
5690: 54 68 65 20 71 75 65 72 79 20 70 72 6f 63 65 65  The query procee
56a0: 64 73 20 62 79 20 65 78 74 72 61 63 74 69 6e 67  ds by extracting
56b0: 20 74 68 65 20 65 6e 74 72 79 20 66 72 6f 6d 20   the entry from 
56c0: 74 68 65 20 70 72 69 6f 72 69 74 79 20 71 75 65  the priority que
56d0: 75 65 20 74 68 61 74 20 68 61 73 0a 74 68 65 20  ue that has.the 
56e0: 6c 6f 77 65 73 74 20 73 63 6f 72 65 2e 20 20 49  lowest score.  I
56f0: 66 20 74 68 61 74 20 65 6e 74 72 79 20 69 73 20  f that entry is 
5700: 61 20 6c 65 61 66 20 28 6d 65 61 6e 69 6e 67 20  a leaf (meaning 
5710: 74 68 61 74 20 69 74 20 69 73 20 61 6e 20 61 63  that it is an ac
5720: 74 75 61 6c 0a 52 2a 54 72 65 65 20 65 6e 74 72  tual.R*Tree entr
5730: 79 20 61 6e 64 20 6e 6f 74 20 61 20 73 75 62 74  y and not a subt
5740: 72 65 65 29 20 74 68 65 6e 20 74 68 61 74 20 65  ree) then that e
5750: 6e 74 72 79 0a 69 73 20 72 65 74 75 72 6e 65 64  ntry.is returned
5760: 20 61 73 20 6f 6e 65 20 72 6f 77 20 6f 66 20 74   as one row of t
5770: 68 65 20 71 75 65 72 79 20 72 65 73 75 6c 74 2e  he query result.
5780: 20 20 0a 49 66 20 74 68 65 20 65 78 74 72 61 63    .If the extrac
5790: 74 65 64 20 70 72 69 6f 72 69 74 79 20 71 75 65  ted priority que
57a0: 75 65 20 65 6e 74 72 79 20 69 73 20 61 20 6e 6f  ue entry is a no
57b0: 64 65 20 28 61 20 73 75 62 74 72 65 65 29 2c 0a  de (a subtree),.
57c0: 74 68 65 6e 20 73 75 62 2d 73 75 62 74 72 65 65  then sub-subtree
57d0: 73 20 6f 72 20 6c 65 61 76 65 73 20 63 6f 6e 74  s or leaves cont
57e0: 61 69 6e 65 64 20 77 69 74 68 69 6e 20 74 68 61  ained within tha
57f0: 74 20 65 6e 74 72 79 20 61 72 65 20 70 61 73 73  t entry are pass
5800: 65 64 20 74 6f 20 74 68 65 0a 78 51 75 65 72 79  ed to the.xQuery
5810: 46 75 6e 63 20 63 61 6c 6c 62 61 63 6b 2c 20 6f  Func callback, o
5820: 6e 65 20 62 79 20 6f 6e 65 2e 20 20 54 68 6f 73  ne by one.  Thos
5830: 65 20 73 75 62 65 6c 65 6d 65 6e 74 73 20 66 6f  e subelements fo
5840: 72 20 77 68 69 63 68 20 74 68 65 20 78 51 75 65  r which the xQue
5850: 72 79 46 75 6e 63 0a 63 61 6c 6c 62 61 63 6b 20  ryFunc.callback 
5860: 73 65 74 73 20 65 57 69 74 68 69 6e 20 74 6f 20  sets eWithin to 
5870: 50 41 52 54 4c 59 5f 57 49 54 48 49 4e 20 6f 72  PARTLY_WITHIN or
5880: 20 46 55 4c 4c 59 5f 57 49 54 48 49 4e 20 61 72   FULLY_WITHIN ar
5890: 65 20 61 64 64 65 64 20 74 6f 20 74 68 65 20 70  e added to the p
58a0: 72 69 6f 72 69 74 79 0a 71 75 65 75 65 20 75 73  riority.queue us
58b0: 69 6e 67 20 74 68 65 20 73 63 6f 72 65 20 73 75  ing the score su
58c0: 70 70 6c 69 65 64 20 62 79 20 74 68 65 20 63 61  pplied by the ca
58d0: 6c 6c 62 61 63 6b 2e 20 20 53 75 62 65 6c 65 6d  llback.  Subelem
58e0: 65 6e 74 73 20 74 68 61 74 20 72 65 74 75 72 6e  ents that return
58f0: 0a 4e 4f 54 5f 57 49 54 48 49 4e 20 61 72 65 20  .NOT_WITHIN are 
5900: 64 69 73 63 61 72 64 65 64 2e 20 20 54 68 65 20  discarded.  The 
5910: 71 75 65 72 79 20 72 75 6e 73 20 75 6e 74 69 6c  query runs until
5920: 20 74 68 65 20 70 72 69 6f 72 69 74 79 20 71 75   the priority qu
5930: 65 75 65 20 69 73 20 65 6d 70 74 79 2e 0a 0a 3c  eue is empty...<
5940: 70 3e 45 76 65 72 79 20 6c 65 61 66 20 65 6e 74  p>Every leaf ent
5950: 72 79 20 61 6e 64 20 6e 6f 64 65 20 28 73 75 62  ry and node (sub
5960: 74 72 65 65 29 20 77 69 74 68 69 6e 20 74 68 65  tree) within the
5970: 20 52 2a 54 72 65 65 20 68 61 73 20 61 6e 20 69   R*Tree has an i
5980: 6e 74 65 67 65 72 20 22 6c 65 76 65 6c 22 2e 0a  nteger "level"..
5990: 5e 54 68 65 20 6c 65 61 76 65 73 20 68 61 76 65  ^The leaves have
59a0: 20 61 20 6c 65 76 65 6c 20 6f 66 20 30 2e 20 20   a level of 0.  
59b0: 54 68 65 20 66 69 72 73 74 20 63 6f 6e 74 61 69  The first contai
59c0: 6e 69 6e 67 20 73 75 62 74 72 65 65 20 6f 66 20  ning subtree of 
59d0: 74 68 65 20 6c 65 61 76 65 73 20 68 61 73 0a 61  the leaves has.a
59e0: 20 6c 65 76 65 6c 20 6f 66 20 31 2e 20 20 54 68   level of 1.  Th
59f0: 65 20 72 6f 6f 74 20 6f 66 20 74 68 65 20 52 2a  e root of the R*
5a00: 54 72 65 65 20 68 61 73 20 74 68 65 20 6c 61 72  Tree has the lar
5a10: 67 65 73 74 20 6c 65 76 65 6c 20 76 61 6c 75 65  gest level value
5a20: 2e 20 20 5e 54 68 65 0a 6d 78 4c 65 76 65 6c 20  .  ^The.mxLevel 
5a30: 65 6e 74 72 79 20 69 6e 20 74 68 65 20 73 71 6c  entry in the sql
5a40: 69 74 65 33 5f 72 74 72 65 65 5f 71 75 65 72 79  ite3_rtree_query
5a50: 5f 69 6e 66 6f 20 73 74 72 75 63 74 75 72 65 20  _info structure 
5a60: 69 73 20 74 68 65 20 6c 65 76 65 6c 20 76 61 6c  is the level val
5a70: 75 65 20 66 6f 72 0a 74 68 65 20 72 6f 6f 74 20  ue for.the root 
5a80: 6f 66 20 74 68 65 20 52 2a 54 72 65 65 2e 20 20  of the R*Tree.  
5a90: 54 68 65 20 69 4c 65 76 65 6c 20 65 6e 74 72 79  The iLevel entry
5aa0: 20 69 6e 20 73 71 6c 69 74 65 33 5f 72 74 72 65   in sqlite3_rtre
5ab0: 65 5f 71 75 65 72 79 5f 69 6e 66 6f 20 67 69 76  e_query_info giv
5ac0: 65 73 20 74 68 65 0a 6c 65 76 65 6c 20 66 6f 72  es the.level for
5ad0: 20 74 68 65 20 6f 62 6a 65 63 74 20 62 65 69 6e   the object bein
5ae0: 67 20 69 6e 74 65 72 72 6f 67 61 74 65 64 2e 0a  g interrogated..
5af0: 0a 3c 70 3e 5e 28 4d 6f 73 74 20 52 2a 54 72 65  .<p>^(Most R*Tre
5b00: 65 20 71 75 65 72 69 65 73 20 75 73 65 20 61 20  e queries use a 
5b10: 64 65 70 74 68 2d 66 69 72 73 74 20 73 65 61 72  depth-first sear
5b20: 63 68 2e 20 20 54 68 69 73 20 69 73 20 61 63 63  ch.  This is acc
5b30: 6f 6d 70 6c 69 73 68 65 64 20 62 79 20 73 65 74  omplished by set
5b40: 74 69 6e 67 0a 74 68 65 20 72 53 63 6f 72 65 20  ting.the rScore 
5b50: 65 71 75 61 6c 20 74 6f 20 69 4c 65 76 65 6c 2e  equal to iLevel.
5b60: 29 5e 20 20 41 20 64 65 70 74 68 2d 66 69 72 73  )^  A depth-firs
5b70: 74 20 73 65 61 72 63 68 20 69 73 20 75 73 75 61  t search is usua
5b80: 6c 6c 79 20 70 72 65 66 65 72 72 65 64 20 73 69  lly preferred si
5b90: 6e 63 65 20 69 74 0a 6d 69 6e 69 6d 69 7a 65 73  nce it.minimizes
5ba0: 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 65   the number of e
5bb0: 6c 65 6d 65 6e 74 73 20 69 6e 20 74 68 65 20 70  lements in the p
5bc0: 72 69 6f 72 69 74 79 20 71 75 65 75 65 2c 20 77  riority queue, w
5bd0: 68 69 63 68 20 72 65 64 75 63 65 73 20 6d 65 6d  hich reduces mem
5be0: 6f 72 79 0a 72 65 71 75 69 72 65 6d 65 6e 74 73  ory.requirements
5bf0: 20 61 6e 64 20 73 70 65 65 64 73 20 70 72 6f 63   and speeds proc
5c00: 65 73 73 69 6e 67 2e 20 20 5e 48 6f 77 65 76 65  essing.  ^Howeve
5c10: 72 2c 20 73 6f 6d 65 20 61 70 70 6c 69 63 61 74  r, some applicat
5c20: 69 6f 6e 20 6d 61 79 20 70 72 65 66 65 72 20 61  ion may prefer a
5c30: 0a 62 72 65 61 64 74 68 2d 66 69 72 73 74 20 73  .breadth-first s
5c40: 65 61 72 63 68 2c 20 77 68 69 63 68 20 63 61 6e  earch, which can
5c50: 20 62 65 20 61 63 63 6f 6d 70 6c 69 73 68 65 64   be accomplished
5c60: 20 62 79 20 73 65 74 74 69 6e 67 20 72 53 63 6f   by setting rSco
5c70: 72 65 20 74 6f 20 6d 78 4c 65 76 65 6c 2d 69 4c  re to mxLevel-iL
5c80: 65 76 65 6c 2e 0a 42 79 20 63 72 65 61 74 69 6e  evel..By creatin
5c90: 67 20 6d 6f 72 65 20 63 6f 6d 70 6c 65 78 20 66  g more complex f
5ca0: 6f 72 6d 75 6c 61 73 20 66 6f 72 20 72 53 63 6f  ormulas for rSco
5cb0: 72 65 2c 20 61 70 70 6c 69 63 61 74 69 6f 6e 73  re, applications
5cc0: 20 63 61 6e 20 65 78 65 72 63 69 73 65 0a 64 65   can exercise.de
5cd0: 74 61 69 6c 65 64 20 63 6f 6e 74 72 6f 6c 20 6f  tailed control o
5ce0: 76 65 72 20 74 68 65 20 6f 72 64 65 72 20 69 6e  ver the order in
5cf0: 20 77 68 69 63 68 20 73 75 62 74 72 65 65 20 61   which subtree a
5d00: 72 65 20 73 65 61 72 63 68 65 64 20 61 6e 64 20  re searched and 
5d10: 6c 65 61 66 0a 52 2a 54 72 65 65 20 65 6e 74 72  leaf.R*Tree entr
5d20: 69 65 73 20 61 72 65 20 72 65 74 75 72 6e 65 64  ies are returned
5d30: 2e 20 20 46 6f 72 20 65 78 61 6d 70 6c 65 2c 20  .  For example, 
5d40: 69 6e 20 61 6e 20 61 70 70 6c 69 63 61 74 69 6f  in an applicatio
5d50: 6e 20 77 69 74 68 20 6d 61 6e 79 0a 6d 69 6c 6c  n with many.mill
5d60: 69 6f 6e 73 20 6f 66 20 52 2a 54 72 65 65 20 65  ions of R*Tree e
5d70: 6e 74 72 69 65 73 2c 20 74 68 65 20 72 53 63 6f  ntries, the rSco
5d80: 72 65 20 6d 69 67 68 74 20 62 65 20 61 72 72 61  re might be arra
5d90: 6e 67 65 64 20 73 6f 20 74 68 61 74 20 74 68 65  nged so that the
5da0: 0a 6c 61 72 67 65 73 74 20 6f 72 20 6d 6f 73 74  .largest or most
5db0: 20 73 69 67 6e 69 66 69 63 61 6e 74 20 65 6e 74   significant ent
5dc0: 72 69 65 73 20 61 72 65 20 72 65 74 75 72 6e 65  ries are returne
5dd0: 64 20 66 69 72 73 74 2c 20 61 6c 6c 6f 77 69 6e  d first, allowin
5de0: 67 20 74 68 65 0a 61 70 70 6c 69 63 61 74 69 6f  g the.applicatio
5df0: 6e 20 74 6f 20 64 69 73 70 6c 61 79 20 74 68 65  n to display the
5e00: 20 6d 6f 73 74 20 69 6d 70 6f 72 74 61 6e 74 20   most important 
5e10: 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 71 75 69 63  information quic
5e20: 6b 6c 79 2c 20 61 6e 64 0a 66 69 6c 6c 69 6e 67  kly, and.filling
5e30: 20 69 6e 20 73 6d 61 6c 6c 65 72 20 61 6e 64 20   in smaller and 
5e40: 6c 65 73 73 20 69 6d 70 6f 72 74 61 6e 74 20 64  less important d
5e50: 65 74 61 69 6c 73 20 61 73 20 74 68 65 79 20 62  etails as they b
5e60: 65 63 6f 6d 65 20 61 76 61 69 6c 61 62 6c 65 2e  ecome available.
5e70: 0a 0a 3c 70 3e 4f 74 68 65 72 20 69 6e 66 6f 72  ..<p>Other infor
5e80: 6d 61 74 69 6f 6e 20 66 69 65 6c 64 73 20 6f 66  mation fields of
5e90: 20 74 68 65 20 73 71 6c 69 74 65 33 5f 72 74 72   the sqlite3_rtr
5ea0: 65 65 5f 71 75 65 72 79 5f 69 6e 66 6f 20 73 74  ee_query_info st
5eb0: 72 75 63 74 75 72 65 20 61 72 65 0a 61 76 61 69  ructure are.avai
5ec0: 6c 61 62 6c 65 20 66 6f 72 20 75 73 65 20 62 79  lable for use by
5ed0: 20 74 68 65 20 78 51 75 65 72 79 46 75 6e 63 20   the xQueryFunc 
5ee0: 63 61 6c 6c 62 61 63 6b 2c 20 69 66 20 64 65 73  callback, if des
5ef0: 69 72 65 64 2e 20 20 5e 28 54 68 65 20 69 52 6f  ired.  ^(The iRo
5f00: 77 69 64 20 66 69 65 6c 64 0a 69 73 20 74 68 65  wid field.is the
5f10: 20 72 6f 77 69 64 20 28 74 68 65 20 66 69 72 73   rowid (the firs
5f20: 74 20 6f 66 20 74 68 65 20 33 20 74 6f 20 31 31  t of the 3 to 11
5f30: 20 63 6f 6c 75 6d 6e 73 20 69 6e 20 74 68 65 20   columns in the 
5f40: 52 2a 54 72 65 65 29 20 66 6f 72 20 74 68 65 20  R*Tree) for the 
5f50: 65 6c 65 6d 65 6e 74 0a 62 65 69 6e 67 20 63 6f  element.being co
5f60: 6e 73 69 64 65 72 65 64 2e 20 20 69 52 6f 77 69  nsidered.  iRowi
5f70: 64 20 69 73 20 6f 6e 6c 79 20 76 61 6c 69 64 20  d is only valid 
5f80: 66 6f 72 20 6c 65 61 76 65 73 2e 29 5e 20 20 5e  for leaves.)^  ^
5f90: 54 68 65 20 65 50 61 72 65 6e 74 57 69 74 68 69  The eParentWithi
5fa0: 6e 20 61 6e 64 0a 72 50 61 72 65 6e 74 53 63 6f  n and.rParentSco
5fb0: 72 65 20 76 61 6c 75 65 73 20 61 72 65 20 63 6f  re values are co
5fc0: 70 69 65 73 20 6f 66 20 74 68 65 20 65 57 69 74  pies of the eWit
5fd0: 68 69 6e 20 61 6e 64 20 72 53 63 6f 72 65 20 76  hin and rScore v
5fe0: 61 6c 75 65 73 20 66 72 6f 6d 20 74 68 65 0a 63  alues from the.c
5ff0: 6f 6e 74 61 69 6e 69 6e 67 20 73 75 62 74 72 65  ontaining subtre
6000: 65 20 6f 66 20 74 68 65 20 63 75 72 72 65 6e 74  e of the current
6010: 20 72 6f 77 2e 20 20 5e 54 68 65 20 61 6e 51 75   row.  ^The anQu
6020: 65 75 65 20 66 69 65 6c 64 20 69 73 20 61 6e 20  eue field is an 
6030: 61 72 72 61 79 0a 6f 66 20 6d 78 4c 65 76 65 6c  array.of mxLevel
6040: 2b 31 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 65  +1 unsigned inte
6050: 67 65 72 73 20 74 68 61 74 20 74 65 6c 6c 20 74  gers that tell t
6060: 68 65 20 63 75 72 72 65 6e 74 20 6e 75 6d 62 65  he current numbe
6070: 72 20 6f 66 20 65 6c 65 6d 65 6e 74 73 20 69 6e  r of elements in
6080: 0a 74 68 65 20 70 72 69 6f 72 69 74 79 20 71 75  .the priority qu
6090: 65 75 65 20 61 74 20 65 61 63 68 20 6c 65 76 65  eue at each leve
60a0: 6c 2e 0a 0a 3c 68 33 3e 36 2e 33 20 41 64 64 69  l...<h3>6.3 Addi
60b0: 74 69 6f 6e 61 6c 20 43 6f 6e 73 69 64 65 72 61  tional Considera
60c0: 74 69 6f 6e 73 20 66 6f 72 20 43 75 73 74 6f 6d  tions for Custom
60d0: 20 51 75 65 72 69 65 73 3c 2f 68 33 3e 0a 0a 3c   Queries</h3>..<
60e0: 70 3e 0a 5e 54 68 65 20 4d 41 54 43 48 20 6f 70  p>.^The MATCH op
60f0: 65 72 61 74 6f 72 20 6f 66 20 61 20 63 75 73 74  erator of a cust
6100: 6f 6d 20 52 2a 54 72 65 65 20 71 75 65 72 79 20  om R*Tree query 
6110: 66 75 6e 63 74 69 6f 6e 20 6d 75 73 74 20 62 65  function must be
6120: 20 61 20 74 6f 70 2d 6c 65 76 65 6c 0a 41 4e 44   a top-level.AND
6130: 2d 63 6f 6e 6e 65 63 74 65 64 20 74 65 72 6d 20  -connected term 
6140: 6f 66 20 74 68 65 20 57 48 45 52 45 20 63 6c 61  of the WHERE cla
6150: 75 73 65 2c 20 6f 72 20 65 6c 73 65 20 69 74 20  use, or else it 
6160: 77 69 6c 6c 20 6e 6f 74 20 62 65 20 75 73 61 62  will not be usab
6170: 6c 65 0a 62 79 20 74 68 65 20 52 2a 54 72 65 65  le.by the R*Tree
6180: 20 71 75 65 72 79 20 6f 70 74 69 6d 69 7a 65 72   query optimizer
6190: 20 61 6e 64 20 74 68 65 20 71 75 65 72 79 20 77   and the query w
61a0: 69 6c 6c 20 6e 6f 74 20 62 65 20 72 75 6e 6e 61  ill not be runna
61b0: 62 6c 65 2e 0a 5e 49 66 20 74 68 65 20 4d 41 54  ble..^If the MAT
61c0: 43 48 20 6f 70 65 72 61 74 6f 72 20 69 73 20 63  CH operator is c
61d0: 6f 6e 6e 65 63 74 65 64 20 74 6f 20 6f 74 68 65  onnected to othe
61e0: 72 20 74 65 72 6d 73 20 6f 66 20 74 68 65 20 57  r terms of the W
61f0: 48 45 52 45 20 63 6c 61 75 73 65 20 0a 76 69 61  HERE clause .via
6200: 20 61 6e 20 4f 52 20 6f 70 65 72 61 74 6f 72 2c   an OR operator,
6210: 20 66 6f 72 20 65 78 61 6d 70 6c 65 2c 20 74 68   for example, th
6220: 65 20 71 75 65 72 79 20 77 69 6c 6c 20 66 61 69  e query will fai
6230: 6c 20 77 69 74 68 20 61 6e 20 65 72 72 6f 72 2e  l with an error.
6240: 0a 0a 3c 70 3e 0a 5e 54 77 6f 20 6f 72 20 6d 6f  ..<p>.^Two or mo
6250: 72 65 20 4d 41 54 43 48 20 6f 70 65 72 61 74 6f  re MATCH operato
6260: 72 73 20 61 72 65 20 61 6c 6c 6f 77 65 64 20 69  rs are allowed i
6270: 6e 20 74 68 65 20 73 61 6d 65 20 57 48 45 52 45  n the same WHERE
6280: 20 63 6c 61 75 73 65 2c 20 61 73 20 6c 6f 6e 67   clause, as long
6290: 0a 61 73 20 74 68 65 79 20 61 72 65 20 63 6f 6e  .as they are con
62a0: 6e 65 63 74 65 64 20 62 79 20 41 4e 44 20 6f 70  nected by AND op
62b0: 65 72 61 74 6f 72 73 2e 20 20 48 6f 77 65 76 65  erators.  Howeve
62c0: 72 2c 0a 74 68 65 20 52 2a 54 72 65 65 20 71 75  r,.the R*Tree qu
62d0: 65 72 79 20 65 6e 67 69 6e 65 20 6f 6e 6c 79 20  ery engine only 
62e0: 63 6f 6e 74 61 69 6e 73 20 61 20 73 69 6e 67 6c  contains a singl
62f0: 65 20 70 72 69 6f 72 69 74 79 20 71 75 65 75 65  e priority queue
6300: 2e 20 20 5e 54 68 65 20 70 72 69 6f 72 69 74 79  .  ^The priority
6310: 0a 61 73 73 69 67 6e 65 64 20 74 6f 20 65 61 63  .assigned to eac
6320: 68 20 6e 6f 64 65 20 69 6e 20 74 68 65 20 73 65  h node in the se
6330: 61 72 63 68 20 69 73 20 74 68 65 20 6c 6f 77 65  arch is the lowe
6340: 73 74 20 70 72 69 6f 72 69 74 79 20 72 65 74 75  st priority retu
6350: 72 6e 65 64 20 62 79 20 61 6e 79 0a 6f 66 20 74  rned by any.of t
6360: 68 65 20 4d 41 54 43 48 20 6f 70 65 72 61 74 6f  he MATCH operato
6370: 72 73 2e 0a                                      rs..