数据结构与算法——20.B-树

这篇具有很好参考价值的文章主要介绍了数据结构与算法——20.B-树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

这篇文章我们来讲解一下数据结构中非常重要的B-树。

目录

1.B树的相关介绍

1.1、B树的介绍

1.2、B树的特点

2.B树的节点类

3.小结


1.B树的相关介绍

1.1、B树的介绍

在介绍B树之前,我们回顾一下我们学的树。

首先是二叉树,这个不用多说,然后为了查找的效率,我们提出了搜索二叉树(或者称为二叉搜索树),就是节点类加个key值,然后左边小右边大的那个。然后为了避免极端情况的出现,就是二叉搜索树节点集中在一侧的情况,我们提出了平衡二叉树,就是带自旋的,可以左旋或者右旋的,高度差小于1的那种,平衡二叉树里面有AVL树和红黑树两种实现方式,注意,平衡二叉树是在二叉搜索树的基础上提出的,所以平衡二叉树也叫平衡二叉搜索树

下面介绍一下B树。

B-树是一种自平衡的多路查找树,注意: B树就是B-树,"-"是个连字符号,不是减号 。

在大多数的平衡查找树(Self-balancing search trees),比如 AVL树 和红黑树,都假设所有的数据放在主存当中。那为什么要使用 B-树呢(或者说为啥要有 B-树呢)?要解释清楚这一点,我们假设我们的数据量达到了亿级别,主存当中根本存储不下,我们只能以块的形式从磁盘读取数据,与主存的访问时间相比,磁盘的 I/O 操作相当耗时,而提出 B-树的主要目的就是减少磁盘的 I/O 操作

大多数平衡树的操作(查找、插入、删除,最大值、最小值等等)需要 O(ℎ)次磁盘访问操作,其中 ℎ 是树的高度。但是对于 B-树 而言,树的高度将不再是log(n)(n为数中节点的个数),而是一个我们可控的高度 ℎ (通过调整 B-树中结点所包含的键【你也可以叫做数据库中的索引,本质上就是在磁盘上的一个位置信息】的数目,使得 B-树的高度保持一个较小的值)一般而言,B-树的结点所包含的键的数目和磁盘块大小一样,从数个到数千个不等。由于B-树的高度 h 可控(一般远小于log(n)),所以与 AVL 树和红黑树相比,B-树的磁盘访问时间将极大地降低。

我们之前谈过红黑树与AVL树相比较,红黑树更好一些,这里我们将红黑树与B-树进行比较,并以一个例子对上面一段的内容进行解释。

假设我们现在有 838,8608 条记录,对于红黑树而言,树的高度 ℎ=log⁡(838,8608)=23 ,也就是说树的高度为23,也就是说如果要查找到叶子结点需要 23 次磁盘 I/O 操作;但是 B-树,情况就不同了,假设每一个结点可以包含 8 个键(当然真实情况下没有这么平均,有的结点包含的键可能比8多一些,有些比 8 少一些),那么整颗树的高度将最多 8 ( log8⁡(838,8608)=7.8 ) 层,也就意味着磁盘查找一个叶子结点上的键的磁盘访问时间只有 8 次,这就是 B-树提出来的原因所在。

1.2、B树的特点

下面讲一下B树的特点

在讲B树的特点之前,我们先来了解几个概念

度:degree 指树中节点的孩子数

阶:order 指所有节点中孩子数最大值

B树的特点:

  1. 每个节点最多有m个孩子,其中m称为B-树的阶;(孩子数目的上限)
  2. 除根节点和叶子节点外,其他节点至少有 ceil(m/2) (阶数除以2向上取整)个孩子,就是说B树中节点最大有m个孩子即阶个孩子,至少有 m/2(向上取整) 个孩子;(孩子数目的下限)
  3. 若根节点不是叶子节点,则至少有两个孩子;(根节点孩子数的下限)
  4. 所有叶子节点都在同一层;(B树是否平衡的前提条件)
  5. 每个非叶子节点由 n 个关键字(就是n个关键值,参考二叉搜索树中的关键值)和 n+1 个指针(就是n+1个孩子)组成,其中 ceil(m/2)-1 <= n <= m-1;
  6. 关键字按非降序排列(就是升序排列,和二叉树搜索相同),即节点中的第 i 个关键字大于等于第 i-1 个关键字;
  7. 指针P[ i ] 指向关键字值位于第 i 个关键字和第 i+1 个关键字之间的子树;

这些特性都要理解。看一下一个B树的实例:

数据结构与算法——20.B-树,数据结构与算法,b树,数据结构

2.B树的节点类

下面,我们来看一下B树的具体实现吧

package Tree;

import java.util.Arrays;

public class L5_BTree {

    //B数的节点类
    static class Node{

