DEV Community

Cover image for Why MySQL and Postgres Use B+ Trees Instead of B-Trees for Indexing
Binary Dose
Binary Dose

Posted on Originally published at binarydose.in

Why MySQL and Postgres Use B+ Trees Instead of B-Trees for Indexing

#dbms #database #systemdesign #sql

Why MySQL and Postgres Use B+ Trees Instead of B-Trees for Indexing

When indexing relational databases (such as MySQL's InnoDB or PostgreSQL's standard btree index), the underlying data structure is almost universally a B+ Tree, rather than a standard B-Tree.

To understand why, we must analyze how physical storage hardware and operating system page caches interact with tree fan-out.

1. The Fan-Out Problem in Standard B-Trees

In a standard B-Tree, every node (both internal and leaf) stores:

  • Search Keys
  • Child Pointers
  • Record / Tuple Pointers (Data Pointers)

Because physical storage is organized into fixed-size blocks (typically 16 KB in InnoDB), the inclusion of bulky data pointers significantly reduces the number of keys that can fit into a single page.

The Math:

  • If each entry is 128 bytes (key + data pointer), a 16 KB page holds ≈ 125 keys.
  • If internal nodes store only 16-byte routing entries (8-byte key + 8-byte child pointer), a 16 KB page holds 1,000 keys!

Higher fan-out directly reduces tree height h. In a database indexing 1 billion rows:

  • Lower fan-out B-Tree: Height = 5–6 (5–6 disk seeks).
  • Higher fan-out B+ Tree: Height = 3 (3 disk seeks).

Because the root and level-1 nodes reside permanently in the database RAM buffer pool, nearly all point lookups execute in just 1 physical disk seek!

2. Linked Leaf Nodes for Sequential Range Queries

Relational database queries frequently retrieve ranges of records:

SELECT * FROM orders WHERE order_date BETWEEN '2026-01-01' AND '2026-01-31';
Enter fullscreen mode Exit fullscreen mode

In a B-Tree:

Records matching the range are scattered across internal nodes and leaf nodes. The engine must perform an expensive, recursive in-order tree traversal, repeatedly navigating up and down parent pointers.

In a B+ Tree:

  • All data records reside exclusively in leaf pages.
  • Every leaf page contains a pointer to the next and previous leaf page (forming a doubly-linked list).
  • The engine performs a single point lookup to find the start key (2026-01-01), and then simply scans horizontally across the leaf linked list in O(K) time!

Explore full database storage engine architectures at Binary Dose.

Top comments (0)