Searching and Addition in B-Tree

Searching

The implementation of the find(x) operation, which is illustrated below generalizes the find(x) operation in a binary search tree. The search for x starts at the root and uses the keys stored at a node, u, to determine in which of u’s children the search should continue.

A successful search is shown below (for the value $4$) and an unsuccessful search (for the value $16.5$) in a B-tree. Shaded nodes show where the value of $z$ is updated during the searches.

More specifically, at a node u, the search checks if x is stored in u.keys. If so, x has been found and the search is complete. Otherwise, the search finds the smallest integer, i, such that $\text{u.keys}[i] > x$ and continues the search in the subtree rooted at u.children[i]. If no key in u.keys is greater than x, then the search continues in u’s rightmost child. Just like binary search trees, the algorithm keeps track of the most recently seen key, z that is larger than x. In case $x$ is not found, z is returned as the smallest value that is greater or equal to x

Central to the find(x) method is the findIt(a,x) method that searches in a null-padded sorted array, a, for the value x.

This method, illustrated in above illustration, works for any array, a, where $a[0],...,a[k −1]$ is a sequence of keys in sorted order and $a[k],...,a[\text{a.length}−1]$ are all set to null. If x is in the array at position i, then findIt(a,x) returns −i − 1. Otherwise, it returns the smallest index, i, such that a[i] > x or a[i] = null.

The findIt(a,x) method uses a binary search that halves the search space at each step, so it runs in $O(\log(\text{a.length}))$ time. In our setting, a.length = 2B, so findIt(a,x) runs in $O$ ...