SQLite R*Tree 模块（三十三）

1. 概述

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

R-Tree 概念起源于 Toni Guttman：R-Trees： A Dynamic Index Structure for Spatial Searching， 1984 ACM SIGMOD 数据管理国际会议，第47-57页。在SQLite中发现的实现是对Guttman原始的改进想法，通常称为“R*Trees”，由 Norbert Beckmann、Hans-Peter Kriegel、Ralf Schneider、Bernhard Seeger：R*-树：一种高效且鲁棒的点访问方法和矩形。SIGMOD会议1990：322-331。

2. 编译 R*Tree 模块

SQLite R*Tree 模块的源代码作为一部分包含在内的合并。但是，根据配置选项以及您正在使用的特定版本的 SQLite，它可能会也可能不会默认启用。要确保启用 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 列。三维 R*Tree 有 7 列。一个 4 维 R*Tree 有 9 列。一个 5 维 R*Tree 有 11 列。SQLite R*Tree 实现不支持宽度超过 5 维的 R*Tree。

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

最小值/最大值对列存储为 32 位浮点值 “rtree”虚拟表或“rtree_i32”虚拟表中的 32 位有符号整数表。与常规 SQLite 表不同，它可以将数据存储在各种数据类型和格式，R*Tree 严格执行这些存储类型。如果将任何其他类型的值插入到此类列中，则 r 树模块在写入数据库的新记录。

3.1. 创建 R*Tree 索引

将按如下方式创建新的 R*Tree 索引：

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

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

<name>_node

<name>_rowid

<name>_parent

影子表是普通的 SQLite 数据表。您可以查询它们如果您愿意，请直接使用，尽管这不太可能透露任何特别的信息有用。您可以更新、删除、插入甚至删除影子表，尽管这样做会损坏您的 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 的行为。在 RTREE 虚拟表中，第一列的类型亲和力始终为 INTEGER，所有其他数据列的类型亲和性为 REAL。在RTREE_I32虚拟表中，所有列的类型亲和力均为 INTEGER。

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

3.2. 填充 R*Tree 索引

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

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*树实现只是进行某些类型的查询，特别是有效。对主键的查询是有效的：

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 包含许多条目。前面是一个例子 “contained-within”查询。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 中查找重叠的每个条目查询边界框。向外舍入条目边界框可能会导致在重叠的查询中出现很少的额外条目，如果条目边界框对应于查询边界框的边缘。但重叠查询永远不会错过有效的表条目。

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

3.5. 同时阅读和写作

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

因此，例如，假设一个应用程序对 R 树运行一个查询，例如这：

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 树，最好先运行复杂的查询并存储结果在一个临时表中，然后根据值更新 R 树存储在临时表中。

4. 有效使用 R*Trees

对于 3.24.0 之前的 SQLite 版本（2018-06-04）， 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 对象以及纬度和经度如果纬度/经度包含在边界。人们可能会认为“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 树表可以具有存储任意数据的辅助列。可以使用辅助柱代替辅助表，例如“demo_data”。

辅助列在列名前标有“+”符号。辅助列必须位于所有坐标边界列之后。 RTREE 表的总列数不能超过 100 列。换言之，包含整数主键列的列计数，坐标边界列和所有辅助列必须小于 100。以下示例显示了一个包含辅助列的 r 树表，该表具有辅助列等同于上面的两个表“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虚拟的 table 仍然在内部使用浮点计算作为 R 树算法。

6. 自定义 R-Tree 查询

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

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

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 之一会创建一个新的 SQL 函数，该函数由第二个参数（zQueryFunc 或 zGeom）。当该 SQL 函数出现时在 MATCH 运算符的右侧和 MATCH 运算符是 R*Tree 虚拟表中的任意列，然后是回调由第三个参数（xQueryFunc 或 xGeom）定义，用于确定如果特定对象或子树与所需区域重叠。

例如，可以使用如下所示的查询来查找所有与圆重叠的 R*树条目居中 45.3,22.9 和半径 5.0：

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

无论哪种方式，自定义查询的 SQL 语法都是相同的接口，sqlite3_rtree_geometry_callback（）或 sqlite3_rtree_query_callback（），用于注册 SQL 函数。但是，较新的查询样式回调使应用程序能够更好地控制查询的进行方式。

6.1. 遗留的 xGeom 回调

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

第一个参数的sqlite3_rtree_geometry结构 xGeom 回调指向的结构如下所示。一模一样 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 成员结构始终设置为 pContext 的副本参数传递给 sqlite3_rtree_geometry_callback（）当回调已注册。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 树接收更多信息每次调用时的查询引擎，并将更多信息发送回查询引擎在它返回之前。为了帮助保持接口的可管理性，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 条目。

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

R*Tree 中的每个叶条目和节点（子树）都有一个整数“级别”。叶子的等级为 0。第一个包含叶子的子树有 A 级 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 运算符连接到 WHERE 子句的其他术语例如，通过 OR 运算符，查询将失败并显示错误。

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

7. 实施细节

以下各节介绍了 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（）虚拟表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 表。