知识卡片
跳跃层减少无效比对
当一条有序倒排列表很长、另一条很短时,逐项推进会经过大量不可能命中的 ID。
文中用跳跃层举例:长列表可从 1 跳到 20、50,跨过一段无用区间。跳跃索引可减少某些比较,但收益取决于分布与索引布局;原文把整个交集写成 O(log n) 缺少足够条件,不能当作通用复杂度。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
原书出处
参考来源
- 位置:《架构师之路》第54章《深入浅出搜索架构引擎、方案与细节(上)》(源文件:_epub-src/OEBPS/Text/54.html)
- 结论依据:原文用稀疏列表与长列表的例子说明跳过无效区间;该例只支持减少局部扫描,不足以证明整体交集一律为对数复杂度。
- 原始内容:set1的指针能够由1跳到20再跳到50 , 中间能够跳过很多元素,无需进行一一比对 ,跳表求交集的时间复杂度近似O(log(n)),这是搜索引擎中常见的算法。