关系型数据库如何基于二级索引实现多列ORDER BY排序？

最优方案：复用联合索引的天然有序性 #

当排序要求和已创建的联合索引顺序、排序方向完全匹配时，数据库会直接复用B+树的天然有序性，逻辑和单列索引排序完全一致。

比如你要执行ORDER BY FirstName ASC, LastName ASC，只要预先创建了(FirstName, LastName)的联合二级索引，该索引的B+树键结构为(FirstName值, LastName值, 关联主键ID)，本身就完全符合排序规则。执行逻辑如下：

• 按顺序遍历联合索引的叶子节点
• 只要键中携带的主键属于待排序的ID集合，就将其从待处理集合移除，加入结果输出列表
• 待处理ID集合为空或索引遍历完成后直接返回结果

这个方案不需要额外排序操作，是性能最高的实现。

无匹配联合索引时的通用排序方案 #

如果没有对应顺序的联合索引，主流数据库会优先选择「索引扫描+排序」的方案，而非扫描多个独立索引做平局决胜，核心原因是多次随机IO扫描索引的成本远高于内存/磁盘排序的计算成本。

你提到的「用第二个独立索引做平局决胜」的方案几乎不会被主流数据库采用，仅在待排序数据量远超内存容量、且排序字段均有高选择性独立索引的极端场景下才会被纳入执行计划评估。

MySQL的实现逻辑 #

MySQL会根据待排序数据量大小选择不同的排序模式：

1. 内存排序：如果待排序数据量小于sort_buffer_size配置阈值，直接在内存中使用快速排序完成多列排序：
   • 先通过索引或全表扫描拿到所有待排序行的排序字段值+主键ID，存入sort buffer
   • 按ORDER BY的规则对sort buffer里的条目进行排序
   • 排序完成后，按需回表查询其他需要返回的字段，或直接返回覆盖索引中已有的字段
2. 外部磁盘排序（filesort）：如果待排序数据量超过内存阈值，会将数据拆分到多个临时磁盘文件，分别对每个文件做归并排序，最后合并所有文件的有序结果。
3. Top-N优化：如果ORDER BY后带有LIMIT子句，MySQL会直接使用堆排序，只维护大小为LIMIT的堆结构，不需要全量排序，大幅降低计算开销。

PostgreSQL的实现逻辑 #

PostgreSQL的逻辑和MySQL类似，但有两个专属优化：

• 当排序字段上有独立索引时，会优先收集所有待排序ID对应的排序字段值，在内存中用多路归并完成排序
• 同样支持Top-N堆排序优化，且对于存在NULL值的排序场景会做额外的分支裁剪，进一步降低排序耗时

内容的提问来源于stack exchange，提问作者Martin Häusler