B-Trees as Database Indexes

Let’s now take a look at how B-trees may be used in the real world.

Many databases are organized as tables of columns and rows. An example database table is that stores data about houses for sale.

Only a small section of the table is shown, but you can see that it includes data regarding numerous house details, including the address, style, and asking_price.

Typically, databases use the id column to map each row to its location in memory. For example, if we ask the computer to find the row where the id is 7, the computer can do so in one step since it knows the exact memory address where that row is located. In any case, in this table, the rows are sorted by the order of the id.

Now, let’s imagine that our table contains 10 million rows. If we were to ask the database to find a house located in, say, San Diego, it would have to perform a linear search on up to all 10 million rows to pick out a San Diego home. The database cannot leverage the id in any way since the id has no correlation to the house’s city. A San Diego house might belong to any id!

To combat this problem, many databases allow us to create something known as a database index. Here’s an example of what a database index looks like conceptually:

This is a kind of mini-table that contains only the city and id columns of each house, and omits all the other attributes. And most importantly, this table keeps the rows in alphabetical order by city name.

(For simplicity’s sake, this data only has one home in each city. Realistically, a single city such as Atlanta will have many homes. As such, the table would put all the Atlantas next to each other, and our search will indeed return all those rows.)

Now, if this data structure were an ordered list, and we search for a San Diego home, we can now perform binary search on the list to find San Diego in speedy logarithmic time. And once the database finds the San Diego row in the database index, it sees that the id is 4, and can, in one more step, retrieve the entire row of data for id 4.

Very often, we have to create multiple database indexes. This database index only helps us quickly find a home if we search for it by the city name. But if we plan on also searching for homes by, say, the asking_price, then we’d have to create a separate database index just for that.

At the same time, we don’t necessarily want to create database indexes for each and every column of a table, since database indexes involve a trade-off. That is, they can dramatically increase the speed of search, but they also can take up a lot of space. If our table contains 10 million rows, for example, then so too does a database index. This is a balance that database designers always need to consider.

There’s another ramification of the fact that database indexes can consume a lot of space, namely, that often the index is too large to fit into main memory. Now, this isn’t a death knell. We could still store the index as an ordered list and simply keep it in a file in the filesystem.

However, if we structure our database index as an ordered list, our only option to search through it would be with external-memory binary search, which we’ve seen takes log₂ N I/Os. We can do much better with B-trees.

You’ve learned that B-trees offer a much faster search, namely, that of log_B+1 N I/Os. It is for this reason that numerous database engines use B-trees to store database indexes. It allows us to keep a large database index in the filesystem but still offer a blazing-fast search.

For a visual, how the previous database index may be stored in a B-tree with nodes that contain a maximum of 3 values is .

This B-tree stores both the city and id in each slot, and the keys are arranged alphabetically by city name. We can search this tree with just log_B+1 N I/Os. Once we find the city we’re looking for, we can then see its associated id. We then use that id to immediately find the memory location of the entire row of data corresponding to that home.

While some databases use classical B-trees to hold their database indexes, other databases use variants of the B-tree, such as the B+ tree, the B* tree, and others. Feel free to research those and explore all the delicious B-tree flavors out there.