Small. Fast. Reliable.
Choose any three.
SQLite R * Tree模块

1.概述

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

R-Tree概念起源于 Toni GuttmanR-Trees:用于空间搜索的动态索引结构,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 * Tree。

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索引:

使用rtree(<column-names>)创建虚拟表<name>

所述<名称>对于R *树索引和应用程序选择的名称<列名>是逗号分隔的3和11之间的列的列表。虚拟<name>表创建三个阴影表以实际存储其内容。这些影子表的名称为:

<名称> _node 
<名称> _rowid
<名称> _parent

影子表是普通的SQLite数据表。您可以根据需要直接查询它们,尽管这不可能揭示任何特别有用的东西。而且您可以UPDATEDELETEINSERT甚至是DROP 影子表,尽管这样做会破坏您的R * Tree索引。因此,最好只是忽略影子表。认识到他们持有您的R * Tree索引信息,然后就这样继续进行下去。

例如,考虑创建一个二维R * Tree索引以用于空间查询:

使用rtree创建虚拟表demo_index
   id,-整数主键
   minX,maxX,-最小和最大X坐标
   minY,maxY-最小和最大Y坐标
);

3.1.1。列命名详细信息

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

建议的做法是在rtree规范中省略任何额外的标记。让“ rtree”的每个参数都是单个普通标签,它是对应列的名称,并从参数列表中省略所有其他标记。

3.2。填充R * Tree索引

常规INSERTUPDATEDELETE命令在R * Tree索引上工作,就像在常规表上一样。因此,要将一些数据插入示例R * Tree索引中,我们可以执行以下操作:

插入demo_index VALUES(
    1,-主键-SQLite.org总部
    -80.7749,-80.7747,-经度范围
    35.3776、35.3778-纬度范围
);
插入demo_index VALUES(
    2,北卡罗来纳州第12国会选区,2010年
    -81.0,-79.6,
    35.0、36.2
);

上面的条目可能表示(例如)SQLite.org主办公室周围的边界框和SQLite.org所在的北卡罗来纳州第12国会区(2011年重新分区之前)的边界框。

3.3。查询R * Tree索引

任何有效的查询都将对R * Tree索引起作用。但是R * Tree实现旨在使两种查询特别有效。首先,针对主键的查询非常有效:

SELECT * FROM demo_index WHERE id = 1;

当然,普通的SQLite表也可以有效地对其整数主键进行查询,因此前一个表没什么大不了的。使用R * Tree的真正原因是可以有效地对坐标范围进行不等式查询。要查找包含在北卡罗来纳州夏洛特附近的所有索引元素,可以这样做:

SELECT id from demo_index
 在哪里minX> =-81.08 AND maxX <=-80.58
   AND minY> = 35.00 AND maxY <= 35.44;

即使R * Tree包含数百万个条目,上面的查询也会非常快速地找到ID为1。上一个是“内部包含”查询的示例。R * Tree还支持“重叠”查询。例如,要查找与夏洛特(Charlotte)区域重叠的所有边界框:

SELECT id from demo_index
 在哪里maxX> =-81.08 AND minX <=-80.58
   AND maxY> = 35.00 AND minY <= 35.44;

第二个查询将找到完全包含在查询框中的条目1(SQLite.org办公室)以及第十二届国会区,该区在查询框之外延伸,但仍与查询框重叠。

注意,不必为了有效地进行索引搜索而约束R * Tree索引中的所有坐标。例如,可能要查询与第35个平行项重叠的所有对象:

SELECT id from demo_index
 其中maxY> = 35.0并且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
 其中maxY> = 35.0并且minY <= 35.0;

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

更新demo_index SET maxY = maxY + 0.5 WHERE id =?1;

然后,UPDATE可能会失败,并显示SQLITE_LOCKED错误。原因是初始查询尚未运行完毕。它正在记住它在扫描R-Tree的过程中的位置。因此无法容忍对R-Tree的更新,因为这会中断扫描。

也可以在单个查询中表达对R-Tree的这种同时读写,例如,如果UPDATE语句尝试根据来自另一行的复杂查询来更改R-Tree的一行的值,同一棵R-Tree的树,也许是这样的:

更新demo_index 
   SET maxY =(从demo_index AS x2选择SELECT max(maxX)
                WHERE x2.maxY> demo_index.x2)
 其中maxY> = 35.0并且minY <= 35.0;

