Why MySQL Chooses B+ Trees Over Skip Lists for Indexing

B+ Tree Structure

In a B+ tree, data pages (typically 16 KB) form a multi‑level hierarchy where leaf nodes store the actual rows and non‑leaf nodes store index entries (primary key and page number). Searching proceeds from the root, following records that point to child pages, and uses binary search within a page to locate the target row, reducing query complexity from O(n) to O(log n).

Skip List Structure

A skip list builds multiple linked‑list layers on top of a basic singly linked list. Each higher layer contains a subset of the lower‑layer nodes, allowing a search to jump over large ranges and halve the search space at each level, achieving O(log n) complexity.

Differences Between B+ Tree and Skip List

Insertion in B+ Tree

A B+ tree is a balanced multi‑branch tree; when a leaf or index node becomes full (assumed 3 rows per page for illustration), the node splits and may propagate upward, possibly adding a new level if both leaf and index nodes are full.

Both leaf and index nodes not full – insert directly into the leaf.

Leaf full, index not full – split the leaf and add a new index entry.

Both leaf and index full – split both and create an additional upper level.

Insertion in Skip List

When inserting a new element, the bottom‑level list always receives the node. Whether the element is promoted to higher levels is decided by a random function: 50 % chance to appear in level 2, 25 % in level 3, and so on, yielding an expected binary‑search‑like distribution without any rebalancing cost.

Why MySQL Uses B+ Trees Instead of Skip Lists

Each B+‑tree node holds a 16 KB page, giving a high fan‑out; typically three levels can store around 20 k rows, requiring at most three disk I/O operations per query. A skip list storing the same amount of data would need about 24 levels, potentially causing up to 24 disk I/O operations, making B+ trees faster for read‑heavy workloads.

Why Redis Uses Skip Lists Instead of B+ Trees

Redis operates entirely in memory, so disk I/O is irrelevant. Skip lists have a simple implementation and avoid the rotation and balancing overhead of tree structures. Therefore, Redis adopts skip lists for its sorted‑set (ZSET) implementation, achieving fast writes with minimal complexity.

Conclusion

B+ trees are high‑fan‑out balanced search trees; with only three levels they can store ~20 k rows, giving far fewer disk I/O operations than a comparable skip list, so MySQL selects B+ trees for indexing.

Redis stores data in memory, eliminating disk‑I/O concerns; skip lists provide simple, low‑overhead indexing, making them suitable for Redis ZSET.

RocksDB uses skip lists internally, offering better write performance than InnoDB’s B+‑tree engine, but read performance is slower, so B+ trees remain preferable in read‑dominant scenarios.