一、概述

R树是专为进行范围查询而设计的特殊索引。R 树最常用于地理空间系统，其中每个条目都是一个具有最小和最大 X 和 Y 坐标的矩形。给定一个查询矩形，R-Tree 能够快速找到包含在查询矩形内或与查询矩形重叠的所有条目。这个想法很容易扩展到三个维度以用于 CAD 系统。R-Trees 也可用于时域范围查找。例如，假设一个数据库记录了大量事件的开始和结束时间。R-Tree 能够快速找到在给定时间间隔内任何时间处于活动状态的所有事件，或在特定时间间隔内开始的所有事件，或在给定时间间隔内开始和结束的所有事件。等等。

R-Tree 概念起源于 Toni Guttman： R-Trees：A Dynamic Index Structure for Spatial Searching，Proc。1984 年 ACM SIGMOD 数据管理国际会议，第 47-57 页。SQLite 中的实现是对 Guttman 最初想法的改进，通常称为“R*Trees”，Norbert Beckmann、Hans-Peter Kriegel、Ralf Schneider、Bernhard Seeger 对此进行了描述： R*-Tree：高效且稳健的访问点和矩形的方法。SIGMOD 会议 1990：322-331。

2.编译 R*Tree 模块

SQLite R*Tree 模块的源代码作为合并的一部分包含在内，但默认情况下是禁用的。要启用 R*Tree 模块，只需使用定义的SQLITE_ENABLE_RTREE C 预处理器宏进行编译。对于许多编译器，这是通过将选项“-DSQLITE_ENABLE_RTREE=1”添加到编译器命令行来实现的。

3.使用 R*Tree 模块

SQLite R*Tree 模块作为虚拟表实现。每个 R*Tree 索引都是一个包含 3 到 11 之间的奇数列的虚拟表。第一列始终是一个 64 位带符号整数主键。其他列是成对的，每个维度一对，分别包含该维度的最小值和最大值。因此，一维 R*Tree 有 3 列。二维 R*Tree 有 5 列。3 维 R*Tree 有 7 列。4 维 R*Tree 有 9 列。而一个 5 维 R*Tree 有 11 列。SQLite R*Tree 实现不支持宽度超过 5 维的 R*Trees。

SQLite R*Tree 的第一列类似于普通 SQLite 表的整数主键列。它可能只存储一个 64 位有符号整数值。向该列中插入 NULL 值会导致 SQLite 自动生成一个新的唯一主键值。如果尝试将任何其他非整数值插入此列，r-tree 模块会在将其写入数据库之前静默地将其转换为整数。

最小值/最大值对列存储为“rtree”虚拟表的 32 位浮点值或“rtree_i32”虚拟表中的 32 位带符号整数。与可以以各种数据类型和格式存储数据的常规 SQLite 表不同，R*Tree 严格执行这些存储类型。如果任何其他类型的值被插入到这样的列中，r-tree 模块会在将新记录写入数据库之前悄悄地将其转换为所需的类型。

3.1. 创建 R*Tree 索引

一个新的 R*Tree 索引创建如下：

CREATE VIRTUAL TABLE <name> USING rtree(<column-names>);

<name>是您的应用程序为 R*Tree 索引选择的名称， < column-names>是 3 到 11 列之间的逗号分隔列表。虚拟 <name> 表创建三个影子表来实际存储其内容。这些影子表的名称是：

<name>_node

<name>_rowid

<name>_parent

影子表是普通的 SQLite 数据表。如果愿意，您可以直接查询它们，尽管这不太可能揭示任何特别有用的信息。您可以UPDATE、DELETE、INSERT甚至DROP 影子表，尽管这样做会破坏您的 R*Tree 索引。所以最好简单地忽略影子表。认识到它们保存着您的 R*Tree 索引信息并就此放手。

例如，考虑创建一个用于空间查询的二维 R*Tree 索引：

CREATE VIRTUAL TABLE demo_index USING rtree(
   id,              -- Integer primary key
   minX, maxX,      -- Minimum and maximum X coordinate
   minY, maxY       -- Minimum and maximum Y coordinate
);

3.1.1. 列命名详细信息

