数据结构与算法系列|数据结构与算法系列 (6) 树数据结构与算法系列(6)树

1.树 1.1 为什么需要树这种数据结构

#数组有序数组，查找很快，但是想要在有序数组中插入一个数据项，就必须先找到插入数据项的位置，然后将所有插入位置后面的数据项全部向后移动一位，来给新数据腾出空间，平均来讲要移动N/2次，这是很费时的。同理，删除数据也是。#链表链表的插入和删除很快，我们只需要改变一些引用值就行了，但是查找数据却很慢了，因为不管我们查找什么数据，都需要从链表的第一个数据项开始，遍历到找到所需数据项为止，这个查找也是平均需要比较N/2次。#树而"树"是一种能同时具备数组查找快的优点以及链表插入和删除快的优点的数据结构。

1.2 树概念

树（tree）是一种抽象数据类型（ADT），用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点通过连接它们的边组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。#概念 1.节点：下图的圆圈，比如A,B,C等都是表示节点。节点一般代表一些实体，在java中，节点一般代表对象。2.边：连接节点的线称为边，边表示节点的关联关系。一般从一个节点到另一个节点的唯一方法就是沿着一条顺着有边的道路前进。在Java中通常表示引用。3.路径：顺着节点的边从一个节点走到另一个节点，所经过的节点的顺序排列就称为“路径”。4.根：树顶端的节点称为根。一棵树只有一个根，如果要把一个节点和边的集合称为树，那么从根到其他任何一个节点都必须有且只有一条路径。A是根节点。5.父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；B是D的父节点。6.子节点：一个节点含有的子树的根节点称为该节点的子节点；D是B的子节点。7.兄弟节点：具有相同父节点的节点互称为兄弟节点；比如下图的D和E就互称为兄弟节点。8.叶节点：没有子节点的节点称为叶节点，也叫叶子节点，比如下图的H、E、F、G都是叶子节点。9.子树：每个节点都可以作为子树的根，它和它所有的子节点、子节点的子节点等都包含在子树中。10.节点的层次：从根开始定义，根为第一层，根的子节点为第二层，以此类推。11.深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；12.高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0；13.森林: 多颗子树构成森林

文章图片
树形结构.png 1.3 树的分类

#二叉树：树的每个节点最多只能有两个子节点, 二叉树子节点根据位置分为“左子节点”和“右子节点”。如红黑树。#多路树: 节点有三个及以上子节点，就不是二叉树，而是称为多路树。如B树, B+ 树, B*树。

2.二叉树(binary tree)

#满二叉树如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2^n -1 , n 为层数，则我们称为满二叉树。#完全二叉树如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。#二叉搜索树(binary search tree) 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。

文章图片
满二叉树.png

文章图片
完全二叉树.png

文章图片
二叉搜索树.png 2.0 二叉树的存储结构

有两种，分别为顺序存储和链式存储。

2.0.1 二叉树的顺序存储结构

二叉树的顺序存储，指的是使用顺序表（数组）存储二叉树。顺序存储只适用于完全二叉树(含满二叉树)。换句话说，只有完全二叉树才可以使用顺序表存储。因此，如果我们想顺序存储普通二叉树，需要提前将普通二叉树转化为完全二叉树。#普通二叉树转完全二叉树只需给二叉树额外添加一些节点，将其"拼凑"成完全二叉树即可。

文章图片
普通二叉树转完全二叉树.png

#顺序存储二叉树的特点: >> 顺序二叉树通常只考虑完全二叉树 >> 第n个元素的左子节点为2 * n + 1 >> 第n个元素的右子节点为2 * n + 2 >> 第n个元素的父节点为(n-1) / 2 >> n : 表示二叉树中的第几个元素(由于在数组中, 所以从0开始编号)

文章图片
完全二叉树在数组中的存储状态.png

文章图片
普通二叉树在数组中的存储状态.png 2.0.2 二叉树的链式存储结构

二叉树并不适合用数组存储，因为并不是每个二叉树都是完全二叉树，普通二叉树使用顺序表存储或多或多会存在空间浪费的现象。于是便有了链式存储结构。#采用链式存储二叉树时，其节点结构由 3 部分构成： >> 指向左孩子节点的指针（L）； >> 节点存储的数据（data）； >> 指向右孩子节点的指针（R）；

文章图片
二叉树的链式存储结构.png 2.0.3 线索二叉树

