I'm reading through Cormen et. al. again, specifically the chapter on BTrees, and I am implementing one in C. However, I had a question about whether I could improve performance in searching by using binary search rather than linear search. The pseudocode given in the book looks something like:

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);
  }
}

(I have modified it to look like C and used index 0 rather than 1)

My question(s):

This looks like a linear search. However, since each collection of keys in a BTree node is implemented as an array, couldn't I use binary search instead? Would that lessen the time complexity of searching each node from O(n) to O(lg(n))? Or does reading from the disk make a binary search here rather pointless. The reason I'm asking this is because it seems relatively trivial to implement, and I am confused why Cormen et. al., doesn't mention it at all. Or perhaps I am just missing something.

If you take the time to answer or attempt to answer this question, thank you for your time!

CodePudding user response：

Yes, you can definitely use a binary search.

Whether or not there's an advantage in it depends on how big your blocks are and how much it cost to read them, but as you say, it's not difficult, and it's not going to be slower.

I would always do this with a binary search.

Perhaps the authors just didn't want to complicate the lesson on B-Trees, or maybe they they are assuming that you've already spent a lot more time reading those blocks in the first place.