有效地查询包含多维数据的B + Tree

Question

我有一组(x,y)64位整数的元组组成我的数据集.比方说,我有数万亿这些元组; 将数据集保存在地球上的任何机器上是不可行的.但是,将它们存储在磁盘上是非常合理的.

我有一个磁盘存储(B + -tree),允许在一个维度上快速,并发地查询数据.但是,我的一些查询依赖于这两个维度.

查询示例:

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

我发现的最好的赌注是Z阶曲线,但我似乎无法弄清楚如何根据我的二维数据集进行查询.

不可接受的解决方案包括对数据的顺序扫描,这可能太慢了.

Answer 1

您是说您不知道如何查询 z 顺序曲线吗？维基百科页面描述了如何进行范围搜索。

z 曲线将您的空间划分为嵌套的矩形，其中键中的每个附加位将空间分成两半。要搜索一个点：

Start with the largest rectangle that might contain your point.

    Recursively:

        Create a result set of rectangles    

    For each rectangle in your set        
        If the rectangle is a single point, you are done, it is what you are looking for.
        Otherwise, divide the rectangle in two (specify one additional bit of the z-curve)
            If both halves contain a point
                If one half is better 
                    Add that rectangle to your result set of rectangles
                Otherwise
                    Add both rectangles to your result set of rectangles
            Otherwise, only one half contains a point
                    Add that rectangle to your result set of rectangles

    Search your result set of rectangles

当然，最坏情况下的性能很差。您可以通过更改构建 z 顺序索引的方式来调整它。