B+树相较于跳表的优势有哪些？——基于CMU数据库课程的疑问

Great question! I’ve wrestled with this exact comparison after catching that same CMU database lecture—skip lists do feel like a "rotated" B+ tree on paper, with similar average time complexity, but there are critical reasons why nearly all disk-based DBMS stick with B+ trees for primary and secondary indexes. Let’s break down the key advantages:

1. Unbeatable Disk I/O Efficiency #

This is the biggest one. DBMS mostly operate on disk storage, where sequential I/O is orders of magnitude faster than random I/O. B+ trees are designed from the ground up to align with disk page sizes (typically 4KB-8KB):

• Each B+ tree node is exactly one disk page, so a single I/O operation loads an entire node’s worth of keys and pointers.
• Leaf nodes form a contiguous ordered linked list. For range queries (e.g., SELECT * FROM orders WHERE order_date BETWEEN '2023-01-01' AND '2023-01-31'), you only need to find the starting leaf node, then read sequentially through the linked list—no backtracking to upper layers, no random jumps.

Skip lists, by contrast, have scattered nodes across memory/disk. Even with their layered pointers, each node holds far fewer keys than a B+ tree page, leading to more random I/O operations to traverse the structure. Range queries on skip lists also lack the sequential read benefit of B+ tree leaves, since nodes aren’t stored contiguously.

2. Better Space Utilization #

While skip lists avoid storing "intermediate" nodes in the B+ tree sense, they carry their own overhead: each skip list node has multiple pointers (one for each layer it exists in), leading to O(n log n) total space overhead on average.

B+ trees, however, maximize space efficiency:

• Internal nodes only store keys and child pointers, with no duplicate data (all actual records or pointers to records live in leaves).
• Nodes are densely packed (usually filled to 50-100% capacity depending on split/merge rules), minimizing wasted space. For large datasets, this adds up to significant savings in disk storage and memory footprint.

3. Deterministic, Predictable Performance #

B+ trees have a fixed, predictable height based on the number of elements and node fanout (e.g., a fanout of 1000 means a tree with 1 billion elements only has 3 layers). This means every query, insert, or delete requires exactly the same number of disk I/O operations—no variance.

Skip lists rely on randomization to build their layers. While average time complexity is O(log n), worst-case performance can degrade to O(n) (if the random layer assignments are unlucky). For production DBMS, consistent, predictable performance is non-negotiable—you can’t have a query suddenly take 100x longer because of a bad random seed.

4. Decades of Optimized Tooling & Compatibility #

B+ trees have been the standard for DBMS indexes since the 1970s, which means there’s a massive ecosystem of optimizations tailored to them:

• Prefix compression: Internal node keys can be compressed by storing only the difference from the previous key, saving space.
• Buffer pool integration: DBMS buffer pools are designed to cache frequently accessed B+ tree nodes, with eviction policies optimized for tree traversal patterns.
• MVCC support: Most modern DBMS use Multi-Version Concurrency Control, and B+ trees are easily adapted to store multiple versions of records in leaf nodes.
• Concurrency control: Node-level latches (lightweight locks) work seamlessly with B+ trees—you only need to lock the specific nodes being modified, leaving the rest of the tree accessible.

Skip lists, while simpler to implement in memory, lack this mature tooling. Adapting a DBMS to use skip lists would require rewriting core components like buffer management and transaction handling, which is rarely worth the effort.

5. Superior Range Query & Sorting Support #

Beyond sequential I/O, B+ trees’ leaf node linked list makes range queries and sorted operations trivial. For example:

• Finding all records greater than a value requires just traversing the leaf list from the starting point.
• Sorting results by the indexed column is free, since the leaf nodes are already in order.

Skip lists can handle range queries, but they require jumping between layers and traversing scattered nodes, which is far less efficient—especially on disk. There’s no equivalent to the B+ tree’s contiguous leaf list for fast sequential access.

When Do Skip Lists Make Sense? #

Don’t get me wrong—skip lists have their place! In-memory databases like Redis use skip lists because disk I/O isn’t a concern, and their simpler implementation (no complex split/merge logic) is a plus. But for disk-based DBMS that prioritize I/O efficiency, space utilization, and predictable performance, B+ trees are still the clear winner.

内容的提问来源于stack exchange，提问作者Yifeng