数据库排序：外部归并排序(External Merge Sort)详解

"排序与聚集是数据库管理系统的常见操作，特别是在执行SQL查询时。当需要对大量数据进行排序，而这些数据无法一次性加载到内存时，就会涉及到外排序，特别是2阶（2路）外排序算法。外排序是处理海量数据的一种策略，它通过将大文件分割成小块，对每个块进行内存内的排序，然后再合并这些排序后的块来实现全局排序。" 在SQL中，如果不特别指定，查询结果通常是未排序的。然而，通过添加`ORDER BY`关键字，用户可以要求返回的结果集按照特定字段进行排序。当数据量过大，无法全部装入内存时，数据库管理系统(DBMS)需要采用外排序方法，如外部归并排序(External Merge Sort)。 外部归并排序借鉴了分治策略，首先将大文件分割成多个称为sorted run的小块，每个块足够小，可以装入内存并排序。在排序过程中，每个键值对(KV)根据Key进行排序。对于Value，有两种处理方式：早物化和晚物化。早物化是指Value是整个tuple，而晚物化仅保存tuple的recordid，以减少内存消耗，尤其是当tuple非常大或表宽时。晚物化允许我们根据recordid在主表中查找完整信息，降低了调整开销。 以2阶外排序为例，假设数据分布在N页上，而内存只能容纳B页。首先，读取硬盘上的一页数据到内存，进行排序，然后写回硬盘。重复此过程，使得硬盘上有原始页和已排序页。接着，创建大小为3页的内存空间，将硬盘上已排序的页读入内存，执行merge操作，将两个已排序的块合并成一个更大的有序块。当内存中的排序页填满后，再将其写回硬盘，如此反复，直至所有数据都被排序并合并。 这个过程涉及多次硬盘I/O操作，因为数据必须在内存和硬盘之间来回移动。这种算法的关键在于有效利用有限的内存资源，并通过高效的合并策略减少I/O次数，提高整体排序效率。在实际的数据库系统中，外排序算法的优化和实现是性能优化的重要环节，特别是在大数据处理和云计算环境中。