B-树——Java高阶数据结构（详细版）

目录

一.学习B-树的原因

二.B-树的概念

三.B-树的插入分析

四.B-树的插入代码实现(包含B-树的简单验证）

五.B-树的性能分析

六.B+树和B*树

七.总结

八.B-树的应用

正文

一.学习B-树的原因

1.1基本搜索结构

以上数据结构只适用于数据量不是特别大的时候，如果数据量特别大，一次性无法加载到内存中，使用上述结构就不是很方便。比如使用平衡树搜索一个大文件，，效率低。

1.2B-树的引入

上面方法其实只在内存中保存了每一项数据信息中需要查找的字段以及数据在磁盘中的位置，整体的数据实际也在磁盘中。
缺陷：

• 1. 树的高度比较高，查找时最差情况下要比较树的高度次
• 2. 数据量如果特别大时，树中的节点可能无法一次性加载到内存中，需要多次IO
     那如何加速对数据的访问呢？
• 1. 提高IO的速度
• 2. 降低树的高度—多叉树平衡树

二.B-树的概念

1970年，R.Bayer和E.mccreight提出了一种适合外查找的树，它是一种平衡的多叉树，称为B树(有些地方写的是B-树，注意不要误读成"B减树")。一棵M（M>2)阶的B树，是一棵平衡的M路平衡搜索树，可以是空树或者满足以下性质的树：

• 1.根节点至少有两个孩子。
• 2.每个非根节点至少有（M/2-1）（M/2向上取整）个关键字，至多有M-1个关键字，并且以升序排列（当数据类型为数值时，若 数据类型不为数值类型，我们则需要重写comparator比较器）。
  （如9/2-1，9/2=4.5，向上取整5，所以9/2-1=4）
• 3.每个非根节点至少有M/2（向上取整）个孩子，至多有M个孩子。
• 4.每个根节点key[i]和key[i=1]之间的孩子的值介于key[i]和key[i+1]之间。
• 5.所有叶子节点都在同一层。

三.B-树的插入分析

为了简单起见，假设M=3，即三叉树，每个节点中存储两个数据，两个数据可以将区间分割成三部分，因此节点应该有三个孩子，为了后续实现简单，节点的结构如下：

注意：三叉树结构原本为图一，但是我们为了后续的分裂方便，我们在三叉树的基础上通过代码给三叉树每个节点分别多分配一个关键字和孩子（图二）。尽管多分配了，但是实际上该树依旧是三叉树，M依旧为3，而非四叉树。所以当关键字>M-1，即2时便需要进行分裂（拆分）。 我们为什么采用多分配一个关键字和一个孩子的方法呢？原因如下：
一：背景设定：

• 这是一个M=3的B-树
• 按照B-树的定义
  • 每个节点至多有M-1个关键字
  • 每个节点至多有M个孩子
• 正常的节点数组大小应该是：
  • 关键字数组：大小2
  • 孩子数组：大小3
    ** 二：如果不多分配会有什么问题？**
• 假设你严格定义：
  关键字数组大小2，孩子数组大小3.
  现在向一个已满的节点（已经有两个关键字）插入一个新节点，比如向{53,75}中插入60.
  不多分配的做法：
• 1.当前节点没有空位放60
• 2.你必须：
  • 2.1创建一个新节点
  • 2.2将中间节点（60）提到父节点
  • 2.3让比中间节点小的（53）留在旧节点
  • 2.4把比中间节点大的（75）放到新节点
    此时存在问题如下，以及多分配的好处：
    **不多分配，**意味着分裂必须在“没有临时存储空间”的条件下完成，导致插入和分裂必须嵌套执行。数据还分散在两处，所以代码里要有临时构造，手动排序，特殊递归处理等操作，代码逻辑复杂。多分配一个关键字和孩子时，插入只需要通过插入排序迅速插入到合适的位置，分裂只管“拆”，效率高，逻辑也简单。

注意：孩子永远比数据（关键字）多一个。

• 插入的过程中可能需要分裂，分裂的前提是：
  • 假设，当前是要组成一个M路查找树，关键字数必须<=M-1;当关键字数必须>M-1时则需要对节点进行拆分。
  • 拆分节点的规则是：
    • 把中间的元素提取出来，放到父亲节点上，左边的单独构成一个节点，右边的也单独构成一个节点。
      **以{53, 139, 75, 49, 145, 36, 101}构建B树的过程如下：
  • 1.插入53
    
    2.插入139
    

3.插入75

此时关键字数量为3>M-1需要对节点进行分裂：
由于该节点即为根节点，所以需要新创建两个新节点（非根节点分裂只需要新创建一个新节点即可）
1.中间节点75，往父节点（创建的）提
2.比中间节点小的53留在旧节点
3.比中间节点大的139放到新节点
分裂结果如下

