An Introduction to B-Trees

What are B-Trees?

Search Trees that have a degree ≥2 (maximum # of children)
Access and insertion similar to BSTs
Obey BST order property

Different B-Trees can have different degrees:

Image of a simple B-Tree

What are 2-3-4 Trees?

B-Trees with a degree of 4
2-3-4 denotes the number of children a node can have

2-3-4 Tree Insertion Algorithm

Important: we only add values to the bottom of the tree i.e. only in leaf nodes.

  1. If there is space in the node, add it.
  2. If there is no space in the node, split the leaf node and push the middle value to the parent node.

Premptive Split

On the way down to the leaf node that you are inserting a value into, split any node that you step through which is full.
This helps ensure that there is always space in the parent of any potentially split child node to hold one more value.

The parent node can never be full:

If the root node is full, a split causes the middle value to go up and become its own root node. This is the only case in which the depth of the tree is incremented.

You may find more information here.