搜索组织为 B 树的一百万个键如何需要 114 次比较？
How searching a million keys organized as B-tree will need 114 comparisons?
请解释如何进行 114 次比较。以下是我的书的屏幕截图（第 350 页，使用 C 的数据结构，第二版。Reema Thareja，牛津大学出版社）。我的推理是，在最坏的情况下，每个节点只有最少数量的子节点（即 5），所以我取一百万的对数基数 5，结果是 9。所以假设在树的每个级别我们搜索最小数量键（即 4），大约有 36 次比较，远不及 114 次。
Consider a situation in which we have to search an un-indexed and
unsorted database that contains n key values. The worst case running
time to perform this operation would be O(n). In contrast, if the data
in the database is indexed with a B tree, the same search operation
will run in O(log n). For example, searching for a single key on a set
of one million keys will at most require 1,000,000 comparisons. But if
the same data is indexed with a B tree of order 10, then only 114
comparisons will be required in the worst case.
Page 350, Data Structures Using C, 2nd Ed. Reema Thareja, Oxford Univ. Press
最坏情况的树在所有地方都有最少数量的键除了在你正在搜索的路径上。
如果每个内部节点的大小在[5,10)之间，那么在最坏的情况下，当大多数节点有5个键时，拥有一百万个项目的树将有大约10层深。
然而，到节点的最坏情况路径可能在每个节点中有 10 个键。该声明似乎假设您将在每个节点内进行线性搜索而不是二进制搜索（我建议改为进行二进制搜索），这样可以导致大约 10*10 = 100 次比较。
如果仔细考虑细节，真正的数字很可能是114。
（这不是对问题的回答，而是相关的讨论。）
听起来像是教科书问题，而不是现实生活中的问题。
计数比较可能是判断内存树的最佳方式，但不适用于基于磁盘的数据集。
即便如此，“平均”比较次数（对于内存中）或磁盘命中（对于基于磁盘的）可能是要计算的指标。
（当然，计算最大数作为理解结构的有用练习是很好的。）
也许 在内存中 搜索的最佳“树”是二叉树，但具有 3 向扇出。并在每个节点中使用 2 或 3 个元素保持树平衡。
对于基于磁盘的搜索——想想数据库——最佳的可能是 BTree，其块的大小基于从磁盘读取的效率。当涉及到获取一行所花费的总时间时，在可怜的一秒钟内计算比较。
请解释如何进行 114 次比较。以下是我的书的屏幕截图（第 350 页，使用 C 的数据结构，第二版。Reema Thareja，牛津大学出版社）。我的推理是，在最坏的情况下，每个节点只有最少数量的子节点（即 5），所以我取一百万的对数基数 5，结果是 9。所以假设在树的每个级别我们搜索最小数量键（即 4），大约有 36 次比较，远不及 114 次。
Consider a situation in which we have to search an un-indexed and unsorted database that contains n key values. The worst case running time to perform this operation would be O(n). In contrast, if the data in the database is indexed with a B tree, the same search operation will run in O(log n). For example, searching for a single key on a set of one million keys will at most require 1,000,000 comparisons. But if the same data is indexed with a B tree of order 10, then only 114 comparisons will be required in the worst case.
Page 350, Data Structures Using C, 2nd Ed. Reema Thareja, Oxford Univ. Press
最坏情况的树在所有地方都有最少数量的键除了在你正在搜索的路径上。
如果每个内部节点的大小在[5,10)之间，那么在最坏的情况下，当大多数节点有5个键时，拥有一百万个项目的树将有大约10层深。
然而，到节点的最坏情况路径可能在每个节点中有 10 个键。该声明似乎假设您将在每个节点内进行线性搜索而不是二进制搜索（我建议改为进行二进制搜索），这样可以导致大约 10*10 = 100 次比较。
如果仔细考虑细节，真正的数字很可能是114。
（这不是对问题的回答，而是相关的讨论。）
听起来像是教科书问题，而不是现实生活中的问题。
计数比较可能是判断内存树的最佳方式，但不适用于基于磁盘的数据集。
即便如此，“平均”比较次数（对于内存中）或磁盘命中（对于基于磁盘的）可能是要计算的指标。
（当然，计算最大数作为理解结构的有用练习是很好的。）
也许 在内存中 搜索的最佳“树”是二叉树，但具有 3 向扇出。并在每个节点中使用 2 或 3 个元素保持树平衡。
对于基于磁盘的搜索——想想数据库——最佳的可能是 BTree，其块的大小基于从磁盘读取的效率。当涉及到获取一行所花费的总时间时，在可怜的一秒钟内计算比较。