2022-03-24 15:52 已编辑民生科技_大数据开发

关注

B树和B+树

1，二分法到二叉树

二分法是一种查找算法，实现思路为：

首先对数据集进行排序。
找到数据集中间位置的节点。
用查找的条件和间节点进行比较，等于则直接返回，中间节点数据小于查找条件则说明数据在排序列表的左边，大于则说明数据在排序列表的右边。

从二分法查找的过程来看，如果能保证数据的有序性，并且预先把数据进行分段存储好数据的中间节点，那么查找的时候就会很简单，所以如果要使用二分法，我们通常都会在数据存储的时候就预先把数据整理成适合二分法查找的数据结构，这就演化出了树和跳表两种数据结构。

2，二叉查找树到平衡二叉树

二叉查找树充分了利用二分法的思维提升了数据查找的效率，不过我们在构建二叉树的时候就会发现很容易出现一个问题，就是二叉查找树的“高度”不稳定。

如果树的节点变成线性结构，那么就会极大的降低我们的查询效率，所以必须要有一种方式来保证二叉树节点的平衡，让树的节点高度差不会太大，这个时候就衍生了一些平衡算法，比如AVL树和红黑树，称为平衡二叉树，平衡二叉树通常会保证树的左右子树高度差的绝对值不会超过1。

3，平衡二叉树

平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构；

性质：

（1）非叶子节点最多拥有两个子节点；

（2）非叶子节值大于左边子节点、小于右边子节点；

（3）树的左右两边的层级数相差不会大于1;

（4）没有值相等重复的节点;

4，B树

B树和平衡二叉树稍有不同的是B树属于多叉树，又名平衡多路查找树（查找路径不只两个），数据库索引技术里大量使用者B树和B+树的数据结构。

4.1B树定义

00，定义

通常m阶的B树，它必须满足如下条件：

每个节点最多只有m个子节点。
每个非叶子节点（除了根）具有至少 m/2 子节点。
如果根不是叶节点，则根至少有两个子节点。
具有k个子节点的非叶节点包含k -1个键。
所有叶子都出现在同一水平，没有任何信息（高度一致）。

01，B树的阶？

B树中一个节点的子节点数目的最大值，用m表示，假如最大值为10，则为10阶

所有节点中，节点【13,16,19】拥有的子节点数目最多，四个子节点（灰色节点），所以可以定义上面的图片为4阶B树。

02，根节点

节点【10】即为根节点。

特征：

如果根节点不是树中唯一节点，那么至少有两个子节点，不然就是单支了。

在根节点不是树中唯一节点的m阶B树中，有：子节点数量M满足：2 <= M <= m，每个节点包含的元素数量K满足：1 <= K <= m-1。

03，内部节点

节点【3，6】、【13，16，19】均为内部节点。

特征：

内部节点是除叶子节点和根节点之外的所有节点，拥有父节点和子节点。

假定m阶B树的内部节点的子节点数量为M，则一定要符合m/2 <= M <= m关系式，该内部节点包含元素数量为M-1；子节点包含的元素数量K满足（m/2）-1 <= K <= m-1。m/2向上取整。

04，叶子节点

最后一层为叶子节点。

特征：

在m阶B树中叶子节点的元素数量K符合：（m/2）-1 <= K <= m-1

05，B树的高度

一颗含有N个节点值的m阶B树的最大高度为：

log_m/2(N+1)/2 + 1

06，总结

m阶B树：

根节点的子节点个数：[2，m]

根节点的元素个数：[1，m-1]

内部节点的子节点个数：[ceil(m/2)，m]

非根节点的元素个数：[ceil(m/2)-1，m-1]

4.2 B树的操作

01，插入

针对m阶高度h的B树，插入一个元素时，首先在B树中是否存在，如果不存在，即在叶子结点处结束，然后在叶子结点中插入该新的元素。

若该节点元素个数小于m-1，直接插入；
若该节点元素个数等于m-1，引起节点分裂；以该节点中间元素为分界，取中间元素（偶数个数，中间两个随机选取）插入到父节点中；
重复上面动作，直到所有节点符合B树的规则；最坏的情况一直分裂到根节点，生成新的根节点，高度增加1；

02，删除

首先查找B树中需删除的元素,如果该元素在B树中存在，则将该元素在其结点中进行删除；删除该元素后，首先判断该元素是否有左右孩子结点，如果有，则上移孩子结点中的某相近元素(“左孩子最右边的节点”或“右孩子最左边的节点”)到父节点中，然后是移动之后的情况；如果没有，直接删除。

某结点中元素数目小于（m/2）-1,(m/2)向上取整，则需要看其某相邻兄弟结点是否丰满；
如果丰满（结点中元素个数大于(m/2)-1），则向父节点借一个元素来满足条件；
如果其相邻兄弟都不丰满，即其结点数目等于(m/2)-1，则该结点与其相邻的某一兄弟结点进行“合并”成一个结点；

5，B+树

B+树是应文件系统所需而产生的B树的变形树

5.1 B+树的特征

有m个子树的中间节点包含有m个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引；
所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)；
所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)；