从数据结构角度理解B树的特性

一 背景

之前通过网课学习了B树和B+树的一些知识，我再另一篇笔记中分析比较了4钟类型的树结构，文章地址，最近忙于考研，正好看到了王道书上B树和B+树的知识点，从数据结构角度来讲解的，为了加深理解，我将结合王道书的内容和自己的理解，写成本篇笔记。

二 B树的概念

首先标明几个概念：

1.阶：B树中所有结点的孩子个数的最大值

2.终端结点：除叶子结点外最底层的那一层结点

1.概念：B树称为多路平衡查找树。

2.特点：

1).树中每个结点至多有m棵子树，即至多含有m-1个关键字，这里的关键字就是指一个索引结点中含有m-1个元素值。

2).若根节点不是终端结点，则至少有两棵子树

3).除根结点外的非叶子结点至少有m/2(向上取整)棵子树，即至少含有m/2-1（向上取整）个关键字

4).查找的叶节点都出现在同一层次上，并且不带信息关键字

3举个例子：

先推荐个数据结构可视化的网站：戳我进入

分析：

1.结点中的孩子（子树）个数等于该结点中的关键字个数+1，例如222，665所在的结点A，那么A的子树个数为3，关键字为2

2.如果根结点没有关键字，则为空；如果根结点有关键字，则其子树个数必大于等于2，即其关键字个数必大于等于1。

3.除了根结点外的非终端结点至少有5/2(向上取整)，关键字至少有5/2-1（向上取整），至多有5棵子树，关键字至多有4个

4.所有的叶子结点均在第4层，代表查找失败的位置。

三 B树的高度

1.B树的高度即磁盘I/O操作的次数

2.因为B树中每个结点最多有m棵子树，m-1个关键字，所以高度h和m阶B树中的关键字个数n所应满足的公式为：h>=logm (n+1)

3.若让每个结点中的关键字个数达到最少，则容纳同样多的关键字的B树的高度就会最高。

因为关键字结点个数为n，所以叶结点的结点为n+1。而叶子结点所在那层至少有2*(m/2)的h-1次幂，因此n+1 >= 2*(m/2)的h-1次幂，即h<=log的m/2(向上取整)((n+1)/2)+1

四 B树的查找

1.B树查找的两个基本操作：

（1）在磁盘上查找B树中的结点

（2）将结点放入内存，在内存中比较结点中的关键字

2.查找到叶结点时，没有对应的关键字

五 B树的插入

1.通过B树查找算法定位到最底层中的某个非叶子结点上。

2.插入到某个结点后，如果该结点中的关键字个数小于m，则直接插入，不需要变换位置。

如果插入后检查被插入结点内的关键字个数大于m-1了，则此时需要对结点进行分裂。

具体分裂的方法：

取一个新的结点，再插入key的原结点后，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，如果刚好m-1为奇数，则中间位置m/2（向上取整)的结点插入原结点的父结点。整个过程需要递归向上和递归向下插入结点。

六 B树的删除

1.直接删除关键字，如果删除关键字所在的结点删除前的关键字个数>=m/2（向上取整），则直接删除

2.借兄弟的结点，如果删除关键字所在的结点删除前的关键字个数=m/2（向上取整)-1，且与次结点相邻的左右兄弟结点的关键字个数>=m/2(向上取整)

则调整左，右，双亲的结点位置。

3.兄弟的结点不够借：根据第2中思想，发现左右兄弟关键字个数均为m/2-1（向上取整），发现不好借，因为借了之后，左/右兄弟结点都也不平衡了。因此就尝试向父亲借，然后再调整左，右，双亲的结点位置。

七 B树和B+树的区别

1.在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；而在B树中，具有n个关键字的结点只含有n+1棵子树

2.在B+树中，每个结点的关键字个数n的范围为m/2（向上取整)<=n<=m，而在B树中，每个结点的关键字个数n的范围为m/2-1（向上取整)<=n=<m-1

3.在B+树中，只有叶子结点包含数据信息和存储地址，而非叶子结点中只存索引地址。非叶子结点的每个索引项只包含最大关键字和索引地址（关键字其实指的就是索引项）

4.在B+树中，叶子结点包含了所有的关键字，并且每个关键字都用指针从小到大链接，因此叶子结点和非叶子结点中关键字是会有重复的。而B树中，叶子结点和非叶子结点中的关键字是不重复的。

八 B+树比B树搜索更快的原因

就我理解而言，他们俩的数据结构的差异，即B+树的非叶子结点只起到了索引作用，因此B+树一个结点中包含的关键字个数相对于B树来说要多很多。