在 CREATE VIRTUAL TABLE 语句的“rtree”参数中，列的名称取自每个参数的第一个标记。每个参数中的所有后续标记都将被静默忽略。这意味着，例如，如果您尝试为列赋予类型亲和性或向列添加诸如 UNIQUE 或 NOT NULL 或 DEFAULT 的约束，这些额外的标记将被接受为有效的，但它们不会更改树。在 RTREE 虚拟表中，第一列始终具有 INTEGER类型关联，所有其他数据列具有 REAL类型关联。在 RTREE_I32 虚拟表中，所有列都具有 INTEGER 类型关联。

推荐的做法是省略 rtree 规范中的任何额外标记。让“rtree”的每个参数都是一个普通标签，即相应列的名称，并从参数列表中省略所有其他标记。

3.2. 填充 R*Tree 索引

通常的INSERT、UPDATE和DELETE命令在 R*Tree 索引上工作，就像在常规表上一样。因此，要将一些数据插入到我们的示例 R*Tree 索引中，我们可以这样做：

INSERT INTO demo_index VALUES
  (28215, -80.781227, -80.604706, 35.208813, 35.297367),
  (28216, -80.957283, -80.840599, 35.235920, 35.367825),
  (28217, -80.960869, -80.869431, 35.133682, 35.208233),
  (28226, -80.878983, -80.778275, 35.060287, 35.154446),
  (28227, -80.745544, -80.555382, 35.130215, 35.236916),
  (28244, -80.844208, -80.841988, 35.223728, 35.225471),
  (28262, -80.809074, -80.682938, 35.276207, 35.377747),
  (28269, -80.851471, -80.735718, 35.272560, 35.407925),
  (28270, -80.794983, -80.728966, 35.059872, 35.161823),
  (28273, -80.994766, -80.875259, 35.074734, 35.172836),
  (28277, -80.876793, -80.767586, 35.001709, 35.101063),
  (28278, -81.058029, -80.956375, 35.044701, 35.223812),
  (28280, -80.844208, -80.841972, 35.225468, 35.227203),
  (28282, -80.846382, -80.844193, 35.223972, 35.225655);

上面的条目是北卡罗来纳州夏洛特附近 14 个邮政编码的边界框（经度和纬度）。一个真实的数据库会有数千、数百万或数十亿个这样的条目，但这个 14 行的小样本足以说明这些想法。

3.3. 查询 R*Tree 索引

任何有效的查询都适用于 R*Tree 索引。R*Tree 实现只是让某些类型的查询特别高效。针对主键的查询是有效的：

SELECT * FROM demo_index WHERE id=28269;

当然，一个普通的 SQLite 表也会高效地查询它的整数主键，所以前面的并不重要。使用 R*Tree 的一个重要原因是您可以有效地对坐标范围进行范围查询。例如，SQLite 项目的主办公室位于 35.37785，-80.77470。要查找哪些邮政编码可以为该办公室提供服务，可以正确：

SELECT id FROM demo_index
 WHERE minX<=-80.77470 AND maxX>=-80.77470
   AND minY<=35.37785  AND maxY>=35.37785;

上面的查询将快速定位在其边界框中包含 SQLite 总部的所有邮政编码，即使 R*Tree 包含许多条目也是如此。上一个是“包含在其中”查询的示例。R*Tree 还支持“重叠”查询。例如，要查找与 28269 邮政编码重叠的所有邮政编码边界框：

SELECT A.id FROM demo_index AS A, demo_index AS B
 WHERE A.maxX>=B.minX AND A.minX<=B.maxX
   AND A.maxY>=B.minY AND A.minY<=B.maxY
   AND B.id=28269;

第二个查询将找到 28269 条目（因为每个边界框都与其自身重叠）以及其他与 28269 足够接近以至于它们的边界框重叠的邮政编码。

请注意，为了使索引搜索高效，不必限制 R*Tree 索引中的所有坐标。例如，可能想要查询与 35 度线重叠的所有对象：

SELECT id FROM demo_index
 WHERE maxY>=35.0  AND minY<=35.0;

但是，一般来说，R*Tree 模块必须处理的约束越多，边界框越小，结果返回的速度就越快。

3.4. 舍入误差

