数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究数据结构中的希尔伯特树
希尔伯特R树，一种R树的变体，被定义为多维对象的索引，例如线、区域、3D对象或基于高维特征的参数对象。可以将其想象为B+树在多维对象上的扩展。
R树的性能取决于对节点上的数据矩形进行聚类的算法的质量。希尔伯特R树实现空间填充曲线，特别是希尔伯特曲线，以便对数据矩形施加线性排序。
希尔伯特R树有两种类型：一种用于静态数据库，另一种用于动态数据库。在这两种情况下，都实现希尔伯特空间填充曲线以实现节点中多维对象的更好排序。这种排序必须被视为“良好”，因为它应该将“相似”的数据矩形组合在一起，以减少生成的最小边界矩形 (MBR) 的面积和周长。打包的希尔伯特R树适用于更新非常少或根本没有更新的静态数据库。
基本思想
虽然下面的例子是针对静态环境的，但它讨论了良好R树设计的直观原则。这些原则对静态和动态数据库都适用。
Roussopoulos和Leifker提出了一种构建打包R树的技术，该技术实现了近100%的空间利用率。
该思想是根据矩形的一个角的x或y坐标对数据进行排序。对四个坐标中的任何一个进行排序都会得到相同的结果。在这个讨论中，点或矩形都根据矩形左下角的x坐标进行排序，记为“lowx打包R树”。扫描矩形的排序列表；将连续的矩形分配给相同的R树叶节点，直到该节点满为止；然后构建一个新的叶节点，并继续扫描排序列表。因此，生成的R树的节点将被完全打包，除了每个级别上的最后一个节点可能例外。这导致空间利用率≈100%。树的较高层次以类似的方式构建。
希尔伯特打包算法
(将矩形打包到R树中)
步骤1. 计算每个数据矩形的希尔伯特值。
步骤2. 按升序希尔伯特值对数据矩形进行排序。
步骤3. /* 创建叶节点 (级别l=0) */
- 当 (还有更多矩形)
- 生成一个新的R树节点
- 将接下来的C个矩形分配到此节点
步骤4. /* 创建更高级别的节点 (l + 1) */
- 当 (级别l上有>1个节点)
- 按升序创建时间对级别l≥0的节点进行排序
- 重复步骤3
这里的假设是数据是静态的，或者修改频率很低。这是一种简单的启发式方法，用于构建空间利用率约为100%的R树，同时具有良好的响应时间。
542 次浏览
