Mar*_*ari 5 c++ tree b-tree data-structures
在B +树的常见实现中，我们可以假定键具有固定的长度（例如25个字节）。然后，我们可以定义每个节点必须具有最小数量的键，并且必须具有最大数量。
如果我希望树接受可变长度的键，我应该修改什么？如果我说节点必须至少有2个密钥，但是我要插入的密钥太大而无法容纳该节点的块，该怎么办？
小智 2
简单的解决方案是将键存储为指针（包装在覆盖相对运算符等的类型中）而不是值，但这当然会损害作为使用 B+ 树的一部分的局部性。
也就是说，项目越大，项目在内存中相邻的重要性就越小。巨大的项目甚至无法容纳一个缓存页面，更不用说同一页面中的多个项目了。
另一种相对简单的方法是使用联合类型或新的放置或其他任何方式在内存换项目类型中分配项目，该类型对于您可能使用的所有项目类型来说都足够大。每个项目仍然有固定数量的字节，但项目不一定使用所有这些字节。
如果您愿意做这项工作，您可以拥有可变大小的节点。当然，使用这些节点时您会遇到一些麻烦，具体取决于您如何安排节点内数据结构来应对这些问题。例如，节点内可能有一个小的项目指针数组，指向也在节点内部的项目（未在堆上单独分配）。
此外，每次更改节点时，您可能需要重新分配它。即使您所做的只是重新平衡，这可能会将一个巨大的项目从一个节点移动到另一个节点，并且即使目标节点有空间（从为项目提供空闲插槽的意义上来说），它也可能没有足够的字节来存储该项目。价值。
从某种意义上说，每个节点都是一个迷你堆，您可以在其中为大小的项目分配或释放空间，但有时您必须返回到堆本身，以用更大或更小的项目替换该迷你堆一。
再次值得一提的是，如果项目那么大，节点内的局部性可能无论如何都是不相关的。
我之前已经在内存中实现了 B+ 风格的多路树，但我从未走到过这个极端。