首页 > Coding > 初探SQLite的R-Tree

初探SQLite的R-Tree

2012年9月11日 发表评论 阅读评论

R-Tree简介:

R-Tree是一种为空间查询而生的数据结构。只要给出一个空间对象的范围,使用R-Tree就可以快速而精确的查询出你所需要的空间对象(一个精确对象或是与之叠加的一组对象)。

让你的SQLite支持R-Tree

如果你使用的SQLite是从SQLite官网上直接下载的DLL文件,那么它应该已经包含了R-Tree功能模块。如果你使用的是自己定制的SQLite库,那么你在编译的时候,就需要打开R-Tree开关了(R-Tree模块默认是禁用的)。在C模式下编译的时候,添加 SQLITE_ENABLE_RTREE 宏开关,就可以获取R-Tree模块支持了。

在SQLite中使用R-Tree

构建R-Tree结构

SQLite中的R-Tree以虚表(Virtual Table)实现,最多支持5维空间索引。在N维R-Tree中,需要给出一个64位有符号整型作为索引(同时也是主键),然后给出N维的32位浮点数的空间范围值对。例如,一维的R-Tree,需要给出三个字段:索引、最小值、最大值,二维的R-Tree,需要给出五个字段:索引、X最小值、X最大值、Y最小值、Y最值…以此类推,五维的R-Tree,有11个字段。

在SQLite中创建一个R-Tree很简单,只需要一条Sql语句就可以搞定:

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

例如: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

);

 

执行完这条语句,你会发现,SQLite自动帮你创建了另三个表:

<name>_node
<name>_rowid
<name>_parent

这三个表是<name>的辅助表。你可以对它们进行任何操作。但是,你最好不要动它们(看看就好)。你需要做的,仅仅是使用和维护<name>表就够了。

向R-Tree添加索引

我们在向SQLite中插入一条新记录时,如果需要为该记录添加索引,就可以在R-Tree里添加一条记录。例如:

只需要执行类似上面的语句,SQLite就会自动将索引构建好。具体的结构,你可以通过查看R-Tree的三个辅助表来了解。

通过R-Tree查询索引

利用R-Tree快速检索,无疑是我们使用R-Tree的最终目的。

对于SQLite的R-Tree来说,我们只需要给出需要查询的范围,就可以迅速找到需要的索引。至于SQLite如何去找,那就不是我们需要关心的事了。如果你确实感兴趣,可以看看SQLite3/ext/rtree/rtree.c 里的代码是如何实现的。

查询的SQL语句如下:

 

需要特别注意的是:

Sqlite的R-Tree中,四至范围的数据类型只能是32位浮点型。

R-Tree表中存储的数值是经过其计算后再存储的,存储前后的值会出现偏差。值越大,偏差越大。

  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.