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

知识卡片

普通读书笔记卡 · 2338.f.1.a

双指针求有序列表交集

理解等级:未标注

倒排列表按文档 ID 排序后,可用两个指针求交集:相等时记录该 ID 并前进;不等时前进较小值所在列表的指针。每轮至少推进一个指针,扫描成本随两表长度之和增长,避免双重循环逐项配对。多词查询可逐次求交集,但耗时仍取决于倒排列表长度和命中分布。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:《架构师之路》第54章《深入浅出搜索架构引擎、方案与细节(上)》(源文件:_epub-src/OEBPS/Text/54.html) - 结论依据:原文把有序倒排列表交集称为拉链法,描述双指针遇相等取结果、否则移动较小值,且每个元素最多比较一次。 - 原始内容:两个指针指向首元素,比较元素的大小: (1)如果相同,放入结果集,随意移动一个指针 (2)否则,移动值较小的一个指针,直到队尾 这种方法的好处是: