按非主键字段排序时数据库B+树的实际工作原理是什么？

1. y非主键时是否需要全表排序？ #

不一定，取决于y字段是否有对应的B+树索引：

• 如果y字段建有普通二级B+树索引，无需全表排序。二级索引的叶子节点本身就是按照y值的顺序存储的，DBMS可以直接遍历该索引的叶子节点获取有序序列。如果执行的是select * from x order by y查询，只需要按顺序回表到主键索引中查询完整行数据即可。
• 如果y字段没有建立任何索引，DBMS就需要先扫描全表获取所有数据，再对全表数据做排序操作，也就是常说的filesort流程。

2. 无索引时全表排序的开销是否较大？ #

开销非常大：

• 排序操作本身的时间复杂度为O(n log n)，数据量越大计算耗时越高。
• 如果排序的结果集超过了数据库配置的排序内存阈值，还会生成磁盘临时文件做外排序，额外产生大量磁盘IO开销，性能会出现断崖式下跌。

3. y为主键时的排序查询速度是否远高于y为其他字段的场景？ #

需要分场景判断，没有绝对的结论：

• 当y字段没有索引时，主键排序的速度会远高于非主键y的排序，前者只需顺序遍历主键索引叶子节点，没有额外排序开销，性能差距可能达到数倍甚至数十倍。
• 当y字段建有二级索引时：
  • 如果查询可以用到覆盖索引（比如执行的是select y from x order by y，不需要读取其他字段），两者性能几乎没有差异，都是直接顺序读取有序的索引叶子节点即可。
  • 如果执行select *需要回表查询整行数据，非主键排序的性能会低于主键排序，差距取决于回表的随机IO开销：数据量小、回表全部命中缓存时差距不明显；数据量很大、回表产生大量离散IO时，性能差距会非常显著。

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