Searching and Addition in B-Tree
Learn about searching and addition in the B-trees.
We'll cover the following...
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 (for the value ) and an unsuccessful search (for the value ) in a -tree is shown below. 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 u.key[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 than or equal to x
.
T find(T x) {T z = null;int ui = ri;while (ui >= 0) {BTreeNode u = bs.readBlock(ui);int i = findIt(u.keys, x);if (i < 0) return u.keys[-(i + 1)]; // found itif (u.keys[i] != null)z = u.keys[i];ui = u.children[i];}return z;}
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 above, works for any array, a
, where is a sequence of keys in sorted order and 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
.
int findIt(T[] a, T x) {int lo = 0, hi = a.length;while (hi != lo) {int m = (hi + lo) / 2;int cmp = a[m] == null ? -1 : compare(x, a[m]);if (cmp < 0)hi = m; // look in first halfelse if (cmp > 0)lo = m + 1; // look in second halfelsereturn -m - 1; // found it}return lo;}
The findIt(a, x)
method uses a binary search that halves the search
space at each step, so it runs in time. In our setting,
, so findIt(a,x)
runs in time.
We can analyze the running time of a -tree find(x)
operation both in ...