默认情况下，坐标使用 32 位浮点值存储在 R*Tree 中。当一个坐标不能用 32 位浮点数精确表示时，下界坐标向下取整，上界坐标向上取整。因此，边界框可能比指定的稍大，但绝不会变小。这正是执行更常见的“重叠”查询所需要的，应用程序希望在 R*Tree 中找到与查询边界框重叠的每个条目。如果条目边界框的边缘对应于查询边界框的边缘，则向外舍入条目边界框可能会导致一些额外的条目出现在重叠查询中。但是重叠查询永远不会错过有效的表条目。

但是，对于“包含在其中”样式的查询，如果条目边界框的边缘与查询边界框的边缘相对应，则向外舍入边界框可能会导致某些条目从结果集中排除。为防止这种情况，应用程序应通过向下舍入每个维度中的较低坐标并向上舍入顶部坐标来稍微扩展其包含的查询框（0.000012%）。

3.5. 同时阅读和写作

Guttman R-Tree 算法的本质是任何写入都可能从根本上重构树，并在此过程中更改节点的扫描顺序。由于这个原因，通常不可能在 R-Tree 的查询中间修改 R-Tree。尝试这样做将失败并出现SQLITE_LOCKED “数据库表已锁定”错误。

因此，举例来说，假设一个应用程序像这样对 R-Tree 运行一个查询：

SELECT id FROM demo_index
 WHERE maxY>=35.0  AND minY<=35.0;

然后对于返回的每个“id”值，假设应用程序创建如下所示的 UPDATE 语句并将返回的“id”值绑定到“?1”参数：

UPDATE demo_index SET maxY=maxY+0.5 WHERE id=?1;

那么 UPDATE 可能会因 SQLITE_LOCKED 错误而失败。原因是初始查询尚未运行完成。它记住它在 R 树扫描中间的位置。因此不能容忍对 R-Tree 的更新，因为这会中断扫描。

这只是 R-Tree 扩展的限制。SQLite 中的普通表是可以同时读写的。其他虚拟表可能（或可能不会）也具有该功能。在某些情况下，如果 R-Tree 能够在开始更新之前弄清楚如何可靠地运行查询直至完成，则 R-Tree 可以同时进行读写。但是您不应该对每个查询都指望它。一般来说，最好避免同时对同一个 R-Tree 运行查询和更新。

如果您确实需要根据针对同一 R-Tree 的复杂查询更新 R-Tree，最好先运行复杂查询并将结果存储在临时表中，然后根据存储的值更新 R-Tree在临时表中。

4.有效使用 R*Trees

对于 3.24.0 (2018-06-04) 之前的 SQLite 版本，R*Tree 索引存储的关于对象的唯一信息是它的整数 ID 和它的边界框。附加信息需要存储在单独的表中，并使用主键与 R*Tree 索引相关联。对于上面的示例，可以创建一个辅助表，如下所示：

CREATE TABLE demo_data(
  id INTEGER PRIMARY KEY,  -- primary key
  objname TEXT,            -- name of the object
  objtype TEXT,            -- object type
  boundary BLOB            -- detailed boundary of object
);

在此示例中，demo_data.boundary 字段旨在保存对象精确边界的某种二进制表示形式。R*Tree 索引仅包含对象的轴对齐矩形边界。R*Tree 边界只是真实对象边界的近似值。所以通常发生的情况是，R*Tree 索引用于将搜索范围缩小到候选对象列表，然后对每个候选对象进行更详细和昂贵的计算，以确定候选对象是否真正满足搜索条件。

要点： R*Tree 索引通常不会提供准确的答案，而只是将潜在答案集从数百万减少到几十个。

假设 demo_data.boundary 字段包含邮政编码复杂二维边界的一些专有数据描述，并假设应用程序使用sqlite3_create_function()接口创建了应用程序定义的函数“contained_in(boundary,lat,long)”接受 demo_data.boundary 对象和纬度和经度，如果纬度/经度包含在边界内，则返回 true 或 false。人们可能会认为“contained_in()”是一个相对较慢的函数，我们不想过于频繁地调用它。那么找到主要 SQLite 办公室的特定邮政编码的有效方法是运行这样的查询：

