知识卡片
前缀节点预存热门候选
在每个前缀节点保存少量最高频候选,查询定位后即可返回,避免反复遍历和排序后代。代价是更大空间与更新传播;所谓常数查询成本依赖前缀长度及返回条数都有固定上限的假设。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 搜索自动补全 · 查看原书依据
Cache top search queries at each node To avoid traversing the whole trie, we store top k most frequently used queries at each node. Since 5 to 10 autocomplete suggestions are enough for users, k is a relatively small number. In our specific case, only the top 5 search queries are cached. By caching top search queries at every node, we significantly reduce the time
参考来源
- 位置:《System Design Interview – An insiders guide, Second Edition》第13章《搜索自动补全》(来源项目 book-sources;源文件:extracted/System Design Interview – An insiders guide, Second Edition/_epub-src/text/part0031_split_003.html)
- 结论依据:原文在该位置给出所述对象、机制或比较,支持本卡的解释;原书未展开的实现不作为已证明结论,算式与一致性边界在正文明确限定。
- 原始内容:Cache top search queries at each node To avoid traversing the whole trie, we store top k most frequently used queries at each node. Since 5 to 10 autocomplete suggestions are enough for users, k is a relatively small number. In our specific case, only the top 5 search queries are cached. By caching top search queries at every node, we significantly reduce the time