这仅是R-Tree扩展的限制。SQLite中的普通表能够同时读取和写入。其他虚拟表可能(也可能不)也具有该功能。如果可以确定在开始更新之前如何可靠地运行查询以使其完成,R-Tree在某些情况下似乎可以同时进行读写操作。但是,您不应该在每个查询中都依靠它。一般来说,最好避免同时运行查询和对同一R-Tree的更新。

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

4.有效使用R * Tree

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

创建表demo_data(
  id INTEGER PRIMARY KEY,-主键
  objname TEXT,-对象的名称
  objtype TEXT,-对象类型
  boundary BLOB-对象的详细边界
);

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

关键点: R * Tree索引通常不提供确切答案,而只是将潜在答案的集合从数百万个减少到数十个。

假设demo_data.boundary字段保存了对象的复杂二维边界的一些专有数据描述,并且假定应用程序已使用sqlite3_create_function()接口创建了接受两个demo_data的应用程序定义函数“ contained_in”和“ overlaps”。边界对象并返回true或false。可以假设“ contained_in”和“ overlaps”是相对较慢的函数,我们不想太频繁地调用它们。然后一种有效的方法来查找位于北卡罗来纳州第十二区的所有对象的名称,一种方法是运行如下查询:

从demo_data,demo_index中选择objname
 在哪里demo_data.id = demo_index.id
   AND contains_in(demo_data.boundary,:boundary)
   AND minX> =-81.0 AND maxX <=-79.6
   AND minY> = 35.0 AND maxY <= 36.2;

在上面的查询中,可能会将第12区的精确边界的二进制BLOB描述绑定到“:boundary”参数。

注意上面的查询是如何工作的:R * Tree索引在外循环中运行,以查找包含在经度-81 ..- 79.6和纬度35.0..36.2的边界框中的条目。对于找到的每个对象标识符,SQLite在demo_data表中查找相应的条目。然后,它将demo_data表中的边界字段用作contains_in()函数的参数,如果该函数返回true,则demo_data表中的objname字段将作为查询结果的下一行返回。

使用以下更简单的查询,无需使用R * Tree索引就可以得到相同的答案:

从demo_data中选择objname
 在哪里contains_in(demo_data.boundary,:boundary);

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

4.1。辅助柱

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

辅助列在列名称前标有“ +”符号。辅助列必须位于所有坐标边界列之后。辅助列的数量不得超过100个。以下示例显示带有辅助列的r树表,该表与上面的两个表“ demo_index”和“ demo_data”等效:

使用rtree创建虚拟表demo_index2(
   id,-整数主键
   minX,maxX,-最小和最大X坐标
   minY,maxY,-最小和最大Y坐标
   + objname TEXT,-对象的名称
   + objtype TEXT,-对象类型
   + boundary BLOB-对象的详细边界
);

通过将位置数据和相关信息合并到同一表中,辅助列可以提供更简洁的模型并减少连接的需要。例如,现在可以将demo_index和demo_data之间的早期 连接编写为简单查询,如下所示:

从demo_index2选择objname
 在哪里contains_in(boundary,:boundary)
   AND minX> =-81.0 AND maxX <=-79.6
   AND minY> = 35.0 AND MAXY> = 36.2;

4.1.1。局限性

对于辅助列,仅列名很重要。该类型的亲和力被忽略。诸如NOT NULL,UNIQUE,REFERENCES或CHECK之类的约束也将被忽略。但是,SQLite的未来版本可能会开始注意类型的亲和性和约束,因此建议辅助列的用户将两者都留为空白,以避免将来出现兼容性问题。

5.整数值的R-树

默认虚拟表(“ rtree”)通常将坐标存储为单精度(4字节)浮点数。如果需要整数坐标,请改为使用“ rtree_i32”声明表:

使用rtree_i32(id,x0,x1,y0,y1,z0,z1)创建虚拟表intrtree

rtree_i32将坐标存储为32位带符号整数。但是它仍然在内部使用浮点计算作为r-tree算法的一部分。

6.自定义R树查询

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

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

