The Magic of B-trees

I'd like to talk a little about and give an implementation of B-Trees, perhaps the best example of an algorithmic data structure designed specifically 'real computers' rather than the theory of academia. Given that, it took me a while to figure out the why on earth B-Trees are used. It's sort of like the Binary tree's uncoordinated half-cousin who looks slow, but turns out to be speedy when tested.

As it turns out, there is a very real need for a structure that avoids the space constraints of a gigantic hash table while simultaneously providing efficient lookup. When creating database indices or file systems, a sort is often necessary, which tends to throw out the unordered nature of the hash table. Additionally, resizing in particular would be a huge problem in a file system as all files would have to be rehashed.

Okay, "That's fine," you might say, "but why not use a simple binary tree like AVL that does all comparisons and rebalancing in O(log(n))"? It's true, binary trees are both efficient in space, search, and reordering so if you have 1,000,000 elements it will take roughly 19 comparisons to find a given element in average time. The problem however, comes that in practice 19 comparisons becomes too many when the disk must seek to search for the next element.

That's sort of the crux of the b-tree, when we get out of the fairyland of theory and into the harsh realities of life, disk seeking becomes the operation that dominates runtime. B-trees essentially create trees of smaller height where each node contains an index of subtrees and can be viewed as an atomically loaded element. These nodes are then traversed in memory to decide which node to load next, saving disk seeking costs.

Whew, now that we're done with some intro, let's get to coding. I've outlined my b-tree class below. The class allows for any comparable type really but I'm going to use integers as they are our friends.

class BTree:

    def __init__(self, array = [], children = []):
        self.array = array
        self.children = children

Initially our tree starts with an array of numbers and an array of children, simple, right? The 'array' variable acts as the index for the children, directing the search algorithm to the next node. However, with all these arrays it can be tricky to keep our tree balanced and efficient. In practice there are many different rules and algorithms governing how nodes reallocate data, but I'm going to go with a very simple implementation, the 2-3 Tree. 2-3 Trees are perhaps the simplest type of B-Tree with each tree containing either 1 or 2 elements and 0,1 or 2 children.

First I'll outline the search function. We start at the root of the tree and look through its array for our search term. If we encounter an element greater than the one we are searching for, then we look at the child pointer that comes before that element and recurse on that subtree. This can be made more efficient with binary search, but since our arrays are limited to 2 elements we will simply do a linear search here.

def search(self, element):

    if len(self.array) == 0 return False

    # Go through the array looking for the element or the index.
    for i in range(len(array)):
        if array[i] == element:
            return True
        if array[i] > element:
            if(len(children) > i):
                return children[i].search(element)
            else:
                return False
    # Not found, so check the last child pointer
    if len(self.children) > len(self.array):
        return children[-1].search(element)
    else:
        return False

Alright, the final call is how to do an insertion, which gets complicated quickly with B-trees. I'm just going to demonstrate a moderately correct algorithm of the leaves, though there could definitely be errors in it as I just pseudocoded it in Python. In a few weeks I'll follow up with a more complete (tested) implementation and its comparison to binary trees.

def insert(self, element):
    # Case 1: Leaf is empty
    if len(self.array) == 0:
        self.array.append(element)

    # Case 2: Leaf has only a single data item
    elif len(self.array) == 1:
        if self.array[0] > element:
            self.array.insert(0, element)
        else:
            self.array.append(element)

    elif len(self.array) == 2:
        # Case 3: Leaf is full and parent has some data item
        parent = self.parent
        if element < self.array[0]:
            small, middle, large = element, self.array[0], self.array[1]
        elif element > self.array[1]:
            small, middle, large = self.array[0], self.array[1], element
        else:
            small, middle, large = self.array[0], element, self.array[1]

        # No parent, we are at root so one must be created
        if parent == None:
            self.array.remove(largest)
            p = Node(array=[middle], children=[self, Node(array=[largest])]

        if len(parent.array) >= 1:
            # Check whether this is the left child or right child
            if self == parent.children[0]:
                index = 1
            else:
                index = 2

            parent.insert(middle)
            self.array.remove(large)
            parent.children.insert(index, Node(array=largest))

The most important point to keep in mind is that B-Tree insertions are typically a bottom up process, like in an AVL tree. This keeps things balanced and working well. Thus, sorts, in-order traversals and search are pretty easy and space efficient with a B-Tree. The indexing of the nodes allows nodes to be loaded like pages one at a time. At any rate, the take home message of using B-Trees is this: When the cost of loading the node is greater than the comparison of two values, use a B-Tree. Hopefully I'll run a later post with a non-pseudocoded version that loads nodes as files to simulate the speedup gained from using a B-Tree.

Next week I'll try and explore some compression techniques, hopefully with some tested code and metrics this time. Until then, stay classy!