#线索二叉树 n个节点的二叉链表中含有n+1【公式 2n-(n-1)=n+1】个空指针域。利用二叉链表中的空指针域，存放指向该节点在某种遍历次序下的前驱和后继节点的指针（该指针即"线索"）。这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。 >> 将这颗二叉树的所有节点右子节点为空的指针域指向它的后继节点。 >> 将这颗二叉树的所有节点左指针域为空的指针域指向它的前驱节点。#线索二叉树分类根据线索性质的不同，线索二叉树可分为 >> 前序线索二叉树 >> 中序线索二叉树 >> 后序线索二叉树#前驱节点 & 后继节点 >> 一个节点的前一个节点，称为前驱节点 >> 一个节点的后一个节点，称为后继节点

文章图片
构建线索二叉树过程.png 2.1 二叉搜索/排序树(BST, binary search/sort tree)

#二叉排序树：BST: (Binary Sort(Search) Tree) 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。 #特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点。#查找某个节点，必须从根节点开始遍历。 ①查找值比当前节点值大，则搜索右子树； ②查找值等于当前节点值，停止搜索（终止条件）； ③查找值小于当前节点值，则搜索左子树； >> 树的效率：查找节点的时间取决于这个节点所在的层数，每一层最多有2n-1个节点，总共N层共有2n-1个节点，那么时间复杂度为O(logn),底数为2。#遍历树遍历树是根据一种特定的顺序访问树的每一个节点。比较常用的有前序遍历，中序遍历和后序遍历(核心在于父节点何时输出)。而二叉搜索树最常用的是中序遍历。 >> 前序遍历:父节点——》左子树——》右子树 >> 中序遍历:左子树——》父节点——》右子树 >> 后序遍历:左子树——》右子树——》父节点#查找最大值和最小值要找最小值，一直找根节点的左节点，直到没有左节点的节点，那么这个节点就是最小值。要找最大值，一直找根节点的右节点，直到没有右节点，则就是最大值。#插入节点要插入节点，必须先找到插入的位置。与查找操作相似，由于二叉搜索树的特殊性，待插入的节点也需要从根节点开始进行比较，小于根节点则与根节点左子树比较，反之则与右子树比较，直到左子树为空或右子树为空，则插入到相应为空的位置，在比较的过程中要注意保存父节点的信息及待插入的位置是父节点的左子树还是右子树，才能插入到正确的位置。#删除节点 ##a.删除没有子节点的节点要删除叶节点，只需要改变该节点的父节点引用该节点的值，即将其引用改为 null 即可。要删除的节点依然存在，但是它已经不是树的一部分了，由于Java语言的垃圾回收机制，我们不需要非得把节点本身删掉，一旦Java意识到程序不在与该节点有关联，就会自动把它清理出存储器。删除节点，我们要先找到该节点，并记录该节点的父节点。再检查该节点是否有子节点。如果没有子节点，接着检查其是否是根节点，如果是根节点，只需要将其设置为null即可。如果不是根节点，是叶节点，那么断开父节点和其的关系即可。##b.删除有一个子节点的节点只需要将其父节点原本指向该节点的引用，改为指向该节点的子节点即可。##c.删除有两个子节点的节点较为复杂#是否真的需要删除节点呢? 其实我们可以不用真正的删除该节点，只需要在Node类中增加一个标识字段isDelete，当该字段为true时，表示该节点已经删除，反正没有删除。那么我们在做比如find()等操作的时候，要先判断isDelete字段是否为true。这样删除的节点并不会改变树的结构。

文章图片
二叉搜索树-->遍历树示例1.png

文章图片
二叉搜索树-->遍历树示例2.png

文章图片
二叉搜索树--删除没有子节点的节点.png

文章图片
删除有一个子节点的节点.png 二叉树的效率

#查找效率大部分对树的操作都需要从根节点到下一层一层的查找。一颗满树，每层节点数大概为2n-1，那么最底层的节点个数比树的其它节点数多1，因此，查找、插入或删除节点的操作大约有一半都需要找到底层的节点，另外四分之一的节点在倒数第二层，依次类推。总共N层共有2n-1个节点，那么时间复杂度为O(logn),底数为2。#插入效率在有1000000个数据项的无序数组和链表中，查找数据项平均会比较500000 次，但是在有1000000个节点的二叉树中，只需要20次或更少的比较即可。有序数组可以很快的找到数据项，但是插入数据项的平均需要移动 500000 次数据项，在 1000000 个节点的二叉树中插入数据项需要20次或更少比较，再加上很短的时间来连接数据项。#删除效率同样，从 1000000 个数据项的数组中删除一个数据项平均需要移动 500000 个数据项，而在 1000000 个节点的二叉树中删除节点只需要20次或更少的次数来找到他，然后再花一点时间来找到它的后继节点，一点时间来断开节点以及连接后继节点。#summary 所以，树对所有常用数据结构的操作都有很高的效率。#一些不足遍历可能不如其他操作快，但是在大型数据库中，遍历是很少使用的操作，它更常用于程序中的辅助算法来解析算术或其它表达式。

