为何10阶B树搜索百万个键最坏需114次比较，与自行计算结果不符

假设我们需要搜索包含n个键值的未建索引、未排序数据库，该操作的最坏情况运行时间为O(n)。反之，如果数据库使用B树建立索引，相同搜索操作的运行时间为O(log n)。例如，在100万个键的集合中搜索单个键，最坏情况最多需要1000000次比较；但如果相同数据使用阶数为10的B树建索引，最坏情况仅需要114次比较。
上述内容出自《Data Structures Using C, 2nd Ed.》（Reema Thareja著，牛津大学出版社，第350页）。

你的推导逻辑的正确性 #

首先明确通用的m阶B树定义：

• 每个节点最多有m个子节点，对应最多存储m-1个排序键
• 除根节点外，每个节点最少有⌈m/2⌉个子节点，对应最少存储⌈m/2⌉-1个键

10阶B树对应最少子节点数为5，最少键数为4，和你的推导前提完全一致。最坏搜索场景对应树高最大的情况（所有节点都存储最少数量的键），此时树高为⌈log₅(1000000+1)⌉≈9层，每层线性搜索节点内的键最坏需要4次比较，总比较次数约为9*4=36次，你的计算结果符合标准B树的性质，是完全正确的。

教材数值错误的可能原因 #

目前没有符合10阶B树定义的场景可以得到114次的比较结果，出现该差异的可能原因包括：

• 阶数定义不标准：部分旧教材将B树的阶数定义为节点最多可容纳的键数，而非最大子节点数，即使按该定义计算，10阶B树最坏总比较次数最多为80次，仍达不到114。
• 编写笔误：更大可能性是教材编写时的计算错误，或是混淆了B树和其他数据结构的比较次数数值，比如错误代入了其他阶数的B树、二叉搜索树或是B+树的计算结果。
• 最坏情况定义偏差：如果教材的最坏情况同时要求每个节点存储最大数量的键，此时树高约为6层，每层最坏比较9次，总次数仅为54次，仍远低于114。

结论 #

教材给出的114次比较属于错误数值，你的推导符合B树的标准性质，无需被错误内容误导。

内容的提问来源于stack exchange，提问作者Recurrence Relation