algorithm - BTree-预定大小？

Question

我在维基百科上读到的:

In B-trees, internal (non-leaf) nodes can have a variable number of child nodes within some pre-defined range. When data is inserted or removed from a node, its number of child nodes changes. In order to maintain the pre-defined range, internal nodes may be joined or split. Because a range of child nodes is permitted, B-trees do not need re-balancing as frequently as other self-balancing search trees, but may waste some space, since nodes are not entirely full.

我们必须为 B 树指定这个范围。即使当我查找 CLRS(算法简介)时，它似乎也使用数组作为键和子项。我的问题是——有没有办法通过将键和子项定义为列表而不是预先确定的数组来减少这种空间浪费？这是不是太麻烦了？

此外，对于我来说，我无法在 btreeDeleteNode 上获得像样的伪代码。在此也感谢您的任何帮助。

Answer 1

当你说“列表”时，你指的是链表吗？

某种元素的数组在每个插槽中占用一个元素的内存，无论该插槽是否已填满。链表只为它实际包含的元素占用内存，但对于每个元素，它占用一个元素的内存，加上一个指针的大小(如果它是双向链表，则为两个，除非你可以使用 xor 技巧来重叠它们)。

如果您正在存储指针，并使用单向链表，那么每个链表链接的大小是每个数组槽的两倍。这意味着除非列表少于一半，否则链表将使用更多内存，而不是更少。

如果您使用的语言的运行时具有针对每个对象的开销(如 Java 和 C，除非您自己处理内存分配)，那么您还必须为每个列表链接支付该开销，但仅一旦在阵列上，比例就更差了。

我建议您的平衡算法应使树节点至少保持半满。如果在节点已满时将其拆分，则会创建两个半满节点。然后，当相邻节点未满一半时，您需要合并它们。然后您可以使用数组，因为它比链表更有效。

不知道删除的细节，抱歉!