B树、B+树

B树是一种的平衡的多路查找树，我们把树中结点最大的孩子数目称为B树的阶。通常记为m。

一棵m阶B树或为空树，或为满足如下特征的m叉树：

1）树中每个结点至多有m棵子树。（即至多含有m-1个关键字）（“两棵子树指针夹着一个关键字”）
2）若根结点不是终端结点（最底层非叶子结点），则至少含有两棵子树。
3）除根结点外的所有非叶子结点至少含有 ceil(m/2) 棵子树。（即至少含有ceil(m/2)-1个关键字）
4）所有叶结点的结构如下：

[n，p0，k1，p1，k2，…，kn，pn]

其中 ki(i=1,2,…,n)为节点的关键字，且满足 k1<k2<k3…<kn

其中pi(i=0,1,2,3…,n)为指向子树根结点的指针，
指针pi-1所指的子树的所有节点的关键字都小于ki
指针pi所指向子树的所有节点的关键字都小于ki 1，如p0指向的子树所有结点的值都小于k1的值

n是结点中关键字的个数

5）所有的叶子结点出现在同一层次上，不带信息。（就像是二分查找判断树中查找失败的结点）

B树的操作

1、B树的查找

B树是多路查找树，二叉排序树是二路查找，B树是多路查找，所以它是二叉排序树的拓展。因此B树的查找操作和二叉排序树的查找操作非常类似。

查找过程：
①先让待查找关键字key和结点中关键字比较，如果等于其中某个关键字，则查找成功。
②如果和所有关键字都不相等，则看key处在哪个范围内，然后去对应的指针所指向的子树查找。

Eg：如果key比第一个关键字k1还小，则去p0指针所指向的子树中查找，如果比最后一个关键字kn还大，则去pn指针所指的子树查找。

比如查找 key=16
首先与第一个节点10比较，发现比10大，然后查找其右子树，其右子节点从左往右（因为已经有序），比14大比20小，查找其中间的指针所指子树，得到16所在的结点。

2、B树的插入操作

在二叉排序树中，仅需查找到插入的终端节点的位置，但是，B树中找到插入的位置后，并不能简单地将其添加到终端结点位置，因为此时可能会导致整棵树不满足B树定义中的要求。

如果B树所有的非叶子结点的左右子树的结点数目均保持差不多（平衡），那么B树的搜索效率能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变B树结构（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销。

给定一组关键字{20,30,50,52,60,68,70}，给出创建一颗3阶B树的过程

第一步：由于m=3，所以除了根节点以外，非叶子结点至少有ceil(3/2)-1=1个关键字，最多有3-1=2个关键字。所以依次插入20和30两个关键字到结点。

第二步：接下来插入50，如下左图，但是由于最多有2个关键字，所以这个结点不满足B数需求，需要分裂。得到如下右图。

分裂的方法：取这个关键字数组中的中间关键字（在这里面20,30,50为3个关键字，序号为1,2,3，中间关键字就是ceil(3/2)=2，即30为中间关键字）为新节点，然后其他关键字形成两个节点作为新节点的左右孩子。

第三步：接下来插入52，由于50只有一个关键字，所以可以插入52

第四步：接下来插入60，插入60之后该结点关键字数量又不符合要求，需要分裂。

分裂过程:取中间关键字52，由于根节点只含有30一个关键字，可以将52和30合并到一起。接下来需要处理50和60两个结点，由于30<50<52，60>52，所以50和60各自单独作为一个结点。第五步：接下来插入68，由于60结点只有一个关键字，所以可以插入68

第六步：接下来插入70，插入70之后关键字数量有不符合要求，需要分裂，分裂后得到下图：

第七步：分裂根节点，类似的，取中间关键字52作为新的根节点的关键字（这个例子说明B树的插入过程可能会有连锁分裂的现象）

如上图所示，这一系列插入就完成了。

3、B树的删除操作

