# 全文索引与Like

# 1. 应用和原理

全文索引的单位是「词语」,Like的基本单位是字符。比如对于“我爱中国”这句话,如果是全文索引,“我”、“中国”、“爱”都可以匹配到,但是“爱中”就不行。但是对于Like,则都可以。

全文索引的数据结构是一颗Trie树,或者基于此的延伸数据结构,比如DAT。好处就是,搜索复杂度不取决于数据量(非常牛逼的特性),而取决于字典树的深度,而字典树的深度,取决于词语的长度。

# 2. 适用场景

对于Like,适合姓名、昵称、性别等此类的小字段。

对于全文检索,适合中长文本。

# 3. 中文的全文索引

对于中文的全文索引,需要借助「分词算法」,将句子拆分为词语。再根据词语建立字典树。比较成熟的分词库是「jieba分词」:

# 其他解决方案

上面介绍了全文索引和LIKE,确定了LIKE不适合这种场景,依托数据库建立全文索引可行,但是当数据量过大的时候,性能可能是瓶颈。因为场景是数据量大,更新不频繁,下面再介绍两种处理方法。

# 分词+内存hash

将标题文本分词后,对词语进行hash,根据hash值查询对应的文章列表docList。再对所有的分词hash的结果查询到的文章列表,进行交集运算。

在时间复杂度上,这与数据量大小无关,复杂度只与进行交集运算的结果集大小有关。优点是,纯内存操作,非常快,实现简单,容易水平扩展;缺点是,不容易持久化,需要设计相关策略,防止数据丢失。

# 分词+DAT

Trie树的优点是,索引可以及时更新,但是内存占用大。如果对于「更新」不频繁的场景,使用DAT即可,它需要提前建立索引,不能实时更新。

⚠️ 虽然Trie树可以通过hash表方式进行优化,但是对于本例,并不能很方便地持久化。而DAT非常容易进行水平拓展。

# 参考链接