B树节点中的链表优于数组吗？

Question

我想为我的数据库实现 B 树索引。

我读了很多数据结构和算法书籍来学习如何做。所有实现都使用数组来保存数据和子索引。

现在我想知道：B树节点中的链表优于数组吗？我想过一些想法：

1. 分割节点时，复制操作将比数组更快。

2. 插入数据时，如果将数据插入到数组的中间或头部，速度会比插入到链表低。

Answer 1

链表并不是更好，事实上简单的数组也不是更好（除了它的简单性，这是它的一个很好的论据，并且如果排序的话搜索速度）。

您必须认识到，“阵列”实现更多的是“参考”实现，而不是真正的全功能实现。例如，商业实现中B-Tree节点内的数据/密钥对的实现使用多种策略来解决两个问题：存储效率和节点中密钥的高效搜索。

关于高效搜索，顶部具有内部平衡树结构的键/值数组可以使插入/删除/搜索在 O(log N) 内完成，对于大型 B 树节点来说这是有意义的。

就内存效率而言，键和值中数据的性质非常重要。例如，字典键可以通过共同的开始来缩短（例如“good”、“great”有共同的“g”），也可以使用与数据的性质相关的任何可能的方案来压缩数据。键的压缩更加复杂，因为您需要保留此字典顺序属性。请记住，在节点中填充的数据和密钥越多，磁盘访问速度就越快。

分割节点的时间仅部分相关，因为它将比在典型介质上读取或写入节点的时间少几个数量级。在 SSD 和极快的磁盘上（预计 10 到 20 年后磁盘将与 RAM 一样快），进行了许多研究来寻找 B 树的后继者，分层 B 树就是一个例子。