c++ - 具有可变长度键的 B+ 树

Question

在 B+ 树的常见实现中，我们可以假设密钥具有固定长度（例如 25 个字节）。然后我们可以定义每个节点必须有一个最小数量的键和一个最大值。

如果我希望树接受可变长度的键，我应该修改什么？如果我说节点必须至少有 2 个键，但我试图插入的键太大以至于它不适合保存节点的块怎么办？

Answer 1

简单的解决方案是将键存储为指针（包装在覆盖相对运算符等的类型中）而不是值，但这当然会损害作为使用 B+ 树的一部分的局部性。

也就是说，项目越大，项目在内存中的相邻性就越不重要。一个巨大的项目甚至一个缓存页面都装不下，更不用说同一页面中的多个项目了。

另一种相对简单的方法是使用联合类型或放置 new 或其他任何方式在内存换项目类型中分配项目，该类型对于您可能使用的所有项目类型都足够大。每个项目仍然有固定数量的字节，但项目不一定使用所有这些字节。

如果您愿意做这项工作，您可以拥有可变大小的节点。当然，您在使用这些节点时会遇到一些麻烦，这取决于您如何安排节点内数据结构来处理这些问题。您可能在节点内有一个小项目指针数组，例如，指向也在节点内的项目（未在堆上单独分配）。

此外，每次更改节点时，都可能需要重新分配它。即使您所做的只是重新平衡，这可能会将一个巨大的项目从一个节点移动到另一个节点，并且即使目标节点有空间，即为项目提供一个空闲插槽，它也可能没有足够的字节来存储价值。

从某种意义上说，每个节点都是一个迷你堆，您可以在其中为大小项目分配或释放空间，但有时您必须返回适当的堆以将那个迷你堆替换为更大或更小的一。

再次值得一提的是，如果项目如此庞大，那么节点内的位置可能无论如何都无关紧要。

我之前在内存中实现了 B+ 风格的多路树，但我从来没有走到这个极端。

Answer 2

您可以将其余的大键保留在溢出页面中，就像那里一样。

Answer 3

使用散列。散列是键的固定大小表示。有关良好的散列函数，请参见http://www.cse.yorku.ca/~oz/hash.html。