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

Question

在 B+ 树的常见实现中，我们可以假设键具有固定长度(例如 25 字节)。然后我们可以定义每个节点必须有最少数量的键和最多数量的键。

如果我想让树接受可变长度的键，我应该修改什么？如果我说节点必须至少有 2 个 key ，但我要插入的 key 太大以至于无法放入包含该节点的 block 中怎么办？

Answer 1

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

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

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

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

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

从某种意义上说，每个节点都是一个迷你堆，您可以在其中为大小项目分配或释放空间，但有时您必须回到堆本身以用更大或更小。

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

我之前在内存中实现过 B+ 风格的多路树，但我从未走到过这种极端。