B+Tree实现图解

目前的操作系统的文件索引和关系型数据库索引大多是选用B+Tree的数据结构(非关系数据库，如Mongodb索引用B-Tree结构，Redis索引使用跳表结构)，相对B-Tree为什么B+Tree更受到关系型数据库的欢迎呢？

关于B+树

与前一篇描述的B树相比，本篇文章所谈论的B+树在定义上似乎没有官方的定义，从论坛上看，目前还是对定义存在两点争论:

其一：B+Tree是否B-Tree一样是结点有M-1个关键字拥有M棵子树，还是M个关键字拥有M颗子树。

其二：内部结点的索引值使用最大值还是最小值。

不过上述的争论对于实现并没有大的影响，我们可以自己去定义。所以这里选用百度百科上对B+树的描述:

(1)每个结点至多有m个子女；

(2)除根结点外，每个结点至少有[m/2]个子女，根结点至少有两个子女；

(3)有k个子女的结点必有k个关键字。

下面是实现的树(貌似根结点可以有一个关键字，但是这里还是引用k个子女的结点必有k个关键字 这条逻辑)。

对比B树

从上面B+树的图可以看出与B-树相比，非叶子结点不存储数据，仅充当索引结点，其次是所有的数据都存储在叶子结点上， 且叶子结点利用指针形成单链表。通过这些特征我们可以得知：

1.由于B+树内部结点不存储数据，所以树更加矮，内部结点在相同大小的磁盘页能存储更多，一次性读入内存的关键字也会更多，减少IO操作。

2.由于B+树内部结点不存储数据，所以查询全部落入叶子结点，所以相对B树查询更加稳定，

3.由于B+树叶子结点使用指针链接成链表，所以相对与B-树，其范围查询更加高效，因为B-树中范围查询 需要对B-树进行中序遍历，所以效率会低。

注:B-Tree稳定不代表一定会快，如果是随机访问或者单一查询，有可能B树更快(数据存储在距离根结点越近则越快)， 同理IO操作也不一定比B+Tree多。这也是为什么非关系型数据库不选用B+Tree的原因，因为非关系型数据库通常都是单一查询， 不需要遍历匹配。

还需要注意的是，B+Tree与B-Tree一样，当按照key值的大小顺序插入分裂时，每个叶子结点的存储效率只有50%，如下图，我们会发现2与3之间不能再插入其他的正整数， 也就造成了空间的浪费

构建B+树

仍以5阶为例，来构建5阶B+树。通过B+树的定义，我们可以知道，其结点最多有5个关键字，最少有[5/2]=3个关键字。

这里假设存储的关键字为3, 8, 31, 11, 23, 29, 50, 28,1, 2，来看如何构建。

新增

首先定义一颗空树，然后依次新增，新增流程如下：

依次插入3, 8, 31, 11, 23

此时结点关键字已经达到M个的要求，如果再继续新增29时，会同B树一样，需要进行分裂。但是与B树分裂存在一些区别， 如下图，关键字上升的过程中，关键字并未从原来的结点中移除(B树中会被移除)，其次根结点形成时，上升了两个关键字， 来保证k个子女的结点必有k个关键字的要求(我见到也有根结点有一个关键字的博文，这里感觉不打紧，所以就不纠结)， 最后就是叶子结点之间利用形成单向链表

继续新增50。这一步相对与B树同样存在一些特殊步骤，更新内部的索引结点，插入50之前，31是最大值，索引结点存储11,31表明 目前31对应子树关键字范围在(11,31]之间，但是插入50之后，沿路的索引值也需要进行更新

最后插入28，1，2，这次插入无需更新沿路的索引结点，因为其并未打破索引的范围规则

通过新增的流程，我们会发现，相比较B树，插入逻辑要复杂一些。复杂在当插入结点打破索引规则时， 需要更新沿路索引，其次对于分裂的叶子结点需要形成一个单向链表

删除

新增操作之后继续看删除的流程，我们依次删除50，23，28，1，2。

删除50后，虽然结点多于最小关键字个数，但是索引结点的平衡被打破，即不存在50的索引，所以需要更新索引结点。

删除23的过程中，即没有打破索引，也没有导致结点关键字少于最小关键字个数，所以整棵树并没有大的改动， 但是当我们删除28的时候，结点最关键字小于最小关键字个数。此时就需要借结点或者合并结点。针对删除28，我们会发现，他的左兄弟结点关键字个数大于最小关键字个数，所以可以借用，借用过程：借用左兄弟最大关键字或者右兄弟最小关键字，如果是借用左兄弟，则更新左兄弟对应父结点的索引值(因为最大关键字被借走)， 如果借用右兄弟则更新当前结点对应父结点的索引值(因为借过来的肯定比当前索引值大)

继续删除1，2。在删除2的过程中，结点关键字个数少于最小关键字个数，此时兄弟结点的关键字个数无法外借(因为已经是最少关键字)， 此时进行合并，合并流程：如果合并之后根结点孩子不足2，则移除根结点，合并结点充当根结点，如果合并之后，根结点孩子大于等于2， 则将被合并结点对应父结点的索引值移除。

层序遍历

我们可以借用栈(受限的线性表)，对于树进行层序遍历。

    private Queue<Node<K, V>> queue = new LinkedBlockingQueue<>();

    public void levelOrder() {
        queue.add(root);
        while (!queue.isEmpty()) {
            Node<K, V> root = queue.poll();
            for (Entry<K, V> entry : root.entries) {
                System.out.print(entry.k + " ");
            }
            System.out.print("->");
            for (Node<K, V> node : root.child) {
                queue.add(node);
            }
        }
    }

总结

二叉查找树进化品种的红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构。这是因为索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级， 所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。为什么使用B-/+Tree，还跟磁盘存取原理有关。