BTree 中的二进制搜索以提高性能

Question

我正在阅读 Cormen 等。阿尔。再次，特别是关于 B 树的章节，我正在用 C 实现一个。但是，我有一个问题，即我是否可以通过使用二分搜索而不是线性搜索来提高搜索性能。书中给出的伪代码类似于：

ordered_pair* btree_search(btreenode* root, double val){
  i = 0;
  while(i < root->num_vals && val > x->vals[i]) i++;
  if(i < x->num_keys && val == x->vals[i]) return ordered_pair(x, i);
  else if (x->leaf) return NULL;
  else {
    disk_read(x->children[i]);
    return btree_search(x->children[i], val);
  }
}

（我已将其修改为看起来像 C 并使用索引 0 而不是 1）

我的问题：

这看起来像是线性搜索。但是，由于 BTree 节点中的每个键集合都是作为数组实现的，我不能改用二进制搜索吗？这会减少从 O(n) 到 O(lg(n)) 搜索每个节点的时间复杂度吗？或者从磁盘读取是否使此处的二进制搜索变得毫无意义。我问这个的原因是因为实施起来似乎相对微不足道，而且我很困惑为什么 Cormen 等。 al.，根本没有提到它。或者也许我只是遗漏了一些东西。

如果您花时间回答或试图回答这个问题，感谢您抽出时间！

Answer 1

是的，你绝对可以使用二进制搜索。

有没有优势要看你的块有多大，读起来要花多少钱，不过你说的不难，也不会慢。

我总是会使用二分查找来做到这一点。

也许作者只是不想让 B-Trees 上的课程复杂化，或者他们假设您一开始就已经花了很多时间阅读这些模块。

BTree 中的二进制搜索以提高性能

Binary search within BTree to improve performance

algorithm

data-structures