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

一、空间索引

空间索引是对二维或者多维空间坐标的索引，其本质不外乎树和哈希表两种结构。比如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层中只有一个节点，那么该节点就是根节点，算法结束
否则，把该层节点按照生成时间升序排序，重复步骤三

数据结构：

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

五、总结

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

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