0%

静态的希尔伯特RTree

先考虑一个常见的问题:如何搜索附近的人(车、银行、餐厅等)?
可以把这类问题抽象成:快速搜索二维(或者高维)空间上某一指定区域内的数据。
很明显,简单的二叉树或者哈希表解决不了这个问题。

一、空间索引

空间索引是对二维或者多维空间坐标的索引,其本质不外乎树和哈希表两种结构。比如GeoHash就是将空间划分成若干子空间,然后再映射成唯一的编码,以哈希表的形式存储。再比如KDTree和RTree,其本质都是树,不同的是KDTree是通过分割空间的方式构建树,而RTree是通过选取空间的方式构建树。

二、RTree

RTree是高度平衡的多叉树。他用最小外接矩形(minimum bounding rectangle, MBR)表示一个节点,N个子节点的最小外接矩形构成了他们的父节点,如果某一层只有一个节点,那么该节点就是根(root)节点。如下图:

如上图,R8、R9、R10是叶子节点,它们的最小外接矩形构成了它们的父节点R3。R3、R4、R5的最小外接矩形又构成了它们的父节点R1。
构建RTree的关键就是如何构建这些最小外接矩形,一般这些矩形的面积、周长越小越好。也就是说同一节点下的各子节点距离越近越好。

三、希尔伯特曲线

希尔伯特曲线是一种填充曲线,可以线性地贯穿二维或者更高维度每个离散单元,并且仅仅穿过一次,并对每个离散单元进行线性排序和编码,该编码作为该单元的唯一标识。希尔伯特曲线可以将高维空间中的数据映射到一维空间。如下图所示:

从上图可以看出,希尔伯特编码相近的点在平面上的位置也相近。当然,这一性质在数学上是有证明的,这里不做讨论。

四、希尔伯特RTree

利用希尔伯特曲线的性质,可以将RTree的各子节点进行编码、排序,如此往复就可以构建一棵希尔伯特RTree。

算法描述:

步骤一:计算每一个数据矩形中心的希尔伯特值
步骤二:按照希尔伯特值升序将数据矩形排序
步骤三:// 构造结点(层L=1)
while(有更多的矩形)
生成一个新的R树结点
将后续C个矩形分配到这个结点上
步骤四:// 构造更高层(L+1)的结点
L = L + 1
如果L层中只有一个节点,那么该节点就是根节点,算法结束
否则,把该层节点按照生成时间升序排序,重复步骤三

数据结构:

1
2
3
4
5
struct HilbertRTree {
std::vector<Node> nodes_; // 所有的非叶子节点,root节点在末尾
std::vector<Rectangle> leaves_; // 叶子节点的最小外接矩形,和leaf_ids_ 一一对应
std::vector<int> leaf_ids_; // 和leaves_ 一一对应
};

五、总结

这个希尔伯特RTree有如下特点:

  1. 只支持批量加载,不支持插入和删除。
  2. 各节点的空间利用率接近100%,节省内存。
  3. 内存是连续的,可以直接将内存镜像写入文件,序列化和反序列化的速度很快。
  4. 同一节点下的各子节点相邻,查询效率较高。