为什么 B+ 树的范围查询和排序特别高效？

简化版

因为 B+ 树的所有叶子节点从左到右用指针连成了一条有序链表，覆盖了全部数据。做范围查询时，只要先定位到范围起点所在的叶子（O(logₘn)），然后顺着链表指针一路向右扫到终点即可，全程不用回树里绕。排序、ORDER BY、分页也都是「扫叶子链表」，天然有序、还是顺序 IO，所以特别快。

详细版

一次范围查询 WHERE key BETWEEN 10 AND 50 在 B+ 树上分两步：

定位起点：像普通查找一样从根下降到叶子，找到 key=10（或第一个 ≥10）所在的叶子位置。O(logₘn) 次 IO。
顺链扫描：从该位置沿叶子链表向右依次读取，直到遇到 > 50 的 key 停止。这一步是顺序访问相邻叶子页。

叶子层（有序链表）：
[..8] → [10 12 15] → [20 28] → [33 41 50] → [55..] → ...
          ↑起点                       ↑终点
从起点顺着 → 指针扫到终点，全程不回树

对比 B 树：B 树叶子不相连，范围查询要不断回到父节点、再下降到下一个子树（中序遍历式的上下回溯），慢且是随机 IO。

完整版教学

一、叶子链表：范围查询的关键

B+ 树相比 B 树最实用的改进，就是把所有叶子用指针串成有序链表。这条链表按关键字从小到大覆盖了全部数据，等于在树的底部铺了一条「有序高速公路」。任何「一段连续区间」的查询，都可以变成「在这条公路上从某点开到某点」，而不需要在树的枝干间上下攀爬。

二、范围查询为什么快

范围查询的代价 = 定位起点 O(logₘn) + 顺链扫描 O(结果数量)。

定位起点和普通查找一样，几次 IO。
之后顺着链表扫，读的是物理上大致连续的叶子页，属于顺序 IO——磁盘顺序读比随机读快一个数量级。
不需要任何回溯，读多少数据就扫多少，没有额外开销。

而 B 树做同样的范围查询，要在树里做中序遍历：读完一个子树，回到父节点，再下降到下一个子树……大量随机 IO 和回溯，慢得多。

三、排序和 ORDER BY 为什么免费

因为叶子链表本身就是按索引列有序的，所以：

ORDER BY 索引列 可以直接顺着叶子链表输出，不需要额外排序（省掉一次 filesort）。
SELECT ... ORDER BY id LIMIT 10 这种，扫链表前 10 个就返回。

这也是为什么「按索引列排序」比「按非索引列排序」快得多——前者白嫖了 B+ 树叶子的天然有序，后者要额外排序。

四、分页与 LIMIT

分页 LIMIT offset, n 也受益于叶子链表：顺着链表跳过 offset 个、取 n 个。（不过 offset 很大时要跳过很多，仍有「深分页」性能问题，可用「记住上次最大 id、WHERE id > ?」的方式优化——本质还是利用叶子链表的有序性从某点继续扫。）

五、双向链表让「倒序」也快

很多实现（如 InnoDB）的叶子是双向链表（每个叶子既指向后一个也指向前一个）。这样 ORDER BY 索引列 DESC（倒序）也能顺着链表反向扫，同样高效，不用额外排序。

六、常见误区与追问

考点	正确口径
定位起点	从根到叶找到范围左边界
顺序扫描	沿叶子链表向右扫
停止条件	超过范围右边界或满足 LIMIT

seek lower_bound
while leaf && key <= high:
  read records in leaf
  leaf = leaf.next

B+ 树范围查询快，关键是叶子节点按 key 有序并通过链表相连。

误区：范围查询需要每条记录都重新从根查一次。 只需先定位左边界，后续沿叶子链表顺序扫描即可。
误区：B 树和 B+ 树范围查询一样方便。 B 树数据分散在内部节点和叶子节点，顺序扫描不如 B+ 树叶子链表自然。
误区：ORDER BY 总是需要额外排序。 当查询顺序与索引顺序匹配时，可以直接按叶子链表顺序输出。
追问：为什么 LIMIT 分页仍可能慢？ 大 offset 需要跳过很多叶子记录，虽然有序但仍要扫描和丢弃大量行。
追问：倒序范围查询怎么办？ 很多实现叶子页有双向链表，可以从右边界定位后向左扫描。
追问：复合索引范围查询有什么限制？ 要遵守最左前缀，遇到范围条件后，后续列通常不能继续用于精确定位。

七、加强记忆

B+ 树范围查询/排序快，靠叶子节点连成的有序链表（覆盖全部数据）。范围查询 = 定位起点 O(logₘn) + 顺链向右扫描（顺序 IO、无回溯）；ORDER BY 索引列 直接顺链输出、免额外排序；双向链表让倒序也快。对比 B 树叶子不相连、范围查询要中序回溯 + 随机 IO，B+ 树的链表是它做数据库索引的杀手锏。

简化版

详细版