4.2　二分搜索

我们已经讨论了B树查找算法（参见2.3.4节），并提到我们使用二分搜索算法在节点内定位键。二分搜索只对排序后的数据有效，如果键没有排序，则无法进行二分搜索。这就是为什么一定要保持键有序。

二分搜索算法接收一个包含已排序元素的数组和一个搜索键，并返回一个数字。如果返回的数字是整数，则我们找到了要搜索的键，并且数字指定了它在输入数组中的位置。而返回值为负数则表示搜索到的键不存在于输入数组中，并给出了一个插入点。

插入点是第一个大于给定键的元素的下标。这个数字的绝对值是该搜索键可以被插入以保持数组有序的下标。插入可以通过从插入点开始将之后的每个元素移动一个位置（为插入的元素腾出空间）来完成[SEDGEWICK11]。

在较高的层次上，大多数搜索并不会产生精确的匹配，此时我们感兴趣的是搜索的方向，在这种情况下，我们必须找到第一个大于搜索元素的值，然后跟随相应的子链接进入相关联的子树。

带间接指针的二分搜索

B树页中的单元格按插入顺序存储，只有单元格偏移量保留了逻辑元素的顺序。为了通过页单元格进行二分搜索，我们选取中间的单元格偏移量，跟随它的指针来定位单元格，将来自这个单元格的键与搜索键进行比较，以决定搜索应该向左还是向右继续，此后递归地进行这个过程，直到找到要搜索的元素或插入点，如图4-7所示。