小巧。快速。可靠。
三选二。
三选二。
一个 R-Tree 是一种专门为范围查询设计的特殊索引。R-Tree 最常用于地理空间系统，其中每个条目都是一个矩形，具有最小和最大 X 和 Y 坐标。给定一个查询矩形，R-Tree 可以快速找到所有包含在查询矩形内或与查询矩形重叠的条目。这个想法很容易扩展到三个维度，用于 CAD 系统。R-Tree 也用于时域范围查找。例如，假设一个数据库记录了大量事件的开始和结束时间。R-Tree 可以快速找到在给定时间间隔内一直处于活动状态的所有事件，或在特定时间间隔内开始的所有事件，或在给定时间间隔内开始和结束的所有事件。等等。
R-Tree 的概念起源于 Toni Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching, Proc. 1984 ACM SIGMOD International Conference on Management of Data, pp. 47-57。SQLite 中的实现是 Guttman 原有想法的改进，通常被称为“R*Tree”，由 Norbert Beckmann、Hans-Peter Kriegel、Ralf Schneider、Bernhard Seeger 描述：The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331。
SQLite R*Tree 模块的源代码作为 合并 的一部分包含在内。但是，根据配置选项和您使用的特定 SQLite 版本，它可能默认启用或禁用。要确保 R*Tree 模块已启用，只需使用定义了 SQLITE_ENABLE_RTREE C 预处理器宏进行编译即可。在许多编译器中，这可以通过向编译器命令行添加选项“-DSQLITE_ENABLE_RTREE=1”来实现。
SQLite R*Tree 模块实现为一个 虚拟表。每个 R*Tree 索引都是一个虚拟表，具有 3 到 11 个奇数个列。第一列始终是一个 64 位有符号整数主键。其他列是成对的，每个维度一对，包含该维度的最小值和最大值。因此，一维 R*Tree 有 3 列。二维 R*Tree 有 5 列。三维 R*Tree 有 7 列。四维 R*Tree 有 9 列。五维 R*Tree 有 11 列。SQLite R*Tree 实现不支持超过 5 维的 R*Tree。
SQLite R*Tree 的第一列类似于普通 SQLite 表的整数主键列。它只能存储 64 位有符号整数值。将 NULL 值插入此列会导致 SQLite 自动生成新的唯一主键值。如果尝试将任何其他非整数值插入此列，则 r-tree 模块会在将其写入数据库之前将其静默转换为整数。
最小值/最大值对列存储为 32 位浮点值（对于“rtree”虚拟表）或 32 位有符号整数（对于“rtree_i32”虚拟表）。与可以以各种数据类型和格式存储数据的常规 SQLite 表不同，R*Tree 严格强制执行这些存储类型。如果将任何其他类型的数值插入此类列，则 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 数据表。如果您愿意，可以查询它们，尽管这不太可能揭示任何特别有用的信息。您可以 更新、删除、插入 甚至 删除 影子表，但这样做会破坏您的 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 );
在“rtree”的 CREATE VIRTUAL TABLE 语句的参数中，列的名称取自每个参数的第一个标记。每个参数中的所有后续标记都会被静默忽略。这意味着，例如，如果您尝试给一个列指定 类型亲和性 或向列添加约束（如 UNIQUE 或 NOT NULL 或 DEFAULT），则会接受这些额外的标记，但它们不会改变 rtree 的行为。在 RTREE 虚拟表中，第一列始终具有 类型亲和性 INTEGER，所有其他数据列都具有 类型亲和性 REAL。在 RTREE_I32 虚拟表中，所有列的类型亲和性都为 INTEGER。
建议的做法是省略 rtree 规范中的任何额外标记。让“rtree”的每个参数都是对应列的名称的单个普通标签，并省略参数列表中的所有其他标记。
通常的 插入、更新 和 删除 命令适用于 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 行的小样本足以说明这些想法。
任何有效的查询都可以针对 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 模块必须处理的约束越多，边界框越小，结果返回的速度就越快。
默认情况下，坐标使用 32 位浮点值存储在 R*Tree 中。当坐标不能被 32 位浮点数精确表示时，下限坐标会被向下舍入，上限坐标会被向上舍入。因此，边界框可能略大于指定大小，但绝不会小于指定大小。这正是为进行更常见的“重叠”查询而需要的，在该查询中，应用程序希望找到 R*Tree 中与查询边界框重叠的所有条目。将条目边界框向外舍入可能会导致一些额外的条目出现在重叠查询中，如果条目边界框的边缘对应于查询边界框的边缘。但重叠查询永远不会错过有效的表条目。
但是，对于“包含在内”类型的查询，如果条目边界框的边缘对应于查询边界框的边缘，则将边界框向外舍入可能会导致一些条目从结果集中排除。为了防止这种情况发生，应用程序应该稍微扩展其“包含在内”的查询框（0.000012%），方法是向下舍入较低的坐标，向上舍入较高的坐标，在每个维度上。
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-Tree 扫描中的位置。因此，无法容忍对 R-Tree 的更新，因为这会扰乱扫描。
这只是 R-Tree 扩展的限制。SQLite 中的普通表能够同时读写。其他虚拟表也可能（或可能不）具有此功能。在某些情况下，R-Tree 似乎能够同时读写，如果它能够弄清楚如何在开始更新之前可靠地完成查询运行。但你不应该依赖于每种查询都能实现这一点。一般来说，最好避免在同一时间对同一个 R-Tree 运行查询和更新。
如果您确实需要根据对同一个 R-Tree 的复杂查询来更新 R-Tree，最好先运行复杂查询并将结果存储在临时表中，然后根据临时表中存储的值来更新 R-Tree。
对于 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*树索引仅保存对象的轴对齐矩形边界。R*树边界只是真实对象边界的近似值。因此，通常发生的情况是，使用 R*树索引将搜索范围缩小到候选对象列表，然后对每个候选对象执行更详细且更昂贵的计算，以确定候选对象是否真正满足搜索条件。
关键点：R*树索引通常不会提供确切的答案，而只是将潜在答案集从数百万个缩减到几十个。
假设 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*树索引在外部循环中运行，以查找在其边界框内包含 SQLite 主办公室的条目。对于找到的每一行，SQLite 在 demo_data 表中查找相应的条目。然后，它使用 demo_data 表中的 boundary 字段作为 contained_in() 函数的参数，如果该函数返回 true，那么我们就知道所搜索的坐标在该邮政编码边界内。
不使用 R*树索引，使用以下更简单的查询也可以得到相同的结果
SELECT objname FROM demo_data WHERE contained_in(demo_data.boundary, 35.37785, -80.77470);
这个后一种查询的问题是，它必须对 demo_data 表中的所有条目应用 contained_in() 函数。在倒数第二个查询中使用 R*树将对 contained_in() 函数的调用次数减少到整个表的子集。R*树索引本身并没有找到确切的答案，它只是限制了搜索空间。
从 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;
对于辅助列，只有列名很重要。类型亲和性 将被忽略。NOT NULL、UNIQUE、REFERENCES 或 CHECK 等约束也将被忽略。但是，SQLite 的未来版本可能会开始注意类型亲和性和约束，因此建议辅助列的用户将两者都留空，以避免未来的兼容性问题。
默认的虚拟表（“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 算法的一部分。
通过在 SELECT 查询的 WHERE 子句中使用标准 SQL 表达式，程序员可以查询与特定边界框相交或包含在特定边界框内的所有 R*树条目。使用 WHERE 子句中的 MATCH 运算符进行自定义 R*树查询，允许程序员查询与任何任意区域或形状（不仅仅是盒子）相交的 R*树条目集。例如，此功能在计算 R*树中从三维空间中定位的相机可见的对象子集时很有用。
自定义 R*树查询的区域由应用程序实现并通过调用以下两个 API 之一向 SQLite 注册的 R*树几何回调定义。
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*树虚拟表中的任何列时，将调用第三个参数（xQueryFunc 或 xGeom）定义的回调，以确定特定对象或子树是否与所需区域重叠。
例如，以下查询可能用于查找与以 45.3,22.9 为中心，半径为 5.0 的圆形重叠的所有 R*树条目。
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 语法都是相同的。但是，更新的查询样式回调为应用程序提供了对查询执行方式的更大控制。
传统 xGeom 回调将使用四个参数调用。第一个参数是指向 sqlite3_rtree_geometry 结构的指针，该结构提供有关 SQL 函数调用方式的信息。第二个参数是每个 r-tree 条目中的坐标数，对于任何给定的 R*树，它始终是相同的。对于一维 R*树，坐标数为 2；对于二维 R*树，坐标数为 4；对于三维 R*树，坐标数为 6，依此类推。第三个参数 aCoord[] 是一个包含 nCoord 个坐标的数组，定义要测试的边界框。最后一个参数是指针，回调结果应写入该指针。如果 aCoord[] 定义的边界框完全位于 xGeom 回调定义的区域之外，则结果为零；如果边界框位于 xGeom 区域内或与 xGeom 区域重叠，则结果为非零。xGeom 回调通常应该返回 SQLITE_OK。如果 xGeom 返回除 SQLITE_OK 以外的任何值，则 r-tree 查询将中止并出现错误。
xGeom 回调的第一个参数指向的 sqlite3_rtree_geometry 结构具有如下所示的结构。对于同一查询中相同的 MATCH 运算符，每个回调都使用完全相同的 sqlite3_rtree_geometry 结构。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 函数的参数值。在上面的“圆形”查询示例中，nParam 将设置为 3，aParam[] 数组将包含三个值 45.3、22.9 和 5.0。
sqlite3_rtree_geometry 结构的 pUser 和 xDelUser 成员最初设置为 NULL。回调实现可以将 pUser 变量设置为任何可能对同一查询内后续回调调用有用的任意值（例如，指向用于测试区域交点的复杂数据结构的指针）。如果将 xDelUser 变量设置为非 NULL 值，则在查询运行完毕后，SQLite 会自动使用 pUser 变量的值作为唯一参数调用它。换句话说，可以将 xDelUser 设置为 pUser 值的析构函数。
更新的 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*树被组织成树。树的每个节点都是一个边界框。树的根是一个包含树所有元素的边界框。在根部之下是许多子树（通常为 20 个或更多），每个子树都有自己的较小边界框，并且每个子树都包含 R*树条目的子集。子树可能有子子树，依此类推，直到最后到达树的叶子，这些叶子是实际的 R*树条目。
R*树查询通过将根节点作为按 rScore 排序的优先级队列中的唯一条目来初始化。查询通过从优先级队列中提取具有最低得分的条目来继续。如果该条目是叶子（意味着它是一个实际的 R*树条目，而不是子树），则该条目将作为查询结果的一行返回。如果提取的优先级队列条目是一个节点（子树），则该节点的下一个子节点将传递给 xQueryFunc 回调。如果节点还有更多子节点，则将它返回到优先级队列。否则，它将被丢弃。那些 xQueryFunc 回调将 eWithin 设置为 PARTLY_WITHIN 或 FULLY_WITHIN 的子元素将使用回调提供的得分添加到优先级队列中。返回 NOT_WITHIN 的子元素将被丢弃。查询一直运行，直到优先级队列为空。
R*树内的每个叶条目和节点（子树）都有一个整型“级别”。叶子有 0 级。叶子的第一个包含子树有 1 级。R*树的根具有最大的级别值。sqlite3_rtree_query_info 结构中的 mxLevel 条目是 R*树根的级别值。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 个无符号整数的数组，这些整数告诉每级优先队列中的当前元素数量。
自定义 R*Tree 查询函数的 MATCH 运算符必须是 WHERE 子句中顶级的 AND 连接项，否则它将无法被 R*Tree 查询优化器使用，并且查询将无法运行。例如，如果 MATCH 运算符通过 OR 运算符连接到 WHERE 子句的其他项，则查询将失败并出现错误。
在同一个 WHERE 子句中允许使用两个或多个 MATCH 运算符，只要它们通过 AND 运算符连接即可。但是，R*Tree 查询引擎只包含一个优先队列。分配给搜索中每个节点的优先级是任何 MATCH 运算符返回的最低优先级。
以下部分描述了 R*Tree 实现的一些低级细节，这些细节可能对故障排除或性能分析有用。
R*Tree 索引的内容实际上存储在三个名称源自 R*Tree 名称的普通 SQLite 表中。这三个表被称为 "影子表"。这是它们的模式
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 影子表将条目 rowid 映射到包含该条目的节点。
附加到 %_rowid 表的额外列包含 辅助列 的内容。这些额外的 %_rowid 列的名称可能与实际的辅助列名称不同。
标量 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-tree 结构中的每个单元格（%_node 表），
对于每个维度，(coord1 <= coord2)。
除非单元格在根节点上，否则单元格受父节点上的父单元格的边界限制。
对于叶子节点，%_rowid 表中有一个对应于单元格 rowid 值的条目，该条目指向正确的节点。
对于非叶子节点上的单元格，%_parent 表中有一个条目，将单元格的子节点映射到它所在的节点。
%_rowid 表中的条目数量与 r-tree 结构中的叶子单元格数量相同，并且有一个叶子单元格对应于 %_rowid 表中的每个条目。
%_parent 表中的条目数量与 r-tree 结构中的非叶子单元格数量相同，并且有一个非叶子单元格对应于 %_parent 表中的每个条目。
此页面上次修改于 2023-02-20 00:00:42 UTC