2.2 平衡二叉树

二叉搜索树BST在一定条件下可能变为链表, 如 {1,2,3,4,5,6,7,8,9}. 为了解决这种问题, 其中一种方案, AVL树诞生了.#平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树，可以保证查询效率较高。 >> 具有以下特点它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 >> 常见实现方案平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。

2.2.1 AVL 树
2.2.2 红黑树

二叉搜索树对于某个节点而言，其左子树的节点关键值都小于该节点关键值，右子树的所有节点关键值都大于该节点关键值。二叉搜索树作为一种数据结构，其查找、插入和删除操作的时间复杂度都为O(logn),底数为2。但是这个时间复杂度是在平衡的二叉搜索树上体现的，也就是如果插入的数据是随机的，则效率很高; 如果插入的数据是有序的，比如从小到大的顺序【10,20,30,40,50】插入到二叉搜索树中：从大到小就是全部在左边，这和链表没有任何区别了，这种情况下查找的时间复杂度为O(N)，而不是O(logN)。当然这是在最不平衡的条件下，实际情况下，二叉搜索树的效率应该在O(N)和O(logN)之间，这取决于树的不平衡程度。那么为了能够以较快的时间O(logN)来搜索一棵树，我们需要保证树总是平衡的(或者大部分是平衡的), 也就是说每个节点的左子树节点个数和右子树节点个数尽量相等。#红黑树红-黑树的就是这样的一棵平衡树，对一个要插入的数据项（删除也是），插入例程要检查会不会破坏树的特征，如果破坏了，程序就会进行纠正，根据需要改变树的结构，从而保持树的平衡。

红-黑树的特征

①每个节点都有颜色(非黑即红)；当然也可以是任意别的两种颜色，这里的颜色用于标记，可以在节点类Node中增加一个boolean型变量isRed，以此来表示颜色的信息。②在插入和删除的过程中，要遵循保持这些颜色的不同排列规则： 1.每个节点不是红色就是黑色的； 2.根节点总是黑色的； 3.如果节点是红色的，则它的子节点必须是黑色的(反之不一定), (也就是从每个叶子到根的所有路径上不能有两个连续的红色节点)； 4.从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）。 #注意：新插入的节点颜色总是红色的，这是因为插入一个红色节点比插入一个黑色节点违背红-黑规则的可能性更小，原因是插入黑色节点总会改变黑色高度(违背规则4)，但是插入红色节点只有一半的机会会违背规则3(因为父节点是黑色的没事，父节点是红色的就违背规则3)。另外违背规则3比违背规则4要更容易修正。当插入一个新的节点时，可能会破坏这种平衡性，那么红-黑树是如何修正的呢？

红-黑树的自我修正

红-黑树主要通过三种方式对平衡进行修正，改变节点颜色、左旋和右旋。#改变节点颜色新插入的节点为3，一般新插入颜色都为红色，那么我们发现直接插入会违反规则3，改为黑色却发现违反规则4。这时候我们将其父节点颜色改为黑色，父节点的兄弟节点颜色也改为黑色。通常其祖父节点10颜色会由黑色变为红色，但是由于10是根节点，所以我们这里不能改变根节点颜色。#右旋节点本身不会旋转，旋转改变的是节点之间的关系，选择一个节点作为旋转的顶端，如果做一次右旋，这个顶端节点会向下和向右移动到它右子节点的位置，它的左子节点会上移到它原来的位置。右旋的顶端节点必须要有左子节点。#左旋左旋的顶端节点必须要有右子节点。#需要注意的是：改变颜色也是为了帮助判断何时执行什么旋转，而旋转是为了保证树的平衡。光改变节点颜色是不能起到任何作用的，旋转才是关键的操作，在新增节点或者删除节点之后，可能会破坏二叉树的平衡，那么何时执行旋转以及执行什么旋转，这是需要重点关注的。

