B+树原理分析及Java代码实现

左手的ㄟ右手 2022-11-19 04:25 327阅读 0赞

今天我们分析B+树原理及Java代码实现，以前我写过一篇关于mysql 存储引擎B+Tree、 B-Tree和hash三种原理及区别，[可以先参考][Link 1]

我们都知道B+树，是B树的一个变种，需要先明确一下B树的定义：

一、B/B+树的基本定义：

**1、B 树**可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点。

*  根节点至少有两个子节点
 *  每个节点有M-1个key，并且以升序排列
 *  位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
 *  其它节点至少有M/2个子节点

下图是一个M=4 阶的B树:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70][]

可以看到B树是2-3树的一种扩展，他允许一个节点有多于2个的元素。

B树的插入及平衡化操作和2-3树很相似，这里就不介绍了。下面是往B树中依次插入

**6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4**

的演示动画：

![89f1cb27d14ebbd147cfa87fb5d10ea7.png][]

**2、B+**树既然是对B树的一种变种树，它与B树的差异在于：

*  有k个子结点的结点必然有k个关键码；
 *  非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。
 *  树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。

如下图，是一个M=4的B+树:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1][]

下图是B+树的插入动画：[动画参考][Link 2]

![4c27b7e3bb7440019f3cc9d032cb122e.png][]

3、B和B+树的区别在于，B+树的非叶子结点只包含导航索引信息，不包含实际的值（这样可以放更多的key索引），所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。

4、B+ 树的优点在于：

*  由于B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。
 *  B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。

但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。

二、代码实现：我们先贴出代码，在逐个方法分析

1、核心代码：

