Binary Search Tree – Part 5 B-Tree

Hi, in the fifth part of my tree series, I want to talk about the B-tree. In the fourth part, we learned what a red-black tree is and what it does.

What is a B-Tree?

The B-tree is a very special tree, because it can contain more than 1 key in each node. Furthermore, each node can have more than 2 children. Ok sounds complicated but it is not. A B-tree is a balanced tree, which must be completely flat. That means all leaves are on the same level.

A B-tree is a data structure, which is often used in database systems and file systems. How must one imagine something like that? As a simplified example, we imagine that a B-tree is structured similarly to the file system, which I once did with the Composit pattern.

For example, a B-tree looks like this.

We see that our example B-tree can hold a maximum of 2 keys per node. Furthermore, we also see that each node can also hold a maximum of 3 children. Also, all leaves are on one level.

So we can state the following: Let $O = 1$ be the order, where $K = O + 1$, then it follows that $C = K + 1$.

This means that if a B-tree has the order 2, then each node can store 3 keys. If each node can store a maximum of 3 keys, then each node can have a maximum of 4 children.

Rules of a B-Tree

The rule is quite simple, and we also see that a 234-tree is a 2nd order B- tree.

Let's move on to the rules of insertion.

• It can only be inserted in leaves, never inside a branch.
• If we have an empty tree we create a node.
• If an overflow occurs at a node, this node is split and the middle element moves one level higher.

Zum nachspielen: https://www.cs.usfca.edu/~galles/visualization/BTree.html

How a B-Tree works

A small animation shows how the insertion works. The B-tree is of the 1st order.

As you can see, whenever there is an overflow, the node is always split. And the middle element (median) moves one level higher. What we also see is that it is always inserted only at the leaves.

The deletion works similarly, but here we make sure that we do not get underflows. This means that if we delete keys and our sheet is empty, we have to compensate for this by either merging the left side with the next larger parent entry or the other way around. But if we delete a key that is not in the leaf level, we have to swap it with the next smaller or bigger one, so that the key is in a leaf at the end.

A small animation shows how deletion works in a B-tree.

The search of keys is similar to a binary search tree.

Small Funfact! I mentioned the 234-tree, and that this is also a B-tree. The funny thing is, a 234-tree is also a red-black-tree, because you can transform a 234-tree into a red-black-tree.

A small example shows how the rules look like.

If we represent our 234-tree with the numbers $[1,2,3,4,5,6,7,8]$ as a red-black tree, it would look like this.

Wow magic! If you want to follow this, you can do it on this page: http://inst.eecs.berkeley.edu/~cs61b/fa17/materials/demos/red-black-2_4-demo.html

I hope I could give an insight to B-trees 😄