文章图片
红黑树自我修正-->改变节点颜色.png

文章图片
红黑树自我修正--右旋.gif

文章图片
红黑树自我修正--左旋.gif 红-黑树的插入操作

大部分和二叉树的插入操作一样，都是得先找到插入的位置，然后再将节点插入。因为插入后可能会导致树的不平衡，最后一步要分析何时变色，何时左旋，何时右旋。 >>如果是第一次插入，由于原树为空，所以只会违反红-黑树的规则2，所以只要把根节点涂黑即可； >>如果插入节点的父节点是黑色的，那不会违背红-黑树的规则，什么也不需要做；#但是遇到如下三种情况，我们就要开始变色和旋转了： >>①插入节点的父节点和其叔叔节点（祖父节点的另一个子节点）均为红色。 >>②插入节点的父节点是红色的，叔叔节点是黑色的，且插入节点是其父节点的右子节点。 >>③插入节点的父节点是红色的，叔叔节点是黑色的，且插入节点是其父节点的左子节点。#在下面的讨论中，使用N,P,G,U表示关联的节点。 N(now)表示当前节点， P(parent)表示N的父节点， U(uncle)表示N的叔叔节点， G(grandfather)表示N的祖父节点，也就是P和U的父节点。#对于情况1：插入节点的父节点和其叔叔节点（祖父节点的另一个子节点）均为红色。此时，肯定存在祖父节点，但是不知道父节点是其左子节点还是右子节点，但是由于对称性，我们只要讨论出一边的情况，另一种情况自然也与之对应。这里考虑父节点是其祖父节点的左子节点的情况，如"红黑树插入操作-图1"所示.对于这种情况，要做的操作有：将当前节点(4) 的父节点(5) 和叔叔节点(8) 涂黑，将祖父节点(7)涂红,变成了"红黑树插入操作-图2"所示的情况。再将当前节点指向其祖父节点，再次从新的当前节点(7)开始算。 "这样上右图就变成情况2了。"#对于情况2：插入节点的父节点是红色的，叔叔节点是黑色的，且插入节点是其父节点的右子节点。对于这种情况，要做的操作有：将当前节点(7)的父节点(2)作为新的节点，以新的当前节点为支点做左旋操作。完成后如"红黑树插入操作-图3"所示，"这样左下图就变成情况3了。"#对于情况3：插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的左子节点。对于这种情况，要做的操作有：将当前节点的父节点(7)涂黑，将祖父节点(11)涂红，在祖父节点为支点做右旋操作。最后把根节点涂黑，整个红-黑树重新恢复了平衡，如"红黑树插入操作-图4"所示。至此，插入操作完成！#summary 如果是从情况1开始发生的，必然会走完情况2和3，也就是说这是一整个流程，如果从情况2开始发生，那再走个情况3即可完成调整，如果直接只要调整情况3，那么前两种情况均不需要调整了。故变色和旋转之间的先后关系可以表示为："变色->左旋->右旋。"

文章图片
红黑树插入操作--图1.png

文章图片
红黑树插入操作--图2.png

文章图片
红黑树插入操作--图3.png

文章图片
红黑树插入操作--图4.png 【数据结构与算法系列|数据结构与算法系列 (6) 树】删除操作

红-黑树的删除和二叉查找树的删除是一样的，只是删除后多了个平衡的修复。我们先来回忆一下二叉搜索树的删除： ①如果待删除的节点没有子节点，那么直接删除即可。 ②如果待删除的节点只有一个子节点，那么直接删掉，并用其子节点去顶替它。 ③如果待删除的节点有两个子节点，这种情况比较复杂：首先找出它的后继节点，然后处理“后继节点”和“被删除节点的父节点”之间的关系，最后处理“后继节点的子节点”和“被删除节点的子节点”之间的关系。每一步中也会有不同的情况。#删除过程太复杂了很多情况下会采用在节点类中添加一个删除标记属性，并不是真正的删除节点。

红黑树的效率

红黑树的查找、插入和删除时间复杂度都为O(log2^N)，额外的开销是每个节点的存储空间都稍微增加了一点，因为一个存储红黑树节点的颜色变量。插入和删除的时间要增加一个常数因子，因为要进行旋转，平均一次插入大约需要一次旋转，因此插入的时间复杂度也是O(log2N),(时间复杂度的计算要省略常数)，但实际上比普通的二叉树是要慢的。大多数应用中，查找的次数比插入和删除的次数多，所以应用"红黑树"取代普通的"二叉搜索树"总体上不会有太多的时间开销。而且红黑树的优点是对于有序数据的操作不会慢到O(N)的时间复杂度。

