知识卡片
Trie与DAT权衡前缀检索和索引更新
两种索引各有代价:
- Trie 按公共前缀组织节点,适合前缀查找;标题数和长度增长时,节点开销可能明显。
- 双数组 Trie(DAT)以更紧凑的数组保存转移关系,原文认为可降低内存占用,但增量更新较麻烦。
选型需同时看查询形态、构建与更新频率,不能只按“内存更少”选 DAT。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
原书出处
参考来源
- 位置:《架构师之路》第66章《如何快速实现高并发短文检索》(源文件:_epub-src/OEBPS/Text/66.html)
- 结论依据:原文介绍 Trie 以公共前缀减少比较、DAT 为其紧凑变体,并指出 DAT 更新不便及 Trie 内存占用。
- 原始内容:DAT是double array trie的缩写,是trie树的一个变体优化数据结构