倒排索引原理

假设一个电商网站,关于手机有如下数据(数据量为10亿条):

id	product	describe
1	新款小米至尊-纪念版手机	手机中的战斗机
2	新款小米全功能NFC手机	小米手机,支持全功能NFC,手机中的战斗机
3	红米手机	狂拽酷炫吊炸天
…	…	…
100000000	…	…

当用户购买手机时,会根据需求关键字进行搜索. 如用户希望购买一台: 小米有NFC功能的手机
那么在搜索是用户搜索关键字: 小米NFC手机

该如怎么做才能够准确快速的将结果返回给用户呢?

假设上面手机相关的数据时存储在关系型数据库中(以Mysql为例), 那么SQL语句为:

1	SQL复制代码select * from table where product like "%小米NFC手机%"

该方案如下存在问题:

表中有10亿条数据, 如果不对 product 列创建索引,会造成SQL全表扫描, 该SQL的执行时间会非常长;
如果对 product 列创建索引, 那么因为 product 列数据比较长, 导致数据库索引 B+ 树的深度会非常深, 查询时需要加载的节点增多, 随机 I/O 变多, 查询时间也非常长.
而且即使 produc t列创建了索引, 上面的 SQL 条件为 “%小米NFC手机%”, 坐侧的 “%” 也会导致索引失效,无法使用索引,还是全表扫描
根据表中的数据可知, 没有匹配 “%小米NFC手机%” 的数据, 查询结果为空. 存在查询精度差的问题.

综合上面的分析可知,使用 RDB 作为该场景的搜索引擎,存在: 时间长,精度差 的问题

———-Elasticsearch(Lucene) 带着倒排索引来拯救世界了!!!————-

elasticsearch 如果组织这些数据呢?
首先 elasticsearch 会将内容进行分词, 同时记录该词对应的数据ID.分词后结果如下

关键词	包含该关键词的数据ID
新款	1, 2
小米	1, 2
至尊	1
纪念版	1
手机	1, 2, 3
全功能	2
NFC	2
红米	3

当用户搜索搜索 “小米NFC手机” 时, 执行流程如下:

对搜索语句进行分词: “小米”, “NFC”, “手机”.
依次查询每个分词, 查询的结果为
- 小米对应的数据ID为 [ 1, 2 ]
- NFC 对应的数据ID为 [ 2 ]
- 手机对用的数据ID为 [1, 2, 3]
对根据第2步的查询结果汇总: 配置的数据ID 为 1, 2, 3
根据第2步的查询结果,对结果排序:
- ID 为 2 的数据出现3次(匹配: 小米, NFC, 手机), 匹配度最高, 排在第一位
- ID 为 1 的数据出现2次(匹配: 小米, NFC), 排在第二位
- ID 为 3 的数据出现1次(匹配: 手机), 排在第三位
返回查询结果

数据的这种组织形式既为倒排索引.

倒排索引结构

在elasticsearch中,倒排索引存储结构如下:

term index(词项索引)	term dictionary(词项字典)	倒排表(posting list)
	新款	1, 2
	小米	1, 2
	至尊	1
	纪念版	1
	手机	1, 2, 3
	全功能	2
	NFC	2
	红米	3

3 倒排索引核心算法

3.1 倒排表的压缩算法

倒排表(posting list)存储的为包含该关键字的所有数据的ID,且有序排列. 试想下如果包含该关键字的数据非常多,假设达到100万条, 由于 posting list 为 int 数组, 那么这100万的数据所需要的存储空间为:

100W * 4 Byte = 400W (Byte) ≈ 4 (MB)
elasticsearch 支持 PB 级数据, 那么 posting list 所占用的空间将非常的大, 那么对该数据进行压缩存储就变的非常必要.
那么就需要一个好的压缩算法, 做到压缩效率高以及快速的编码和解码速度. elasticsearch 支持两种压缩算法: FOR 和 RBM

3.1.1 FOR：Frame Of Reference

假设posting list 存储的数据都是连续的值, 既: [1,2,3,4,5…100w], 那么如果每个都以 int (4 Byte)存储, 那么100W的数据所占用的空间为:

100W * 4 Byte = 400W (Byte) ≈ 4 (MB)

———————————进入 FOR 算法原理装逼时间————————————

如果我们每项只存储其与前一项的差值, 既:

posting list[n] = value(n) - value(n-1)

那么这 100W 的数据存储形式就成了: [1,1,1,1,1……1], 既 100W 个 1, 而 1 只需要 1个bit就可以存储, 之前一个ID需要4 Byte(32 bit)存储,现在 1 bit 就可以存储, 空间节省 32 倍.
100W 所占用的空间就是:

100W * 1 bit = 100W bit = 125000 Byte ≈ 0.125M

———————————进入 FOR 算法实际存储方式分析————————————

