返回主题:倒排索引与查询处理

知识卡片

普通读书笔记卡 · 1227.a

倒排化为外部排序

理解等级:未标注

[[建索引即转置矩阵]]的病灶是访问模式和存储介质不匹配——原始数据按文档顺序写入,倒排索引却要按词序读出,直接转换意味着大量随机磁盘寻道。基于排序的算法先把文本解析成三元组⟨词,文档号,词频⟩顺序写入临时文件,再用外部归并排序按词排序,相同词的记录自然聚在一起,顺序扫一遍就能生成倒排列表。这把随机I/O问题改造成了顺序I/O可解决的经典排序问题,代价是需要两倍最终索引大小的临时磁盘空间。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:第5章《索引构造》「基于排序的方法」小节(源文件:_chapter-text/ch05.txt) - 结论依据:原文说明用<词,文档号,词频>三元组顺序写入临时文件再做外部归并排序,把倒排问题转化为排序问题,直接支持卡片论点。 - 原始内容:"该文件以<t ,d ,f d,t >三元组的格式存储每个术语编号t和文档编号d ,以及出现在文档d 中术语t的次数。然后倒排文件按照术语t的升序排列,即把相同术语的项聚集在一起,这样可以通过扫描已经有序的列表创建每个术语的倒排列表。……图5-3所示算法的第3步为排序,通过外部的归并排序实现。"