SELECT objname FROM demo_data, demo_index
 WHERE demo_data.id=demo_index.id
   AND contained_in(demo_data.boundary, 35.37785, -80.77470)
   AND minX<=-80.77470 AND maxX>=-80.77470
   AND minY<=35.37785  AND maxY>=35.37785;

请注意上面的查询是如何工作的：R*Tree 索引在外循环中运行，以查找边界框中包含 SQLite 总部的条目。对于找到的每一行，SQLite 在 demo_data 表中查找相应的条目。然后它使用 demo_data 表中的边界字段作为 contained_in() 函数的参数，如果该函数返回 true，则我们知道所寻找的坐标位于该邮政编码边界内。

使用以下更简单的查询，即使不使用 R*Tree 索引，也能得到相同的答案：

SELECT objname FROM demo_data
 WHERE contained_in(demo_data.boundary, 35.37785, -80.77470);

后一个查询的问题在于它必须将 contained_in() 函数应用于 demo_data 表中的所有条目。在倒数第二个查询中使用 R*Tree 将对 contained_in() 函数的调用次数减少到整个表的一小部分。R*Tree 索引本身并没有找到确切的答案，它只是限制了搜索空间。

4.1. 辅助栏目

从 SQLite 版本 3.24.0 (2018-06-04) 开始，r-tree 表可以有存储任意数据的辅助列。可以使用辅助列代替辅助表，例如“demo_data”。

辅助列在列名称前标有“+”符号。辅助列必须在所有坐标边界列之后。RTREE 表的总列数不能超过 100。也就是说，整数主键列、坐标边界列和所有辅助列的列数必须小于或等于100。以下示例显示了一个带有辅助列的 r-tree 表，它等效于上面的两个表“demo_index”和“demo_data”：

CREATE VIRTUAL TABLE demo_index2 USING rtree(
   id,              -- Integer primary key
   minX, maxX,      -- Minimum and maximum X coordinate
   minY, maxY,      -- Minimum and maximum Y coordinate
   +objname TEXT,   -- name of the object
   +objtype TEXT,   -- object type
   +boundary BLOB   -- detailed boundary of object
);

通过将位置数据和相关信息组合到同一个表中，辅助列可以提供更清晰的模型并减少连接的需要。例如，之前 demo_index 和 demo_data 之间的连接现在可以写成一个简单的查询，如下所示：

SELECT objname FROM demo_index2
 WHERE contained_in(boundary, 35.37785, -80.77470)
   AND minX<=-80.77470 AND maxX>=-80.77470
   AND minY<=35.37785  AND maxY>=35.37785;

4.1.1. 限制

对于辅助列，只有列名很重要。忽略类型关联。NOT NULL、UNIQUE、REFERENCES 或 CHECK 等约束也将被忽略。但是，未来版本的 SQLite 可能会开始关注类型亲和性和约束，因此建议辅助列的用户将两者留空，以避免将来出现兼容性问题。

5.整数值 R 树

默认虚拟表（“rtree”）将坐标存储为单精度（4 字节）浮点数。如果需要整数坐标，请改为使用“rtree_i32”声明表：

CREATE VIRTUAL TABLE intrtree USING rtree_i32(id,x0,x1,y0,y1,z0,z1);

rtree_i32 将坐标存储为 32 位有符号整数。尽管它使用整数存储值，rtree_i32 虚拟表仍然在内部使用浮点计算作为 r-tree 算法的一部分。

6.自定义 R 树查询

通过在 SELECT 查询的 WHERE 子句中使用标准 SQL 表达式，程序员可以查询与特定边界框相交或包含在特定边界框内的所有 R*Tree 条目。自定义 R*Tree 查询，在 SELECT 的 WHERE 子句中使用 MATCH 运算符，允许程序员查询与任意区域或形状相交的 R*Tree 条目集，而不仅仅是一个框。例如，此功能可用于计算 R*Tree 中从位于 3-D 空间中的相机可见的对象子集。

自定义 R*Tree 查询的区域由应用程序实现的 R*Tree 几何回调定义，并通过调用以下两个 API 之一向 SQLite 注册：

