倒排索引查询原理_千丈之松的博客-CSDN博客_倒排索引查询
倒排索引查询原理
千丈之松
于 2018-08-03 13:58:02 发布
23917
收藏
35
分类专栏：
数据结构-算法
solr+lucene
搜索系统
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/hu948162999/article/details/81386384
版权
数据结构-算法
同时被 3 个专栏收录
11 篇文章
0 订阅
订阅专栏
solr+lucene
43 篇文章
2 订阅
订阅专栏
搜索系统
10 篇文章
0 订阅
订阅专栏
Lucene 查询过程
在lucene中查询是基于segment。每个segment可以看做是一个独立的subindex，在建立索引的过程中，lucene会不断的flush内存中的数据持久化形成新的segment。多个segment也会不断的被merge成一个大的segment，在老的segment还有查询在读取的时候，不会被删除，没有被读取且被merge的segement会被删除。这个过程类似于LSM数据库的merge过程。下面我们主要看在一个segment内部如何实现高效的查询。
为了方便大家理解，我们以人名字，年龄，学号为例，如何实现查某个名字（有重名）的列表。
docidnameageid1Alice181012Alice201023Alice211034Alan211045Alan18105
在lucene中为了查询name=XXX的这样一个条件，会建立基于name的倒排链。以上面的数据为例，倒排链如下： 姓名
Alice | [1,2,3] ---- | --- |  Alan | [4,5] 如果我们还希望按照年龄查询，例如想查年龄=18的列表，我们还可以建立另一个倒排链：
18 | [1,5] ---| --- |  20 | [2] 21 | [3,4]
在这里，Alice，Alan，18，这些都是term。所以倒排本质上就是基于term的反向列表，方便进行属性查找。到这里我们有个很自然的问题，如果term非常多，如何快速拿到这个倒排链呢？在lucene里面就引入了term dictonary的概念，也就是term的字典。term字典里我们可以按照term进行排序，那么用一个二分查找就可以定为这个term所在的地址。这样的复杂度是logN，在term很多，内存放不下的时候，效率还是需要进一步提升。可以用一个hashmap，当有一个term进入，hash继续查找倒排链。这里hashmap的方式可以看做是term dictionary的一个index。 从lucene4开始，为了方便实现rangequery或者前缀，后缀等复杂的查询语句，lucene使用FST数据结构来存储term字典，下面就详细介绍下FST的存储结构。
FST
我们就用Alice和Alan这两个单词为例，来看下FST的构造过程。首先对所有的单词做一下排序为“Alice”，“Alan”。
插入“Alan” 插入“Alice”
这样你就得到了一个有向无环图，有这样一个数据结构，就可以很快查找某个人名是否存在。FST在单term查询上可能相比hashmap并没有明显优势，甚至会慢一些。但是在范围，前缀搜索以及压缩率上都有明显的优势。
在通过FST定位到倒排链后，有一件事情需要做，就是倒排链的合并。因为查询条件可能不止一个，例如上面我们想找name="alan" and age="18"的列表。lucene是如何实现倒排链的合并呢。这里就需要看一下倒排链存储的数据结构
SkipList
为了能够快速查找docid，lucene采用了SkipList这一数据结构。SkipList有以下几个特征：
元素排序的，对应到我们的倒排链，lucene是按照docid进行排序，从小到大。跳跃有一个固定的间隔，这个是需要建立SkipList的时候指定好，例如下图以间隔是3SkipList的层次，这个是指整个SkipList有几层
有了这个SkipList以后比如我们要查找docid=12，原来可能需要一个个扫原始链表，1，2，3，5，7，8，10，12。有了SkipList以后先访问第一层看到是然后大于12，进入第0层走到3，8，发现15大于12，然后进入原链表的8继续向下经过10和12。 有了FST和SkipList的介绍以后，我们大体上可以画一个下面的图来说明lucene是如何实现整个倒排结构的：
有了这张图，我们可以理解为什么基于lucene可以快速进行倒排链的查找和docid查找，下面就来看一下有了这些后如何进行倒排链合并返回最后的结果。
倒排合并
假如我们的查询条件是name = “Alice”，那么按照之前的介绍，首先在term字典中定位是否存在这个term，如果存在的话进入这个term的倒排链，并根据参数设定返回分页返回结果即可。这类查询，在数据库中使用二级索引也是可以满足，那lucene的优势在哪呢。假如我们有多个条件，例如我们需要按名字或者年龄单独查询，也需要进行组合 name = "Alice" and age = "18"的查询，那么使用传统二级索引方案，你可能需要建立两张索引表，然后分别查询结果后进行合并，这样如果age = 18的结果过多的话，查询合并会很耗时。那么在lucene这两个倒排链是怎么合并呢。 假如我们有下面三个倒排链需要进行合并。
在lucene中会采用下列顺序进行合并：
在termA开始遍历，得到第一个元素docId=1Set currentDocId=1 在termB中 search(currentDocId) = 1 (返回大于等于currentDocId的一个doc),
因为currentDocId ==1，继续如果currentDocId 和返回的不相等，执行2，然后继续到termC后依然符合，返回结果currentDocId = termC的nextItem然后继续步骤3 依次循环。直到某个倒排链到末尾。
整个合并步骤我可以发现，如果某个链很短，会大幅减少比对次数，并且由于SkipList结构的存在，在某个倒排中定位某个docid的速度会比较快不需要一个个遍历。可以很快的返回最终的结果。从倒排的定位，查询，合并整个流程组成了lucene的查询过程，和传统数据库的索引相比，lucene合并过程中的优化减少了读取数据的IO，倒排合并的灵活性也解决了传统索引较难支持多条件查询的问题。
BKDTree
在lucene中如果想做范围查找，根据上面的FST模型可以看出来，需要遍历FST找到包含这个range的一个点然后进入对应的倒排链，然后进行求并集操作。但是如果是数值类型，比如是浮点数，那么潜在的term可能会非常多，这样查询起来效率会很低。所以为了支持高效的数值类或者多维度查询，lucene引入类BKDTree。BKDTree是基于KDTree，对数据进行按照维度划分建立一棵二叉树确保树两边节点数目平衡。在一维的场景下，KDTree就会退化成一个二叉搜索树，在二叉搜索树中如果我们想查找一个区间，logN的复杂度就会访问到叶子结点得到对应的倒排链。如下图所示：
如果是多维，kdtree的建立流程会发生一些变化。 比如我们以二维为例，建立过程如下：
确定切分维度，这里维度的选取顺序是数据在这个维度方法最大的维度优先。一个直接的理解就是，数据分散越开的维度，我们优先切分。切分点的选这个维度最中间的点。递归进行步骤1，2，我们可以设置一个阈值，点的数目少于多少后就不再切分，直到所有的点都切分好停止。
下图是一个建立例子：
BKDTree是KDTree的变种，因为可以看出来，KDTree如果有新的节点加入，或者节点修改起来，消耗还是比较大。类似于LSM的merge思路，BKD也是多个KDTREE，然后持续merge最终合并成一个。不过我们可以看到如果你某个term类型使用了BKDTree的索引类型，那么在和普通倒排链merge的时候就没那么高效了所以这里要做一个平衡，一种思路是把另一类term也作为一个维度加入BKDTree索引中。
如何实现返回结果进行排序聚合
通过之前介绍可以看出lucene通过倒排的存储模型实现term的搜索，那对于有时候我们需要拿到另一个属性的值进行聚合，或者希望返回结果按照另一个属性进行排序。在lucene4之前需要把结果全部拿到再读取原文进行排序，这样效率较低，还比较占用内存，为了加速lucene实现了fieldcache，把读过的field放进内存中。这样可以减少重复的IO，但是也会带来新的问题，就是占用较多内存。新版本的lucene中引入了DocValues，DocValues是一个基于docid的列式存储。当我们拿到一系列的docid后，进行排序就可以使用这个列式存储，结合一个堆排序进行。当然额外的列式存储会占用额外的空间，lucene在建索引的时候可以自行选择是否需要DocValue存储和哪些字段需要存储。
千丈之松
关注
关注
11
点赞
35
收藏
打赏
评论
倒排索引查询原理
Lucene 查询过程在lucene中查询是基于segment。每个segment可以看做是一个独立的subindex，在建立索引的过程中，lucene会不断的flush内存中的数据持久化形成新的segment。多个segment也会不断的被merge成一个大的segment，在老的segment还有查询在读取的时候，不会被删除，没有被读取且被merge的segement会被删除。这个过程类似...
复制链接
扫一扫
专栏目录
正排索引和倒排索引
岁月静好
09-23
3万+
正排索引（正向索引）
正排表是以文档的ID为关键字，表中记录文档中每个字的位置信息，查找时扫描表中每个文档中字的信息直到找出所有包含查询关键字的文档。
正排表结构如图1所示，这种组织方法在建立索引的时候结构比较简单，建立比较方便且易于维护;因为索引是基于文档建立的，若是有新的文档加入，直接为该文档建立一个新的索引块，挂接在原来索引文件的后面。若是有文档删除，则直接找到该文档号文档对应的索引信息
信息检索——简单易懂的倒排索引（原理+例子）
热门推荐
土豆同学的博客
03-14
2万+
倒排索引
0 引言
今天介绍一下倒排索引，倒排索引又叫反向索引(inverted index)，既然有反向索引那就有正向索引(forward index)了。一些相关概念可以看前文信息检索(Information Retrieval)相关概念
1 正向索引和反向索引
先介绍一下正向索引: 当用户发起查询时（假设查询为一个关键词），搜索引擎会扫描索引库中的所有文档，找出所有包含关键词的文档，这样依次从文档中去查找是否含有关键词的方法叫做正向索引。互联网上存在的
评论 2
您还未登录，请先
登录
后发表或查看评论
C++倒排索引
02-28
读入文本集，建立倒排索引，内含有的TXT文本可以替换，源代码可以直接运行
Faiss索引
最新发布
weixin_61785507的博客
09-29
614
1、faiss有两种索引构建模式，一种是全量构建，二是增量的索引构建，也就是在原来的基础上添加向量。第一次构建索引时需要经过Train和Add两个操作，后续添加新embedding就直接执行Add就是增量构建了。2、Faiss提供了三种索引类型精确索引-IndexFlatL2、indexFlatIP、倒排快速索引-IndexIVFFlat、乘积量化索引-IndexIVFPQ， 精确索引是一种暴力无误差模式，检索库数据量不大时，优先追求精度时可以用这个。检索库数据量较大时，推荐使用乘积量化索引。
Elasticsearch倒排索引
不如打代码
10-28
845
Elasticsearch倒排索引
倒排索引的概念是相对于MySQL这样的正向索引而言的。
1.正向索引
那么什么是正向索引呢？例如给商品表（tb_goods）中的id创建索引：
如果是根据字段id查询，那么直接走索引，查询速度非常快。
但如果是基于title做模糊查询，只能是逐行扫描数据，流程如下：
1）用户搜索数据，条件是title符合"%手机%"
2）逐行获取数据，比如id为1的数据
3）判断数据中的title是否符合用户搜索条件
4）如果符合则放入结果集，不符合则丢弃。回到步骤1
逐行扫描，也就是
倒排索引(一)
哆啦咪~fo
07-08
5614
毕业以后在网页搜索组，所以抽空就看看了《这就是搜索引擎--核心技术详解》，书比较白话文，对于我这样的入门小白再合适不过了，还有一本《信息检索导论》比较系统和专业化，感兴趣的可以买来看看。海量的网页数据，如何快速的找到包含用户查询的所有网页至关重要，如同我们拿到一本很厚的书时，如果没有目录，我们可能要花费很长的时间找自己需要的内容，但是有了目录，我们就能快速定位，这里的目录就相当于索引的功能。常见的...
倒排索引总结
许诗宇的博客
06-22
590
目录
倒排索引简介
Elasticsearch 建立倒排索引
参考了 https://www.cnblogs.com/cjsblog/p/10327673.html
倒排索引简介
倒排索引（Inverted Index）也叫反向索引，有反向索引必有正向索引。通俗地来讲，正向索引是通过key找value，反向索引则是通过value找key。
先来回忆一下我们是怎么插入一条索引记录的：
curl -X PUT "localhost:9200/user/_doc/1" -H 'Content-..
检索与倒排索引
whaty6的博客
02-22
684
一、检索
Information Retrieval (IR)：从大规模非结构化数据 的集合中找到满足用户信息需求的资料。包括信息的获取、表示、存储、组织和访问。
倒排索引
ES查询原理：倒排索引
zh_nanfang的博客
07-12
1290
前端数据搜索：针对各种查询条件，需要快速、准确的响应数据结果。但是底层数据表很大，如果按照正常逻辑直接去表查询，这样查询效率很慢，而且是关联多表进行查询。针对这样的情况，项目中引入了ES,那为什么ES查询效率就这么快呢，下面就剖析一下ES查询原理ES倒排索引1、每个文档对应一个docId，文档内容会被切割成多个关键词，每个关键词都会记录在文档中的次数与位置，可以参考下图
2、有了倒排索引，这样的话，就会很快的相应数据请求，比如前端要搜索 XXX，根据倒排索引可以很快的定位到某个文档，然后直接去文档get
什么是倒排索引?
u013008898的博客
05-07
2222
为什么需要倒排索引
倒排索引，也是索引。
索引，初衷都是为了快速检索到你要的数据。
每种数据库都有自己要解决的问题（或者说擅长的领域），对应的就有自己的数据结构，而不同的使用场景和数据结构，需要用不同的索引，才能起到最大化加快查询的目的。
对 Mysql 来说，是 B+ 树，对 Elasticsearch/Lucene 来说，是倒排索引。
Elasticsearch 是建立在全文搜索引擎库 Lucene 基础上的搜索引擎，它隐藏了 Lucene 的复杂性，取而代之的提供一套简单一致的 RESTf
ElasticSearch倒排索引详解
qq_39144436的博客
04-30
6003
概述
Lucene 作为 Apache 开源的一款搜索工具，一直以来是实现搜索功能的神兵利器，现今火热的 Solr 和 Elasticsearch 均基于该工具包进行开发，而 Lucene 之所以能在搜索中发挥至关重要的作用正是因为倒排索引。因此，本文将介绍一下倒排索引的概念以及倒排索引在 Lucene 中的实现。
基本原理
什么是倒排索引
搜索的核心需求是全文检索，全文检索简单来说就是要在大量文档中找到包含某个单词出现的位置，在传统关系型数据库中，数据检索只能通过 like 来实现。
例如需要在
算法篇--倒排索引
小强签名设计 的博客
08-01
2312
文章目录一、前言二、单词——文档矩阵
一、前言
  见其名知其意，有倒排索引，对应肯定，有正向索引。正向索引（forward index），反向索引（inverted index）更熟悉的名字是倒排索引。
  在搜索引擎中每个文件都对应一个文件ID，文件内容被表示为一系列关键词的集合（实际上在搜索引擎索引库中，关键词也已经转换为关键词ID）。例如“文档1”经过分词，提取了20个关键词，每个关键词都会记录它在文档中的出现次数和出现位置。
  得到正向索引的结构如下：一般是通过key，去找value。
