精华内容
下载资源
问答
  • 数据结构 红黑的详解 红黑是具有下列着色性质的二叉查找: 1.每一个节点或者着红色,或者着黑色。 2.根是黑色的。 3.如果一个节点是红色的,那么它的子节点必须是黑色。 4.从一个节点到一个NULL指针的每一条...
  • 数据结构树(Tree)详解

    2021-03-30 13:29:23
    (tree)(Tree)的基本...是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的称为空(null或empty)。一棵非空的包括一个根结点,还(很可能)有多个附加结点,所有结点构成

    树(Tree)的基本概念

    定义

    树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点,还(很可能)有多个附加结点,所有结点构成一个多级分层结构
    例如:
    树的结构与自然树是倒过来的
    图 1(A) 是使用树结构存储的集合 {A,B,C,D,E,F,G,H,I,J,K,L,M} 的示意图。对于数据 A 来说,和数据 B、C、D 有关系;对于数据 B 来说,和 E、F 有关系。这就是“一对多”的关系。

    将具有“一对多”关系的集合中的数据元素按照图 1(A)的形式进行存储,整个存储形状在逻辑结构上看,类似于实际生活中倒着的树(图 1(B)倒过来),所以称这种存储结构为“树型”存储结构。

    树的结构

    结点:使用树结构存储的每一个数据元素都被称为“结点”。例如,图 1(A)中,数据元素 A 就是一个结点;

    父结点(双亲结点)、子结点和兄弟结点:对于图 1(A)中的结点 A、B、C、D 来说,A 是 B、C、D 结点的父结点(也称为“双亲结点”),而 B、C、D 都是 A 结点的子结点(也称“孩子结点”)。对于 B、C、D 来说,它们都有相同的父结点,所以它们互为兄弟结点。

    树根结点(简称“根结点”):每一个非空树都有且只有一个被称为根的结点。图 1(A)中,结点A就是整棵树的根结点。
    树根的判断依据为:如果一个结点没有父结点,那么这个结点就是整棵树的根结点。
    叶子结点:如果结点没有任何子结点,那么此结点称为叶子结点(叶结点)。例如图 1(A)中,结点 K、L、F、G、M、I、J 都是这棵树的叶子结点。此外还有以下属性:

    节点的度(degree):该节点子树的个数称为该节点的度。
    树的度:所有节点中,度的最大值称为树的度。
    非叶子节点:度不为零的节点。
    高度(height):当前节点到最远叶子节点的路径长,所有树叶的高度为零。
    深度(depth):对于任意节点n,n的深度为从根到n的唯一路径长。有些地方认为根深度为0,有些地方认为根深度为1。
    兄弟节点:具有相同父节点的节点互相称为兄弟节点。
    节点的层数(level):从根开始定义,根为第一层,根的子节点为第二层。以此类推。
    堂兄弟节点:父节点在同一层的节点互为堂兄弟。
    节点的祖先(ancestor):从根到该节点所经分支上的所有节点。
    子孙(descendant):以某节点为根的子树中任一节点都称为该节点的子孙。
    森林:由m(m >= 0)棵互不相交的树的集合称为森林。

    一般来说数据结构如下(Java)

    
    public class TreeNode<T> {
        public T value;
        public TreeNode<T> leftNode;
        public TreeNode<T> rightNode;
        //public List<TreeNode<T>> nodes;
    }
    
    

    二叉树

    二叉树是每个节点最多有两个子树的树结构,左侧子树节点称为“左子树”(left subtree),右侧子树节点称为“右子树”(right subtree)。每个节点最多有2个子节点的树(即每个定点的度小于3)

    二叉树的特点

    至少有一个节点(根节点)

    每个节点最多有两颗子树,即每个节点的度小于3。

    左子树和右子树是有顺序的,次序不能任意颠倒。

    即使树中某节点只有一棵子树,也要区分它是左子树还是右子树

    满二叉树

    除了叶子节点外每一个节点都有两个子节点,且所有叶子节点都在二叉树的同一高度上
    满二叉树

    完全二叉树

    如果二叉树中除去底层节点后为满二叉树,且底层节点依次从左到右分布,则此二叉树被称为完全二叉树。

    完全二叉树

    二叉查找树(Binary Search Tree - BST,又称二叉排序树、二叉搜索树)

    二叉查找树根节点的值大于其左子树中任意一个节点的值,小于其右子树中任意一节点的值,且该规则适用于树中的每一个节点。

    二叉查找树
    二叉查找树的查询效率介于O(log n)~O(n)之间,理想的排序情况下查询效率为O(log n),极端情况下BST就是一个链表结构(如下图),此时元素查找的效率相等于链表查询O(n)。

    二叉查找树需要注意的是删除节点操作时的不同情况,删除节点根据节点位置会有以下三种情况:

    删除节点的度为0,则直接删除

    删除节点的度为1,则该子节点替代删除节点

    删除节点的度为2,则从左子树中寻找值最大的节点替代删除节点。对树结构改动最少、节点值最进行删除节点值的必然是左子树中的最大叶子节点值与右子树中的最小叶子节点值
    平衡二叉搜索树 (Balanced binary search trees,又称AVL树、平衡二叉查找树)

    AVL树

    AVL树是最早被发明的自平衡二叉搜索树,树中任一节点的两个子树的高度差最大为1,所以它也被称为高度平衡树,其查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log n)。

    平衡二叉搜索树由Adelson-Velskii和Landis在1962年提出,因此又被命名为AVL树。平衡因子(平衡系数)是AVL树用于旋转平衡的判断因子,某节点的左子树与右子树的高度(深度)差值即为该节点的平衡因子。

    AVL树的特点

    具有二叉查找树的特点(左子树任一节点小于父节点,右子树任一节点大于父节点),任何一个节点的左子树与右子树都是平衡二叉树

    任一节点的左右子树高度差小于1,即平衡因子为范围为[-1,1] 如上左图根节点平衡因子=1,为AVL树;右图根节点平衡因子=2,固非AVL树,只是BST。
    为什么选择AVL树而不是BST?

    大多数BST操作(如搜索、最大值、最小值、插入、删除等)的时间复杂度为O(h),其中h是BST的高度。对于极端情况下的二叉树,这些操作的成本可能变为O(n)。如果确保每次插入和删除后树的高度都保持O(log n),则可以保证所有这些操作的效率都是O(log n)。

    二叉树的存储结构

    二叉树的存储结构有两种,分别为顺序存储和链式存储。本节先介绍二叉树的顺序存储结构。

    二叉树的顺序存储:

    指的是使用顺序表(数组)存储二叉树。需要注意的是,顺序存储只适用于完全二叉树。换句话说,只有完全二叉树才可以使用顺序表存储。因此,如果我们想顺序存储普通二叉树,需要提前将普通二叉树转化为完全二叉树。
    有读者会说,满二叉树也可以使用顺序存储。要知道,满二叉树也是完全二叉树,因为它满足完全二叉树的所有特征。

    普通二叉树转完全二叉树的方法很简单,只需给二叉树额外添加一些节点,将其"拼凑"成完全二叉树即可。如图 1 所示:
    普通二叉树
    左侧是普通二叉树,右侧是转化后的完全(满)二叉树。
    完全二叉树的顺序存储,仅需从根节点开始,按照层次依次将树中节点存储到数组即可

    在这里插入图片描述
    上图的数组存储结构
    存储由普通二叉树转化来的完全二叉树也是如此,例如上图普通二叉树,可以如此存储:
    普通二叉树的顺序存储

    二叉树的链式存储结构

    普通二叉树
    此为一棵普通的二叉树,若将其采用链式存储,则只需从树的根节点开始,将各个节点及其左右孩子使用链表存储即

    链式存储结构

    遍历二叉树的算法

    遍历算法

    层次遍历

    前面讲过,树是有层次的,拿图 1 来说,该二叉树的层次为 3。通过对树中各层的节点从左到右依次遍历,即可实现对正棵二叉树的遍历,此种方式称为层次遍历。
    层次遍历
    代码实现:

     public static void leverErgodic(TreeNode root) {
            if (root == null) return;
            LinkedList<TreeNode<Integer>> list = new LinkedList<TreeNode<Integer>>();
            list.add(root);
            TreeNode currentNode;
            while (!list.isEmpty()) {
                currentNode = list.poll();
                System.out.println(((Integer) currentNode.value).intValue());
                if (currentNode.leftNode != null) {
                    list.add(currentNode.leftNode);
                }
                if (currentNode.rightNode != null) {
                    list.add(currentNode.rightNode);
                }
            }
        }
    

    普通遍历

    其实,还有一种更普通的遍历二叉树的思想,即按照 “从上到下,从左到右” 的顺序遍历整棵二叉树。
    普通遍历
    普通遍历又可以分为:
    中序遍历:即左-根-右遍历,对于给定的二叉树根,寻找其左子树;对于其左子树的根,再去寻找其左子树;递归遍历,直到寻找最左边的节点i,其必然为叶子,然后遍历i的父节点,再遍历i的兄弟节点。随着递归的逐渐出栈,最终完成遍历
    先序遍历:即根-左-右遍历
    后序遍历:即左-右-根遍历

    先序遍历:

     //先序遍历
        public static void preTraver(TreeNode root) {
            if (null != root) {
                System.out.print(root.value.toString());
                
                preTraver(root.leftNode);
                
                preTraver(root.rightNode);
            }
        }
    

    中序遍历:

      //中序遍历
        public static void midTraver(TreeNode root) {
            if (null != root) {
                midTraver(root.leftNode);
                System.out.print(root.value.toString());
                midTraver(root.rightNode);
            }
        }
    

    后序遍历

     //后序遍历
        public static void lastTraver(TreeNode root) {
            if (null != root) {
                lastTraver(root.leftNode);
                lastTraver(root.rightNode);
                System.out.print(root.value.toString());
            }
        }
    

    二叉查找树-插入

      //二叉 查找树 插入
        public static void insertNode(TreeNode<Integer> insert, TreeNode<Integer> root) {
            if (insert.value.intValue() == root.value.intValue()) {
                return;
            } else if (insert.value.intValue() > root.value.intValue()) { //大于根结点 ,右侧
                if (insert.rightNode == null) {
                    insert.rightNode = insert;
                    return;
                } else {
                    insertNode(insert, root.rightNode);
                }
            } else {
                if (insert.leftNode == null) {
                    insert.leftNode = insert;
                    return;
                } else {
                    insertNode(insert, root.leftNode);
                }
            }
        }
    

    删除节点存在 3 种情况,分别如下:

    1. 没有左右子节点,可以直接删除
    2. 存在左节点或者右节点,删除后需要对子节点移动
    3. 同时存在左右子节点,不能简单的删除,但是可以通过和后继节点交换后转换为前两种情况
      实现代码如下:
     /**
         * 获取后继节点
         *
         * @param node
         * @return
         */
        public TreeNode getNode(TreeNode node) {
            if (!node.hR()) {
                return null; //无后继
            }
    
            TreeNode temp = node.rightNode;
            while (temp.hL()) {
                temp = temp.leftNode;
            }
            return temp;
        }
    
        TreeNode root;
    
        /**
         * 非相邻节点的替换逻辑(非相邻加粗!)
         *
         * @param node    被替换节点
         * @param replace 替换的节点
         */
        public void replaceNode(TreeNode node, TreeNode replace) {
            if (node.isLeft) {
                node.fNode.leftNode = replace;
            } else if (node.isRight) {
                node.fNode.rightNode = replace;
            } else {//根结点
                root = replace;
            }
            node.leftNode.fNode = node.rightNode.fNode = replace;
            replace.fNode = node.fNode;
            replace.leftNode = node.leftNode;
            replace.rightNode = node.rightNode;
        }
    
        public void deleteNode(TreeNode node, TreeNode root) {
    
    
            if (node.hL() && !node.hR()) {// 只有左节点
                if (node.isLeft) {
                    node.fNode.leftNode = node.leftNode;
                } else if (node.isRight) {
                    node.fNode.rightNode = node.leftNode;
                } else// 待删除节点是根节点
                    root = node.leftNode;
                node.leftNode.fNode = node.fNode;
            } else if (node.hR() && !node.hL()) {// 只有右节点
                if (node.isLeft) {
                    node.fNode.leftNode = node.rightNode;
    
                } else if (node.isRight) {
                    node.fNode.rightNode = node.rightNode;
                } else// 待删除节点是根节点
                    root = node.rightNode;
                node.rightNode.fNode = node.rightNode;
            } else if (node.hL() && node.hR()) {// 有左右子节点
                TreeNode sNode = getNode(node);
                if (sNode == node.rightNode) {// 后继节点是右子节点
                    sNode.fNode = node.fNode;
                    if (node.isLeft)
                        node.fNode.leftNode = sNode;
                    else if (node.isRight)
                        node.fNode.rightNode = sNode;
                    else {// 是根节点
                        sNode = root;
                    }
    
                    sNode.fNode = node.fNode;
                    sNode.leftNode = node.leftNode;
                    node.leftNode.fNode = sNode;
    
                } else {// 后继节点是右子节点的最左子节点
                    if (sNode.hR()) {// 左子节点有右子树
                        sNode.fNode.leftNode = sNode.rightNode;
                        sNode.rightNode.fNode = sNode.fNode;
                        replaceNode(node, sNode);
                    } else {// 左子节点没有右子树
                        // 叶节点,直接删除
                        sNode.fNode.leftNode = null;
                        replaceNode(node, sNode);
                    }
                }
    
            } else {// 没有子节点
                if (node.isLeft) {
                    node.fNode.leftNode = null;
                } else if (node.isRight) {
                    node.fNode.rightNode = null;
                }
    
            }
            node = null;
    
        }
    
    
    展开全文
  • 数据结构】B、B+与B*详解

    千次阅读 2017-07-21 11:05:28
    B(B-tree)是对2-3树数据结构的扩展,又称为多路平衡查找,它的一个节点可以拥有多于2个子节点的二叉查找。与自平衡二叉查找不同, B是一种自平衡树数据结构,可以保持数据排序,它能够存储数据、对其...

    B树

    1.B树的定义

    • B树(B-tree)是对2-3树数据结构的扩展,又称为多路平衡查找树,它的一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同,

    • B树是一种自平衡树数据结构,可以保持数据排序,它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构

    • B树针对读写大数据块的系统进行了优化。B树的算法减少定位记录时所经历的中间过程,从而加快存取速度。普遍运用在数据库和文件系统。

    注:有人说B-树,其实就是B树,因为B树的原英文名称为B-tree

    2.B树的性质

    一棵m阶的B 树 (m叉树)的性质

    • 树中每个结点最多含有m个孩子(m>=2);

    • 若根结点不是叶子结点,则至少有2个孩子

    • 除根结点和叶子结点外,其它每个结点至少有[ceil(m / 2)]个孩子

    • 所有叶子结点都出现在同一层,叶子结点不包含任何关键字信息

    • 每个非终端结点中包含有n个关键字信息,并且以升序排列

    B树实示例图
    这里写图片描述

    注:小红方块表示这个17文件内容在硬盘中的存储位置;p1表示指向17左子树的指针

    3.B树的插入与删除

    (1)插入的步骤

    • 插入一个元素时,首先在B树中是否存在,如果不存在,即在叶子结点处结束,然后在叶子结点中插入该新的元素

    • 如果叶子结点空间足够,这里需要向右移动该叶子结点中大于新插入关键字的元素,如果空间满了以致没有足够的空间去添加新的元素,则将该结点进行“分裂”,将一半数量的关键字元素分裂到新的其相邻右结点中,中间关键字元素上移到父结点中(当然,如果父结点空间满了,也同样需要“分裂”操作),

    • 当结点中关键元素向右移动了,相关的指针也需要向右移。如果在根结点插入新元素,空间满了,则进行分裂操作,这样原来的根结点中的中间关键字元素向上移动到新的根结点中,因此导致树的高度增加一层

    实例:构造一个包含C N G A H E K Q M F W L T Z D P R X Y S元素的5阶B树
    (关键字小于2个就合并,超过4个就分裂)

    1>结点空间足够,4个字母插入相同的结点中

    这里写图片描述

    2>插入H时,结点发现空间不够,以致将其分裂成2个结点,移动中间元素G上移到新的根结点中,把A和C留在当前结点中,而H和N放置新的其右邻居结点中

    这里写图片描述

    3>插入E,K,Q时,不需要任何分裂操作

    这里写图片描述

    4>插入M需要一次分裂,因为M恰好是中间关键字元素,所以向上移到父节点中

    这里写图片描述

    5>插入F,W,L,T不需要任何分裂操作

    这里写图片描述

    6>插入Z时,最右的叶子结点空间满了,需要进行分裂操作,中间元素T上移到父节点中,注意通过上移中间元素,树最终还是保持平衡,分裂结果的结点存在2个关键字元素。

    这里写图片描述

    7>插入D时,导致最左边的叶子结点被分裂,D恰好也是中间元素,上移到父节点中,然后字母P,R,X,Y陆续插入不需要任何分裂操作

    这里写图片描述

    8>最后,当插入S时,含有N,P,Q,R的结点需要分裂,把中间元素Q上移到父节点中,但是情况来了,父节点中空间已经满了,所以也要进行分裂,将父节点中的中间元素M上移到新形成的根结点中

    这里写图片描述

    (2)删除的步骤

    • 首先查找B树中需删除的元素,如果该元素在B树中存在,则将该元素在其结点中进行删除,

    • 删除该元素后,首先判断该元素是否有左右孩子结点,如果有,则上移孩子结点中的某相近元素(“左孩子最右边的节点”或“右孩子最左边的节点”)到父节点中,然后是移动之后的情况;如果没有,直接删除后,移动之后的情况。

    • 删除元素,移动相应元素之后,如果某结点中元素数目(即关键字数)小于ceil(m/2)-1,则需要看其某相邻兄弟结点是否丰满(结点中元素个数大于ceil(m/2)-1)

    • 如果丰满,则向父节点借一个元素来满足条件;如果其相邻兄弟都刚脱贫,即借了之后其结点数目小于ceil(m/2)-1,则该结点与其相邻的某一兄弟结点进行“合并”成一个结点,以此来满足条件。

    实例:删除B树中的h、r、p、d元素

    这里写图片描述

    B+树

    1.B+树的定义

    B+-tree是应文件系统所需而产生的一种B-tree的变形树。

    2.B+树与B树区别

    • B+树中有n棵子树的结点中含有n个关键字,而B 树是n棵子树有n-1个关键字

    • B+树所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针,所有的叶子结点和相连的节点使用链表按从小到大的顺序相连,便于区间查找和遍历。而B 树的叶子节点并没有包括全部需要查找的信息。

    • B+树所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键字。 (而B 树的非终节点也包含需要查找的有效信息)

    • B+树的叶子结点都是相链的,因此对整棵树的便利只需要一次线性遍历叶子结点即可。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻,所以缓存命中性没有B+树好。

    • B+树在内部节点上不包含数据信息,因此在内存页中能够存放更多的key。 数据存放的更加紧密,具有更好的空间局部性。因此访问叶子几点上关联的数据也具有更好的缓存命中率。B树的优点:由于B树的每一个节点都包含key和value,因此经常访问的元素可能离根节点更近,因此访问也更迅速。

    B+树示例图
    这里写图片描述

    B*树

    1.B*树的定义

    B*-tree是B+-tree的变体,在B+ 树非根和非叶子结点再增加指向兄弟的指针

    2.B*树的性质

    • B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2)

    • B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针。

    • B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针。

    • B*树分配新结点的概率比B+树要低,空间使用率更高;

    B*树示例图
    这里写图片描述

    B树和B+树的应用场景

    1.文件存储系统

    在B+树中,内节点只存储导航用到的key,并不存储具体值,这样内节点个数较少,能够全部读取到主存中,外接点存储key及值,并且顺序排列,具有良好的空间局部性。所以B及B+树比较适合与文件系统的数据结构。

    2.数据库系统

    Mysql的MyISAM和InnoDB两个存储引擎的索引实现方式:

    • MyISAM

      • MyISAM引擎使用B+ Tree作为索引结构,叶节点存放的是数据记录的地址。
      • MyISAM引擎的辅助索引(二级索引)和主索引在结构上没有区别,只是辅助索引的key可以重复,叶节点上存放的也是数据记录的地址。
      • MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。
    • InnoDB

      • InnoDB中表数据本身就是按B+ Tree组织的一个索引结构,叶节点存放的就不是数据记录的地址,而是完整的数据记录。所以InnoDB这种存储方式,又称为聚集索引,使得按主键的搜索十分高效,但二级索引搜索需要检索两遍索引:首先二级索引获得主键,然后用主键到主索引中检索到数据记录。
      • 因为主键是InnoDB表记录的”逻辑地址“,所以InnoDB要求表必须有主键,MyISAM可以没有。



    本人才疏学浅,若有错,请指出
    谢谢!

    参考资料:

    1.B树详解
    2.平衡查找树之B树
    3.B树详解——维基百科
    4.简单清晰的B树、Trie树详解
    5.MySQL索引背后的数据结构及算法

    展开全文
  • 数据结构(三)、B,B+,B*

    千次阅读 2020-08-04 21:32:06
    而在现实情况大部分数据存储在磁盘,对于数据量比较大的情况下,对导致二叉树结构的深度也随之变大造成磁盘IO读写频繁导致查询效率低下,因此大部分关系型数据库都使用本篇要介绍的B+Tree结构,要理解B+,需要...

    动态查找树主要有:二叉查找树,平衡二叉树,红黑树,B-tree/B+-tree/B*-tree。前三个都是典型的二叉树结构,查找的时间复杂度O(log2N)和树的深度相关,随着树的深度降低会提高查找效率。而在现实情况中大部分数据存储在磁盘中,对于数据量比较大的情况下,对导致二叉树结构的深度也随之变大造成磁盘IO读写频繁导致查询效率低下,因此大部分关系型数据库都使用本篇要介绍的B+Tree结构,要理解B+树,需要先理解B树,本篇也会一起介绍B*树。


    数据结构(一)、二叉树(BT),二叉查找树(BST),平衡二叉树(AVL树)

    数据结构(二)、红黑树(RBT)

    目录

    B树

    简介

    概念

    查询流程

    插入流程

    删除流程

    更新操作

    B+树

    简介

    概念

    查询流程

    插入流程

    删除流程

    B*树

    简介

    总结对比


    B树

    简介

    上面提到,对于数据库来说,数据几乎都是存储在磁盘内,磁盘查找存取的次数由树的深度决定,因此,只要我们通过某种较好的树结构尽量减少树的深度,是不是就能有效减少磁盘查找存取的次数呢?于是就出现了一个新的查找树结构:多路查找树。增加树的度来减少树的深度。

    正如平衡二叉树之于二叉查找树,自然就想到平衡多路查找树结构之于多路查找树,也就是本篇所要阐述的第一个主题B-Tree(B树)结构,B树的各种操作能让B树保持较低的深度,从而达到有效避免磁盘过于频繁的查找存取操作,达到有效提高查找效率的目的。

    B树(B-tree,B-树),和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树(查找路径不只两个),与红黑树相比,B树可以比红黑树的深度小许多,因为B树的分支因子比较大,所以B树可以在O(logN)时间内,实现各种如插入(insert),删除(delete)等动态集合操作。数据库索引技术里大量使用者B树和B+树的数据结构。

    在线测试B-tree数据结构:

    https://www.cs.usfca.edu/~galles/visualization/BTree.html

    概念

    由上图可以看到,B树的节点,对应硬盘中的页(page)或磁盘块(block) ,每个节点中包含了关键字子节点指针两部分信息。 

    一个节点对应一个页,磁盘预读是以页为单位的,因此访问一个节点就代表访问一次磁盘(读取一页),也就是代表一次I/O操作;

    m阶B-Tree满足以下条件

    1. 树中每个节点最多含有m个子节点(m>=2)。
    2. 每个内节点至少 [ceil(m / 2)] 个子节点。 内节点即非根节点非页子节点,也可以叫中间节点。
    3. 关键字key的数量 [ceil(m / 2)-1]<= n <= m-1,关键字按递增排序。
    4. 每个叶节点具有相同的深度,即树的高度h,而且不包含关键字信息。

    下面这是个5阶的B树:

    上图也可以称为最小度数为3的B树,(degree) ,简写t。

    t就是上面第二个条件中 [ceil(m / 2)] 的值,即t=[ceil(m/2)], 3=ceil(5/2) 。

    1. 每个非根节点至少有t-1个关键字,非根内节点至少有t个子节点。 t称为度数(degree),t>=2 。
    2. 每个节点至多有2t-1关键字,每个内节点最多有2t个子节点。
    3. 每个叶节点具有相同的深度,即树的高度h,而且不包含关键字信息。

    m阶:每个节点至多有m个子树。表示一个树节点最多有多少个查找路径,m=m路,当m=2则是2叉树,m=3则是3叉。

    最小度数t:(degree) ,简写t,t=[ceil(m/2)]。每一个节点能包含的关键字数量有一个上界和下界。这个下界就是最小度数t。

    查询流程

    对于上面的3阶B树,如果想查找15的位置,会经过下面的流程:

    1. 在根节点先判断9<15<33,于是根据根节点中间的指针找到13节点(根据二分法,左小右大);
    2. 然后在13节点判断13<15,于是找到15节点在13节点右边的指针指向的节点内;
    3. 在15,16节点内判断15=15,于是找到15的位置,返回关键字和指针信息(如果树结构里面没有包含所要查找的节点则返回null);

    插入流程

    规则:

    节点分裂规则:对于一个m路查找树,关键字数量必须小于等于m-1,当关键字数大于m-1时就会进行节点拆分;

    排序规则:满足节点本身比左边节点大,比右边节点小的排序规则;

    进行拆分时,中间的元素提取升级到父节点, 左边的元素单独构成一个节点, 右边的元素单独构成一个节点;

    :定义一个5阶B树,依次插入3,9,13,32,22,27,70,29:

    删除流程

    规则:

    节点合并规则:对于一个m路查找树,关键字数必须大于等于ceil(m/2)-1,当关键字数量小于该值时就会进行节点合并;

    排序规则:满足节点本身比左边节点大,比右边节点小的排序规则;

    关键字数量小于 ceil(m/2)-1 时先从子节点取,子节点没有符合条件时就向父节点取,取中间值往父节点放;

    :从5阶B树中删除27:

    更新操作

    B树的更新操作通常有两种:

    1. 直接对数据进行更新;
    2. 分解为删除加插入操作;

    B+树

    简介

    从上面的B树中,我们可以看到 相比于二叉平衡树,B树由于每个节点存储更多的关键字,可以将树的深度降低,在查询单条数据是非常快的。但在范围查询场景下,B树每次都要从根节点查询一遍,这是很慢的,因此出现了B树的变种,B+树。相对于B树来说B+树更充分的利用了节点的空间,让查询速度更加稳定,其速度完全接近于二分法查找。

    在线测试B-tree数据结构:

    https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

    概念

    规则

    1. B+树的非叶子节点不保存关键字记录的指针,只进行数据索引,这样使得B+树每个非叶子节点所能保存的关键字大大增加;
    2. B+树叶子节点保存了父节点的所有关键字记录的指针,所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样;
    3. B+树叶子节点的关键字从小到大有序排列,左边结尾数据都会保存右边节点开始数据的指针;
    4. 非叶子节点的子节点数等于关键字数;

    非叶子节点相当于是叶子节点的索引(稀疏索引),叶子节点相当于是存储(关键字)数据的数据层;

    所有关键字都出现在叶子节点的链表中(稠密索引),且链表中的关键字恰好是有序的;

    特点

    1. B+树的层级更少:相较于B树,B+树每个非叶子节点存储的关键字数更多,树的层级更少所以查询数据更快;
    2. B+树查询速度更稳定:B+所有关键字数据地址都存在叶子节点上,所以每次查找的次数都相同所以查询速度要比B树更稳定;
    3. B+树天然具备排序功能:B+树所有的叶子节点数据构成了一个有序链表,在查询大小区间的数据时候更方便,数据紧密性很高,缓存的命中率也会比B树高。
    4. B+树全节点遍历更快:B+树遍历整棵树只需要遍历所有的叶子节点即可,而且由于数据顺序排列并且相连,所以便于区间查找和搜索,而不需要像B树一样需要对每一层进行遍历,这有利于数据库做全表扫描。

    B树相对于B+树的优点是,如果经常访问的数据离根节点很近,而B树的非叶子节点本身存有关键字其数据的地址,所以这种数据检索的时候会要比B+树快。

    查询流程

    与B-树也基本相同,区别是B+树只有达到叶子节点才命中(B-树可以在非叶子节点命中),其性能也等价于在关键字全集做一次二分查找;

    对于上面的5阶B+树,如果想查找122,133,144的位置,会从根节点[111]-->[133,155] 然后判断,122<133,于是在[133,155]节点的第一个孩子里找到122,133<=133<=155,133<=144<=155,于是在[133,155]节点的第二个孩子里找到133和144。

    插入流程

    与B树一样,往B+树内插入数据时候会根据下面的规则触发分裂规则。

    B+树的分裂规则

    • 当一个节点满(关键字数量等于阶数)时,分配一个新的节点,并将原节点中1/2的数据复制到新节点,最后在父节点中增加新节点的指针;(将当前节点,分为左右两个叶子节点,左叶子节点包含前M/2个记录,右叶子节点包含剩余记录,并且将第M/2+1个记录的关键字上移到父节点。当前节点指针指向父节点。)
    • B+树的分裂只影响原节点和父节点,而不会影响兄弟节点,所以它不需要指向兄弟的指针。

    :定义一个5阶B+数,依次往里插入11,22,33,44,36,40,38:

    删除流程

    B+树删除算法

    1. 找到目标关键字所在的叶节点位置,进行删除,若删除后,当前节点关键字数量大于等于ceil(M/2)−1,结束,否则进行步骤2;

    2. 若兄弟节点的关键字有富余(大于ceil(M/2)−1),向兄弟借一个记录,同时用借到的key替换父节点中对应的关键字,结束。否则进行步骤3;

    3. 若兄弟节点没有富余,则当前节点和兄弟节点合并成一个新的节点,删除父节点的关键字,新节点指向父节点相应的位置。进行步骤4;

    4. 若索引节点的关键字个数大于等于ceil(M/2)−1,则结束,否则进行步骤5;

    5. 若兄弟节点有富余,父节点key下移,兄弟节点key上移,删除结束。进行步骤第6步;

    6. 当前节点和兄弟节点及父节点下移key合并成一个新的节点。将当前节点指向父节点,重复第4步;

    :从5阶B+树种删除44,77: 

    B*树

    简介

    B*树是B+树的变种,相对于B+树他们的不同之处如下:

    (1)首先是关键字个数限制问题,B+树初始化的关键字初始化个数是cei(m/2),b*树的初始化个数为(cei(2/3*m)

    (2)B+树节点满时就会分裂,而B*树节点满时会检查兄弟节点是否满(因为每个节点都有指向兄弟的指针),如果兄弟节点未满则向兄弟节点转移关键字,如果兄弟节点已满,则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来;

    B*树的分裂

    • 当一个节点满时,如果它的下一个兄弟节点未满,那么将一部分数据移到兄弟节点中,再在原节点插入关键字,最后修改父节点中兄弟节点的关键字(因为兄弟节点的关键字范围改变了);
    • 如果兄弟也满了,则在原节点与兄弟节点之间增加新节点,并各复制1/3的数据到新节点,最后在父节点增加新节点的指针。

    B*树分配新节点的概率比B+树要低,空间使用率2/3 相比于B+树1/2 更高。

    总结对比

    B树:多路搜索树,每个节点存储M/2到M个关键字,非叶子节点存储指向关键字范围的子节点;所有关键字在整颗树中出现,且只出现一次,非叶子节点可以命中;

    B+树:在B树基础上,为叶子节点增加链表指针,所有关键字都在叶子节点中出现,非叶子节点作为叶子节点的索引;B+树总是到叶子节点才命中;

    B*树:在B+树基础上,为非叶子节点也增加链表指针,将节点的最低利用率从1/2提高到2/3;

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

    为什么B+树比B树更适合实际应用中操作系统的文件索引和数据库索引?

    1. B+tree的磁盘读写代价更低
      B+tree的内部节点并没有指向关键字具体信息的指针。因此其内部节点相对B树更小。如果把所有同一内部节点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

      例:假设磁盘中的一个盘块容纳16bytes,而一个关键字2bytes,一个关键字具体信息指针2bytes。一棵9阶B-tree(一个节点最多8个关键字)的内部节点需要2个盘快。而B+ 树内部节点只需要1个盘快。当需要把内部节点读入内存中的时候,B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。

    2. B+tree的查询效率更加稳定
      由于非叶子节点并不是最终指向文件内容的节点,而只是叶子节点中关键字的索引。所以任何关键字的查找必须走一条从根节点到叶子节点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。

    3. B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题,B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的,而B树不支持这样的操作(或者说效率太低)。

     

    希望本文对你有帮助,请点个赞鼓励一下作者吧~ 谢谢!

    展开全文
  • B+(索引的数据结构)

    千次阅读 2019-03-25 23:17:21
    B+ 一、文章背景 ...B+是一种数据结构,但是因为它常常是出现在文件存储系统和数据库系统,所以大多数讨论到B+是基于它作为数据库索引数据结构,所以本文结合MySQL索引探讨一下B+。 本文参考: ...

    B+树

    一、文章背景

    引用维基百科的定义:’'在计算机科学中,B树(B-tree)是一种树状数据结构,它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。"

    B+树是一种数据结构,但是因为它常常是出现在文件存储系统和数据库系统中,所以大多数讨论到B+树是基于它作为数据库索引数据结构,所以本文结合MySQL索引探讨一下B+树

    本文参考: 平衡查找树之B树

    二、内容概要

    1. 简要说明一下B树B+树的数据结构。
    2. 探讨B树B+树两种数据结构在从磁盘读取时的差异。
    3. 结合MySQL的组合索引,分析组合索引的最左原则,不满足最左原则查询一定不走索引吗?

    三、详细内容

    3.1 简要介绍B树B+树

    B树,概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉树不同,B树为系统最优化大块数据的读和写操作。B-Tree算法减少定位记录时所经历的中间过程,从而加快存取速度。

    B树看做是对2-3查找树的一种扩展,即他允许每个节点有M-1个子节点(M 为树的阶,也叫度)。

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

    B+树,是对B树的一种变形树,他与B树的差异在于:

    • 有K个子节点的节点必然有K个关键码。
    • 非叶子节点仅具有索引的作用,具体的值或者说是具体的信息放在叶子节点中。
    • 树的所有叶子节点构成一个有序链表,可以按照关键码的次序遍历全局记录。

    两中数据结构的差异也就是B+树的优势:

    • 因为非叶子节点不存储具体信息,所以能够存放更多的key。数据的存放更加紧密,具有更好地空间局部性。因此访问叶子节点上关联的数据具有更好的缓存命中率。
    • B+树的叶子节点是相链的,是有序链表结构,因此遍历B+树只需要先行遍历一遍叶子节点。而B树则需要遍历整个树。

    3.2 B树B+树两种数据结构在从磁盘读取时的差异。

    这里要讲一个预读的概念,由于存储介质的特性,磁盘本身存取就比主存慢得多,再加上机械运动耗费,因此为了提高效率,要尽量减少磁盘I/O,减少读写操作。为了达到这个目的,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存。理论依据:局部性理论,当一个数据被用到时,其附近的数据也通常会马上被使用。

    预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页得大小通常为4k),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续运行。

    文件系统及数据库系统的设计者利用了磁盘预读原理,将一个节点的大小设为等于一个页,这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的,在实际实现B-Tree还需要使用如下技巧:

    因为在磁盘读取时,每次读取的数据量大小是固定的,因为B树的非叶节点存储了指针信息,所以每次读取B树结构的数据时,所能够获取的索引信息较少。相反,因为B+树的非叶子节点之存储索引,所以拿到的key相对多,即B+树的阶比较大,同时B+树的高度更低,更扁平。而高度决定了I/O次数,所以B+树结构能够减少I/O次数。

    3.3 结合MySQL的组合索引,分析组合索引的最左原则,不满足最左原则查询一定不走索引吗?

    先简单介绍一下组合索引,例:创建组合索引(a,bc),那么相当于创建了(a),(a,b),(a,b,c)三个索引.

    由于b+树的结构,索引有了最左原则

    那么一定要遵循最左原则吗?不遵循最左原则的SQL语句,一定不走索引,全文搜索吗?

    select a from table_a where b =1 and c =2;
    

    使用explain命令,得出,该语句type属性为index

    同样走了索引,不同的是,index表示查询索引时,是遍历索引而不是特殊算法。

    但是,如果是

    select * from table_a where b =1 and c =2;
    

    即:在查询结果列时,如果有列名不是组合索引中的,那么,explain命令得出,type属性为All

    展开全文
  • 一种简单的新的数据结构产生了,那就是,大部分操作的运行时间平均为。 (Tree)是一些节点的集合,可以为空,也就是说可以为空集。非空,是有一个根节点(root简写r)r以及0个或者多个非空子组成。一颗...
  •  是n(n≥0)个节点的有限集。n=0时称为空。在任意一颗非空树种: (1)有且仅有一个特定的称为根的节点 (2)当n&gt;1时,其余节点可分为m(m&gt;0)个互不相交的有限集T1、T2、....、Tm,其中每一...
  • 这些子树每一颗的根都被来自根r的一条有向的边所连接。 的基础概念: 深度:任意节点nin_ini​的深度为从根到nin_ini​惟一路径的长。因此,根的深度为0。 高度:nin_ini​的高度是从nin_ini​到一片树叶的...
  • 本系列博客整理自网络... 数据结构中有很多的结构,其中包括二叉树、二叉搜索、2-3、红黑、B、B+、B*等等下面从最基础的概念开始,介绍结构与实现。 1、什么是是一种数据结构,可以用来表示...
  • B+ 数据结构

    千次阅读 2019-08-16 16:34:50
    MySQL 索引采用B+数据结构进行存储,如下图所示: 真实的数据存在于叶子节点,即3、5、9、10、13、15、28、29、36、60、75、79、90、99. 非叶子节点不存储真实数据,只存储指引搜索方向的数据项(指针),如17...
  • 数据结构Huffman及编码

    千次阅读 2017-06-16 23:42:56
    一、 实验目的构造一个哈夫曼,并根据所构造的哈夫曼求其哈夫曼的编码; 二、 基本思路 将每个英文字母依照出现频率由小排到大,最小在左,组成一个序列 每个字母都代表一个终端节点(叶节点),比较每个字母...
  • 详细介绍了这种数据结构的基本概念,以及通用的的Java实现方式,为后面各种的深入学习打好基础。
  • 数据结构的知识点梳理和分析

    千次阅读 2018-12-04 17:04:39
    我们先来介绍一下的基本组成结构由一个个带有数据和指针的节点组成,指针使得不同节点之间获得了联系,所有的节点都源自于终端节点(根节点),它可以指向若干子节点,子节点又会指向更多子节点,最终指向终端...
  • 当你第一次学习编码时,大部分人都是将数组作为主要数据结构来学习。...当你开始学习和图的数据结构时,你会觉得它是如此的混乱。因为它的存储方式不是线性的,它们都有自己特定的方式存储数据。 定义 ...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    在计算机科学发展过程,早期数据结构教材大都采用PASCAL语言为描述工具,后来出现了采用C语言为描述工具的教材版本、至今又出现了采用C++语言为描述工具的多种教材版本。本教实验指导书是为已经学习过C++语言的...
  • 对于很多人来说,字典和数组是非常熟悉也经常用的数据结构。链表也还算比较常用。 他们的特点如下: 1.字典和数组都是线性结构 2.字典和数组,链表都是按照位置来存储数据的,例如字段是通过哈希计算下标,数组是...
  • 数据结构 详细介绍

    2020-11-26 19:28:28
    形结构是一类重要的非线性数据结构树中结点之间具有明确的层次关系,并且结点之间有分支,非常类似于真正的形结构在客观世界大量存在,如行政组织机构和人类社会家谱等都可以用形结构形象表示。 二、...
  • python数据结构形结构

    千次阅读 2019-04-09 17:19:01
    python数据结构 二叉树 的查询,遍历,存储
  • 带权路径长度有一个求法是:wpl=非叶子...但是这个方法是针对huffman的,如果不是huffman,必须按照叶子结点的深度与权值之积总和来求解。https://blog.csdn.net/qq_39328436/article/details/107866297 ...
  • 数据结构

    2017-09-07 11:45:47
    1、满二叉树 除叶子节点外,每个节点都有两个子节点,除了最后一层,每一层上的节点数达到最大值,第K层有2(k-1)个子节点,高度为m的满... (1)定义:设x是二叉搜索树中的一个结点。如果y是x左子树的一个结点,那么
  • Java数据结构与算法解析(九)——B

    万次阅读 多人点赞 2017-09-27 09:41:56
    这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作,都在对数时间内完成。特点阶为M的B是一颗具有以下特点的: 1.数据项存储在树叶上 2.非叶子节点直到M-1个关键字以指示搜索的方向:关键字i代表...
  • BUAA_数据结构_5TH_1. 树叶节点遍历(-基础题) 题目描述: 从标准输入输入一组整数,在输入过程按照左子结点值小于根结点值、右子结点值大于等于根结点值的方式构造一棵二叉查找,然后从左至右输出所有...
  • 数据结构中的这6种「」,你心中有数吗? 数据结构这门课程是计算机相关专业的基础课,数据结构指的是数据在计算机的存储、组织方式。 我们在学习数据结构时候,会遇到各种各样的基础数据结构,比如堆栈、队列、...
  • 的基本概念
  • //二叉树数据结构 struct node { DataType info ; //存放结点数据 struct node *lchild , *rchild ; //指向左右孩子的指针 }; typedef struct node *BiTree ; /*创建二叉树 函数名:createBiTree 参数:无 返回值:...
  • 数据结构二叉树遍历求树叶数及的深度,个人作业,仅供大家参考或改进
  • 赫夫曼结构三. 赫夫曼的实现代码 一. 关于赫夫曼 路径:从中一个结点到另一个结点之间的分支构成两个结点之间的路径。 路径长度:路径上的分支数目 的路径长度:从树根到每一结点的路径之和 结点的权...
  • 数据结构

    2018-03-09 22:49:05
    1、定义::是n(n&gt;=0)个结点的有限集合。当n=0时,集合为空,称为空。...(实际上,表示了一组结点之间不同于线性表的前继和后继关系的数据结构.一般而言,树种任何一个结点只有一个前继(根结点...
  • 顾名思义,第一想到的就是路边的,有树干、树根、树叶数据结构中也是这样延伸过来的,只不过专用名词不一样,如图 关于的一些专有名词:A 是 B 的父节点,B 是 A 的子节点,D 是 B 的兄弟节点,C 和 D ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,795
精华内容 4,718
关键字:

数据结构中树的树叶

数据结构 订阅