int sqlite3_rtree_query_callback(
  sqlite3 *db,
  const char *zQueryFunc,
  int (*xQueryFunc)(sqlite3_rtree_query_info*),
  void *pContext,
  void (*xDestructor)(void*)
);
int sqlite3_rtree_geometry_callback(
  sqlite3 *db,
  const char *zGeom,
  int (*xGeom)(sqlite3_rtree_geometry *, int nCoord, double *aCoord, int *pRes),
  void *pContext
);

sqlite3_rtree_query_callback() 在 SQLite 版本 3.8.5 (2014-06-04) 中可用，并且是首选接口。sqlite3_rtree_geometry_callback() 是一个较旧且不太灵活的接口，支持向后兼容。

对上述 API 之一的调用会创建一个由第二个参数（zQueryFunc 或 zGeom）命名的新 SQL 函数。当该 SQL 函数出现在 MATCH 运算符的右侧并且 MATCH 运算符的左侧是 R*Tree 虚拟表中的任意列时，则由第三个参数（xQueryFunc 或 xGeom）定义的回调是调用以确定特定对象或子树是否与所需区域重叠。

例如，可以使用如下查询来查找与以 45.3、22.9 为中心、半径为 5.0 的圆重叠的所有 R*Tree 条目：

SELECT id FROM demo_index WHERE id MATCH circle(45.3, 22.9, 5.0)

无论是sqlite3_rtree_geometry_callback() 还是sqlite3_rtree_query_callback() 用于注册SQL 函数的接口，自定义查询的SQL 语法都是相同的。但是，较新的查询式回调使应用程序可以更好地控制查询的进行方式。

6.1. 旧版 xGeom 回调

使用四个参数调用旧版 xGeom 回调。第一个参数是指向 sqlite3_rtree_geometry 结构的指针，它提供有关如何调用 SQL 函数的信息。第二个参数是每个 r-tree 条目中的坐标数，并且对于任何给定的 R*Tree 始终相同。坐标数对于一维 R*Tree 为 2，对于二维 R*Tree 为 4，对于 3 维 R*Tree 为 6，等等。第三个参数 aCoord[] 是一个 nCoord 坐标数组，用于定义要测试的边界框。最后一个参数是一个指针，回调结果应该写入其中。如果 aCoord[] 定义的边界框完全在 xGeom 回调定义的区域之外，则结果为零；如果边界框在 xGeom 区域内部或与 xGeom 区域重叠，则结果为非零。xGeom 回调通常应返回 SQLITE_OK。如果 xGeom 返回 SQLITE_OK 以外的任何内容，则 r-tree 查询将因错误而中止。

xGeom 回调的第一个参数指向的 sqlite3_rtree_geometry 结构具有如下所示的结构。完全相同的 sqlite3_rtree_geometry 结构用于同一查询中同一 MATCH 运算符的每个回调。sqlite3_rtree_geometry 结构的内容由 SQLite 初始化，但随后不会修改。如果需要，回调可以自由更改结构的 pUser 和 xDelUser 元素。

typedef struct sqlite3_rtree_geometry sqlite3_rtree_geometry;
struct sqlite3_rtree_geometry {
  void *pContext;                 /* Copy of pContext passed to s_r_g_c() */
  int nParam;                     /* Size of array aParam */
  double *aParam;                 /* Parameters passed to SQL geom function */
  void *pUser;                    /* Callback implementation user data */
  void (*xDelUser)(void *);       /* Called by SQLite to clean up pUser */
};

注册回调时，sqlite3_rtree_geometry 结构的 pContext 成员始终设置为传递给 sqlite3_rtree_geometry_callback() 的 pContext 参数的副本。aParam[] 数组（大小为 nParam）包含传递给 MATCH 运算符右侧的 SQL 函数的参数值。在上面的示例“circle”查询中，nParam 将设置为 3，aParam[] 数组将包含三个值 45.3、22.9 和 5.0。

sqlite3_rtree_geometry 结构的 pUser 和 xDelUser 成员最初设置为 NULL。pUser 变量可以由回调实现设置为任何可能对同一查询中回调的后续调用有用的任意值（例如，指向用于测试区域交叉的复杂数据结构的指针）。如果 xDelUser 变量设置为非 NULL 值，则在查询完成运行后，SQLite 会自动调用它，并将 pUser 变量的值作为唯一参数。换句话说，可以将 xDelUser 设置为 pUser 值的析构函数。

