Why MySQL Uses B+ Trees Instead of Skip Lists for Indexing

B+ Tree Structure

In a B+ tree, data pages (typically 16KB) form a multi‑level hierarchy. Leaf nodes store the actual row data, while internal nodes store index information (primary key and page number) to accelerate searches.

When searching for a key, the algorithm starts at the root, follows the appropriate record pointers, and uses binary search within a page directory to locate the exact row, reducing the search 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 nodes from the layer below, allowing searches to skip large portions of the list and achieve O(log n) average complexity.

Insertion involves adding the element to the bottom layer and, based on a random function, promoting it to higher layers with decreasing probabilities (50% to level 2, 25% to level 3, etc.).

Differences Between B+ Trees and Skip Lists

Both structures store all data in the lowest layer and maintain sorted order for range queries, but they differ in how they handle inserts and deletes. B+ trees maintain balance through node splits and merges, while skip lists rely on randomness without rebalancing.

B+ Tree Insertion

If neither leaf nor internal node is full, the new record is inserted directly into the leaf.

If the leaf is full but the internal node is not, the leaf splits and the internal node receives a new index entry.

If both leaf and internal nodes are full, both split and a new level may be added.

Skip List Insertion

The bottom‑level list always receives the new element. Whether the element is promoted to higher levels is determined solely by a random function, giving each level a 50%, 25%, 12.5%… chance respectively.

Why MySQL Uses B+ Trees Instead of Skip Lists

B+ trees have a high fan‑out because each node holds many index entries (a 16KB page can store thousands of keys). Typically only three levels are needed to index around 20,000 rows, resulting in at most three disk I/O operations per lookup.

In contrast, a skip list storing the same number of entries would require roughly 24 levels, potentially causing up to 24 disk I/O operations in the worst case, making reads slower.

For writes, skip lists have an advantage because they avoid the costly node splits and rebalancing required by B+ trees; however, MySQL’s storage engines (MyISAM, InnoDB) are designed around B+ tree indexes.

Why Redis Uses Skip Lists Instead of B+ Trees

Redis is an in‑memory database, so disk I/O is not a concern. Skip lists provide simple, fast insertion without the need for balancing operations, making them ideal for Redis’s sorted set (ZSET) implementation.

Because there is no disk I/O penalty, the higher level count of a skip list does not degrade performance, and the random‑level promotion simplifies implementation compared to balanced tree structures.

Summary

B+ trees are multi‑branch balanced search trees with high fan‑out, requiring few levels (≈3) for typical data sizes, leading to fewer disk I/O operations and better read performance than skip lists.

Redis’s in‑memory nature eliminates disk I/O concerns, and skip lists offer simpler insertion without balancing overhead, making them a better fit for Redis’s sorted sets.

RocksDB uses skip lists internally, achieving better write performance but slower reads compared to InnoDB’s B+ tree indexes, so B+ trees remain preferable for read‑heavy workloads.

References

《MYSQL内核：INNODB存储引擎 卷1》

《RocksDB和Innodb引擎性能PK胜负难料？》

https://cloud.tencent.com/developer/article/1813695