        int[] keys; //关键字,即关键值,排序用的
        Node[] children; //孩子,存孩子用的节点类数组
        int keyNumber; //有效关键字数目(就是真正存了几个关键字)
        boolean leaf = true; //是否是叶子节点
        int t; //最小度数(最小孩子数)

        //构造函数
        public Node(int t) { // t >= 2
            this.t = t;//手动设置最小孩子数
            this.children = new Node[2 * t];//最大孩子数是最小孩子数的二倍
            this.keys = new int[2 * t -1];//关键字的最大数量 是 最大孩子数-1
        }

        @Override
        public String toString() {
            return Arrays.toString(Arrays.copyOfRange(keys,0,keyNumber));
        }

        //多路查找,就是我给你一个关键值,你返回这个关键值对应的节点
        Node get(int key){
            int i = 0; //设置个变量i,方便用来循环遍历
            while (i < keyNumber){ //节点中有关键字
                if (keys[i] == key){ //如果节点中的关键字 等于 我给出的关键字,那就返回这个关键字对应的节点
                    return this;
                }
                if (keys[i] > key){ //如果关键字中的最小值都比给出的大,那就直接退出这个节点的循环了
                    break;
                }
                i++; //变量i自增
            }
            //执行到这里,就是说当前节点的关键字一定比给出的大,或者说,超出索引了,即keys[i]>key 或 i == keyNumber
            if (leaf){ //如果是叶子节点,那就肯定没有孩子了
                return null;
            }
            //这种情况就是 i == keyNumber 了,就找这个节点所对应的孩子了(孩子数比节点关键值数多1)
            return children[i].get(key);
        }

        //写一个方法,向 keys 指定索引 index 处插入 key
        void insertKey(int key, int index){
            for (int i = keyNumber-1; i >= index ; i--) {
                keys[i+1] = keys[i];
            }
            keys[index] = key;
            keyNumber++;
        }

        //写一个方法,向 children 指定索引 index 处插入 child
        void insertChild(Node child, int index){
            System.arraycopy(children,index,children,index+1,keyNumber);
            children[index] = child;
        }

        //移除指定index处的key
        int removeKey(int index){
            int t = keys[index];
            System.arraycopy(keys,index+1,keys,index,--keyNumber-index);
            return t;
        }
        //移除最左边的key
        int removeLeftmostKey(){
            return removeKey(0);
        }
        //移除最右边的key
        int removeRightmostKey(){
            return removeKey(keyNumber-1);
        }


        //移除指定index处的child
        Node removeChild(int index){
            Node node = children[index];
            children[index] = null;
            return children[index];
        }
        //移除最左边的child
        Node removeLeftmostChild(){return removeChild(0);}
        //移除最右边的child
        Node removeRightmostChild(){return removeChild(keyNumber);}

        //返回index孩子处左边的兄弟
        Node childLeftSibling(int index){
            return index > 0 ? children[index-1]:null;
        }
        //返回index孩子处右边的兄弟
        Node childRightSibling(int index){
            return index == keyNumber ? null : children[index+1];
        }

        //复制当前节点的所有key和child到target
        void moveToTarget(Node target){
            int start = target.keyNumber;
            if (!leaf){
                for (int i = 0; i <= keyNumber; i++) {
                    target.children[start+i] = children[i];
                }
            }
            for (int i = 0; i < keyNumber; i++) {
                target.keys[target.keyNumber++] = keys[i];
            }
        }

    }


    Node root; //定义一个根节点
    int t; //树中节点的最小度数(就是一个节点的最小孩子数,根节点叶子节点除外)
    final int MIN_KEY_NUMBER;//最小关键字的数量
    final int MAX_KEY_NUMBER;//最大关键字的数量

    //无参构造,最小度数默认值为2
    public L5_BTree() {
        this(2);
    }
    //有参构造
    public L5_BTree(int t) {
        this.t = t;
        root = new Node(t);//new出根节点,并给出根节点最小度数
        MIN_KEY_NUMBER = t-1;
        MAX_KEY_NUMBER = 2*t-1;
    }

    //判断关键字中是否存在指定关键字对应的节点
    public boolean contains(int key){
        return root.get(key) != null;
    }

