B+ 树为什么要把叶子节点串成链表？

简化版

B+ 树把所有真实数据或数据指针放在叶子节点，并把叶子节点按 key 顺序串成链表，是为了让范围查询、排序扫描和分页扫描更高效。定位到范围起点后，只要沿叶子链表顺序向后扫，不需要反复回到根节点查下一条记录。

详细版

B+ 树内部节点主要负责导航，叶子节点保存完整有序的数据项。叶子链表让“点查”和“范围扫”分工清楚：点查先从根一路下降到目标叶子，复杂度 O(log_f n)；范围查询先定位起点 leaf，再沿叶子链表顺序扫描 K 条结果，复杂度接近 O(log_f n + K)。其中 f 是扇出，通常很大，所以树高很低。

如果没有叶子链表，查 [10, 30] 这类范围时，找到 10 后还要不断回到父节点或重新从根查找后继，I/O 和指针跳转都会增加。叶子链表还天然支持 ORDER BY index_key、索引全扫描、顺序预读等数据库场景。这也是 B+ 树比普通 B 树更适合数据库索引的重要原因之一。

完整版教学

一、先理解 B+ 树的数据放在哪里

B+ 树和 B 树最大的区别之一，是 B+ 树把真实数据项或行指针集中放在叶子节点，内部节点只保存导航 key。这样所有查询最终都会走到叶子层，叶子层又是完整有序的 key 序列。把这一层串成链表后，B+ 树就同时具备“树形快速定位”和“链表顺序扫描”两种能力。

          [20 | 40]
         /    |    \
 [1,5,10] -> [20,25,30] -> [40,50,60]
       leaf linked list, ordered by key

这个结构不是装饰，而是数据库索引能高效支持范围查询的关键。如果只有树，没有叶子链，点查仍然快，但连续扫描会很别扭。

二、范围查询为什么特别依赖叶子链表

假设要查 WHERE age BETWEEN 20 AND 30。B+ 树先从根定位到第一个 age >= 20 的叶子位置，然后沿叶子链表向右扫描，直到遇到大于 30 的 key 停止。这个过程只需要一次树高搜索，后续就是顺序读。

range [20, 30]

1. root -> internal -> leaf，找到 20
2. leaf 内顺序扫 20,25,30
3. 如果当前 leaf 扫完，沿 next 指针去下一页
4. 遇到 40，停止

如果每取下一条都重新从根查后继，假设返回 1000 条记录、树高 3，就可能产生接近 1000 * 3 次层级访问；叶子链表则是 1 次定位加顺序扫描，I/O 模式友好很多。

三、叶子链表和磁盘顺序读的关系

数据库索引节点通常按页存储，例如一页 16KB。范围查询最怕随机 I/O，因为磁盘或 SSD 的随机读开销都比顺序读更难预测。叶子链表让相邻 key 的叶子页可以按顺序访问，数据库还可以做预读，把后续页提前读入缓存。

查询类型	没有叶子链表	有叶子链表
单点查询	影响不大，都是走树高	走树高到叶子
范围查询	后继查找麻烦，可能反复回根	定位起点后顺序扫
排序扫描	需要额外遍历逻辑	叶子层天然有序
分页读取	连续性较差	可以顺着叶子页读

这也是为什么 B+ 树常被称为“既适合随机查找，也适合范围扫描”的索引结构。

四、为什么普通链表不能替代 B+ 树

有人会问：既然叶子链表适合范围查询，为什么不用一个有序链表做索引？答案是：链表只能顺序扫，不能快速定位起点。要查 key=500000，如果只有链表，最坏要从头走到 500000；B+ 树可以先靠内部节点快速跳到目标叶子页。

有序链表:
  定位起点 O(n)，范围扫描 O(k)

B+ 树 + 叶子链表:
  定位起点 O(log_f n)，范围扫描 O(k)

这里的 f 是扇出，可能是几百。100 万条记录在扇出 200 的 B+ 树里，树高大约 3 到 4 层；这比链表从头扫描要稳定得多。

五、叶子链表带来的维护代价

叶子链表不是免费午餐。插入导致叶子页分裂时，需要把新叶子接入链表；删除导致页合并或重分布时，也要调整前后指针。也就是说，B+ 树把查询收益换成了写入维护成本。

叶子页分裂:

before:
  [10,20,30,40] -> [60,70]

insert 50, split:
  [10,20,30] -> [40,50] -> [60,70]

不过这个成本通常是可接受的，因为数据库索引的核心目标就是在海量数据中稳定支持点查和范围查。页分裂不会每次插入都发生，且可以通过填充因子、顺序主键等手段降低频率。

六、常见误区与追问

记忆钩子：B+ 树用树定位起点，用叶子链表完成连续扫描。

误区：叶子链表只是为了方便遍历整棵树。 它更重要的价值是范围查询、排序扫描和顺序预读。
误区：有叶子链表就不需要树形索引了。 链表无法快速定位起点，树负责把定位成本降到 O(log_f n)。
误区：B 树和 B+ 树范围查询能力完全一样。 B+ 树叶子层完整有序且相连，更适合连续范围扫描。
追问：叶子链表是单向还是双向？ 实现可以单向或双向；数据库常为了倒序扫描和维护便利使用双向链。
追问：叶子链表会不会影响插入性能？ 会增加分裂和合并时的指针维护，但换来了范围查询和扫描效率。
追问：为什么范围查询复杂度常写 O(log n + k)？ log n 用于定位起点，k 是返回或扫描的结果数量。

七、加强记忆

B+ 树叶子链表的核心价值是把两种访问模式接起来：树的上层负责快速定位第一个满足条件的叶子页，叶子链表负责从这个位置开始顺序扫描后续记录。没有树，链表定位太慢；没有链表，范围查询要频繁找后继。面试回答时要把“点查靠树、范围靠链、维护靠分裂合并时更新指针”这条线说清楚。

简化版

详细版