Understanding the Whole Computer with B-Trees as Database Indexes

As a skill in the workplace, “coding” is more prevalent today than ever before. One doesn’t have to bear the title of “Software Engineer” to work intimately with the logical power of computer code. Exceptional technology professionals, though, will not only understand how to implement software programs, but also how the hardware of the machine is engineered to support those programs.

Wyoming, North America, USA (Source: Daniel George)

Database indexes present a convenient opportunity to learn about the computer in a holistic sense. This article explains the implementation of B-trees as database indexes, in both software and hardware, to demonstrate the value of understanding the whole computer. It is targeted to those who may not have taken a formal course in algorithms and would like to peel back the curtain on database indexes.

What is a Database Index?

A database index is a data structure which functions just like an index in the back of a book. It would take a long time to search for every instance of the word “polymer” in a chemistry textbook. An index, meanwhile, can locate “polymer” in no time. Database indexes work in much the same way and support query optimization, so that queries tend to run faster.

How is a Database Index Implemented in Software?

B-trees are often the data structure of choice to implement database indexes. A B-tree is a generalization of a binary search tree (BST). A BST is a sorted data structure composed of “nodes” (which hold data) and left and right “pointers” (which direct to other nodes within the BST). A BST has exactly two “children” nodes per node, while a B-tree can have more than two child nodes per node. These qualities of BSTs allow for very fast search, insertion and retrieval operations, relative to other data structures, which makes the BST a good place to start when implementing a database index.

The starting point of a tree is called the “root” and paths through the tree terminate in “leaves”. In code, a node looks like this:

Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

Java:

public class Node {

    public int data;
    public Node left;
    public Node right;

    public Node(int data) {
        this.data = data;
    }
}

Binary Search Tree (BST) showing nodes connected by pointers. The root is at the top and leaves are at the bottom.

How Is A B-Tree Implemented in Hardware?

The reason why a B-tree is a more compelling choice for an index than a BST is that a B-tree tends to have a much shorter height (the distance from the root node to the farthest leaf node) than a BST. This means that when the B-tree is stored in the hardware on disk, more information about the B-tree can be stored in one disk sector than would be stored when using a BST.

A disk sector represents a unit of memory transaction between the disk and the CPU. The standard size of a sector is 512 bytes, and a typical read operation of a sector takes about 15 milliseconds (depending on the machine).

A rotating memory disk showing a highlighted 512-byte sector.

When a BST is stored on disk, it is unlikely that all of the nodes in the BST will be neatly stored in one sector as the tree’s height grows. Instead, a BST may require many disk reads to retrieve data from an arbitrary node. A BST with n nodes has height h such that:

This means that if we want to locate a single, arbitrary node of our BST, we would need to complete h operations in the worst case, working our way down the tree. Since a particularly large BST won’t likely be stored sequentially in memory within a sector, we may access the disk as many as h times. Let’s see how long this would take in the worst case on a BST with one million nodes. The number of disk accesses, in the worst case, can be expressed as:

Or, about 20 disk accesses. Then, we see that 20 disk accesses × 15 milliseconds/disk read operation = 0.3 seconds in total to access a node in the worst case. That’s pretty fast, but can we do better?

It turns out, we totally can! By contrast, because a B-tree is shorter than a BST in terms of h, it is possible to store more information about a B-tree in one single disk sector. Suppose that a B-tree has a branching factor of 4 (each node has 4 children instead of 2). Then, our performance is:

We can do the same calculation: 10 disk accesses × 15 milliseconds/disk read operation = 0.15 seconds in total to access a node in the worst case. We just improved the performance of our database index by a factor of 2. How cool is that?

This is the impressive performance of a B-tree for the database index use case: with fewer disk accesses needed, you can retrieve data much, much faster. That is a large part of what makes database indexes lightning-fast (and why it is so important for optimization).

Conclusion

Database indexes provide a great opportunity to appreciate the cleverness of a software implementation working within the physical limitations of a computer’s hardware. The more that one can understand the entire computer, the easier it will be to innovate and develop even more effective programs.