小. 快速. 可靠.
选择任意三个.
SQLite R * Tree模块

1. Overview

R-Tree是专门用于进行范围查询的特殊索引. 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. Compiling The R*Tree Module

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

3. Using the R*Tree Module

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. Creating An R*Tree Index

如下创建一个新的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数据表. 您可以根据需要直接查询它们,尽管这不可能揭示任何特别有用的东西. 而且您可以UPDATEDELETEINSERT甚至是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. Column naming details

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

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

3.2. Populating An R*Tree Index

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

INSERT INTO demo_index VALUES(
    1,                   -- Primary key -- SQLite.org headquarters
    -80.7749, -80.7747,  -- Longitude range
    35.3776, 35.3778     -- Latitude range
);
INSERT INTO demo_index VALUES(
    2,                   -- NC 12th Congressional District in 2010
    -81.0, -79.6,
    35.0, 36.2
);

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

3.3. Querying An R*Tree Index

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

SELECT * FROM demo_index WHERE id=1;

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

SELECT id FROM demo_index
 WHERE minX>=-81.08 AND maxX<=-80.58
   AND minY>=35.00  AND maxY<=35.44;

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

SELECT id FROM demo_index
 WHERE maxX>=-81.08 AND minX<=-80.58
   AND maxY>=35.00  AND minY<=35.44;

This second query would find both entry 1 (the SQLite.org office) which is entirely contained within the query box and also the 12th Congressional District which extends well outside the query box but still overlaps the query box.

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

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

But, generally speaking, the more constraints that the R*Tree module has to work with, and the smaller the bounding box, the faster the results will come back.

3.4. Roundoff Error

By default, coordinates are stored in an R*Tree using 32-bit floating point values. When a coordinate cannot be exactly represented by a 32-bit floating point number, the lower-bound coordinates are rounded down and the upper-bound coordinates are rounded up. Thus, bounding boxes might be slightly larger than specified, but will never be any smaller. This is exactly what is desired for doing the more common "overlapping" queries where the application wants to find every entry in the R*Tree that overlaps a query bounding box. Rounding the entry bounding boxes outward might cause a few extra entries to appears in an overlapping query if the edge of the entry bounding box corresponds to an edge of the query bounding box. But the overlapping query will never miss a valid table entry.

但是,对于"包含在内部"样式的查询,如果条目边界框的边缘与查询边界框的边缘相对应,则将边界框向外舍入可能会导致某些条目从结果集中排除. 为了防止这种情况,应用程序应通过将每个维度的下坐标向下舍入并向上舍入顶部坐标来稍微扩展其包含在查询框中的内容(增加0.000012%).

3.5. Reading And Writing At The Same Time

Guttman R-Tree算法的本质是,任何写操作都可以从根本上重组树,并在此过程中更改节点的扫描顺序. 因此,通常无法在查询R-Tree的过程中修改R-Tree. 尝试将失败,并显示SQLITE_LOCKED "数据库表已锁定"错误.

因此,例如,假设一个应用程序针对R-Tree运行一个查询,如下所示:

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

Then for each "id" value returned, suppose the application creates an UPDATE statement like the following and binds the "id" value returned against the "?1" parameter:

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

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

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

UPDATE demo_index 
   SET maxY = (SELECT max(maxX) FROM demo_index AS x2
                WHERE x2.maxY>demo_index.x2)
 WHERE maxY>=35.0  AND minY<=35.0;

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

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

4. Using R*Trees Effectively

对于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()接口创建了接受两个demo_data的应用程序定义函数" contained_in"和" overlaps".边界对象并返回true或false. 可以假设" contained_in"和" overlaps"是相对较慢的函数,我们不想太频繁地调用它们. 然后一种有效的方法来查找位于北卡罗来纳州第十二区的所有对象的名称,一种方法是运行如下查询:

SELECT objname FROM demo_data, demo_index
 WHERE demo_data.id=demo_index.id
   AND contained_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..33.2的边界框中的条目. 对于找到的每个对象标识符,SQLite在demo_data表中查找相应的条目. 然后,它将demo_data表中的边界字段用作contains_in()函数的参数,如果该函数返回true,则demo_data表中的objname字段将作为查询结果的下一行返回.

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

SELECT objname FROM demo_data
 WHERE contained_in(demo_data.boundary, :boundary);

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

4.1. Auxiliary Columns

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

Auxiliary columns are marked with a "+" symbol before the column name. Auxiliary columns must come after all of the coordinate boundary columns. There is a limit of no more than 100 auxiliary columns. The following example shows an r-tree table with auxiliary columns that is equivalent to the two tables "demo_index" and "demo_data" above:

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
);

By combining location data and related information into the same table, auxiliary columns can provide a cleaner model and reduce the need to joins. 通过将位置数据和相关信息合并到同一表中,辅助列可以提供更简洁的模型并减少连接的需要. For example, the earlier join between demo_index and demo_data can now be written as a simple query, like this: 例如,现在可以将demo_index和demo_data之间的早期连接编写为简单查询,如下所示:

SELECT objname FROM demo_index2
 WHERE contained_in(boundary, :boundary)
   AND minX>=-81.0 AND maxX<=-79.6
   AND minY>=35.0 AND maxY>=36.2;

4.1.1. Limitations

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

5. Integer-Valued R-Trees

默认的虚拟表(" rtree")通常将坐标存储为单精度(4字节)浮点数. 如果需要整数坐标,则使用" rtree_i32"声明该表:

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

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

6. Custom R-Tree Queries

通过在SELECT查询的WHERE子句中使用标准SQL表达式,程序员可以查询与特定边界框相交或包含在特定边界框中的所有R * Tree条目. 使用SELECT的WHERE子句中的MATCH运算符的自定义R * Tree查询允许程序员查询与任意区域或形状(而不仅仅是框)相交的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)定义的回调为调用以确定特定对象或子树是否与所需区域重叠.

例如,可以使用如下查询来查找与以半径为5.0的以45.3,22.9为中心的圆重叠的所有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. The Legacy xGeom Callback

旧版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 {
  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. The New xQueryFunc Callback

较新的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以便首先返回最大或最重要的条目,从而允许该应用程序快速显示最重要的信息,并填充较小和不太重要的信息可用的详细信息.

如果需要,可通过xQueryFunc回调使用sqlite3_rtree_query_info结构的其他信息字段. iRowid字段是所考虑元素的rowid(R * Tree中3到11列中的第一列). iRowid仅对叶子有效. eParentWithin和rParentScore值是当前行包含的子树中eWithin和rScore值的副本. anQueue字段是一个由mxLevel + 1个无符号整数组成的数组,用于指示每个级别的优先级队列中的当前元素数.

6.3. Additional Considerations for Custom Queries

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

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

7. Implementation Details

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

7.1. Shadow Tables

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

CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data BLOB)
CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
CREATE TABLE %_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. Integrity Check using the rtreecheck() SQL function

标量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表中的每个条目.

by  ICOPY.SITE