Tags:conceptdatabasebtree Status:🟩

---

B+ trees in Databases

Summary

A B+ tree is a self-balancing data structure used in databases to efficiently store and retrieve large datasets on disk. Each leaf node corresponds to a disk page, holding pointers to actual data, while non-leaf nodes store index keys and pointers to child nodes, guiding searches to the correct leaf. This structure allows B+ trees to handle high-capacity datasets with minimal disk accesses, making them ideal for large-scale storage systems.

Details

B+ trees are a self-balancing trees data structure that are used in databases to efficiently store and retrieve data. They extend of the concept of binary search trees, and are designed to work well with large datasets stored on a disk.

In a B+ tree, each leaf node typically corresponds to one disk page. Inside each disk page, the leaf nodes store pointers (or references) to the actual data records on disk or, in some cases, may store the data directly if the records fit within the page. Non-leaf nodes (internal nodes) in a B+ tree hold only index keys and pointers to child nodes, helping direct searches toward the correct leaf nodes without storing actual data. In this image there are only shown 4 keys. However in real B+ trees can have hundreds of keys.

Just as binary search trees, the B+ tree is sorted from highest to lowest.

B+ tree traversals follow the same order every time, which avoids deadlocks.

Storage Capacity

• A typical tree:

  • Order (Amount of children each non-leaf node has): 1000 (~16 KB per page / 16 bytes per entry)
  • Utilization (typical percentage of each node that is actually filled with entries): 67% (usual numbers in real life)
  • Fanout (average number of child nodes per non-leaf node): 670

• Capacity

  • Root: 670 records
  • Two levels: 6702 = 448,900 records
  • Three levels: 6703 = 300,763,000 records
  • Four levels: 6704 = 201,511,210,000 records

• Top levels may fit in memory

  • Level 1 = 1 page = 16 KB
  • Level 2 = 670 pages = 11 MB
  • Level 3 = 448,900 pages = 7 GB

Operations

Searching

If we want to search in a B+ tree we start from the root, compare our value with the values in the node and decide which path to take based on the sizes of the comparison.

This example above just uses scan, which means going through the data sequentially. This would not be effective in real B+ trees, and therefore binary search should be used instead.

Insertion

When inserting a new key to a node, we search our way down to its position. Sometimes we get lucky and there are space for it to be. Other times we might have to split a node before we can insert a key. The example below goes through a splitting process.

We want to insert the node 8. Since the leaf and the root is full, we have to split.
We first split the leaf Then we copy the middle search key to a new parent node.
We then split the root and move the middle search key into the new root.
Now there is enough space to insert the node 8.