4.插入49

5.插入145

6.插入36

此时关键字数3>M-1=2,所以进行分裂：
1.中间节点49，往父节点提
2.比中间节点小的36留在旧节点
3.比中间节点大的53放到新节点

分裂结果如下：

7.插入101

此时child3节点需要分裂：
1.中间节点139往父节点提
2.101留在旧节点
3.145放到新的节点
结果如下：

此时父节点也需要进行分裂，关键字数3>M-1=2：
分裂逻辑同上，结果如下：

分裂思路总结：
1.如果树是空的，直接插入新节点中，该节点为B-树的根节点
2.树非空，找到待插入的元素在树中合适的位置（注意：找到的节点位置一定在叶子节点）
3.检测是否找到插入位置（假设数中的key是唯一的，即该元素已经存在时则不插入）
4.按照插入排序的思想将该元素插入到找到的节点中
5.检测该节点是否满足B-树的性质：即该节点中的元素个数是否等于M,如果小于则满足
6.如果插入后节点不满足B-树的性质，需要对该节点进行分裂：

• 6.1申请插入新节点
• 6.2找到该节点的中间位置
• 6.3将中间节点左侧的元素和孩子孩子留在旧节点，右侧元素及孩子放到新节点
• 6.4将中间节点元素以及新节点往该节点的双亲节点插入，即继续4
  7.如果向上已经分裂到根节点位置，插入结束。
  结论：
  1.B-树的分裂是横向分裂的
  2.只有当父节点发生分裂时，才会增加树的高度

四.B-树的插入代码实现(包含B-树的简单验证）

public class MyBTree {
    static class BTNode{
        public int[] keys;
        public BTNode[] subs;
        BTNode parent;
        public int usedSize;

        public BTNode() {
            this.keys = new int[M];//多分配一个关键字
            this.subs = new BTNode[M+1];//多分配一个孩子
        }
    }
    public static final int M=3;//三叉树为例
    public BTNode root;
    
    //插入操作
    public boolean insert(int key){
        if(root==null){
            root=new BTNode();
            root.keys[0]=key;
            root.usedSize++;
            return true;
        }
        //不为空则需要检查当前B-树中是否存在key
        Pair<BTNode,Integer> pair=find(key);
        if(pair.getVal()!=-1){
            return false;
        }
        //返回-1说明不存在，此时进行插入操作
        BTNode parent=pair.getKey();
        int index=parent.usedSize-1;
        for(;index>=0;index--){
            if(parent.keys[index]>=key){
                parent.keys[index+1]=parent.keys[index];
            }else{
                break;
            }

        }
        parent.keys[index+1]=key;
        parent.usedSize++;
        if(parent.usedSize<M){
            //没有满
        }else{
            split(parent);
        }
        return true;
    }

    private void split(BTNode cur) {
        //创建新节点存放比中间节点大的
        BTNode newNode=new BTNode();
        //记录当前节点的父亲节点
        BTNode parent=cur.parent;
        //开始挪动数据
        int mid=cur.usedSize>>1;
        int i=mid+1;
        int j=0;
        for(;i< cur.usedSize;i++){
            newNode.keys[j]=cur.keys[i];
            newNode.subs[j]=cur.subs[i];
            //处理刚刚拷贝过来的孩子节点的父亲节点为newNode
            if(newNode.subs[j]!=null){
                newNode.subs[j].parent =newNode;
            }
        }
        //当newNode.subs[j]!=null时再次复制，保证key【i】的左右subs都随节点复制过去
        j++;
        newNode.subs[j]=cur.subs[i];
        if(newNode.subs[j]!=null){
            newNode.subs[j].parent =newNode;
        }
        //处理newNode的有效数据个数
        newNode.usedSize=j;
        //处理cur的有效数据个数   这里的-1是指接下来要处理的中间节点
        cur.usedSize= cur.usedSize-j-1;
        //处理特殊情况：当cur为根节点时
        if(cur==root){
            root=new BTNode();
            root.keys[0]=cur.keys[mid];
            root.subs[0]=cur;
            root.subs[1]=newNode;
            root.usedSize=1;
            cur.parent=root;
            newNode.parent=root;
            return;
        }
        //更新当前父亲节点
        int endT= parent.usedSize-1;
        int midVal=cur.keys[mid];
        for(;endT>=0;endT--){
            if(parent.keys[endT]>midVal){
                parent.keys[endT+1]=parent.keys[endT];
                parent.subs[endT+2]=parent.subs[endT+1];
            }else{
                break;
            }
        }
        parent.keys[endT+1]=midVal;
        parent.subs[endT+1]=cur;
        //当前父节点新增指向newNode的指针
        parent.subs[endT+2]=newNode;
        parent.usedSize++;
        if(parent.usedSize>=M){
            split(parent);
        }
    }

    private Pair<BTNode,Integer> find(int key){
        BTNode parent=null;
        BTNode cur=root;
        while(cur!=null){
            int i=0;
            while(i<cur.usedSize){
                if(cur.keys[i]==key){
                    return new Pair<>(cur,i);
                }else if(cur.keys[i]<key){
                    i++;
                }else{
                    break;
                }
            }
            parent=cur;
            cur=cur.subs[i];
        }
        return new Pair<>(parent,-1);
    }

    //中序遍历简单验证结果
    private void inord(BTNode root) {
        if(root==null){
            return;
        }
        for(int i=0;i<root.usedSize;i++){
            inord(root.subs[i]);
            System.out.print(root.keys[i]+" ");
        }
        inord(root.subs[root.usedSize]);
    }

    public static void main(String[] args) {
        MyBTree myBTree=new MyBTree();
        int[] array=new int[]{53, 139, 75, 49, 145, 36, 101};
        for(int i=0;i< array.length;i++){
            myBTree.insert(array[i]);
        }
        System.out.println("输出结果");
        //中序遍历验证结果
        myBTree.inord(myBTree.root);
    }

}

五.B-树的性能分析

我们知道B-树的分裂横向的，当数据量非常大的时候，我们一半取M=1024，如此
第一层：可以存储1023个数据
第二层：10241023
第三层：102410241023(达10亿）
第四层：1024102410241023
……

六.B+树和B*树

B+树

B+树是B-树的变形，也是一种多路搜索树：
1.其概念基本和B-树相同，除了：
2.非叶子节点的子树指针数量与关键字的数量相同（B-树的关键字比子树指针数量少1）。
3.非叶子节点的字数指针P[i]，指向关键字数值属于[key[i],key[i+1])（左闭右开）的子树。
4.给所有叶子节点增加链指针。
5.所有关键字都在叶子节点出现。

B+树的搜索与B-树基本相同，区别是B+树只有达到叶子节点才能命中（而B-树可能在非叶子节点即可命中），其性能也等价于在关键字全集中做一次二分查找（logN).
B+树的特性：
1.所有关键字都出现在叶子节点的链表当中（稠密索引），且链表的节点都是有序的。
2.要查找的数据不可能在非叶子节点中命中。
3.非叶子节点相当于叶子结点的索引（稀疏索引），叶子节点层相当于存储数据的数据层。
4.B+适合用于文件索引系统。

B*树``

B树是B+树的变形，在B+树的非根和非叶子节点增加指向兄弟的指针。
B树定义了非叶子节点关键字数量至少为（2/3)M，即块的最低利用率为2/3（代替B+树的1/2）。