上面所假设的只是一种理想情况,所有的数据都连续. 下面以一组不连续的数据分析 FOR算法的存储形式:

ini复制代码posting list:
[73, 300, 302, 332, 343, 372]  => 空间为 6 * 4(Byte) = 24(Byte)

差值数组为:
[73, 227, 2, 30, 11, 29]  => 差值的最大数据为227, 需要8个bit(2^8=256 > 227)存储,那么所有的数据都使用8bit存储, 需要占用的空间为 8 * 6(bit) =  48(bit) = 6(Byte)

上面的数据还可以优化: 数组中227 需要 8bit存储, 但是 2 只需要 2bit 存储,如果2也用8bit存储,严重浪费空间, SO 不要懈怠,继续优化...

将上面的数组进行拆分:
[73, 227] => 最大值227, 需要8bit存储, 占用的空间为 2*8bit = 16 bit
[2, 30, 11, 29] => 最大值30, 需要5bit存储, 占用的空间为 4*5bit = 20 bit.

将数组拆分为两组, 第一组每个数据只用 8bit存储, 第二个数组每个数据占用 5bit 存储, 那么解压的时候如何知道呢? 
FOR算法采用的方式为在每个数组头另外用 1Byte(8bit)存储本数组每个数据占用的空间. 那么综上所占用的空间为:

  1 Byte(第一个数组头) + 16bit(2Byte)(第一个数组数据占用的空间) + 1 Byte(第二个数组头) + 20bit(3Byte, 在计算机中数据以 Byte为最小单位, 20bit 实际占用了 3Byte的空间)
= [1Byte + 2Byte](第一个数组占用空间) + [1Byte + 3Byte](第二个数组占用空间)
= 7Byte(还不如不优化-_-, 不优化只占用6Byte)

3.1.2 RBM：RoaringBitmap

FOR算法的思想是前后两个数据的差值比较小(占用的空间比较小),来达到节省空间的目的,但是如果数组的相邻项之间的差值也非常大时, 所达到的优化效果就不太明显.此时就需要 RBM 出来救场…

———————————进入 RBM 算法原理装逼时间————————————

假设如下数组:

[1000, 62101, 131385, 132052, 191173, 196658]

由于postlist为int类型的有序数组, int占用的空间为 4Byte(32bit). 那么将上面的数据拆分为高16bit和底16bit, 以上面数组最后一个数字196658为例:

196658 => 二进制为: 0000 0000 0000 0011 0000 0000 0011 0010

高16为为: 0000 0000 0000 0011 => 转换为十进制为 3

底16位为: 0000 0000 0011 0010 => 转换为十进制为 50

索引196658 可以用 (3, 50) 表示

拆分结果为:

[(0, 1000), (0, 62101), (2, 313), (2, 980), (2, 60101), (3, 50)]

那么将该数组转换为 map类型, key为第一个数字(高16位), value为第二个数字(底16位), 转换结果为:

key = 0 -> value = [1000, 62101]

key = 2 -> value = [313, 980, 60101]

key = 3 -> value = [50]

value为一个真实数据的低16位的数组, 既一个short数组(short类型为 2 Byte = 16 bit). value在 elasticsearch中存储方式有三种:

ArrayContainer
BitmapContainer
RunContainer

3.1.2.1 ArrayContainer

见名知意, value中的每个数据采用一个 short 存储, 既每个数据占用 16bit(2Byte). value为一个short数组:

既 value = short[n]

假设value中数据总数为 n, 那么所占用的空间为:

f(n) = 2 * n (Byte)

3.1.2.2 BitMapContainer

BitMap原理: www.cnblogs.com/cjsblog/p/1…

BitMap的原理为将所有的空间视为一个 bit 数组, 在这个 bit数组中, 第一位代表 1, 第二位代表2 … 第 N 位代表 N.

因为value中存储的为数据的低16位, 16位所能表达的最大数字为: 2^16 = 65535, 既value中可能出现 0 ~ 65535. 那么使用 BitMap存储只需要: 65536 个 bit即可存储(0~65535共 65536个数字, 因为0也算).

65536 bit = 8192 Byte = 8 KB

3.1.2.3 RunContainer

RunContainer用于处理一组特殊情况的数据, 假设数组中的数据连续: 1, 2, 3, 4 … 100W.
那么我们可以使用 2Byte 存储:

第一个Byte存储连续数据的第一个数字, 在本例中第一个Byte存储 1
第二个Byte存储连续数据的最后一个数字, 在本例中第二个Byte存储 100W

那么这100W个数据只需要 2 Byte就可以存储.
RunContainer 在 Lucene 5中新增.

3.1.2.4 RBM 总结

未完待续…

3.2 词项索引的检索原理

3.2.1 FST：Finit State Transducers

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

倒排索引原理

倒排索引结构