零版本Lucene-Coreversion8.8.2-简介Lucene的索引设计基本依赖于磁盘存储,倒排索引是一种依赖大量冗余数据完成分词搜索的技术,所以Lucene正在设计一种数据压缩技术,使用大量的时间换取空间,以保证用最少的磁盘资源存储最多的数据。VInt是非常有趣的结构设计之一。二、技术原理1、总结Java中一个普通的int占用4个字节。但是当int的值为-128~127时,其实只需要一个字节就可以装进去,其他三个字节都是无意义的冗余(其他字节可以表示的区间可以类推),没有很多情况下这四个字节都可以用完。VInt是variantint的意思,是一个变量int。其实质就是按需分配,减少这种冗余。2字节指示位一个普通字节有8个有效数据位,而VInt中只有7个,最高位成为下一个字节的指示位。最高位为1,表示下一个字节还是当前数据。最高位为0,表示后面没有数据。3VInt的副作用对于正数,由于只有7个数据位,当int的值比较大时,可能需要5个字节来表达当前数据(这个问题无法解决,VInt也认为没有需要解决,因为实际生产中这种情况不多)。对于负数,最高位为1,不能压缩(引入zigzagEncoding)4zigzag编码使用位移和异或运算将第一个符号位移动到数据的最后一位。3Demo如果需要分别对1/200/-1这三个int数进行序列化,VInt算法的具体步骤如下(有效数据用黄色标注):11的二进制数为000000000000000000000000000000012001200的二进制数是0000000000000000000011001000-1的二进制数是11111111111111111111111111111111102向前位移一位。01后面的二进制数是000000000000000000000000200二进制数是00000000000000000000-110010000-1。111111111111111111111111111111111111111111111111111111XOR操作的本质是差异为0,相同是1.对于对于,异对于,11111111111111111111111111111111111111111111111111111111111111111111111111成00000000000000000000000000000010;200的处理表达式为00000000000000000000000110010000^11111111111111111111111111111111=00000000000000000000000110010000Fornegativenumbers,orone00000000000000000000000000-1processingexpressionis11111111111111111111111111100^0000000000000000000000000000000000000000000000114eightarereaddatainoneunit,读了八个单元。读完八位后,将第一位作为标记位,如果还有其他数据,再读八位。对于数字1,序列化过程:先读取7位0000010,之前都是0,如果没有数据,则在前面补0,即00000010。读取过程:读取序列化后的数据00000010,则第一位为0,表示只有一个字节,后面没有其他数据,所以数据为00000010,最后一位为0,表示为正数,与11111111异或,得到00000010,将数据移回一位,前面加0,最后是00000001对于数字200序列化过程:先读取七位0010000,如果前面不全为0,则在前面补1,再读取七位0000011,如果之前都是0,那么前面补0,就是00000011,合并后的数据读取为1001000000000011过程:读取序列化后的数据10010000,第一位为1,表示多了一个字节,并且后面还有其他数据,所以数据是0010000,然后读取00000011,第一位是0,表示没有其他数据,数据是0000011,合并后的数据是0000000110010000,最后一位是0,表示这是一个正数。与1111111111111111异或运算结果为0000000110010000将数据后移一位,前端补0,最后为0000000011001000。对于数字-1,序列化过程:先读取七位数字0000011,即之前都是0,如果没有数据,则在前面补0,即00000011。因此,数据最后一位00000011为1,表示为负数,与00000000异或运算,得到11111100,将数据往后移一位,前端加1,最后就是11111110四源码0流程下面源码的调用流程:lucene确认一个Int值调用zigZagEncode(...)将int编码为zint调用writeVInt(...)方法将zint编码为vint,并写入磁盘或其他内存容器从磁盘或其他内存容器调用readVInt()方法读取一个vint值并将其解码为zint调用zigZagDecode(...)方法将zint解码为int1writeZIntwriteZInt(...)方法或在g.apache.lucene.store.DataOutput://这个方法用于zigzag编码后写入一个int值publicfinalvoidwriteZInt(inti)throwsIOException{//BitUtil.zigZagEncode(i)用于zigzag编码writeVInt(BitUtil.zigZagEncode(i));}//用于编写一个VIntpublicfinalvoidwriteVInt(inti)throwsIOException{while((i&~0x7F)!=0){//writeByte(...)方法用于将字节持久化到文件中,这里不用关注writeByte((byte)((i&0x7F)|0x80));i>>>=7;}writeByte((byte)i);}2zigZagEncodezigZagEncode(...)org.apache.lucene.util.BitUtil中的方法://i>>31表示正值或0,返回一个屏障所有0的//i>>31表示负数,返回所有1个障碍publicstaticintzigZagEncode(inti){return(i>>31)^(i<<1);}3readZIntreadZInt(...)方法inorg.apache.lucene.store.DataOutput:publicintreadZInt()throwsIOException{returnBitUtil.zigZagDecode(readVInt());}publicintreadVInt()throwsIOException{//从磁盘读取字节字节b=readByte();//b>=0,代表最高位为0,没有后续值,以下同理if(b>=0)returnb;inti=b&0x7F;//继续读一个byteb=readByte();i|=(b&0x7F)<<7;if(b>=0)returni;//继续读取一个byteb=readByte();i|=(b&0x7F)<<14;if(b>=0)returni;//继续读取一个字节b=readByte();i|=(b&0x7F)<<21;if(b>=0)returni;//继续读取一个字节,在VInt编码下,最多五个字节=readByte();i|=(b&0x0F)<<28;if((b&0xF0)==0)returni;thrownewIOException("InvalidvIntdetected(toomanybits)");}4zigZagDecodezigZagDecode(...)methodinorg.apache.lucene.util.BitUtil://decode的操作与zigZagEncode(...)完全相反publicstaticintzigZagDecode(inti){return((i>>>1)^-(i&1));}
