本篇较长较枯燥,请保持耐心看完。
前面两章介绍了一下倒排索引以及倒排索引字典的两种存储结构,分别是 跳跃表 和 哈希表 ,本篇我们介绍另一种数据结构,他也被大量使用在信息检索领域,我在 github 上实现的搜索引擎的词典也是用的这个数据结构,它就是B+树。
首先,我们看看什么是树,树是程序设计中一个非常基础的数据结构,记得大学时候的数据结构课,链表,栈,队列,然后就是树了,虽然那时候想必大家都被前序遍历,中序遍历,后序遍历折腾过,不过树确实是一种非常有用的数据结构。
上一篇我们说过,表2的第一列首要解决的问题就是能快速找到对应的词,然后找到对应词的倒排列表,除了跳跃表和哈希表,B+树也能满足条件,B+树是B树的变种,我们B树我们就不看了,感兴趣的大家可以直接去google一下,我们主要讲的是B+树,下图就是一个3层的B+树,我画出来可能和大家搜出来的有点出入,但是没关系,关键B+树这种数据结构的思想大家了解了就行。
假设我们有一组数字 34,40,67,5,37,12,45,24 ,那么,把他们存成B+树就是下图这个样子。
我们很明显看到几个特点
我尽量的把B+树说简单点,网上的资料也好,查书也好,看上去都挺复杂的,首先我们看看怎么建立这棵树,我尽量用图了,少一些文字也好理解一点,前方大量图预警。
首先,我们的数组是 34,12,5,67,37,40,45,24
第一步,初始化B+树,是这样子的
这时候,啥也没有,但是占用了两个节点,标识为 无 的,表示这个元素无意义,标记为 NULL 表示 无穷大
第二步,插入34这个元素,那么图变成这样子
我们看到,插入的过程是顺着指针一直走到叶子节点,发现叶子节点是空的,然后把元素插入到叶子节点的头部,然后返回上一级节点,将NULL后移,然后把第一个元素 置为他的子节点的最大值,请记住这句话: 置为他的子节点的最大值
第三步,接着插入第二个元素12
这个步骤复杂一点
第四步,然后是插入5
这一步更复杂一点,产生了 分裂
第五步,接着我们插入67
这一步比较简单
第六步,我们插入37,插完这个后面的我就不写了,感兴趣可以自己画一下
这一步复杂了,这一步不仅分裂了,而且分裂了两次,并且层数增加了一层
按照这六步,前5个元素就插入到B+树中了,后面的步骤您可以自己走一走,B+树基本的思想就是这样子的,可能我没有按照教科书上的做法来说,但这并不影响大家的理解,我相信看完了以后虽然你脑子里没有标准的算法步骤,但应该有个大致的轮廓了,只不过需要自己再仔细想想步骤。
总的来说,B+树的插入步骤无外乎以下几个步骤
查找操作和更新操作几乎一样,就是更新操作的前面两步,就不说了。
一般的更新的时候也是先查找,找到叶子节点,再更新,然后顺着指针往上走继续分裂,这个顺着往上走一般情况下首先想到的是双向指针,但是双向指针分裂的时候有点麻烦,需要把两个指针都重新指新节点,我实现的时候用了一个栈,查找叶子节点的时候把经过的节点依次压栈,到达叶子节点后,完成插入操作,往上遍历的时候依次把栈弹出来就行了,少了一个指针。
回到上一篇说的那个表2的第一列,如果是那个表的话,用这个B+树加上倒排链的话,最后的数据结构就长成这样子了(字符串的大小我随便写的,中文的顺序排列哥的脑子排不出来,你就把他们看成从小到大的顺序吧)
好了,至此,一个倒排索引就建立好了,由两部分组成,我实现的时候就是这么实现的,一个结构用B+树存储字典,另外一个就是一个顺序的文件,B+树的叶子节点存一个指向倒排文件的文件偏移量,当然,你也可以用前面的哈希表或者跳跃表,甚至还有其他类型的树,比如trie树来实现,或者你还有其他新的高效数据结构也行。
我们再来说说B+树,为什么选它?
之前我实现的时候用的是哈希表,而且大部分的搜索引擎用的都是哈希表,为什么用树呢
最后说说我实现的这棵B+树,首先,为了更少的占用内存,我是用的磁盘的形式实现的,并且用了mmap的方式来加快读写速度,没有用双向指针,而用的栈来记录查询的路径,速度还行吧,构造一棵10万个随机字符串的树大约需要3秒,随机查询10万次大约需要150毫秒,每次1.5微秒。
当然,我实现的时候比较仓促,就是按照算法硬编码快速撸出来的,所以我这个B+树还有非常大的优化空间,首先,我的key现在是确定的,不能超过64字节,并且每个节点最多100个元素,当时为了快,确定的key和元素个数比较好编程,如果变成动态的更加节省空间,其次,没有特别的考虑连续key的情况,连续key的插入会造成空间浪费一半,还有,把速度问题交给了mmap来解决,如果内存足够,实际上启动的时候预读取非叶子节点到内存的话,查询起来会更快,不过目前基本上满足需求了,大家如果对B+树实现很感兴趣,可以看看 bolt 这个项目,这个是一个B+树实现的KVDB,而且是带事务的哦。