**** Segment interior nodes ****
** Segment interior nodes store blockids for subtree nodes and terms
** to describe what data is stored by the each subtree. Interior
** nodes are written using InteriorWriter,and read using
** InteriorReader. InteriorWriters are created as needed when
** SegmentWriter creates new leaf nodes,or when an interior node
** itself grows too big and must be split. The format of interior
** nodes:
**
** varint iHeight; (height from leaf level,always >0)
** varint iBlockid; (block id of node's leftmost subtree)
** optional {
** varint nTerm; (length of first term)
** char pTerm[nTerm]; (content of first term)
** array {
** (further terms are delta-encoded)
** varint nPrefix; (length of shared prefix with prevIoUs term)
** varint nSuffix; (length of unshared suffix)
** char pTermSuffix[nSuffix]; (unshared suffix of next term)
** }
** }
**
**
这个block(或者说node)为一个内部node,这个node用来确定如何查找其child node。内部节点只是包含term的内容,不包含docid。
一个node可以包含n个term,这n个term可以划分出n+1个subtree(一个subtree就是一个内部节点或者叶节点),如上几篇文章介绍所说,这n+1个subtree一点是连续的,所以这个node只要记录第一个subtree的blockid就可以,其他n个blockid只要顺序加1就能得到。
n个trem是如何定义n+1个subtree的内容:
term[0] -> 第0个subtree包含的trem都必须 < trem[0],注意没有等于。
term[1] -> 第1个subtree包含的trem范围为 term[0] <= subtree < term[1]
term[2]-> 第2个subtree包含的trem范围为 term[1]<= subtree < term[2]
......
......
term[n-1] -> 第n-1个subtree包含的trem范围为 term[n-2] <= subtree < term[n-1]
暗含最后一个sub -> 第n个subtree包含的trem范围为 term[n-1] <= subtree
在interior node中存储的term没有必要把term的完整字符串都存储进来,只要通过比较操作可以确定subtree的正确位置,我们完全可以只存储term的前几个字符就可以。
比如有2个subtree的内容为 (.....,...,some) (weid,.....,),只需要term:‘w’就可以把这2个subtree划分出来。
解释起来就,
第一个subtree的内容都小于‘w’,
第二个subtree的内容都大于等于‘w’。
所以‘w’就可以把这2个subtree划分。具体算法就是在第二个subtree的第一个trem中找第一个subtree最后一个trem的共同prefix+1个字符。
字节流定义:
第一字节开始,为一个变长的int型数值,表示当前node在b-tree的高度。在b-tree的高度定义中,树的最底层,也就是叶子节点,定义为level 0.由于这个nodes是interior node,所以它的height总是大于0.
接下来还是一个变长的int数值,描述的当前这个interior node对应的所有subtree中第一个subtree的blockid。
再接下来就是顺序存储所有的term。与leaf node中存储term用的是相同的技巧。
第0个term: 长度+内容
第1个term: 与第0个term相同前缀的长度+当前term去除prefix剩下的长度+剩下的内容
。。。。
。。。。
第n-1个term: 与前一个term相同前缀的长度+当前term去除prefix剩下的长度+剩下的内容
这n个term也是排序过,所以相同前缀出现的比率还是很高的。