A summary by Mona Sobhani.

Fifty years ago, Rudolf Bayer and Edward M. McCreight, both working at the Boeing Research Labs, invented a data structure called “B-trees” that is nowadays one of the most used data structures in database systems. It has changed the way of storing data and thereby enormously reduced the IO-costs for searching, deleting and inserting data in a database. This blog post aims to show how the structure of the B-tree is organized, how an algorithm on this structure works and how this data structure has evolved since the invention in 1971, when they published it in a scientific paper which is called “Organization and Maintenance of Large Ordered Indices”.

Structure and characteristics of the B-tree

Before inventing the structure of a B-tree, data was organized with index tables. The more data, the longer the index table got or even became a two-level index. Indexing helped to find data faster. For example, if you are searching for specific data, you would use the index to see what block of data you would have to access (load into memory), to find the data. This allows you to not access all the blocks on the disk but just one block, where you will find the data you are looking for.

If the index table is getting too large, one can use a two-level index where the first index points to another index in the second level. One can even use more than a two-level index. When there are too many levels, a B-tree comes into hand. Having a lot of data, or in this case many primary keys, a B-tree organizes the keys in the nodes of a balanced tree.

Each node consists of an index-key and a pointer to the data block, where the data can be found. If we use the same example as before, how do you we now access the data? Looking for a specific key, we now do a search similarly to a binary search. Start at the root of the key and continue either at the left child node or right child node depending on the key number. The B-tree is balanced and therefore assures us to find every key in O(log n). But before looking at the efficiency of a B-tree, we will have a look at the structure and the conditions of a B-tree.

The following figure should help to understand the structure of the B-tree, which Bayer and McCreight published in their paper.

Bayer and McCreight describe the organization of the B-tree as follows:

“The index is organized in pages of fixed size capable of holding up to 2k keys, but pages need only be partially filled. Pages are the blocks of information transferred between main store and backup store. The pages themselves are the nodes of a rather specialized tree, a so-called B-tree, […].” [1]

Now that we have understood the structure of the B-tree a little better, we will take a look at the rules and conditions of a B-tree, which I will list in the following.

• The keys in the node are always sorted If a node has n keys, it has n+1 pointers
• The root always has a minimum of two pointers
• The left-sided pointer of a key points to a node with keys that are have a smaller size
• The right-sided pointer of a key points to a node with keys that are greater or equal to the key size
• The internal nodes (every node except the root and the leaf’s) have a minimum and maximum number of containing keys
• The B-tree is always balanced

Insert new key into the B-tree

There are three main algorithms that allow the B-tree to stay balanced. I will explain one of those algorithms, the one that inserts a new key into a B-tree.

Whenever a key is inserted into a B-tree, the node where the key will be inserted will be searched for similarly to a binary search. Let 4 be the key that should be inserted. If the key in the root is smaller than the inserted key, here root here is 2, then the key will be inserted into the child node on the right side, once there is space left (see figure 2). Once one node already contains the maximum number of keys it can have (see insertion of 5 in figure 2), the node will be split in two nodes and the keys will be divided into two new nodes containing each of the keys. Remember, that the nodes are not densely packed with keys, so that the insertion becomes efficient because the nodes do not always need to be split when a key is inserted.