搜索 B 树索引：O(log n) 中 log 的底是什么？

Question

搜索数据库 B-Tree 索引可以在 O(log n) 时间内执行。

对于B-Tree索引，日志的基是什么？

我知道在 Big-O 表示法中，基数并不重要。不管怎样，我很好奇 B 树索引的基础是什么。

例如，对排序列表进行二分查找以 2 为底，时间复杂度为 O(log n)。这是因为我们可以在每次比较时丢弃一半的列表。

同样，出于同样的原因，平衡二叉树上的二分搜索以 2 为底。

Answer 1

日志函数的基础实际上并不重要。

通过更改基数，您只需更改一个常数乘法因子即可应用于运行代码的处理器的速度。

也就是说，数据库中的 B 树索引具有分支因子（每个节点的子节点数量），该因子与存储索引值所需的字节数量成反比，具体取决于^{（I/O 页大小）} / _{（条目字节）尺寸）}。

对于 postgres，对于小尺寸条目来说，分支因子的数量可能只有数千。对于 MySql，可能约为50。一般来说，数据库 btree 具有较高的分支因子，以最大限度地减少磁盘页面读取，其速度比处理页面所需的时间慢 1000 倍左右。

遍历的节点数量随 O(log _b n) 变化，其中b是分支因子，因此是日志的基数。