B-Tree index structure

At some point we all worked with a relational database. We all had problems with query performance and we fixed them usually by first looking at indexes. We looked at the columns, at the foreign key for the presence of an index. We noticed there some kind of B-tree structure.

Now I’m gonna explain how this structure is being built.

A B-tree starts with a root node, and within this node, you can store data records using their keys. These data records may have pointers to the actual value assigned to the key, or may have that value inside the data record. These records need to be found fast. To achieve this it’s important that the index keys in each node of a B-tree structure to be sorted.

As an example let’s consider these values

{ 4, 33, 52, 42, 21, 12, 3, 29, 61, 53, 88, 99, 31, 20, 87, 22, 19, 97, 55 }

and also let’s assume we have a maximum node size of 3 elements (in real life there’s much more).

The next element is 42. This is between 33 and 52.

Next is 21. Between 4 and 33.

Next is 12. Between 4 and 33. Smaller than 21.

Next is 3. Smaller than 4. Gets its own node.

Next is 29. Bigger than 33. Smaller than 42.

Next is 61. Bigger that 52. Gets its own node.

Next is 52. Bigger than 52. Smaller than 61.

Next is 88. Bigger than 61.

Next is 99. Bigger than 88.

Next is 31. Bigger than 21. Smaller than 33.

Next is 20. Between 12 and 21.

Next is 87. Between 61 and 88.

Next are 22, 19, 97, 55.

Because the nodes contain the data in a sorted order the operations on the tree will be of complexity O(log n).