8.7.1 外部排序的基本概念
原书定位
印刷页P387起,对应PDF第399页。下文为目视整理的知识提要;完整内容见原书对照。
将部分数据读入内存排序,写回外存形成归并段;随后一边读取各有序段、一边归并输出,最终得到完整有序文件。内存不必同时装下所有输入段和结果。
总代价包括内部排序、内存归并与外存 I/O。外存通常按块读写,应把记录数、块数与每块记录容量分别计算。
对应练习
关联知识
原书对照
展开原书对照截图

原书定位
印刷页P387起,对应PDF第399页。下文为目视整理的知识提要;完整内容见原书对照。
将部分数据读入内存排序,写回外存形成归并段;随后一边读取各有序段、一边归并输出,最终得到完整有序文件。内存不必同时装下所有输入段和结果。
总代价包括内部排序、内存归并与外存 I/O。外存通常按块读写,应把记录数、块数与每块记录容量分别计算。