“文档1
Elasticsearch 倒排索引
做Java整整10年，目前是教别人写代码，嘿嘿
12-23
3707
本篇文章主要是介绍Elasticsearch的自动补全功能，以及提供一个小案例给大家。
倒排索引原理和实现
weixin_34367257的博客
02-21
1321
关于倒排索引
搜索引擎通常检索的场景是：给定几个关键词，找出包含关键词的文档。怎么快速找到包含某个关键词的文档就成为搜索的关键。这里我们借助单词——文档矩阵模型，通过这个模型我们可以很方便知道某篇文档包含哪些关键词，某个关键词被哪些文档所包含。单词-文档矩阵的具体数据结构可以是倒排索引、签名文件、后缀树等。
倒排索引源于实际应用中需要根据属性的值来查找记录，lucene是基于倒排索引实现的。这...
倒排索引
weixin_30443075的博客
08-30
60
倒排索引（英语：Inverted index），也常被称为反向索引、置入档案或反向档案，是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。
有两种不同的反向索引形式：
一条记录的水平反向索引（或者反向档案索引）包含每个引用单词的文档的列表。
一个单词的水平反向索引（或者完全反向索引）又包含每个单词在一...
倒排索引原理，即为什么叫倒排索引
Trisyp的博客
08-19
7223
倒排索引的英文原名是Inverted index，大概因为Invert有颠倒的意思，所以就被翻译成了倒排，然后我们就会在字面上出现误解：很容易让人理解为从A-Z颠倒成Z-A。其实并不是字面上的意思。
倒排索引源于实际应用中需要根据属性的值来查找记录，也就是说，不是由记录来确定属性值，而是由属性值来确定记录，因而称为倒排索引，
建立全文索引中有两项非常重要，一个是如何对文本进行分词，一是建立索引的数据结构。分词的方法基本上是二元分词法、最大匹配法和统计方法。索引的数据结构基本上采用倒排索引的结构，luce
全文检索和倒排索引原理讲解
Apple_Boy的博客
11-09
3200
正排索引
正排表是以文档的ID为关键字，表中记录文档中每个字的位置信息，查找时扫描表中每个文档中字的信息直到找出所有包含查询关键字的文档。
正排表结构如图1所示，这种组织方法在建立索引的时候结构比较简单，建立比较方便且易于维护;因为索引是基于文档建立的，若是有新的文档加入，直接为该文档建立一个新的索引块，挂接在原来索引文件的后面。若是有文档删除，则直接找到该文档号文档对应的索引信息，将其直接删除。...
分布式搜索引擎ElasticSearch-1
DOVISSSS的博客
09-09
1011
分布式搜索引擎ElasticSearch基础1
lucene底层数据结构——FST，针对field使用列存储，delta encode压缩doc ids数组，LZ4压缩算法...
djph26741的博客
12-27
663
参考：
http://www.slideshare.net/lucenerevolution/what-is-inaluceneagrandfinal
http://www.slideshare.net/jpountz/how-does-lucene-store-your-data
http://www.infoq.com/cn/articles/database-timestam...
关于elasticsearch索引,倒排索引简介
justlpf的专栏
02-24
1013
参考文章：终于有人把elasticsearch原理讲通了！
小史是一个非科班的程序员，虽然学的是电子专业，但是通过自己的努力成功通过了面试，现在要开始迎接新生活了。
随着央视诗词大会的热播，小史开始对诗词感兴趣，最喜欢的就是飞花令的环节。
但是由于小史很久没有背过诗词了，飞一个字很难说出一句，很多之前很熟悉的诗句也想不起来。
【倒排索引】
吕老师：但是我让你说出带“前”字的诗句，由于没有索引，你只能遍历脑海...
“相关推荐”对你有帮助么？
非常没帮助
没帮助
一般
有帮助
非常有帮助
提交
©️2022 CSDN
皮肤主题：创作都市
设计师：CSDN官方博客
返回首页
千丈之松
CSDN认证博客专家
CSDN认证企业博客
码龄10年
网易
81
原创
3万+
周排名
116万+
总排名
56万+
访问
等级
4827
积分
193
粉丝
170
获赞
76
评论
365
收藏
私信
关注
热门文章
决策树算法原理及案例
72847
kibana查询语法
51648
解决solr搜索多词匹配度和排序方案
32112
倒排索引查询原理
23915
使用elasticsearch遇到的一些问题以及解决方法
17369
分类专栏
ElasticSearch
16篇
数据结构-算法
11篇
搜索系统
10篇
机器学习
6篇
分布式
20篇
solr+lucene
43篇
推荐系统
5篇
java相关
24篇
Jvm和多线程
7篇
爬虫
7篇
最新评论
lucene倒排索引表搜索原理
gyqhlbt:
图片坏掉了
这篇文章挺好
lucene的两种分页操作
bigfayfay:
先查前N页; 和先查前N-1页, 再查最后1页, 有差别吗?
倒排索引查询原理
菜鸟往前飞:
图片打开不了，看不了图片
美团搜索排序设计方案
田小成plus:
楼主能辛苦更新下图片吗
Redis特性和性能调优
我来烤烤你:
性能调优在哪？
您愿意向朋友推荐“博客详情页”吗？
强烈不推荐
不推荐
一般般
推荐
强烈推荐
提交
最新文章
dubbo相关
搜索引擎是如何设计倒排索引的？
归一化 （Normalization）、标准化 （Standardization）和中心化/零均值化 （Zero-centered）
2021年1篇
2020年3篇
2019年2篇
2018年18篇
2017年15篇
2016年17篇
2015年42篇
2014年32篇
目录
目录
分类专栏
ElasticSearch
16篇
数据结构-算法
11篇
搜索系统
10篇
机器学习
6篇
分布式
20篇
solr+lucene
43篇
推荐系统
5篇
java相关
24篇
Jvm和多线程
7篇
爬虫
7篇
目录
评论 2
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
查看更多评论
打赏作者
千丈之松
你的鼓励将是我创作的最大动力
¥2
¥4
¥6
¥10
¥20
输入1-500的整数
余额支付
(余额：-- )
扫码支付
扫码支付：¥2
获取中
扫码支付
您的余额不足，请更换扫码支付或充值
打赏作者
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额
抵扣说明：
1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。 2.余额无法直接购买下载，可以购买VIP、C币套餐、付费专栏及课程。
余额充值