    //新增一个关键字
    /**描述一下流程吧
     * 你构造一颗B树,给定了最小度数,那么最小关键字数、最大关键字数、阶数也就都定了
     * 你开始往节点中插入关键值,一开始没满,你继续插入
     * 当插入的关键字数等于最大关键字数时,这个节点就要分裂了,即将自身的关键字分出去,变为孩子节点
     * 然后你再插入,它就会按照关键字的顺序去选位置,
     * 如果找到位置了,是叶子节点,那么就直接插入(当然超过MAX_KEY_NUMBER就分裂一下)
     * 如果恰好发现一个非叶子节点里面也有位置,那么应该先搜索一下这个节点的孩子,然后再进行判断插在哪里
     * 当某个节点的关键字数再满,那这个树就再分裂一次
     * */
    public void put(int key){
        doPut(root,key,null,0);
    }
    //递归的函数
    private void doPut(Node node,int key,Node parent,int index){
        int i = 0;
        while (i < node.keyNumber){
            if (node.keys[i] == key){
                return; //更新逻辑
            }
            if (node.keys[i] > key){
                break; //找到插入位置,记为i
            }
            i++;
        }
        if (node.leaf){
            node.insertKey(key,i);
            //可能到达上限
        }else {
            doPut(node.children[i],key,node,i);
            //可能到达上限
        }
        if (node.keyNumber == MAX_KEY_NUMBER){
            split(node,parent,index);
        }
    }

    //分裂函数
    /**
     * left:要分裂的节点
     * parent:分裂节点的父节点
     * index:分裂节点是第几个孩子
     * */
    private void split(Node left, Node parent, int index){
        if (parent == null){//分裂的是根节点
            Node newRoot = new Node(t);
            newRoot.leaf = false;
            newRoot.insertChild(left,0);
            this.root = newRoot;
            parent = newRoot;
        }

        //1.创建right节点,把left中t之后的key和child移动过去
        Node right = new Node(t);
        right.leaf = left.leaf;
        System.arraycopy(left.keys,t,right.keys,0,t-1);

        //分裂节点是非叶子节点的情况
        if (!left.leaf){
            System.arraycopy(left.children,t,right.children,0,t);
        }
        right.keyNumber = t-1;
        left.keyNumber = t-1;

        //2.中间的key(t-1处)插入到父节点中
        int mid = left.keys[t-1];
        parent.insertKey(mid,index);

        //3.right节点作为父节点的孩子
        parent.insertChild(right,index+1);
    }


    //删除一个关键字
    public void remove(int key){doRemove(null,root,0,key);}

    private void doRemove(Node parent,Node node,int index,int key){
        int i = 0;
        while (i < node.keyNumber){
            if (node.keys[i] >= key){
                break;
            }
            i++;
        }
        //找到了,代表待删除key的索引
        //没找到,表示到第 i 个孩子里面继续查找
        if (node.leaf){
            if(!found(node, key, i)){//case1
                return;
            }else {//case2
                node.removeKey(i);
            }
        }else {
            if(!found(node, key, i)){//case3
                doRemove(node,node.children[i],i,key);
            }else {//case4
                Node s = node.children[i+1];
                while (!s.leaf){
                    s = s.children[0];
                }
                int skey = s.keys[0];
                node.keys[i] = skey;
                doRemove(node,node.children[i+1],i+1,skey);
            }
        }
        if (node.keyNumber < MIN_KEY_NUMBER){
            //调整平衡 case5 and case6
            balance(parent,node,index);
        }

    }
    private void balance(Node parent, Node x, int i){
        //case6 根节点
        if (x == root){
            if (root.keyNumber == 0 && root.children[0] != null){
                root = root.children[0];
            }
            return;
        }
        Node left = parent.childLeftSibling(i);
        Node right = parent.childRightSibling(i);
        if (left != null && left.keyNumber > MAX_KEY_NUMBER){
            //case5-1 左边富裕 右旋
            //把父节点中前驱key旋转下来
            x.insertKey(parent.keys[i-1],0);
            if (!left.leaf){
                //left中最大的孩子换爹
                x.insertChild(left.removeRightmostChild(),0);
            }
            //left中最大的key旋转上去
            parent.keys[i-1] = left.removeRightmostKey();
            return;
        }
        if (right != null && right.keyNumber > MAX_KEY_NUMBER){
            //case5-2 右边富裕 左旋
            //把父节点中后继key旋转下来
            x.insertKey(parent.keys[i],x.keyNumber);
            //right中最小的孩子换爹
            if (!right.leaf){
                x.insertChild(right.removeLeftmostChild(),x.keyNumber+1);
            }
            //right中最小的key旋转上去
            parent.keys[i] = right.removeLeftmostKey();
            return;
        }
        //case5-3 两边都不富裕 向左合并
        if(left != null){
            //向左兄弟合并
            parent.removeChild(i);
            left.insertKey( parent.removeKey(i-1), left.keyNumber);
            x.moveToTarget(left);
        }else {
            //自己合并
            parent.removeChild(i+1);
            x.insertKey(parent.removeKey(i),x.keyNumber );
            right.moveToTarget(x);
        }

    }
    private boolean found(Node node, int key, int i) {
        return i < node.keyNumber && node.keys[i] == key;
    }


}

为了对应代码中插入和删除的逻辑思路,下面给出两张图来看一下。

节点中插入key值后的节点分裂展示图:

数据结构与算法——20.B-树,数据结构与算法,b树,数据结构

