sqlite中fts的数据结构说明:segment Interior nodes

**** 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也是排序过，所以相同前缀出现的比率还是很高的。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!