外部排序
外存和内存之间的数据交换
操作系统是以“块”为单位对磁盘存储空间进行管理，如：每块大小1KB各个磁盘块内存放着各种各样的数据
磁盘的读/写以“块”为单位进行的。
外部排序原理
使用“归并排序”的方法，最少只需要在内存当中分配3块大小的缓冲区就可以完成对任意大小的文件进行排序。
归并排序：把两个已经有序的子序列合并成一个更长的有序的序列
构造初始“归并段”
“归并排序”要求各个子序列有序，每次读入两个块的内容，进行内部排序后写回磁盘
然后在把输入缓冲区的数据放到输出缓冲区中，写回磁盘
如此重复操作
第一趟归并
把8个有序子序列（初始归并段）两两归并
先把归并段1和归并段2中更小的块读入内存
缓冲区1空了就要立即用归并段1的下一块补上
第二趟归并
找最小的两块放进输入缓冲区，1放1，2放2
排序后放回
每当一个输入缓冲区空了，就要立马放进去
第三趟归并
时间开销分析
外部排序时间开销=读写外存的时间+内部排序所需时间+内部归并所需时间
读写磁盘次数=32+32*3=128次
32，文件总块数*2
3，归并趟数
如何优化？
优化：多路归并
2路——>4路
将4个有序归并段归并为更长的有序序列
第一趟归并后就只剩下两个归并段了
采用4路归并，只需要进行两趟归并即可，读写磁盘次数=32+32*2=96次
重要结论：采用多路归并可以减少归并趟数，从而减少磁盘I/O（读写）次数
对r个初始归并段，做k路归并，则归并树可用k叉树表示，若树高为h，则
[归并趟数=h-1=lceil log_kr
ceil
]
[推导：k叉树第h层最多有k^{h-1}个结点则rle k^{h-1},(h-1)_{最小}=lceil log_kr
ceil
]
k越大，r越小，归并趟数越少，读写磁盘次数越少
多路归并带来的负面影响：
- k路归并时，需要开辟k个输入缓冲区，内存开销增加。
- 每挑选一个关键字需要对比关键字(k-1)次，内部归并所需时间增加
优化：减少初始归并段数量
生成初始归并段的“内存工作区”越大，可以生成的初始归并段的长度也会越长
结论：若能增加初始归并段的长度，则可减少初始归并段数量r
知识回顾
按照本节介绍的方法生成的初始归并段，若共N个记录，内存工作区可以容纳L个记录，则初始归并段数量r=N/L
置换-选择排序
败者树
什么是多路平衡归并？
k路平衡归并：
- 最多只能有k个段归并为一个；
- 每一趟归并中，若有m个归并段参加归并，则经过这一趟处理得到（m/k向上取整）个新的归并段。
