初探SQLite的R-Tree
目录
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里添加一条记录。例如：
|
1 |
INSERT INTO demo_index VALUES( |
|
1 |
1, -- Primary key |
|
1 |
-80.7749, -80.7747, -- Longitude range |
|
1 |
30.3776, 30.3778 -- Latitude range |
|
1 |
); |
|
1 |
INSERT INTO demo_index VALUES( |
|
1 |
2, |
|
1 |
-81.0, -79.6, |
|
1 |
35.0, 36.2 |
|
1 |
); |
只需要执行类似上面的语句，SQLite就会自动将索引构建好。具体的结构，你可以通过查看R-Tree的三个辅助表来了解。
通过R-Tree查询索引
利用R-Tree快速检索，无疑是我们使用R-Tree的最终目的。
对于SQLite的R-Tree来说，我们只需要给出需要查询的范围，就可以迅速找到需要的索引。至于SQLite如何去找，那就不是我们需要关心的事了。如果你确实感兴趣，可以看看SQLite3/ext/rtree/rtree.c 里的代码是如何实现的。
查询的SQL语句如下：
|
1 |
SELECT id FROM demo_index |
|
1 |
WHERE maxX>=-81.08 AND minX<=-80.58 |
|
1 |
AND maxY>=35.00 AND minY<=35.44; |
需要特别注意的是：
Sqlite的R-Tree中，四至范围的数据类型只能是32位浮点型。
R-Tree表中存储的数值是经过其计算后再存储的，存储前后的值会出现偏差。值越大，偏差越大。