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

Question

我有一个由64位整数元组(x,y)组成的数据集合。我可能有数万亿这样的元组，将数据集存储在地球上任何一台计算机内存中都是不可行的，但将它们存储在磁盘上就非常合理。

我有一个磁盘存储器（B + -tree），可以快速且并发地查询单维度数据，但我的一些查询依赖于两个维度。

例如查询:

找到x大于或等于某个给定值的元组

找到x尽可能小，使得该元组的y大于或等于某个给定值

找到x尽可能小，使得该元组的y小于或等于某个给定值

执行维护操作（插入某些元组，删除某些元组）

我发现最好的解决方案是使用Z-order曲线，但我似乎无法想出如何针对我的二维数据集进行查询。

不可接受的解决方案包括数据的顺序扫描，因为这可能会非常慢。

- user1670103

Answer 1

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

其他相关的数据结构是 Priority Search Tree。它适用于像您的示例 1 到 3 这样的查询，但如果需要频繁更新或磁盘存储，则效率不高。有关详细信息，请参阅 此论文 或本书："数据结构与应用手册"（第18.5章）。

- Evgeny Kluev

---

我无法承担一个强大的R树（任何变体）的实现，使其安全可靠，同时保证事务性已超出了该项目的初衷。 - user1290696

@user1290696：你可以将其投入支持R树（或变体）的关系型数据库管理系统中，如Postgres或SQL-Server。 - ypercubeᵀᴹ

我做不到，那是一个嵌入式设备。 - user1670103

Answer 2

我目前正在设计一种数据结构，它本质上是一个“堆叠”的B+树（或者一个d+树，其中d是维度数），用于多维数据。我相信它非常适合您的数据，并且是专门为您的使用情况而设计的。

基本思路如下：

每个维度都是一个B+树，并链接到下一个维度的B+树。通过第一个维度进行正常搜索，一旦到达叶子节点，它就包含指向下一个B+树的根的指针，该B+树属于下一个维度。第二个B+树中的所有内容都属于相同的x值。

最初的计划是仅存储每个维度的唯一值以及其计数。这采用了一种非常简单的压缩算法（如果您甚至可以称之为压缩算法），同时仍然允许整个数据集被表示。这种“链接”维度方案可以允许在以后添加额外的维度，因为它们只是添加到B+树的堆栈中。

对于2个维度的总插入/搜索/删除时间将类似于以下内容：

log b(card(x)) + log b(card(y))

b是每个B+树的基数，card(x)将是x维度的基数。

希望这说得清楚。我仍然在进行实现，但请随意使用甚至增强这个想法。

- max

Answer 3

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

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

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-order索引的方式来进行调整。

- antlersoft

---

我认为那些只是查询示例，而不是他们可能需要的全部查询范围。话虽如此，对于两个变量，我猜最多只有4个不同的索引（即x、y、x+y和x-y），所以没问题。 :) - João Mendes

这个不起作用，看例子2：我正在寻找至少为20的y和最小的x。将y和x连接起来，并为y+x创建大于或等于查询，看起来像是20+0。这可能会找到20+50，但会跳过21+10。 - user1290696

我的错——我没有理解你的查询需要，这确实是2D的。我会尝试另一个回答。 - antlersoft

Answer 4

http://fallabs.com/tokyocabinet/

Tokyo Cabinet是一个用于管理数据库的例程库。该数据库是一个包含记录的简单数据文件，每个记录都是键和值的一对。每个键和值都是具有可变长度的串行字节。二进制数据和字符字符串都可以用作键和值。没有数据表或数据类型的概念。记录以哈希表、B+树或固定长度数组的形式组织。

Tokyo Cabinet使用C语言编写，并提供C、Perl、Ruby、Java和Lua的API。Tokyo Cabinet可在符合C99和POSIX API的平台上使用。Tokyo Cabinet是一款自由软件，采用GNU Lesser General Public License许可证。

希望这样翻译对您嵌入方便。

- Ryan Wong