Elasticsearch倒排索引(二)深入Term Index

本文涉及的产品
检索分析服务 Elasticsearch 版,2核4GB开发者规格 1个月
简介: Elasticsearch倒排索引(二)深入Term Index

1. 理解Term Index

在《Elasticsearch倒排索引(一)简介》中我们讲到,需要一种高效的数据结构对映射关系中的词语集合也就是Term Dictionary进行索引,这种结构叫作Term Index。那么,Term Index是以怎样的形式进行组织的呢?


最简单的理解,Term Index 就像一本词典的目录一样:

A ……………. xx 页

C ……………. xx 页

E ……………. xx 页

但是实际上Term可以是任意的 byte 数组,而不仅仅是英文字符,因此实际的 Term Index 是一棵 Trie Tree:

如图所示是一棵 Trie Tree。这棵 Trie Tree 不会包含所有的 term,它包含的是 term 的一些前缀。通过 Term Index 可以快速地定位到 Term Dictionary 的某个 offset,然后从这个位置再往后顺序查找。再加上一些压缩技术 e.g. FST,Term Index 需要的存储空间非常小,可能只有所有 term 占用空间的几十分之一,因此 Term Index 被完全缓存在内存中是没有问题的。


3.使用了 Term Index 后,ES的倒排索引整体效果如下:

现在我们可以很清楚地知道为什么ES的检索要比MySQL快得多了。在MySQL中,即使建立了索引,但索引是以B+ Tree的形式存储在磁盘上的,在数据量比较大的情况下,想要检索到一条记录,需要若干次的random access的磁盘操作。而ES在Term Dictionary(相当于MySQL中的索引)的基础上,又添加了Term Index这一结构,并且直接以Trie Tree的形式缓存在内存中。在检索一个term时,只需要从Term Index查找到对应的Term Dictionary的block的位置,再到磁盘上去访问对应的数据,大大减少了对磁盘的random access操作的次数。


2. 减小Term Index存储空间 —— FST

1.在前一小节我们说到,Term Index要被直接缓存在内存中以提升查找速度,那么就必然要采用某种结构来压缩Term Index。Term Index在内存中就是以FST(Finite State Transducers,有限状态转换机)的形式来存储的。


2.说到FST,就不得不提FSM(Finite State Machines,有限状态机):表示有限个状态集合以及这些状态之间转移和动作的数学模型。其中一个状态被标记为开始状态,0个或多个状态被标记为final状态。一个FSM同一时间只处于一个状态。

在图中,椭圆形中代表的是状态,而箭头则代表了转移。图中这个FSM代表了对人的一天之内活动的一个抽象,但是未标注开始状态与结束状态。人在同一时间只能处于一种状态,并且从一个状态转移到下一个状态需要一个输入。如果在这个FSM中,人的初始状态为“睡觉”,然后接收的输入依次为:睡醒了、吃饱了、累了、有新电影上映、困了,那么这个人的状态就会依次变化:睡觉 → 吃饭 → 工作 → 逛街 → 睡觉。

  1. FST是一种类Trie Tree,使用FSM作为数据结构,可以理解为key -> value形式。
  2. FST具有两大优点:
  • 空间占用小:通过对前缀和后缀的重复利用,压缩了存储空间;
  • 查询速度快:时间复杂度为O(len(str));

FST的构造过程如下:

我们假设创建以下一组映射:

Key → Value

“cat” → 5

“deep” → 10

“do” → 15

“dog” → 2

“dogs” → 8


由于在处理大数据的情况下,不太可能把整个FST都同时放在内存中,而是要边建立FST边将建好的部分存储在外部文件中以便节省内存,所以经典FST算法要求key必须按字典序从小到大加入到FST中。所以首先要对所有key按照字典序进行排序(本例已按照字典序排列)。


根据此例的输入,可以建立下图所示的FST:

从上图可以看出,每条边有两个属性,Label(key)和Out(value)。注意Out不一定是数字,也有可能是字符串,但要求必须满足叠加性,比如:

2 + 8 = 10;

a + bc = abc;


建立FST之后,就可以很轻松地根据一个key找到对应的value了。例如:查找dog,我们查找的路径为:0 → 4 → 8 → 9。 其权值和为: 2 + 0 + 0 + 0 = 2。其中最后一个零表示 node[9].finalOut = 0。所以“dog”对应的value为2。

