B-Trees

In this chapter, we cover B-trees, also called multiway search trees. Multiway search trees are what they sound like — they're search trees. We've seen search trees before, namely the binary search tree:

With binary trees, we have the restriction that every node in the tree can have, at most, two children. If we increased the number of keys, however, then the number of children can also increase. This is precisely what multiway search trees (MWay trees for short) are supposed to accomplish:

In the MWay tree above, the root has two keys, allowing us to construct a tree with three children. Because the tree now has three children, we say that the above tree is an MWay tree of degree-3. Alternatively, the tree above is also called a 2-3 tree (2 keys, degree 3).

B-Trees

2-3 trees are height-balanced search trees. Below, is the same 2-3 tree with the height-balance factors indicated:

As such, they are members of the set of B-trees. B-trees are height-balanced trees of any degree. Because of this classification, 2-3 trees can also be referred to as B-trees of degree-3. For readability, we'll use the term 2-𝑛 tree, where 𝑛 is the degree of the B-tree.

Properties of 2-n Trees

Alongside their height-balanced nature, 2-𝑛 trees have several other properties that distinguish them from other trees. First, all the leaves of a 2-𝑛 tree are positioned at the same level:

Notice that all of the leaves in the tree above exist on the same level. The second property is that every node in the 2-𝑛 tree has at at least half of 𝑛. In our example tree, we have n=3.{n = 3.} Thus, each node must have, at a minimum,

⌈n2⌉=⌈32⌉=⌈1.5⌉=2 \left\lceil \dfrac{n}{2} \right\rceil = \left\lceil \dfrac{3}{2} \right\rceil = \left\lceil 1.5 \right\rceil = 2

children.

Ordered Children. A further property to observe with 2-𝑛 trees is that each node's keys have a particular ordering. That is, given the tree:

each k1 is always less than its parent's L1, and each k2 is always less than its parent's R2.

No Duplicates. Like all other search trees, 2-𝑛 trees do not contain duplicates. If a duplicate is encountered, it is not inserted.

Constructing a 2-3 Tree

To construct a 2-3 tree, we need a way to insert nodes. Say we wanted to insert the following values:

[20,30,40,50,60,10,15,70,80] \ix{20, 30, 40, 50, 60, 10, 15, 70, 80}

The first key we encounter is 20. Our tree contains nothing, so we create a node:

Next, we see 30. As we now have a non-empty tree, we follow this procedure for insertion:

  1. Check if the key is in the current node.
  2. If the key is in the right or left fields, return.
  3. Otherwise:
  4. If the key is less than the right field's value, search the right

We place this key in the node containing 20:

Now 40. We can't insert this key into the node with 20 and 30, because this is a 2-3 tree. We can only have 2 keys in a single node at most. So, we have to split the node we already have, and create a new node for 40:

Next, we follow the ordered-property of 2-3 trees: We know that 20<30,{20 \ltn 30,} and 30<40.{30 \ltn 40.} So, the left-child of 30{30} must be 20,{20,} and the right child of 30{30} must be 40;

Notice how this construction differs from the usual binary trees. We're building from bottom to top, rather than top to bottom.

The next key is 50.{50.} We start at 30,{30,} and see that 30<50.{30 \ltn 50.}