一.数据库排序技术整体概述
1.数据库为什么需要排序？
当我们平时写SQL排序语句时：
SELECT *
FROM Student
ORDER BY score;
这时数据库就需要把学生按照score进行排序。但数据库里的数据可能非常大。比如有1000万条学生数据，共占用了5GB的磁盘空间，而计算机可能只有512MB的内存，这时就不能直接把所有数据从磁盘读到内存里从而使用sort()函数进行排序。
这也就是数据库排序和普通程序排序最大的区别之一。
2.数据库排序面对的核心矛盾
数据库中的数据主要存放在磁盘或固态硬盘当中，然而排序通常需要利用内存进行实现，所以数据库排序技术实际是在解决如何尽可能减少磁盘I/O。
因为：CPU排序通常很快，然而磁盘读写通常比较慢。所以排序算法核心重点关注的不是比较操作有多少次，而是需要进行多少次磁盘I/O？
3.排序核心分类
（1）内部排序
内部排序就是所有的待排序数据都可以放进内存，这时我们就可以使用我们常用的标准排序算法如：快速排序，堆排序，归并排序等
（2）外部排序
外部排序就是待排序的数据太大，不能一次性放进内存，只能借助磁盘完成排序。 例如：当磁盘中有100G的数据，但内存只有1GB时，就不能一次性排序。这时数据库通常使用外部归并排序 核心分为两步：
1.建段阶段：将数据分为多个有序段Run，写入磁盘。
2.归并阶段：多路归并有序段，最终生成完整的有序文件。
4.为什么数据库喜欢归并排序？
为了最大化利用磁盘顺序IO，顺序IO的速度是随机IO的几十到上百倍。
- 使用归并排序：读取的顺序串是顺序读，写入最终结果也是顺序写，全程几乎都是顺序IO，把磁盘的特性利用到了极致。
- 若使用快排或堆排：磁盘产生大量随机IO，性能大幅下降。
5.排序核心分类与物料机制
例如有一张学生表如下：
| ID | Name | Score | Age |
|---|---|---|---|
| 1 | 张三 | 85 | 20 |
| 2 | 李四 | 92 | 19 |
| 3 | 王五 | 78 | 21 |
| 4 | 赵六 | 95 | 20 |
当我们对Score进行排序时，我们需要把一整行数据整体进行移动吗？还是只需要将每个人的成绩进行移动，最后再按排序键来排序找到整条完整数据？
这就是 “排序键值存储机制” 要解决的问题。
因为一条完整记录可能很大。一条学生记录可能有：ID，姓名，性别，年龄，地址，电话，邮箱，课程，自我介绍，照片等等信息。完整一条记录可能有500Bytes，而排序键只有4Bytes，如果总共有1000万条记录，那么完整记录会有500MB，而排序键只有4MB，所以排序移动的数据量差别还是非常大的。
排序键值存储：Key+Value其中key就是排序键，value就是与这条记录对应的其他信息。用上面这张学生表来说：Key=score，Value=ID，这样排序的时候就只需要排序key值而不必把整个学生记录都搬动。
（1）早物化
早物化：很早就把各列拼成完整元组，然后拿完整元组去处理。排序时直接存储完整元组数据，排序完成后可直接输出结果，无需二次读取。
（2）晚物化
晚物化：先不要急着把所有列拼起来，先分别处理，真正需要输出的时候再拼。仅存储排序键+元组记录ID，大幅减少排序过程中的内存、磁盘占用，排序结束后再根据ID回表读取完整数据。
二.Top-N堆排序算法
1.问题背景
例如我们需要在一张学生表中找出成绩最高的10个学生。假设这张学生表里有1000万条学生记录，但我们只需要前10名，普通排序可能会将1000万条数据全部排序，然后从这1000万条数据里取前10条，这样就会很浪费性能，因为我们就根本不需要前10名以外的排名。
2.Top-N堆的核心思想
只在内存中保留目前最有希望进入前N名的N条记录。
这时，我们不需要将全部数据进行排序，只需要维护一个大小为N的堆。
例如我们要找Top3，我们希望堆顶就是Top3里面最小的那个，这样来了一个新元素，如果新元素小于等于堆顶，那么这个新元素就不会进入Top3堆，直接将其丢掉，如果这个新元素大于堆顶，就说明这个新元素比当前Top3里最差的还好。那么我们就要进行删除堆顶→加入新元素→重新调整堆
堆本身并不能代表它已经完全排序。它的主要作用是找到Top堆里最小的那个元素，所以我们通常还需要对这个Top堆进行一次排序，整个过程就变成：1000万条数据→扫描→维护大小为N的堆→最终只剩下TopN条数据→对Top堆进行排序→输出
- 最大Top-N需要使用最小堆
- 最小Top-N需要使用最大堆
三.基于B+树索引的排序优化
1.核心本质
B + 树索引的叶子节点天生按索引键有序排列，只要排序需求和索引顺序匹配，数据库可以直接顺着叶子节点顺序读取数据，完全不用做全表归并排序。大幅降低查询开销，是最优排序方案。
2.聚簇B+树
聚簇 B+ 树：叶子节点“就是数据”，或者说数据按照这个索引的顺序组织。叶子节点直接存储完整有序元组，直接从最左叶子节点顺序遍历即可得到全局有序数据，全程为顺序IO，无排序计算，性能优于外归并排序。
3.非聚簇B+树
非聚簇B+树：叶子节点通常存Key+数据定位信息，数据顺序不一定按索引键组织。遍历索引后需要随机IO回表读取完整数据。普通全量排序场景下随机IO开销极大，性能极差；仅适配小N的Top-N查询。
四.数据库聚合算法
1.数据库聚合算法概念
聚合的核心是 按分组键归类数据+每组做统计运算。 主流实现路线：排序聚合 和 哈希聚合
2.排序聚合算法
先按照 GROUP BY 的字段排序，让相同组的数据挨在一起，然后顺着扫描计算。
（1）核心原理
先按 GROUP BY 的分组键做排序，让相同分组键的记录连续排列；再单次顺序扫描数据，相邻相同键值的元组即为同组数据，实时累加计算聚合结果，维护当前组的聚合值（sum、count 等），遇到新分组键就输出上一组结果、重置计数器。
本质：排序让相同键聚在一起，一次遍历完成聚合。
（2）优缺点
优点： 结果天然有序，无需二次排序。
缺点： 排序开销大，性能损耗高；无需有序结果时存在大量冗余计算。
3.哈希聚合算法
绝大多数聚合查询不需要有序输出结果，排序聚合的排序开销完全冗余。因此引入哈希聚合，通过哈希映射直接分组，规避全量排序。不排序，而是利用哈希表把相同 GROUP BY Key 的数据放到一起。
（1）核心原理
在内存中构建哈希表，以分组键为 key，聚合状态为 value。遍历每条数据时，按分组键计算哈希值，定位到对应桶并更新聚合值（累加 sum、计数 count 等）。全部数据遍历完成后，遍历哈希表输出所有分组结果。
本质：用哈希表直接分组，一次遍历完成，不需要排序。
（2）外部哈希聚合
当哈希表太大内存放不下时，我们就需要先把数据按照哈希值分区写到磁盘，再分别处理每个分区。
因为相同的Key一定会进入相同的磁盘分区，这样就能把同一个Key聚合起来。然后对每个磁盘分区构建内存哈希表。读取，，每个分区数据，在内存中完成聚合计算。
（3）优缺点
优点： 无需排序，计算开销极低，性能优于排序聚合，适配海量无序聚合查询
缺点： 输出结果无序，需要排序需二次处理。
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/2502_93869639/article/details/167039131