相关实践学习
使用阿里云Elasticsearch体验信息检索加速
通过创建登录阿里云Elasticsearch集群,使用DataWorks将MySQL数据同步至Elasticsearch,体验多条件检索效果,简单展示数据同步和信息检索加速的过程和操作。
ElasticSearch 入门精讲
ElasticSearch是一个开源的、基于Lucene的、分布式、高扩展、高实时的搜索与数据分析引擎。根据DB-Engines的排名显示,Elasticsearch是最受欢迎的企业搜索引擎,其次是Apache Solr(也是基于Lucene)。 ElasticSearch的实现原理主要分为以下几个步骤: 用户将数据提交到Elastic Search 数据库中 通过分词控制器去将对应的语句分词,将其权重和分词结果一并存入数据 当用户搜索数据时候,再根据权重将结果排名、打分 将返回结果呈现给用户 Elasticsearch可以用于搜索各种文档。它提供可扩展的搜索,具有接近实时的搜索,并支持多租户。
目录
相关文章
|
3月前
|
存储 缓存 自然语言处理
【Elasticsearch专栏 05】深入探索:Elasticsearch在处理非结构化数据时,倒排索引有何优势
在处理非结构化数据时,倒排索引的优势在于其高效的查询性能,能够迅速匹配文本中的关键词,实现全文搜索。此外,倒排索引支持复杂的查询操作,可扩展性强,且通过压缩技术优化存储空间。这些特点使倒排索引成为处理非结构化数据的理想选择。
|
3月前
|
存储 自然语言处理 搜索推荐
【Elasticsearch专栏 01】深入探索:Elasticsearch的正向索引和倒排索引是什么?
正向索引根据文档ID直接查找文档内容,适用于精确匹配场景;而倒排索引则基于文档内容构建,通过关键词快速定位相关文档,适用于全文搜索,显著提高查询效率,是搜索引擎的核心技术。
|
8天前
|
索引
Elasticsearch exception [type=illegal_argument_exception, reason=index [.1] is the write index for data stream [slowlog] and cannot be deleted]
在 Elasticsearch 中,你尝试删除的索引是一个数据流(data stream)的一部分,而且是数据流的写入索引(write index),因此无法直接删除它。为了解决这个问题,你可以按照以下步骤进行操作:
|
2月前
|
自然语言处理
elasticsearch中term与match区别
elasticsearch中term与match区别
40 0
|
6月前
|
自然语言处理 搜索推荐 索引
分布式系列教程(31) -ElasticSearch倒排索引
分布式系列教程(31) -ElasticSearch倒排索引
59 0
|
3月前
|
缓存 算法 索引
【Elasticsearch专栏 07】深入探索:Elasticsearch的倒排索引如何进行模糊查询和通配符查询
Elasticsearch的倒排索引支持模糊查询和通配符查询,通过特定的算法和数据结构,能够实现对关键词的模糊匹配和通配符匹配。这两种查询类型提供了更灵活的搜索功能,但可能影响查询性能,需结合优化策略使用。
|
3月前
|
存储 自然语言处理 搜索推荐
【Elasticsearch专栏 06】深入探索:Elasticsearch如何处理倒排索引中的分词问题
Elasticsearch通过内置和可定制的分词器及过滤器处理倒排索引中的分词问题,确保文本被拆分成合适的词条并优化存储,为全文搜索等提供高效支持。用户可通过分析API测试和调整分词效果。
|
3月前
|
存储 缓存 自然语言处理
【Elasticsearch专栏 04】深入探索:Elasticsearch倒排索引中的词条是如何存储和管理
倒排索引中,词条以有序方式存储在词典中,关联倒排列表,记录文档ID和位置信息。词条的添加涉及分词、添加到词典和更新倒排列表。删除涉及从词典和倒排列表中移除词条。查询时,快速定位词条,获取倒排列表以定位相关文档。整个过程涉及高效的数据结构和优化策略。
|
3月前
|
存储 自然语言处理 负载均衡
【Elasticsearch专栏 03】深入探索:Elasticsearch倒排索引是如何提高搜索效率的
倒排索引通过直接关联文档内容,将关键词映射到相关文档,减少扫描范围,并使用高效数据结构快速查找和匹配关键词,从而显著提高搜索效率。此外,它支持复杂查询操作和搜索结果优化,进一步提高搜索的准确性和用户满意度。
|
3月前
|
存储 自然语言处理 搜索推荐
【Elasticsearch专栏 02】深入探索:Elasticsearch为什么使用倒排索引而不是正排索引
倒排索引在搜索引擎中更受欢迎,因为它直接关联文档内容,支持全文搜索和模糊搜索,提高查询效率。其紧凑的结构减少了存储空间,并方便支持多种查询操作。相比之下,正排索引在搜索效率、存储和灵活性方面存在局限。

热门文章

最新文章