一尘不染

Elastic search还是Trie搜索/自动完成?

elasticsearch

我的理解是,自动完成/搜索文本/项目在任何可扩展产品(例如Amazon eCommerce / Google)中都可以在高水平上进行的工作是:-

基于elasticsearch(ES)的方法

  1. 文档存储在DB中。一旦持久化给elasticsearch,它就会创建索引并将索引/文档(基于令牌生成器)存储在基于内存或磁盘的配置中。

  2. 用户键入3个字符后,它将搜索ES下的所有索引(可以配置为甚至对ngram进行索引),根据权重对它们进行排名并返回给用户

但是在阅读了谷歌的一些资源后,例如基于特里的搜索

看起来有些可伸缩产品还使用Trie数据结构来进行基于前缀的搜索。

我的问题是,基于特里的方法是否可以很好地替代ES或ES在内部使用,Trie还是我在这里完全错过了?


阅读 482

收藏
2020-06-22

共1个答案

一尘不染

ES自动补全可以通过两种方式实现:

  1. 使用prefix查询
  2. 要么使用(edge-)ngrams
  3. 或使用完成提示

第一种选择是穷人的修养功能。我提到它是因为它在某些情况下很有用,但是如果您有大量文档,则应避免使用它。

第二个选项使用常规的ES索引功能,即它将标记文本,所有(edge-)ngram都将被索引,然后您可以搜索已被索引的任何前缀/中缀/后缀。

第三个选项使用不同的方法,并针对速度进行了优化。基本上,在索引类型的字段时completion,ES将创建一个“有限状态转换器”并将其存储在内存中以实现超快速访问。

就实现而言,有限状态传感器接近特里。您可以查看这篇出色的文章,该文章显示了特里有限状态传感器的比较

更新(2019年6月25日):

ES
7.2引入了一种称为的新数据类型search_as_you_type,该数据类型本身就允许这种行为。有关更多信息,访问:https :
//www.elastic.co/guide/en/elasticsearch/reference/7.2/search-as-you-
type.html

2020-06-22