/**
     * @author wanghuainan
     * @date 2021/4/14 19:05
     */
    public class CatalogBTree<Key extends Comparable<Key>, Value> {
    
        //参数M 定义每个节点的链接数
        private static final int M = 4;
    
        private Node root;
    
        //树的高度  最底层为0 表示外部节点    根具有最大高度，此高度是根之后的高度
        private int height;
    
        //键值对总数
        private int n;
    
        //节点数据结构定义
        private static final class Node{
            //值的数量
            private int m;
            private Entry[] children = new Entry[M];
            private Node(int k){
                m = k;
            }
        }
    
        //节点内部每个数据项定义
        private static class Entry{
            private Comparable key;
            private final Object val;
            //下一个节点
            private Node next;
            public Entry(Comparable key, Object val, Node next){
                this.key = key;
                this.val = val;
                this.next = next;
            }
            @Override
            public String toString() {
                StringBuilder builder = new StringBuilder();
                builder.append("Entry [key=");
                builder.append(key);
                builder.append("]");
                return builder.toString();
            }
    
        }
    
        public CatalogBTree(){
            root = new Node(0);
        }
    
        public int size(){
            return n;
        }
    
        public boolean isEmpty(){
            return size() == 0;
        }
    
        public int height(){
            return height;
        }
    
        /**
         * 查询接口
         * @param key
         * @return
         */
        public Value get(Key key){
            return search(root, key, height);
        }
    
        private Value search(Node x, Key key, int ht) {
            Entry[] children = x.children;//首次进入，相当于根节点
            //外部节点  这里使用顺序查找
            //如果M很大  可以改成二分查找
            if(ht == 0){//到了有数据的子节点（也可能是根节点，如果键值对小于M），此次查询数据。
                for(int j=0; j<x.m; j++){
                    if(equal(key, x.children[j].key))//遍历查询
                        return (Value)children[j].val;
                }
            }
            //内部节点  寻找下一个节点
            else{
                for(int j=0; j<x.m; j++){
                    //最后一个节点  或者 插入值小于某个孩子节点值
                    if(j+1==x.m || less(key, x.children[j+1].key))//定位数据在哪个节点下，然后继续递归查询
                        return search(x.children[j].next, key, ht-1);//去下一层继续查询
                }
            }
            return null;
        }
    
        /**
         * 新增数据接口
         * @param key
         * @param val
         */
        public void put(Key key, Value val){
            //插入后的节点，如果节点分裂，则返回分裂后产生的新节点
            Node u = insert(root, key, val, height);
            n++;//键值对总数加一
            if(u == null) return;//根节点没有分裂  直接返回
            //分裂根节点,已满节点进行分裂，将已满节点后M/2节点生成一个新节点，并将新节点的第一个元素指向父节点，此处是M>>1 = 2（因为M=4）
            Node t = new Node(M>>1);
            //旧根节点第一个孩子和新分裂节点第一个孩子 共同 组成新节点作为根
            t.children[0] = new Entry(root.children[0].key, null, root);
            t.children[1] = new Entry(u.children[0].key, null, u);
            root = t;//新的根节点
            height++;//节点高度加1
        }
    
        private Node insert(Node h, Key key, Value val, int ht) {
            int j;
            //新建待插入数据数据项
            Entry t = new Entry(key, val, null);
            if(ht == 0){//高度为零时，直接遍历
                for(j=0; j<h.m; j++){ // 外部节点  找到带插入的节点位置j
                    if(less(key, h.children[j].key))
                        break;
                }
            }else{
                //内部节点  找到合适的分支节点
                for(j=0; j<h.m; j++){
                    if(j+1==h.m || less(key, h.children[j+1].key)){
                        Node u = insert(h.children[j++].next, key, val, ht-1);
                        if(u == null) return null;
                        t.key = u.children[0].key;
                        t.next = u;
                        break;
                    }
                }
            }
            //j为带插入位置，将顺序数组j位置以后后移一位(从后往前处理) 将t插入
            for(int i=h.m; i>j; i--){
                h.children[i] = h.children[i-1];
            }
            System.out.println(j + t.toString());
            h.children[j] = t;//此处插入成功
            h.m++;//值的数量加一
            if(h.m < M) return null;
                //如果节点已满  则执行分类操作（从根节点开始）
            else return split(h);
        }
    
        private Node split(Node h) {
            //将已满节点h的后，一般M/2节点后的节点分裂到新节点并返回
            Node t = new Node(M/2);
            h.m = M / 2;
            for(int j=0; j<M/2; j++){
                t.children[j] = h.children[M/2+j];//把h节点中M/2节点后的节点分裂到新节点
                h.children[M/2+j] = null;//把h节点中M/2节点后的节点设置为空，以尽快GC
            }
            return t;//返回新节点
        }
    
        /**
         * 删除数据
         * @param key
         */
        public void remove(Key key){
            remove(root, key, height);
    
        }
    
        private void remove(Node x, Key key, int ht){
            Entry[] children = x.children;//首次进入，相当于根节点
            //外部节点  这里使用顺序查找
            //如果M很大  可以改成二分查找
            if(ht == 0){//到了有数据的子节点（也可能是根节点，如果键值对小于M），此次查询数据。
                for(int j=0; j<x.m; j++){
                    if(equal(key, x.children[j].key)){//遍历查询
                        children[j] = null;//删除此节点数据
                        x.m--;//值的数量减一
                    }
                }
            }
            //内部节点  寻找下一个节点
            else{
                for(int j=0; j<x.m; j++){
                    //最后一个节点  或者 插入值小于某个孩子节点值
                    if(j+1==x.m || less(key, x.children[j+1].key))//定位数据在哪个节点下，然后继续递归查询
                         remove(x.children[j].next, key, ht-1);//去下一层继续查询
                }
            }
        }
    
        private boolean equal(Comparable k1, Comparable k2){
            return k1.compareTo(k2)==0;
        }
    
        private boolean less(Comparable k1, Comparable k2){
            return k1.compareTo(k2)<0;
        }
    
        public String toString() {
            return toString(root, height, "") + "\n";
        }
    
        private String toString(Node h, int ht, String indent) {
            StringBuilder s = new StringBuilder();
            Entry[] children = h.children;//此数据相当于根节点
    
            //外部节点
            if (ht == 0) {
                for (int j = 0; j < h.m; j++) {
                    s.append(indent + children[j].key + " " + children[j].val + "\n");
                }
            }
            else {
                for (int j = 0; j < h.m; j++) {
                    s.append(indent + "(" + children[j].key + ")\n");
                    s.append(toString(children[j].next, ht-1, indent + "     "));
                }
            }
            return s.toString();
        }
    
    }

2、分析测试添加数据put方法：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 2][]

insert等方法可以去代码里查看，下面进行main方法测试打印：