xGeom 回调始终对 r 树进行深度优先搜索。

6.2. 新的 xQueryFunc 回调

较新的 xQueryFunc 回调在每次调用时从 r-tree 查询引擎接收更多信息，并在返回之前将更多信息发送回查询引擎。为了帮助保持接口的可管理性，xQueryFunc 回调从查询引擎发送和接收信息作为 sqlite3_rtree_query_info 结构中的字段：

struct sqlite3_rtree_query_info {
  void *pContext;                   /* pContext from when function registered */
  int nParam;                       /* Number of function parameters */
  sqlite3_rtree_dbl *aParam;        /* value of function parameters */
  void *pUser;                      /* callback can use this, if desired */
  void (*xDelUser)(void*);          /* function to free pUser */
  sqlite3_rtree_dbl *aCoord;        /* Coordinates of node or entry to check */
  unsigned int *anQueue;            /* Number of pending entries in the queue */
  int nCoord;                       /* Number of coordinates */
  int iLevel;                       /* Level of current node or entry */
  int mxLevel;                      /* The largest iLevel value in the tree */
  sqlite3_int64 iRowid;             /* Rowid for current entry */
  sqlite3_rtree_dbl rParentScore;   /* Score of parent node */
  int eParentWithin;                /* Visibility of parent node */
  int eWithin;                      /* OUT: Visiblity */
  sqlite3_rtree_dbl rScore;         /* OUT: Write the score here */
  /* The following fields are only available in 3.8.11 and later */
  sqlite3_value **apSqlParam;       /* Original SQL values of parameters */
};

sqlite3_rtree_query_info结构体的前五个字段与sqlite3_rtree_geometry结构体相同，意义完全相同。sqlite3_rtree_query_info 结构还包含 nCoord 和 aCoord 字段，它们与 xGeom 回调中的同名参数具有相同的含义。

xQueryFunc 必须将 sqlite3_rtree_query_info 的 eWithin 字段设置为 NOT_WITHIN、PARTLY_WITHIN 或 FULLY_WITHIN 值之一，具体取决于 aCoord[] 定义的边界框是否完全位于区域之外、与区域重叠或完全位于区域内，分别。此外，xQueryFunc 必须将 rScore 字段设置为一个非负值，该值指示应分析和返回查询的子树和条目的顺序。首先处理较小的分数。

顾名思义，R*Tree 被组织为一棵树。树的每个节点都是一个边界框。树的根是一个边界框，它封装了树的所有元素。根下面是许多子树（通常为 20 个或更多），每个子树都有自己的较小边界框，每个子树都包含 R*Tree 条目的一些子集。子树可能有子子树，依此类推，直到最后到达树的叶子，它们是实际的 R*Tree 条目。

通过使根节点成为按 rScore 排序的优先级队列中的唯一条目来初始化 R*Tree 查询。查询通过从具有最低分数的优先级队列中提取条目来继续。如果该条目是叶子（意味着它是实际的 R*Tree 条目而不是子树），则该条目作为查询结果的一行返回。如果提取的优先级队列条目是一个节点（子树），则该节点的下一个子节点将传递给 xQueryFunc 回调。如果该节点有更多子节点，则将其返回到优先级队列。否则它被丢弃。xQueryFunc 回调将 eWithin 设置为 PARTLY_WITHIN 或 FULLY_WITHIN 的那些子元素将使用回调提供的分数添加到优先级队列中。返回 NOT_WITHIN 的子元素将被丢弃。查询一直运行到优先级队列为空。

R*Tree 中的每个叶条目和节点（子树）都有一个整数“级别”。叶子的级别为 0。叶子的第一个包含子树的级别为 1。R*Tree 的根具有最大的级别值。sqlite3_rtree_query_info 结构中的 mxLevel 条目是 R*Tree 根的级别值。sqlite3_rtree_query_info 中的 iLevel 条目给出了被查询对象的级别。

