外部排序：当数据装不进内存
💡
原文中文，约26100字，阅读约需62分钟。
📝
内容提要
外部排序是处理大数据的重要技术，特别是在内存有限的情况下。其核心思想是分而治之和多路归并，主要包括生成初始有序run和多路归并两个阶段。外部存储模型强调I/O复杂度，优化I/O次数至关重要。替换选择法可以生成更长的run，但在现代硬件上，简单的内部排序法更高效。败者树在多路归并中表现优越，能有效减少比较次数。随着SSD的普及，外部排序的设计也在不断演进。
🎯
关键要点
- 外部排序是处理大数据的重要技术，特别是在内存有限的情况下。
- 外部排序的核心思想是分而治之和多路归并，主要包括生成初始有序run和多路归并两个阶段。
- 外部存储模型强调I/O复杂度，优化I/O次数至关重要。
- 替换选择法可以生成更长的run，但在现代硬件上，简单的内部排序法更高效。
- 败者树在多路归并中表现优越，能有效减少比较次数。
- 随着SSD的普及，外部排序的设计也在不断演进。
❓
延伸问答
外部排序的核心思想是什么？
外部排序的核心思想是分而治之和多路归并，主要包括生成初始有序run和多路归并两个阶段。
外部排序如何优化I/O复杂度？
外部存储模型强调I/O复杂度，优化I/O次数至关重要，外部排序的I/O复杂度下界为O((N/B) · log_{M/B}(N/B))。
替换选择法在外部排序中有什么优势？
替换选择法可以生成更长的run，平均长度为2M，能有效减少归并趟数，但在现代硬件上，简单的内部排序法更高效。
败者树在多路归并中有什么优势？
败者树在多路归并中表现优越，能有效减少比较次数，相比最小堆，比较次数减少一半，且分支预测更好。
外部排序在SSD时代有哪些设计变化？
SSD的普及使得外部排序可以使用更大的归并路数，允许少量随机读，并减少写放大问题。
SQLite是如何实现外部排序的？
SQLite在数据量超过阈值时使用外部排序模式，生成初始run并使用多路归并，采用简单的内存B-tree策略。
➡️
