通过谈谈lucene倒排索引的存储方式(3-2)谈谈lucene倒排索引的存储方式(3-1)的分析可知,当有公共前缀的词的数量达到指定阈值时会写入到一个Block中,不过还没有对其中的细节进行分析,现通过给定的输入abc、abcd、abcde、abcdef、abcdf、abcdg、abe、abf、abg、abh,以及参数阈值MIN_BLOCK_SIZE = 3和MAX_BLOCK_SIZE = 4来对倒排索引的构成进一步研究。

            当输入abe时由于abcd、abcde、abcdef、abcdf、abcdg以abcd为前缀的个数为5个已经超过MIN_BLOCK_SIZE个数,因此达到写成一个Block的条件,由于MAX_BLOCK_SIZE=4所以对这5个item需要进一步按照MIN_BLOCK_SIZE3个为一组进行拆分,即abcd、abcde、abcdef会写到一个Block(该Block也是一个leafBlock,因为它的元素只有词)中,除了前缀abcd,其余的后缀以及postings元数据(经过压缩)会全部写入到termsOut文件流中,对于该Block有以下重要属性prefix, startFP, hasTerms, isFloor, floorLeadLabel, subIndices,其中prefix表示公共前缀即abcd,startFP表示termsOut文件流指针(通过该指针可以从tim文件中解析出该Block中每个词的信息),hasTerms表示该块是否包含词(很明显该Block中全部都是词),isFloor为True表示该块由于超过MAX_BLOCK_SIZE个数进行了进一步分块,floorLeadLabel该块中第一个词的第prefixLen个字符(该块为-1),subIndices表示子块的索引(该块没有子块)。然后abcdf与abcdg会同样写入到一个新块中,不过此时prefix记录的是abcdf,floorLeadLabel记录的是f。写完这两个块就得想办法如何能定位这两个Block了:首先这两个块的Floor都为True,先写入第一个块的fp、hasTerm标记和isFloor,再写入剩余Block的个数对每个Block写入floorLeadLabel(主要用于查询某个词时可以预判,如果不存在就无需加载该块下所有的词),这些信息最终会转换成字节数组并且和前缀abcd一起写入FST中,该FST是保存在第一个Block中的,最后将pending列表中的abcd、abcde、abcdef、abcdf、abcdg替换成该Block,于是pending列表中的元素为pendingTerm:abc、pendingBlock:abcd以及新增的pendingTerm:abe。

           继续添加abf、abg、abh,此时pending列表中有6个entry,其中5个term,1个block。最后需将这6个entry按照MIN_BLOCK_SIZE和MAX_BLOCK_SIZE设定的阈值继续分块:首先term:abc、block:abcd、term:abe会组成一个新的Block,其中在写入block:abcd时记录的是block的文件指针,然后term:abf、abg、abh也会形成一个新的Block,最后这两个新的Block会按照前面所述的方式一起写入FST中并保存在第一个Block中。至此倒排索引的存储方式算是分析结束了,其实lucene的倒排索引的逻辑视图还是树状的(最终会以FST的形式保存索引数据由于FST可以共享后缀所以FST是个图,但是它也可以认为是对树的一种优化,我们可以认为FST是一种共享后缀的前缀树),早期实现的跳跃链表也是树状的,而关系库中常用的B树也是树状的,它们在查询的效率以及读写的实时性上有一定的差异性,以后对这三种形式的树进行仔细的分析。后面还是着重对lucene的索引合并、多线程写入、实时性以及事务性方面进行分析!

10-08 00:02