Lucene索引存储结构

Z时代
2024-01-10
分类：综合

字典数据结构：字典树（Trie tree）、FST
- 字典树（Trie tree）
  - 典型应用是用于统计和排序大量的字符串（但不仅限于字符串），
    - 所以经常被搜索引擎系统用于文本词频统计。
  - 它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
  - 基本的实现有array与linked-list两种：
    - array实现：
    - linked-list实现：
  - 双数组Trie树
    - 在Trie数实现过程中，我们发现了每个节点均需要一个数组来存储next节点，非常占用存储空间，空间复杂度大，
      - 双数组Trie树正是解决这个问题的。
      - 双数组Trie树(DoubleArrayTrie)是一种空间复杂度低的Trie树，
        应用于字符区间大的语言（如中文、日文等）分词领域。
    - 双数组的原理是，将原来需要多个数组才能表示的Trie树，使用两个数组就可以存储下来，可以极大的减小空间复杂度
    - 使用两个数组base和check来维护Trie树，
      - base负责记录状态，
      - check负责检查各个字符串是否是从同一个状态转移而来，
      - 当check[i]为负值时，表示此状态为字符串的结束。
        check[i] 代表从什么状态转换过来，如下，都是从base[t] 转换过来，所以 check[ta] = check[tb]
        base[t] + a.code = base[ta]
        base[t] + b.code = base[tb]
        check[ta] = check[tb]
- FST
  - lucene从4开始大量使用的数据结构是FST（Finite State Transducer）。
  - FST有两个优点：
    - 1）空间占用小。
      - 通过对词典中单词前缀和后缀的重复利用，压缩了存储空间；
    - 2）查询速度快。
  - http://www.shenyanchao.cn/blog/2018/12/04/lucene-fst/
    - FST，不但能共享前缀还能共享后缀。
    - 不但能判断查找的key是否存在，还能给出响应的输入output。
    - 它在时间复杂度和空间复杂度上都做了最大程度的优化，
      - 使得Lucene能够将Term Dictionary完全加载到内存，快速的定位Term找到响应的output（posting倒排列表）。