int sqlite3_rtree_query_callback(
  sqlite3 * db,
  const char * zQueryFunc,
  int(* xQueryFunc)(sqlite3_rtree_query_info *),
  无效* pContext,
  无效(* xDestructor)(无效*)
);
int sqlite3_rtree_geometry_callback(
  sqlite3 * db,
  const char * zGeom,
  int(* xGeom)(sqlite3_rtree_geometry *,int nCoord,double * aCoord,int * pRes),
  无效* 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)定义的回调为调用以确定特定对象或子树是否与所需区域重叠。

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

SELECT id FROM demo_index WHERE id MATCH圈子(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,三维R * Tree的坐标数为6,依此类推。第三个参数aCoord []是nCoord坐标的数组,它定义了要测试的边界框。最后一个参数是应将回调结果写入其中的指针。如果aCoord []定义的边界框完全在xGeom回调定义的区域之外,则结果为零;如果边界框在xGeom区域内或与xGeom区域重叠,则结果为非零。xGeom回调通常应返回SQLITE_OK。如果xGeom返回除SQLITE_OK以外的任何内容,则r树查询将因错误而中止。

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 {
  无效* pContext; / *传递给s_r_g_c()的pContext的副本* /
  int nParam; / *数组aParam的大小* /
  双* aParam; / *传递给SQL geom函数的参数* /
  * pUser; / *回调实现用户数据* /
  void(* xDelUser)(无效*); / *由SQLite调用以清理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 {
  无效* pContext; / * pContext从函数注册时开始* /
  int nParam; / *功能参数数量* /
  sqlite3_rtree_dbl * aParam; / *功能参数的值* /
  * pUser; / *回调可以使用它,如果需要的话* /
  无效(* xDelUser)(无效*); / *函数释放pUser * /
  sqlite3_rtree_dbl * aCoord; / *要检查的节点或条目的坐标* /
  unsigned int * anQueue; / *队列中未决条目的数量* /
  int nCoord; / *坐标数* /
  int iLevel;/ *当前节点或条目的级别* /
  int mxLevel; / *树中最大的iLevel值* /
  sqlite3_int64 iRowid; / *当前条目的Rowid * /
  sqlite3_rtree_dbl rParentScore; / *父节点的分数* /
  int eParentWithin; / *父节点的可见性* /
  int eWithin; / *输出:可见性* /
  sqlite3_rtree_dbl rScore; / * OUT:在此处写分数* /
  / *以下字段仅在3.8.11及更高版本中可用* /
  sqlite3_value ** apSqlParam; / *参数的原始SQL值* /
};

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以便首先返回最大或最重要的条目,从而允许该应用程序快速显示最重要的信息,

如果需要,可通过xQueryFunc回调使用sqlite3_rtree_query_info结构的其他信息字段。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运算符返回的最低优先级。

7.实施细节

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

7.1。影子表

R * Tree索引的内容实际上存储在三个普通的SQLite表中,其名称是从R * Tree的名称派生的。这三个表称为“影子表”。这是他们的模式:

创建表%_node(nodeno整数主键,数据BLOB)
创建表%_parent(nodeno INTEGER PRIMARY KEY,parentnode INTEGER)
创建表%_rowid(rowid INTEGER PRIMARY KEY,nodeno INTEGER)

每个影子表的名称中的“%”被R * Tree虚拟表的名称替换。因此,如果R * Tree表的名称为“ xyz”,则三个阴影表将为“ xyz_node”,“ xyz_parent”和“ xyz_rowid”。

%_node表中的每个R * Tree节点都有一个条目。R * Tree节点由彼此相邻的一个或多个条目组成。一棵树的R * Tree的节点。除根节点外,所有其他节点在%_parent影子表中都有一个条目,用于标识父节点。R * Tree中的每个条目都有一个rowid。%_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()函数执行以下检查:

  1. 对于r树结构(%_node表)中的每个单元格,这是:

    1. 对于每个维度,(coord1 <= coord2)。

    2. 除非该单元格位于根节点上,否则该单元格将受父节点上的父单元格限制。

    3. 对于叶节点,%_ rowid表中存在一个条目,该条目与指向正确节点的单元格的rowid值相对应。

    4. 对于非叶节点上的单元,%_ parent表中存在一个从该单元的子节点到其所在节点的映射的条目。

  2. %_rowid表中的条目数与r树结构中的叶单元格相同,并且存在一个叶单元格对应于%_rowid表中的每个条目。

  3. %_parent表中的条目数与r树结构中的非叶子单元格相同,并且存在一个与%_parent表中的每个条目相对应的非叶子单元格。