跳表和 B+ 树各适合什么场景？为什么 Redis 用跳表而 MySQL 用 B+ 树？

直接回答

跳表是多层有序链表，靠随机化层高实现期望 O(log n) 的增删查；B+ 树是矮胖的多路平衡树，内部节点存键索引导航，叶子节点存数据并串成链表。跳表适合内存型 KV（实现简单、并发友好、范围查询顺）；B+ 树适合磁盘数据库（树高低、单次 IO 读取多键、叶子链表利于范围扫描）。

展开解析

Redis 选跳表的原因：数据全在内存，无需考虑磁盘页；跳表实现远比 B+ 树简单；区间操作（ZRANGE）沿底层链表走即可；并发场景下跳表局部修改、加锁粒度小，而 B+ 树分裂合并涉及多层节点。MySQL InnoDB 选 B+ 树的原因：磁盘 IO 是瓶颈，B+ 树扇出大（一页上千个键），千万级数据树高仅 3~4 层，每次查找磁盘读次数少；内节点不存数据使单页容纳更多索引；叶子间双向链表让范围查询只需定位端点后顺序扫页，且页内数据物理相邻、预读友好。易错点：认为跳表是平衡树——它是概率平衡；B 树与 B+ 树混用——B 树内节点存数据、范围查询要中序遍历。追问：LSM-Tree 与 B+ 树的写放大对比、跳表层高期望分析。