elasticsearch倒排索引原理简介(下)

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

image.png

假设int数组中有1,2,3,4....直到100万个数字,大约占4MB的空间。

每个数字都存储它和前一个数字的差值,差值都是1,一个数字1的话可以用一个bit存储,因为一个bit的存储范围是0-1,本来用32个bit存储一个数字,现在用1个bit来存储。100万个数字只用100万个bit,原本是3200万个bit,压缩倍率是32倍。

如果数据量是32T,压缩之后就变成1T了,从1T中检索的效率是从32T中检索效率的32倍。

这是一个极端特殊的情况,因为实际中id不会重复且不会连续,如果不是连续的,那么差值就不是1。

倒排表里面存储的是id,这里面数字不是连续的,但一定是有序的,从小到大的,在索引创建的时候排好的序。

image.png

6个数字,一个数字占4个字节,也就是会占用24个字节。

计算差值,得到的差值列表是

image.png

1个bit取值范围是0-1;2个bit是0-3,能存储4个数字;3个bit,就是2的3次方为8,取值范围是0-7。


image.png

8个bit能存储256个数字。

自定义类型来存储数字。

看差值列表中最大的数字是227,用7个bit是否可以存储,7个bit能存储的数值最大是127,显然存储不下227,只能用8个bit来存储,因为8个bit最大能存储255。

当前这个数组中的每个数字只用8个bit来存储就可以了即6个数字,48个bit,6个字节。

原本这6个数字需要24个字节,现在只需要6个字节,压缩为原本的1/4。

继续优化...

227用8个bit存储,但是2用2个bit存储就可以了,因为2个bit存储范围是0-3。

image.png

把这个数值切开,前面的大数用8个bit来存储,后面的小数用4个bit来存储。先别管从哪里切,就看哪边的数字间隔比较大,比如前面的数字由227一下子到了2,后面的数字都比较小,前面的数字用8个bit存储,后面的数字取决于它的最大值。

image.png

后面的数最大是30,5个bit(取值范围是0-31)可以存储的下,也就是后面的数组每个数字用5个bit就可以存储。

截止目前将一个大的数组拆分成了2个小的数组,前面的数组每个数字用8个bit来存储,后面的数组每个数字用5个bit来存储。

jdk中定义了用32个bit来存储一个int类型的数据,用64个bit来存储一个long类型的数据。

自定义定义一个用5个bit来存储的类型叫α,定义一个用8个bit来存储的类型叫β,类型的定义也要占用一个字节的空间。如果对每个数字都定义一个类型,那么定义的类型就太多了,就会占用很多的空间。假如说73和227都用8个bit的α来存储,本身α这个类型就占用一个字节。

接下来计算下这个差值列表[73,227,2,30,11,29]一共占多少空间?

73和227使用8个bit的自定义类型β来存储,β类型占1个字节,每个数字占8个bit即1个字节,2个数字占2个字节,共占3个字节。后面的数组2,30,11,29,用5个bit存储的自定义类型α来存储,α类型占1个字节,每个数字占5个bit,4个数字是20个bit即3个字节,共4个字节,所以这个数组一共占3+4=7个字节。

按照每个数字都用一个自定义类型来存储看看会占用多少空间?

73用7个bit来存储(在计算机操作系统层面,数据存储的最小单位是字节,一个字节是8个bit,这里使用7个bit,其实并没有省出空间来,实际占用的还是8个bit,这里就假设占用7个bit),这个定义类型占1个字节;227用8个bit来存储,自定义类型占一个1字节;那么[73,227]这个数组共占用1B+7b+1B+1B共3个字节+7个bit,也就是说不但没有节省空间,反而浪费了好几个bit空间,也就是说这个数组没有必要拆分的那么细,把这些数据浮动不大的数字放在一起,把这些数据较小的放在一起,是最适合的。

倒排索引的过程

image.png