2.3 Huffman树(霍夫曼树)(最优二叉树) 其主要作用在于数据压缩和编码长度的优化。
3.多路树 这里主要讨论多路搜索/平衡/排序树

#二叉树的问题二叉树的操作效率较高，但是二叉树是需要加载到内存的，如果二叉树的节点少，没有什么问题，但是如果二叉树的节点很多(比如1亿)，就存在如下问题: >> 在构建二叉树时，需要多次进行i/o操作(海量数据存在DB或文件中)，节点海量，构建二叉树时，速度有影响 >> 节点海量，也会造成二叉树的高度很大，会降低操作速度.#多路树在二叉树中，每个节点有数据项，最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树（multiway tree）比如2-3树，2-3-4树就是多叉树，多叉树通过重新组织节点，减少树的高度，能对二叉树进行优化。

3.1 2-3 树

2-3树是最简单的B树结构, 其插入规则如下: >> 2-3树的所有叶子节点都在同一层.(只要是B树都满足这个条件) >> 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点. >> 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点 >> 当按照规则插入一个数到某个节点时，不能满足上面三个要求，就需要拆，先向上拆，如果上层满，则拆本层，拆后仍然需要满足上面3个条件。 >> 对于三节点的子树的值大小仍然遵守(BST 二叉排序树)的规则。

3.2 B TREE(balance tree, 也是搜索树或排序树)

#概述 B-tree树即B树，B即Balanced，平衡的意思。有人把B-tree翻译成B-树，容易让人产生误解。会以为B-树是一种树，而B树又是另一种树。实际上，B-tree就是指的B树。#是一种多路搜索/排序/平衡树（并不是二叉的）： 1.定义任意非叶子结点最多只有M个儿子；且M>2； 2.根结点的儿子数为[2, M]； 3.除根结点以外的非叶子结点的儿子数为[M/2, M]； 4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字） 5.非叶子结点的关键字个数=指向儿子的指针个数-1； 6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]； 7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树； 8.所有叶子结点位于同一层；#B树的搜索从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；#B树的特性： 1.关键字集合分布在整颗树中； 2.任何一个关键字出现且只出现在一个结点中； 3.搜索有可能在非叶子结点结束； 4.其搜索性能等价于在关键字全集内做一次二分查找； 5.自动层次控制；#如：（M=3）

文章图片
B TREE.png

由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最底搜索性能为：其中，M为设定的非叶子结点最多子树个数，N为关键字总数；所以B树的性能总是等价于二分查找(与M值无关),也就没有B树平衡的问题；由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并；

文章图片
BTREE-搜索性能.png B树性能优势

B树通过重新组织节点，降低树的高度，并且减少i/o读写次数来提升效率。 1) 如图B树通过重新组织节点，降低了树的高度. 2) 文件系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页(页得大小通常为4k)，这样每个节点只需要一次I/O就可以完全载入 3) 将树的度M设置为1024，在600亿个元素中最多只需要4次I/O操作就可以读取到想要的元素, B树(B+)广泛应用于文件存储系统以及数据库系统中

文章图片
B树性能优势.png 3.2 B+TREE

B+树是B树的变体，也是一种多路搜索树： 1.其定义基本与B树同，除了： 2.非叶子结点的子树指针与关键字个数相同； 3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）； 4.为所有叶子结点增加一个链指针； 5.所有关键字都在叶子结点出现；如：（M=3）B+的搜索与B树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；#B+的特性： 1.所有关键字都出现在叶子结点的链表中(稠密索引), 且链表中的关键字恰好是有序的； 2.不可能在非叶子结点命中； 3.非叶子结点相当于是叶子结点的索引(稀疏索引), 叶子结点相当于是存储(关键字)数据的数据层； 4.更适合文件索引系统；

文章图片
B+TREE.png 3.3 B*TREE

是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针； B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）；#B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针； B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；#B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了); 如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；#所以，B*树分配新结点的概率比B+树要低，空间使用率更高；

文章图片
B*TREE.png

#B树多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；#B+树：在B树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引； B+树总是到叶子结点才命中；#B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

https://blog.csdn.net/weixin_39446980/article/details/90439883
参考资料
http://c.biancheng.net/view/3385.html