B+树的分裂：
当一个节点满时，创建一个新的节点，把原节点的1/2数据移到新链表中，再在父节点中增加指向新节点的指针；B+树的分裂只影响原节点和父节点，而不会影响兄弟节点，所以不需要指向的兄弟指针。
B树的分裂：
当一个节点满了，不是立刻进行分裂，而是先检查它的兄弟直接点是否都满了，如果未满，那么将一部分数据移到兄弟节点，再在原节点插入关键字，最后修改父节点的兄弟节点的关键字（因为兄弟节点的关键字范围改变了）；如果兄弟节点都满了，则在原节点和兄弟节点之间增加新节点，最后在父节点增加指向新节点的指针。
所以，B树分配节点的概率比B+树要低，空间利用率更高（1/2->2/3).

七.总结

• B-树：多路搜索树，每个节点存储M/2到M个关键字，非叶子节点存储指向关键字范围的子节点；所有关键字在整棵树中出现，且只出现一次，非叶子节点可能命中。
• B+树：在B-树的基础上，为叶子节点增加链表指针，所有关键字在叶子节点中出现，非叶子节点作为叶子节点的索引；B+树总是在叶子节点命中。
• B*树：在B+树的基础上，为非叶子节点也增加了链表指针，将节点的利用从1/2提升到2/3.

八.B-树的应用

(1)索引
B-树最常见的应用是用来做索引。索引通俗的来说就是为了方便用户快速找到所寻植物。比如：书记目录可以帮助读者迅速定位所查询的信息；hao1123网页导航网站，为了让用户能快速的找到有价值的分类网站，本质上就是互联网页面中的索引结构。
MYSQL官方对索引的定义为：索引是帮助MYSQL高效获取数据的数据结构，简单来说：索引就是数据结构。
当数据量很大时，为了能够方便管理数据，提高数据查询的效率，一般都会把数据存储在数据库中，因此数据库不仅仅是帮助用户管理数据，而且数据库系统还维护满足特定查找算法的数据结构，这些数据结构以某种方式引用数据，这样就可以在这些数据结构上实现高级查找算法，该数据结构就是索引。