public static void main(String[] args) {
          
            /**
             * 添加的顺序不同，最后树的结构也不同
             */
            CatalogBTree<Integer,String> bt = new CatalogBTree<>();
            bt.put(5,"a");
            bt.put(8,"b");
            //     bt.put(9,"c");
            bt.put(10,"d");
            bt.put(15,"e");
            //     bt.put(18,"f");
            bt.put(20,"g");
            bt.put(26,"h");
            //      bt.put(27,"i");
    
            bt.put(28,"i");
            bt.put(30,"j");
            //      bt.put(33,"k");
            bt.put(35,"l");
            bt.put(38,"m");
            //    bt.put(50,"n");
            bt.put(56,"o");
            bt.put(60,"p");
            //      bt.put(63,"q");
    
            bt.put(65,"r");
            bt.put(73,"s");
            //       bt.put(79,"t");
            bt.put(80,"u");
            bt.put(85,"v");
            //   bt.put(88,"w");
            bt.put(90,"x");
            bt.put(96,"y");
            bt.put(99,"z");
    
    
            /**
             * 插入第三个元素
             */
            bt.put(9,"c");
            bt.put(18,"f");
            bt.put(27,"i");
            bt.put(33,"k");
            bt.put(50,"n");
            bt.put(63,"q");
            bt.put(79,"t");
            bt.put(88,"w");
    
            System.out.println("高度："+bt.height());
            System.out.println("查询："+bt.get(9));
            System.out.println( bt.toString());
        }

用此种顺序添加，最后的结构图是这样的：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1][]

控制台打印也可以验证：（自己可以测试验证）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 3][]

一张没有截完，在来一张

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 4][]

注意：添加节点时经常会出现分裂节点，这块一定要详细琢磨。  比如添加一个34 节点：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 5][]

添加的后面过程中会分裂出一个新的节点；如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 6][]

3、分析测试查询数据get方法：比如get(99),会一直向下循环，循环三次就找到；代码如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 7][]

4、分析测试删除数据remove方法：此方法和get方法类似，遍历找到后设置为空就行，然后数值减一，如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 8][]

删除节点时可能出现合并节点，

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 9][]

比如现在删除一个 80 节点：删除后此处还有一个分支，然后就会合并到左边，如图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 10][]

到此，B+树的原理和实现分析告一段落。

另外，B/B+树经常用做数据库的索引，这方面推荐您直接看张洋的[MySQL索引背后的数据结构及算法原理][MySQL] 这篇文章，这篇文章对MySQL中的如何使用B+树进行索引有比较详细的介绍，推荐阅读。

# 总结 #

在前面两篇文章介绍了平衡查找树中的[2-3树][2-3]，[红黑树][Link 3]之后，本文介绍了文件系统和数据库系统中常用的B/B+ 树，他通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少IO操作。他广泛用于文件系统及数据库中，如：

*  Windows：HPFS文件系统
 *  Mac：HFS，HFS+文件系统
 *  Linux：ResiserFS，XFS，Ext3FS，JFS文件系统
 *  数据库：ORACLE，MYSQL，SQLSERVER等中

希望本文对您了解B/B+ 树有所帮助。参考文章如下：

[参考][Link 4]

[参阅][Link 5]

[参考文章][Link 2]

[Link 1]: https://blog.csdn.net/nandao158/article/details/114065093
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70]: /images/20221022/8c47a81363194394b2115531c898e6af.png
[89f1cb27d14ebbd147cfa87fb5d10ea7.png]: /images/20221022/a987f368a17f45bfb73a4a2b90eb969b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1]: /images/20221022/c10944f4e13648e6be401f4e880ca541.png
[Link 2]: https://www.cnblogs.com/vincently/p/4526560.html
[4c27b7e3bb7440019f3cc9d032cb122e.png]: /images/20221022/4f605dc7b8f04e82aca144536612c4c9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 2]: /images/20221022/e33148cc0fd64c5785398f3d8740eedf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 3]: /images/20221022/415f9d98b7eb423d8f9cc4aafd5b0afe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 4]: /images/20221022/9ba99e06cdb34ceeb887707610c0d401.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 5]: /images/20221022/f8fcfa24ae9142b2a30a5ed266535cc8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 6]: /images/20221022/cb00f83a19ef48669bb5262859e245b6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 7]: /images/20221022/95455a59e1ed43a6bbed82b4b236bfcc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 8]: /images/20221022/005a4e6d56fe4ceb961251f7c0250ab0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 9]: /images/20221022/d4737fbb639f4409bc0c6f0ff78afc85.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 10]: /images/20221022/76ba2c462954426b94aaa7a0582f4848.png
[MySQL]: http://blog.codinglabs.org/articles/theory-of-mysql-index.html
[2-3]: http://www.cnblogs.com/yangecnu/p/Introduce-2-3-Search-Tree.html
[Link 3]: http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html
[Link 4]: https://blog.csdn.net/u014106644/article/details/90174332
[Link 5]: https://blog.csdn.net/qq_33171970/article/details/88395278