algorithm - 在 B-Tree 中使用二分查找

Question

在CLRS(Introduction to algorithms)一书中，第18章介绍了B-Tree，它具有以下性质(P488)

the x.n keys themselves, x.key₁, ..., x.key_x.n stored in nondecreasing order

但是在B-Tree中查找一个元素，将一个元素插入B-Tree的过程中，CLRS使用线性搜索而不是二进制搜索来搜索特定节点中的键。

为什么要这样做？使用二进制搜索会获得更好的性能吗？

Answer 1

如果您想允许顺序变化，那么您是对的:进行二分查找的时间复杂度仍为 O(log n)，而进行线性查找的结果为 O(t log n)。但是如果你考虑B树的顺序(最大度数)是固定的，那么你做二分查找还是线性查找对时间复杂度没有影响。由于顺序通常是由缓存行大小等因素决定的，因此可以进行合理的简化。

在实践中，线性搜索通常会给您带来更好的性能，因为它可以用更少的分支完成，并且更适合 SIMD 处理。实际的 B 树实现要么只使用线性搜索，要么使用初始二分搜索，然后使用线性搜索。花费在搜索上的挂钟时间主要是等待获取节点的时间，而不是搜索合适的子节点的时间。