大多数 R*Tree 查询使用深度优先搜索。这是通过将 rScore 设置为 iLevel 来实现的。深度优先搜索通常是首选，因为它最大限度地减少了优先级队列中的元素数量，从而减少了内存需求并加快了处理速度。但是，某些应用程序可能更喜欢广度优先搜索，这可以通过将 rScore 设置为 mxLevel-iLevel 来实现。通过为 rScore 创建更复杂的公式，应用程序可以对搜索子树和返回叶 R*Tree 条目的顺序进行详细控制。例如，在具有数百万个 R*Tree 条目的应用程序中，可以安排 rScore 以便首先返回最大或最重要的条目，从而使应用程序能够快速显示最重要的信息，

如果需要，sqlite3_rtree_query_info 结构的其他信息字段可供 xQueryFunc 回调使用。iRowid 字段是正在考虑的元素的 rowid（R*Tree 中 3 到 11 列的第一列）。iRowid 只对叶子有效。eParentWithin 和 rParentScore 值是当前行的包含子树中 eWithin 和 rScore 值的副本。anQueue 字段是一个 mxLevel+1 无符号整数数组，它告诉每个级别的优先级队列中当前元素的数量。

6.3. 自定义查询的其他注意事项

自定义 R*Tree 查询函数的 MATCH 运算符必须是 WHERE 子句的顶级 AND 连接项，否则 R*Tree 查询优化器将无法使用它并且查询将无法运行。例如，如果 MATCH 运算符通过 OR 运算符连接到 WHERE 子句的其他项，则查询将失败并出现错误。

同一个 WHERE 子句中允许使用两个或多个 MATCH 运算符，只要它们由 AND 运算符连接即可。然而，R*Tree 查询引擎只包含一个优先级队列。分配给搜索中每个节点的优先级是任何 MATCH 运算符返回的最低优先级。

七、实施细节

以下部分描述了 R*Tree 实现的一些底层细节，这些细节可能对故障排除或性能分析很有用。

7.1. 影子表

R*Tree 索引的内容实际上存储在三个普通的 SQLite 表中，这些表的名称源自 R*Tree 的名称。这三个表称为“影子表”。这是他们的模式：

CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data)
CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode)
CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno)

每个影子表名称中的“%”被 R*Tree 虚拟表的名称替换。因此，如果 R*Tree 表的名称是“xyz”，那么三个影子表将是“xyz_node”、“xyz_parent”和“xyz_rowid”。

每个 R*Tree 节点在 %_node 表中都有一个条目。R*Tree 节点由一个或多个彼此接近的条目组成。树的 R*Tree 节点。除根以外的所有节点在 %_parent 影子表中都有一个条目来标识父节点。R*Tree 中的每个条目都有一个 rowid。%_rowid 影子表将条目 rowids 映射到包含该条目的节点。

附加到 %_rowid 表的额外列包含辅助列的内容。这些额外的 %_rowid 列的名称可能与实际的辅助列名称不同。

7.2. 使用 rtreecheck() SQL 函数进行完整性检查

标量 SQL 函数 rtreecheck(R) 或 rtreecheck(S,R) 对数据库 S 中包含的名为 R 的 rtree 表运行完整性检查。该函数返回对发现的任何问题的人类语言描述，或者字符串 'ok' 如果一切都好。在 R*Tree 虚拟表上运行 rtreecheck() 类似于在数据库上运行PRAGMA integrity_check。

示例：要验证名为“demo_index”的 R*Tree 格式正确且内部一致，请运行：

SELECT rtreecheck('demo_index');

rtreecheck() 函数执行以下检查：

对于 r 树结构（%_node 表）中的每个单元格，即：
1. 对于每个维度，(coord1 <= coord2)。
2. 除非该单元格位于根节点上，否则该单元格由父节点上的父单元格界定。
3. 对于叶节点，%_rowid 表中有一个条目对应于指向正确节点的单元格的 rowid 值。
4. 对于非叶节点上的单元格，%_parent 表中有一个条目从单元格的子节点映射到它所在的节点。
%_rowid 表中的条目数与 r 树结构中的叶单元数相同，并且有一个叶单元对应于 %_rowid 表中的每个条目。
%_parent 表中的条目数与 r 树结构中的非叶单元格数相同，并且有一个非叶单元格对应于 %_parent 表中的每个条目。