倒排索引关键点普及

京东云开发者
• 阅读 69

倒排索引

倒排索引是什么?为什么es、hbase、doris、starrocks都有倒排索引?

倒排索引(英文:Inverted Index),是一种索引方法,常被用于全文检索系统中的一种单词文档映射结构。现代搜索引擎绝大多数的索引都是基于倒排索引来进行构建的,这源于在实际应用当中,用户在使用搜索引擎查找信息时往往只输入信息中的某个属性关键字,如一些用户不记得歌名,会输入歌词来查找歌名;输入某个节目内容片段来查找该节目等等。面对海量的信息数据,为满足用户需求,顺应信息时代快速获取信息的趋势,聪明的开发者们在进行搜索引擎开发时对这些信息数据进行逆向运算,研发了“关键词——文档”形式的一种映射结构,实现了通过了物品属性信息对物品进行映射,可以帮助用户快速定位到目标信息,极大地降低了信息获取难度。倒排索引又叫反向索引,它是一种逆向思维运算,是现代信息检索领域里面最有效的一种索引结构。

倒排索引组成



倒排表:posting list : int有序数组,存储匹配某个item的所有的id,使用roaring bitmaps,frame of reference压缩算法,具体算法可以自行百度,

倒排索引 词项字典term dictionary :

词项索引 term index : 极大的节约内存,使用fst压缩算法,最大可达20倍,,性能不如hashmap,但也很不错



fst构建原理

使用fst算法将词项字段和词项索引存储在内存中,由于压缩倍率大,十亿个词项字典进行fst解析之后,存储在内存中也就1G大小,fst是如何将词项字典和词项索引进行映射的呢? 由于所有英文,或者中文进行解析之后,最终都是有26个英文字母对应,由于fst算法能复用后缀和前缀,因此极大节约了结构树的长度,使得最终存储在内存中,相比普通tree存储节省了内存。下图所示:



倒排索引关键点普及

点赞
收藏
评论区
推荐文章
Stella981 Stella981
2年前
Elasticsearch的filter的caching(缓存)机制详解
编程界的小学生 2017122707:50:54直接举例说明1.假设现在要在倒排索引中去搜索字符串(xxx)比如如下有个倒排索引列表:!Elasticsearch的filter的caching(缓存)机制详解(https://imgconvert.csdnimg.cn/aHR0cDovL3AxLXR0LmJ5dGV
Stella981 Stella981
2年前
Elasticsearch Mapping之字段类型(field datatypes)
ElasticSearch支持如下数据类型:基本类型string(字符串类型)字符串类型包含text与keyword两种类型。1.text文本类型,在索引文件中,存储的不是原字符串,而是使用分词器对内容进行分词处理后得到一系列的词根,然后一一存储在index的倒排索引中。text类型支持如下
Stella981 Stella981
2年前
ES系列八、正排索Doc Values和Field Data
1.DocValues聚合使用一个叫DocValues的数据结构。DocValues使聚合更快、更高效且内存友好。DocValues的存在是因为倒排索引只对某些操作是高效的。倒排索引的优势在于查找包含某个项的文档,而反过来确定哪些项在单个文档里并不高效。结构类似如下:DocTerms
Stella981 Stella981
2年前
Lucene 源码分析之倒排索引(二)
本文以及后面几篇文章将讲解如何定位Lucene中的倒排索引。内容很多,唯有静下心才能跟着思路遨游。我们可以思考一下,哪个步骤与倒排索引有关,很容易想到检索文档一定是要查询倒排列表的,那么就从此处入手。检索文档通过调用IndexSearcher.search(Queryquery,intn)方法返回匹配的文档。publiccla
Stella981 Stella981
2年前
Elasticsearch Mapping parameters(主要参数一览)
Elasticsearch在创建类型映射时可以指定映射参数,下面将一一进行介绍。analyzer指定分词器。elasticsearch是一款支持全文检索的分布式存储系统,对于text类型的字段,首先会使用分词器进行分词,然后将分词后的词根一个一个存储在倒排索引中,后续查询主要是针对词根的搜索。analyzer该参数可以在查询、字段、索引级
Stella981 Stella981
2年前
Elasticsearch Query DSL之Term level queries
简介term\_level查询操作的是存储在反向索引(倒排索引)中的准确词根,这些查询通常用于结构化数据,如数字、日期和枚举,而不是全文字段,无需进行分析(分词),termlevel查询类似于关系型数据库的(where条件过滤)。其查询模式如下:termquery查找包含指定字段中精确匹配查询字符串的文档。
Stella981 Stella981
2年前
Elasticsearch由浅入深(十一)内核原理
倒排索引组成结构以及索引不可变原因对于倒排索引是非常适合用来进行搜索的它的结构:(1)包含这个关键词的documentlist(2)包含这个关键词的所有document的数量:IDF(inversedocumentfrequency)(3)这个关键词在每个document中出现的次数:TF
Stella981 Stella981
2年前
Es学习第七课, term、terms、match等基本查询语法
term、terms查询termquery会去倒排索引中寻找确切的term,它并不知道分词器的存在,这种查询适合keyword、numeric、date等明确值的term:查询某个字段里含有某个关键词的文档GET/customer/doc/_search/{"query":{
Stella981 Stella981
2年前
Flink实时构建倒排索引与全文检索
!(https://oscimg.oschina.net/oscnet/077ed19b13d84bbcbe4b0244c8d0f50f.jpg)对于搜索引擎,大家不会感到陌生,我们每天都在用。我们在百度、谷歌上搜索我们想要的信息。比如,在输入框里输入关键字查询后,会返回很多和关键字相关的内容。或者在电商网站输入想
Stella981 Stella981
2年前
ELK学习笔记之ElasticSearch的索引详解
0x00ElasticSearch的索引和MySQL的索引方式对比Elasticsearch是通过Lucene的倒排索引技术实现比关系型数据库更快的过滤。特别是它对多条件的过滤支持非常好,比如年龄在18和30之间,性别为女性这样的组合查询。倒排索引很多地方都有介绍,但是其比关系型