Lucene技巧分析

「爱情、让人受尽委屈。」 2022-06-08 13:11 159阅读 0赞

Lucene中用到的一些设计，主要是为了满足2个特点：1存储小；2检索快。

这里把Lucene里用到的技巧单独领出来了解下，是为了多学习一些优秀的算法，开阔思路，在工作中万一遇到类似的场景可以学以致用。

技巧一：

Prefix+Suffix记录

在前面的原理学习中我们已经知道lucene的term在字典中是按照顺序排序的，这就为Prefix+Suffix的记录方式奠定了先决条件。

所谓的Prefix+Suffix，是当前一个词是后一个词组成的一部分时，利用一个偏移量来代替具体字符串，以减少存储空间。

![Center][]

例如要存储如下词:term，termagancy，termagant，terminal

照正常方式来存储：

\[VInt = 4\] \[t\]\[e\]\[r\]\[m\]，\[VInt =10\]\[t\]\[e\]\[r\]\[m\]\[a\]\[g\]\[a\]\[n\]\[c\]\[y\]，\[VInt = 9\]\[t\]\[e\]\[r\]\[m\]\[a\]\[g\]\[a\]\[n\]\[t\]，

\[VInt = 8\]\[t\]\[e\]\[r\]\[m\]\[i\]\[n\]\[a\]\[l\]

用前缀后缀规则来储存：

\[VInt = 4\] \[t\]\[e\]\[r\]\[m\]，\[VInt = 4(offset)\]\[VInt = 6\]\[a\]\[g\]\[a\]\[n\]\[c\]\[y\]，\[VInt = 8(offset)\]\[VInt = 1\]\[t\]，

\[VInt = 4(offset)\]\[VInt = 4\]\[i\]\[n\]\[a\]\[l\]

占用空间比是35：22，节约了三分之一空间，前后term相似性越高该算法效果越好，而lucene的term正好是按顺序排序的。

技巧二：

差值算法

在 Lucene 的反向索引中，需要保存很多整型数字的信息，比如文档 ID 号，比如词(Term)在文档中的位置等等。

Lucene中整数的存储类型是VInt（变长整数类型）：每个VInt由多个 Byte，对于每个 Byte 的 8 位，其中后 7 位表示数值，最高 1 位表示是否还有另一个Byte，0 表示没有，1 表示有。130 化为二进制为 1000, 0010，VInt的第一个 Byte 表示后 7 位，并且在最高位置 1 来表示后面还有一个 Byte，所以为(1) 0000010，第二个 Byte 表示第 8 位，并且最高位置 0 来表示后面没有其他的 Byte 了，所以为(0) 0000001。所以130在lucene里存储是10000010、00000001。

VInt的结构决定了随着数值的增大，每个数字占用的Byte 的个数也逐渐的增多。所谓差值规则(Delta)就是先后保存两个整数的时候，后面的整数仅仅保存和前面整数的差即可。

![Center 1][]

以：16386，16387，16388，16389为例

照正常方式来存储，需要的空间如下：

\[(1) 000, 0010\]\[(1) 000, 0000\]\[(0) 000,0001\]，\[(1) 000, 0011\]\[(1) 000, 0000\]\[(0) 000, 0001\]，\[(1)

000, 0100\]\[(1) 000, 0000\]\[(0) 000, 0001\]，\[(1) 000,0101\]\[(1) 000, 0000\]\[(0) 000, 0001\]

应用差值规则来存储，需要的空间如下：

\[(1) 000, 0010\]\[(1) 000, 0000\]\[(0) 000,0001\]，\[(0) 000, 0001\]，\[(0) 000, 0001\]，\[(0) 000, 0001\]

空间占用量12：6，节省了1半。数字之间差距越小空间利用率越高，而lucene中无论是文档 ID，还是词在文档中的位置，都是按从小到大的顺序，逐渐增大的。

技巧三：

跳跃表规则

使用跳跃表规则的前提是数据必须是排序的，跳跃表中的间隔和层次两个概念比较好理解，直接上图

![Center 2][]

这个不细说，跟跳跃表也有好多变种，例如随机跳跃等，本质是牺牲存储换取搜索效率，平衡性靠跳跃间隔和层次来决定。

[Center]: /images/20220608/4dcd3964c8fe4b7c8d43f214572f328f.png
[Center 1]: /images/20220608/fb59e928b7a645809b29fb2f8912d0f5.png
[Center 2]: /images/20220608/611a1d99a6474d949a7b666017ab9a8c.png