知识卡片
用外部归并排序绕开随机访问，把倒排问题转化为排序问题
内容
[[朴素转置矩阵法为何不可行]]的病灶是访问模式和存储介质不匹配——原始数据按文档顺序写入，倒排索引却要按词序读出，直接转换意味着大量随机磁盘寻道。基于排序的算法先把文本解析成三元组⟨词,文档号,词频⟩顺序写入临时文件，再用外部归并排序按词排序，相同词的记录自然聚在一起，顺序扫一遍就能生成倒排列表。这把随机I/O问题改造成了顺序I/O可解决的经典排序问题，代价是需要两倍最终索引大小的临时磁盘空间。
参考来源
- 位置：第5章《索引构造》「基于排序的方法」小节（源文件：_chapter-text/ch05.txt）
- 结论依据：原文说明用<词,文档号,词频>三元组顺序写入临时文件再做外部归并排序，把倒排问题转化为排序问题，直接支持卡片论点。
- 原始内容："图5-3所示算法的第3步为排序，通过外部的归并排序实现……＞三元组的格式存储每个术语编号t和文档编号……排序完成后……只需再顺序扫一遍就能生成倒排列表。"