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

知识卡片

普通读书笔记卡 · 3960

Trie与DAT权衡前缀检索和索引更新

理解等级:中级

两种索引各有代价:

  • Trie 按公共前缀组织节点,适合前缀查找;标题数和长度增长时,节点开销可能明显。
  • 双数组 Trie(DAT)以更紧凑的数组保存转移关系,原文认为可降低内存占用,但增量更新较麻烦。

选型需同时看查询形态、构建与更新频率,不能只按“内存更少”选 DAT。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:《架构师之路》第66章《如何快速实现高并发短文检索》(源文件:_epub-src/OEBPS/Text/66.html) - 结论依据:原文介绍 Trie 以公共前缀减少比较、DAT 为其紧凑变体,并指出 DAT 更新不便及 Trie 内存占用。 - 原始内容:DAT是double array trie的缩写,是trie树的一个变体优化数据结构