Data Structures with Generic Types in Python/

...

/

Searching and Addition in B-Tree

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 is shown below (for the value 44) and an unsuccessful search (for the value 16.516.5) in a BB-tree. Shaded nodes show where the value of zz is updated during the searches.

Press + to interact
Searching in B-tree
Searching in B-tree

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 or equal to x.

Press + to interact
class BTree(BaseSet):

    class Node(object):

        def __init__(self, btree):

            self.btree = btree

            self.keys = new_array(self.btree.b)

            self.children = new_int_array(self.btree.b+1, -1)

            self.id = self.btree.bs.place_block(self)

    

    def __init__(self, b):

        self._initialize(b)

    

    def find(self, x):

        z = None

        ui = self.ri

        while ui >= 0:

            u = self.bs.read_block(ui)

            i = find_it(u.keys, x)

            if i < 0:

                return u.keys[-(i+1)] # found it

            if u.keys[i] is not None:

                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.

Press + to interact
The execution of find_it(a,27)
The execution of find_it(a,27)

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

Press + to interact
class BTree(BaseSet):

    class Node(object):

        def __init__(self, btree):

            self.btree = btree

            self.keys = new_array(self.btree.b)

            self.children = new_int_array(self.btree.b+1, -1)

            self.id = self.btree.bs.place_block(self)

    

    def __init__(self, b):

        self._initialize(b)

    

    def find_it(a, x):

        lo, hi = 0, len(a)

        while hi != lo:

            m = (hi+lo)//2

            if a[m] is None or x < a[m]:

                hi = m # look in first half

            elif x > a[m]:

                lo = m+1 # look in second half

            else:

                return -m-1 # found it

        return lo

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