分类

希尔伯特R树有两种：一种是提供给静态数据库，还有一种是提供给动态数据库。在这两种情况下，希尔伯特的填充曲线都是用来使结点上的多维数据对象获得一个更好的排序。要把一个排序称为“好排序”，从某种意义上来说，它需要将“相似或相近”的数据矩形聚集在一起并使该矩形的面积和最小边界矩形或最小外接矩形（MBRs）结果的周长达到最小。紧缩的希尔伯特R树（Packed Hilbert R-trees）在很少进行数据更新甚至从不需要进行数据更新的静态数据库中显得非常的适用。

动态的希尔伯特R树则适用于插入、删除、更新这些操作发生非常频繁的动态数据库。此外，动态希尔伯特R树采用灵活的延迟的分裂机制来提高空间利用率。每一个结点都有定义明确的一组兄弟结点集合。通过调整分裂的策略，希尔伯特R树可以使其空间利用率达到人们所期望的那样高。因此，在R树结点上提出一种排序，我们便可以达到上述目的。希尔伯特R树（如，最小边界矩形等）依照矩形中心的希尔伯特值来对矩形进行排序。（某一个点的希尔伯特值是从原点到该点的希尔伯特曲线长度）。考虑到这个排序，每一个结点都有一组定义明确的兄弟结点；因此，延迟分裂技术可以被使用。通过调整分裂策略，希尔伯特R树可以获得一个人们所期望的高利用率。相反，其他的R树变体没有在空间利用率上加以控制。

基本思想

尽管下面这个例子是在一个静态的环境下，但是他还是可以将一个好的R树设计原理直观的展现出来。这些原理对静态和动态数据库都有效。

Roussopoulos和Leifker两个人提出了一种构造一个紧缩的R树的方法，几乎可以使R树的空间利用率达到100%。这个想法就是在矩形的一个角的x坐标或者y坐标上来进行数据的排序。从四个角建立坐标系来使数据排序的结果基本一致。在下面的讨论中，我们从左下角开始按x轴来对数据进行排序，我们称这种排序成为“低x轴紧缩R树”（lowx packed R-tree）。排序好的矩形序列通过扫描之后，连续的矩形被分到同一个叶结点直到该结点被填满，然后我们就创建一个新的叶结点，对已排序的序列扫描继续执行。因此，最后生成的R树的叶结点都会被紧密地填满，不过每一层的最后一个节点有可能发生异常。这样空间利用率基本就可以达到100%。这棵树的更高层的生成方式与此相同。

图1-1突出了低x轴紧缩R树的问题。图1-1为我们需要建立R树的所有点的示意图。图1-2展示了以图1-1中展示所有点为基础按照低x轴紧缩方法将会产生的R树的叶结点。可以看出父结点仅仅覆盖了一个很小的区域，这一事实解释了为什么低x轴紧缩R树在点查询上有着如此优异的性能。然而，父亲结点有着非常长的周长解释了区域查询时性能降低的情况。这一结果与R树性能的解析方程的结果一致。我们可以直观的看出，紧缩算法应该把附近的点分配到同一叶结点。低x轴紧缩R树忽视了y轴，这也在某种程度上违反了这个经验法则。

下面一节描述了两种希尔伯特R树的变体。第一种适用于数据更新很少或者基本不更新的静态数据库。最后生成的R树的叶结点都会被紧密地填满，不过每一层的最后一个节点有可能发生异常。这样空间利用率基本就可以达到100%。这种方法被称为紧缩型希尔伯特R树（Packed Hilbert R-tree）。第二种被称为动态希尔伯特R树，它支持在动态的环境中进行插入删除等操作。

紧缩型希尔伯特R树

下面对希尔伯特曲线进行一个简短的介绍。最基本的希尔伯特曲线是在一个2×2的网格中，在图2中用H1来表示。为了衍生出i阶曲线，我们需要用i-1阶曲线来替代每一个在基本曲线上的顶点，不过在有些地方需要进行适当的旋转或对称。图2中同样的展示了二阶和三阶希尔伯特曲线。当希尔伯特曲线趋近于无穷大阶，就像其他空间填充曲线一样，所得到的曲线就是一种分形（fractal），其分形维数为2。希尔伯特曲线可以被推广到更高维。如何以一个给定的顺序画二维分形曲线在和中可以找到相关算法。更高维的算法在中给出。

图2：1阶、2阶、3阶希尔伯特曲线

空间填充曲线的路径给格点附加了一个线性的顺序；我们可以这样来建立这条路径，从一个端点开始沿着曲线直到曲线的另一个端点。每一个点的实际坐标值也就可以被计算出来。然而对于希尔伯特曲线这一数值比z型曲线要难计算得多。图2中还展示了一个4×4网格中的顺序（见曲线H2）。举个例子，点(0,0)在H2上有希尔伯特值0，而点(1,1)有希尔伯特值2。一个矩形的希尔伯特值通过矩形中心的希尔伯特值来表示。

希尔伯特曲线给数据矩形附加了一个线性顺序然后贯穿整个已排序的序列，并且将每一个包含C个矩形的集合分配到R树上的一个结点。最终的结果就会是在同一个结点上的数据矩形集合中的所有矩形和同一结点上其他矩形在线性顺序上都非常的相近，很有可能就是相邻的空间；因此，生成的R树结点的区域就会非常小。图2说明了为什么我们的以希尔伯特曲线为基础的结果会有一个非常好的性能的直观原因。我们所利用的数据是由很多点组合而成（和图一中所给的点相同）。如果我们按照希尔伯特值对这些点进行分组，所产生的的R树结点的最小边界矩阵就会趋向于小的类似于正方形的矩形。这就告诉我们结点就很有可能有小的面积和周长。面积值小意味着点查询性能优异，面积和周长都小则会在大型的查询中有着优异的表现。

希尔伯特紧缩算法

Hilbert-Packing

（将矩形封装成一棵R树）

步骤一：计算每一个数据矩形的希尔伯特值

步骤二：按照希尔伯特值升序将数据矩形排序

步骤三：/*构造叶结点（层l=0）*/