algorithm - 高效查询持有多维数据的 B+ 树

Question

我有一组构成我的数据集的 64 位整数元组 (x,y)。比如说，我有数万亿个这样的元组；将数据集保存在地球上任何机器的内存中都是不可行的。但是，将它们存储在磁盘上是很合理的。

我有一个磁盘存储(B+ 树)，允许在单个维度中快速、并发地查询数据。但是，我的一些查询依赖于这两个维度。

查询示例:

• 找到 x 大于或等于某个给定值的元组
• 找到 x 尽可能小的元组 s.t. y 大于或等于某个给定值
• 找到 x 尽可能小的元组 s.t. y 小于或等于某个给定值
• 执行维护操作(插入一些元组，删除一些元组)

我发现最好的选择是 Z 顺序曲线，但我似乎无法弄清楚如何根据我的二维数据集进行查询。

Not Acceptable 解决方案包括数据的顺序扫描，这可能太慢了。

Answer 1

我认为，最适合您要求的数据结构是 R-tree及其变体(R*-tree、R+-tree、Hilbert R-tree)。 R-tree类似于B+-tree，但也允许多维查询。

其他相关的数据结构是优先搜索树。它适用于您的示例 1 .. 3 之类的查询，但如果您需要频繁更新或磁盘存储，则效率不高。详情见this paper或者这本书:"Handbook of Data Structures and Applications" (第 18.5 章)。