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