在节点中删除key的6种情况展示图(删除的是某个节点的key):

数据结构与算法——20.B-树,数据结构与算法,b树,数据结构

3.小结

说实话,我感觉这东西挺难的,写完之后脑瓜子都嗡嗡的。没有在纸上画图,单靠脑子想,我是肯定写不出来的,所以我的建议是:一定一定一定要画图,一定一定一定要看着图对着代码来一步一步的走,一定一定一定要看图!文章来源地址https://www.toymoban.com/news/detail-851931.html

到了这里,关于数据结构与算法——20.B-树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构和算法——数据结构

    目录 线性结构  队列结构的队列 链表结构的队列 链表的面试题 单向链表应用场景 约瑟夫环问题 栈结构 中缀表达式 前缀表达式 后缀表达式 非线性结构 图 递归解决迷宫问题 递归解决八皇后问题 顺序存储方式,顺序表 常见的顺序存储结构有:数组、队列、链表、栈 链式存

    2024年02月07日
    浏览(53)
  • 数据结构与算法 --- 数据结构绪论

    早期人们都把计算机理解为数值计算工具,就是感觉计算机当然是用来计算的,所以计算机解决问题,应该是先从具体问题中抽象出一个适当的数据模型,设计出一个解此数据模型的算法,然后再编写程序,得到一个实际的软件。 可现实中,我们更多的不是解决数值计算的问

    2024年02月14日
    浏览(52)
  • 数据结构与算法——数据结构有哪些,常用数据结构详解

    数据结构是学习数据存储方式的一门学科,那么,数据存储方式有哪几种呢?下面将对数据结构的学习内容做一个简要的总结。 数据结构大致包含以下几种存储结构: 线性表,还可细分为顺序表、链表、栈和队列; 树结构,包括普通树,二叉树,线索二叉树等; 图存储结构

    2024年02月15日
    浏览(60)
  • 数据结构与算法——什么是数据结构

    当你决定看这篇文章,就意味着系统学习数据结构的开始。下面我们先来讲什么是数据结构。 数据结构,直白地理解,就是研究数据的存储方式。 我们知道,数据存储只有一个目的,即为了方便后期对数据的再利用,就如同我们使用数组存储  {1,2,3,4,5}  是为了后期取得它们

    2024年02月15日
    浏览(53)
  • 【数据结构与算法】不就是数据结构

      嗨喽小伙伴们你们好呀,好久不见了,我已经好久没更新博文了!之前因为实习没有时间去写博文,现在已经回归校园了。我看了本学期的课程中有数据结构这门课程(这么课程特别重要),因为之前学过一点,所以就想着深入学习一下子。毕竟这门课程对于 考研 和 就业

    2024年02月07日
    浏览(48)
  • 【数据结构与算法】1.数据结构绪论

    📚博客主页:爱敲代码的小杨. ✨专栏:《Java SE语法》 ❤️感谢大家点赞👍🏻收藏⭐评论✍🏻,您的三连就是我持续更新的动力❤️ 🙏小杨水平有限,欢迎各位大佬指点,相互学习进步! 数据结构是计算机中存储、组织数据的方式。 数据结构是一种具有一定逻辑关系,

    2024年01月23日
    浏览(52)
  • 【数据结构与算法】一、数据结构的基本概念

    抽象数据类型(ADT)定义举例:Circle的定义 如何处理杂乱无章且多样化的数据: 数据元素 :数据中的个体被称为数据元素。 数据对象 :性质相同的数据元素组成的集合。 数据结构 :数据元素加上数据元素之间的关系,就形成了数据结构。 逻辑结构 :数据结构的逻辑模型。

    2023年04月17日
    浏览(96)
  • 数据结构--》掌握数据结构中的查找算法

            当你需要从大量数据中查找某个元素时,查找算法就变得非常重要。         无论你是初学者还是进阶者,本文将为你提供简单易懂、实用可行的知识点,帮助你更好地掌握查找在数据结构和算法中的重要性,进而提升算法解题的能力。接下来让我们开启数据

    2024年02月08日
    浏览(54)
  • 数据结构--》掌握数据结构中的排序算法

            当我们面对海量数据时,如何高效地将其排序是数据结构领域中一个重要的问题。排序算法作为其中的关键部分,扮演着至关重要的角色。         无论你是初学者还是进阶者,本文将为你提供简单易懂、实用可行的知识点,帮助你更好地掌握排序算法在数据

    2024年02月08日
    浏览(42)
  • 数据结构--》从数据结构开始,打好算法基础

    目录 数据结构的基本概念 数据结构的三要素 算法的基本概念 数据结构的基本概念         在学习某个知识之前,我们是否都有问过自己我们到底在学习的目的是什么?学习数据结构也一样,我们学习数据结构 主要是为了 用程序把现实世界的问题信息化;用计算机高效

    2024年02月09日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包