Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in Python

Searching and Addition in B-Tree

Explore how B-tree implementations perform search and addition operations efficiently in external memory. Understand the recursive approach to find and add values while maintaining balanced tree structure through node splitting. This lesson highlights the time complexity and design considerations that optimize disk access during these operations.

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.

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.

Python 3.10.4
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.

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.

Python 3.10.4
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) ...