然后对当前词项进行规范化(比如大写字母开头的Are转换成are、China和chinese转换成china(这是两个词,希望转换成一个词,降低检索成本)、's转换成is、过去分词转换成现在分词(made转换成make、kidding转换成kid))、去重、字典排序(按照abc..),最终的结果存在词项字典(term dictionary)

image.png

有序的词项字典,存储的是所有去重之后的结果,当然存储并不是按照二维表格的方式存储的。

Posting List 是倒排表,存储的是包含了当前词项的id集合。

TF是该词项出现的频率。

磁盘格式化

微信图片_20220502150341.png


1、容量是选择要格式化的磁盘。

2、文件格式:

  • • exFAT格式

windows、linux、macos都有该文件格式,缺点就是每个格子都比较大,

使用该格式,如果是大文件还可以,如果是小文件,就会占用大量的磁盘空间。

  • • NTFS格式

3、单元就是一个data page空间大小,exFAT默认是128KB,NTFS默认是4KB


image.png

一个文件大小若为1KB,没有占满一个4KB大小的格子,该文件占用空间也是4KB。


image.png

内存检索数据的时候,最少读取磁盘中一个格子的数据,磁盘中一个格子占用空间是4KB,所以内存从磁盘中读取最小的数据单元就是一个4KB大小的格子。

搜索引擎的相关指标

全文检索的搜索引擎包括百度、搜狗、谷歌;垂直搜索的搜索引擎包括汽车之家、小米有品。

  • • 快

高效的压缩和快速的编码和解码

  • • 准确(相关度)

两种相关度评分算法 BM25和TF-IDF

  • • 召回率

召回率是返回数据丰富度的衡量指标,返回的越多,召回率越高。

搜索和检索的区别

搜索是要么符合条件,要么不符合条件,没有说部分符合;但检索是有相关度的。


image.png

这个查询示例中,查询"小米 NFC 手机",id=1的数据中包含2个词项,相关度为2;id=2的数据中包含3个词项,那么id=2的数据和查询需求的相关度更高。

相关实践学习
使用阿里云Elasticsearch体验信息检索加速
通过创建登录阿里云Elasticsearch集群,使用DataWorks将MySQL数据同步至Elasticsearch,体验多条件检索效果,简单展示数据同步和信息检索加速的过程和操作。
ElasticSearch 入门精讲
ElasticSearch是一个开源的、基于Lucene的、分布式、高扩展、高实时的搜索与数据分析引擎。根据DB-Engines的排名显示,Elasticsearch是最受欢迎的企业搜索引擎,其次是Apache Solr(也是基于Lucene)。 ElasticSearch的实现原理主要分为以下几个步骤: 用户将数据提交到Elastic Search 数据库中 通过分词控制器去将对应的语句分词,将其权重和分词结果一并存入数据 当用户搜索数据时候,再根据权重将结果排名、打分 将返回结果呈现给用户 Elasticsearch可以用于搜索各种文档。它提供可扩展的搜索,具有接近实时的搜索,并支持多租户。
相关文章
|
8天前
|
存储 自然语言处理 数据库
Elasticsearch倒排索引
【11月更文挑战第2天】
18 1
|
19天前
|
测试技术 API 开发工具
ElasticSearch核心概念:倒排索引
ElasticSearch核心概念:倒排索引
49 6
|
4月前
|
存储 缓存 自然语言处理
【Elasticsearch】Elasticsearch倒排索引详解
【Elasticsearch】Elasticsearch倒排索引详解
168 12
|
4月前
|
存储 数据采集 数据处理
数据处理神器Elasticsearch_Pipeline:原理、配置与实战指南
数据处理神器Elasticsearch_Pipeline:原理、配置与实战指南
175 12
|
5月前
|
存储 缓存 负载均衡
elasticsearch写入流程和请求检索流程原理全方位解析
elasticsearch写入流程和请求检索流程原理全方位解析
|
5月前
|
存储 监控 固态存储
elasticsearch索引生命周期管理(ILM):原理和实践
elasticsearch索引生命周期管理(ILM):原理和实践
|
5月前
|
数据采集 API 定位技术
elasticsearch pipelineI详解:原理与使用
elasticsearch pipelineI详解:原理与使用
|
5月前
|
缓存 自然语言处理 监控
elasticsearch过滤器filter:原理及使用
elasticsearch过滤器filter:原理及使用
|
5月前
|
存储 数据库 开发者
Elasticsearch中的三种分页策略深度解析:原理、使用及对比
Elasticsearch中的三种分页策略深度解析:原理、使用及对比
|
5月前
|
存储 JSON 自然语言处理
技术经验分享:Elasticsearch倒排索引结构
技术经验分享:Elasticsearch倒排索引结构
42 0