Oracle Berkeley DB 中国研发团队的博客

1 背景

R-Tree是一种和BTree类似的数据结构，支持高维数据的快速检索，被广泛应用于各种空间数据中。R-Tree的一个典型的应用是从许多空间对象的信息中找出用户关心的那个。如给定一座城市各个建筑物的经纬度坐标并存储于R-Tree中，用户可以通过“查找当前位置向西五公里内的所有餐厅”，“查找会展中心方圆一公里内的所有汽车站”等方式来查询自己感兴趣的某些特定建筑。

2 BDB11gR2的R-Tree功能

新发布的BerkeleyDB 11gR2(以下简称BDB11gR2）版本能够无缝地兼容SQLite的接口，从而支持各种基于SQLite的应用，包括SQLite自带R-Tree扩展应用。关于SQLite的R-Tree细节，可参见http://www.sqlite.org/rtree.html。
下面，本文将从编译和使用两方面，介绍如何在BDB11gR2中使用R-Tree功能。

2.1 编译

BDB11gR2通过编译开关控制是否启用R-Tree功能。默认情况下，BDB11gR2是不启用R-Tree的。要获得R-Tree的支持，则应该在编译时加上SQLITE_ENABLE_RTREE标志。

Linux平台

cd build_unix
../dist/configure CPPFLAGS=-DSQLITE_ENABLE_RTREE --enable-sql
make dbsql


Windows平台

在工程文件的属性中，选择 Properties -> Configuration Properties -> c/c++ -> Command Line -> Additional Options, 加入/D DSQLITE_ENABLE_RTREE，并重新编译工程。

2.2 使用R-Tree

一棵R-Tree实际上对应于一张虚拟表。建立R-Tree索引的过程，实际上就是建立虚拟表的过程。和普通表类似的，我们也可以对这张特殊的虚拟表进行插入，删除，更新等操作。

我们以下面这张图为例来说明R-Tree的典型操作和应用。

在图1中，有三个蓝色的矩形，代表三个建筑的边界，标记为1，2，3。它们的坐标信息如图所示。我们要建立一棵R-Tree，来存储这些矩形的坐标信息，并在此基础上进行一些简单的查询。

建立R-Tree索引

CREATE VIRTUAL TABLE demo_index USING rtree(
id,
minX, maxX,
minY, maxY
);

以上操作建立了一张R-Tree索引表。该索引表中每一条记录代表了一个矩形框。每条记录由5列组成，其中id是一个整数类型的主键，minX，maxX分别代表矩形框横坐标的最小值和最大值，minY，maxY分别代表矩形框纵坐标的最小值和最大值。注意，BDB11gR2中的R-Tree表的列数必须是3-11之间的基数，其中第一列是表的主键，2k和2k+1列分别代表第k维数据的下界和上界(k=1~5).

插入数据

向R-Tree的表中插入数据，和向普通表中插入数据的语法是完全一致的。
以下三条语句插入了图1中的三个矩形：

INSERT INTO demo_index VALUES(
1,
0, 2,
0, 1
);
INSERT INTO demo_index VALUES(
2,
3, 5,
3, 5
);
INSERT INTO demo_index VALUES(
3,
4, 5,
1, 4
);

基于R-Tree的查询

和普通表类似的，用户卡可以对R-Tree表进行查询。如

SELECT id FROM demo_index
WHERE id=1;

但R-Tree表上更为常用和典型的查询则是范围查询(Range-Query). 举例如下：

SELECT id FROM demo_index
WHERE minX>=0 AND maxX<=3
AND minY>=0 AND maxY<=2;

查询的结果为
1

上面这条查询的含义是找出图1中所有被包含在红色虚线矩形框中的矩形。

SELECT id FROM demo_index
WHERE maxX>=1 AND minX<=4
AND maxY>=0 AND minY<=4;
查询结果为
1
2

上面这条查询的含义是找出图1中所有和黑色虚线矩形框有交集的矩形。

总结

R-Tree在高维数据的检索中有着广泛的应用。各种地理信息，带时间记录的归档信息等，都可以通过建立基于R-Tree的索引，来达到快速检索的目的。欢迎通过使用Berkeley DB11gR2的RTree功能来构建自己的R-Tree索引，若有任何相关问题，请联系  Linchun dot sun at Oracle dot com。

CREATE VIRTUAL TABLE demo_index USING rtree(

   id,               

   minX, maxX,       

   minY, maxY        

);

以上操作建立了一张R-Tree索引表。该索引表一共由5列组成，每一条记录代表了一个矩形框。其中id是一个整数类型的主键，minX，maxX分别代表矩形框横坐标的最小值和最大值，minY，maxY分别代表矩形框纵坐标的最小值和最大值。注意，r-tree的列数n必须为2m+1，其中m为表示对象的维数。

插入数据

在R-Tree的表中插入数据，和往普通表中插入数据的语法是完全一致的。

以下三条语句插入了图1中的三个矩形：

INSERT INTO demo_index VALUES(

1,                   

0, 2,  

0, 1     

);

INSERT INTO demo_index VALUES(

    2,

    3, 5,

    3, 5

);

INSERT INTO demo_index VALUES(

    3,

    4, 5,

    1, 4

);

基于R-Tree的查询

和普通表类似的，用户卡可以对R-Tree表进行查询。如

SELECT id FROM demo_index

 WHERE id=1;

但R-Tree表上更为常用和典型的查询则是范围查询(Range-Query). 

SELECT id FROM demo_index     

 WHERE minX>=0 AND maxX<=3

   AND minY>=0 AND maxY<=2;

查询的结果为

1

这条查询的含义是找出图1中所有被包含在红色虚线矩形框中的矩形。

SELECT id FROM demo_index     

 WHERE maxX>=1 AND minX<=5

   AND maxY>=0 AND minY<=4;

查询结果为

1

2

3

这条查询的含义是找出图2中所有和黑色虚线矩形框有交集的矩形。