B树的删除操作与插入操作类似，但是要稍微复杂些，要使得的删除后的结点中的关键字个数>= ceil(m/2)-1，因此将涉及结点的“合并”问题。由于删除的关键字位置不同，可以分为关键字在终端结点和不在终端结点两种情况。

（1）如果删除的关键字在终端结点上（最底层非叶子结点）：
分情况讨论：
①结点内关键字数量大于ceil(m/2)-1（关键字数量最小要求），这时删除这个关键字不会破坏B树的定义要求。所以直接删除。
②结点内关键字数量等于ceil(m/2)-1，并且其左右兄弟结点中存在关键字数量大于ceil(m/2)-1的结点，则去兄弟结点中借关键字。
③结点内关键字数量等于ceil(m/2)-1，并且其左右兄弟结点中不存在关键字数量大于ceil(m/2)-1的结点，则需要进行结点合并。

还是看这张图，在这个三阶B树中,ceil(3/2)-1=1
若要删除9，可以看出9所在的结点关键字数目是大于1的满足①条件，可以直接删除。
若要删除2，满足②条件，从右兄弟中借结点，并且需要按照大小顺序进行调整。具体调整如下图:

将2所在的结点删除7来到5的位置，5来到2的位置

若要删除22，满足条件③，其只有左兄弟只有一个关键字，所以需要进行结点合并。
合并：从上一层的结点取关键字与下一层结点合并，如果左右兄弟结点都存在则方式不唯一，这里22只有左兄弟，所以只能把16和22和并成一个结点。结果如下：

（2）如果删除的关键字不在终端结点上（最底层非叶子结点）：需要先转换成在终端结点上，再按照在终端结点上的情况来分别考虑对应的方法。
相邻关键字：对于不在终端结点上的关键字，它的相邻关键字是其左子树中值最大的关键字或者右子树中值最小的关键字。

第一种情况:存在关键字数量大于ceil(m/2)-1结点的左子树或者右子树，在对应子树上找到该关键字的相邻关键字，然后将相邻关键字替换待删除的关键字。

若要删除10，则找到它的相邻关键字9和11在图中的位置，发现两者皆满足其所在结点上关键字数量大于ceil(3/2)=1，所以与任意一个替换均可，这里我们替换9，得到下图：

接着我们使用删除终端结点的方法删除10即可，这里直接删除10

第二种情况:左右子树关键字数量均等于ceil(m/2)-1，则将这两个左右子树结点合并，然后删除待删除关键字。
比如要删除20：直接合并16和22，让14右边的指针指向16和22组成的新结点即可。

这其实适合我们刚才删除终端结点中是一样的，要删除结点20，我们可以先将20和22进行交换，接着我们的目的就变成删除一个终端结点20，删除这样一个终端结点，但是的关键字数目已经等于最小关键字数目要求即，ceil(m/2)-1了，这就是删除终端结点的第三种情况，我们需要进行合并，从上层结点中借一个22来与16进行合并，合并之后可将结点20删除，让14右边指针指向合并后的新结点，其最终效果是一样的。

B 树
B 树是常用于数据库和操作系统的文件系统中的一种用于查找的数据结构。

m阶B 树与m阶的B树的主要差异在于：
（1）在B 树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；而在B树中，具有n个结点的关键字含有（n 1）棵子树。
（2）在B 树中，每个结点（非根内部结点）关键字个数n的范围是ceil(m/2)<=n<=m(根节点1<=n<=m)，在B树中，每个结点（非根内部结点）关键字个数n的范围是ceil(m/2)-1<=n<=m-1（根节点：1<=n<=m-1）。
（3）在B 树中，叶结点包含信息，所有非叶结点仅起到索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。
（4）在B 树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶节点中；而在B树中，叶结点包含的关键字和其他节点包含的关键字是不重复的。
（5）在B 树中，有一个指针指向关键字最小的叶子结点，所有叶子结点连接成一个链表。

这篇好文章是转载于：学新通技术网