数据结构中的希尔伯特树
希尔伯特R树是R树的变体，被定义为多维对象的索引，例如线，区域，3-D对象或基于高维特征的参数对象。可以将其想象为对多维对象的B +树的扩展。
R树的性能取决于将数据矩形聚集在节点上的算法的质量。Hilbert R树实现了空间填充曲线，特别是Hilbert曲线，用于对数据矩形强加线性排序。
希尔伯特R树有两种类型：一种用于静态数据库，另一种用于动态数据库。在这两种情况下，均实现了希尔伯特空间填充曲线，以实现节点中多维对象的更好排序。在这种意义上，必须将“相似”的数据矩形分组在一起，以减小最终的最小边界矩形(MBR)的面积和周长，因此必须将此处理视为“良好”。压缩的希尔伯特R树适用于很少更新或根本没有更新的静态数据库。
基本思路
尽管以下示例是针对静态环境的，但它讨论了良好R树设计的直观原理。这些原则对于静态和动态数据库都是合法的。
Roussopoulos和Leifker提出了一种构建压缩R树的技术，该技术可实现几乎100％的空间利用率。
开发此想法是为了对矩形的一个角的x或y坐标上的数据进行排序。对四个坐标中的任何一个进行排序都会得到相同的结果。在本讨论中，点或矩形都在矩形左下角的x坐标上排序，称为“ lowx压缩R树”。扫描矩形的排序列表；连续的矩形被分配给相似的R树叶子节点，直到该节点已满为止；然后建立一个新的叶子节点，并继续扫描已排序列表。因此，除了每个级别的最后一个节点以外，最终的R-tree的节点都将被完全打包。这导致事件发生，从而使空间利用率≈100％。以类似的方式构建更高级别的树。
算法希尔伯特包
（将矩形包装到R树中）
步骤1.计算每个数据矩形的希尔伯特值。
步骤2.对升序Hilbert值的数据矩形进行排序。
步骤3. / *创建叶节点（级别l = 0）* /
虽然（有更多矩形）
生成一个新的R-tree节点
分配给该节点的下一个C矩形
步骤4. / *创建更高级别的节点（l + 1）* /
虽然（级别l有> 1节点）
在升序创建时对l≥0级别的节点进行排序
重复步骤3
这里的假设是数据是静态的或修改的频率很低。这是构建具有约100％空间利用率的R树的简单方法，同时具有良好的响应时间。
以上是 数据结构中的希尔伯特树 的全部内容， 来源链接： utcz.com/z/357398.html
