B-树(B-树的定义: B-树的查找 B-树的插入 B-树的删除:)

B+树(B+树的定义 B+树的查找 B+树的插入 B+树的删除)

B树(二叉排序树（B树）的查找 二叉排序树（B树）的插入和删除)

B-树

B-树的定义:

B-树是一种平衡的多路查找树，在文件系统中有所应用。主要用作文件的索引。

B-树结构特性：一棵m阶B-树，或为空树，或为满足下列特性的m叉树：(m≥3)

(1)根结点只有1个，关键字字数的范围[1,m-1]，分支数量范围[2,m]；

(2)除根以外的非叶结点，每个结点包含分支数范围[[m/2],m]，即关键字字数的范围是[[m/2]-1,m-1]，其中[m/2]表示取大于m/2的最小整数；

(3)非叶结点是由叶结点分裂而来的，所以叶结点关键字个数也满足[[m/2]-1,m-1]；

(4)所有的非终端结点包含信息：(n，A0，K1，A1，K2，A2，……，Kn，An)，其中Ki为关键字，Ai为指向子树根结点的指针，并且Ai-1所指子树中的关键字均小于Ki，而Ai所指的关键字均大于Ki（i=1，2，……，n）。n+1表示B-树的阶，n表示关键字个数；

(5)所有叶子结点都在同一层，并且指针域为空，具有如下性质：

根据B树定义，第一层为根有一个结点，至少两个分支，第二层至少2个结点，i≥3时，每一层至少有2乘以([m/2])的i-2次方个结点([m/2]表示取大于m/2的最小整数)。若m阶树中共有N个结点，那么可以推导出N必然满足N≥2*(([m/2])的h-1次方)-1 (h≥1)，因此若查找成功，则高度h≤1+log[m/2](N+1)/2，h也是磁盘访问次数(h≥1)，保证了查找算法的高效率。

B-树的查找

在B树中查找给定关键字的方法是，首先把根结点取来，在根结点所包含的关键字K1,…,kj查找给定的关键字（可用顺序查找或二分查找法），若找到等于给定值的关键字，则查找成功；否则，一定可以确定要查的关键字在某个Ki或Ki+1之间，于是取Pi所指的结点继续查找，直到找到，或指针Pi为空时查找失败。

B-树的插入

B-树插入算法分析：

B-树的生成从空树开始，逐个插入关键字而得。关键字的个数必须至少为[m/2]-1，每次插入总在最底层某个终端结点添加一个关键字，如果该结点关键字个数小于m-1则直接插入，如果发现新插入关键字后，关键字总数超过m-1个则结点需要分裂，做法如下：

(a)假设结点p中已经含有m-1个关键字，再插入一个关键字之后(插入总要保持关键字数组的大小有序，从小到大排好序)，可以将p分裂为p和p’，其中p含有的信息为[m/2]-1([m]表示大于m的最小整数)，p’含有的信息为m-[m/2] ([m]表示大于m的最小整数)。然后将关键字K[m/2]和指向p’的指针则一起插入到p的双亲结点中去。

(b)检查双亲结点，如果双亲结点出现(a)的情况，则回到步骤a继续执行。直到插入满足条件为止，树的深度增加过程是随着插入而自下而上生长的过程。

B-树的删除:

B-树删除算法分析，分以下5种情况讨论：

(a)被删除关键字所在的结点为叶结点，关键字数目大于或等于[m/2]，则只需要直接删去Ai和Ki即可；

(b)被删除关键字所在的结点为叶结点，关键字数目等于[m/2]-1，相邻的左右兄弟关键字数目至少有一方大于或者等于[m/2]，此时，如果右兄弟关键字数目大于或者等于[m/2]，则将右兄弟中最小的关键字上移到双亲结点中，然后将其中紧靠在上移关键字左边的一个关键字移动到被删除关键字所在的结点的最右边；否则，如果左兄弟的关键字数目大于或者等于[m/2]，则左兄弟中最大的关键字上移到双亲结点中，将紧靠在该上移关键字右边的一个关键字移动到被删除关键字所在的结点的最左边。这些做法类似于减法的借位运算。

(c)被删除关键字所在的结点为叶结点，关键字数目等于[m/2]-1，相邻的左右兄弟关键字数目均等于[m/2]-1，则从双亲借关键字补充，然后算法进入非叶结点的删除判断；

(d)被删除关键字所在的结点为非叶结点，并且关键字数目大于或等于[m/2]，则删去Ai和Ki后，原来关键字的左右孩子进行合并，若合并后的结点的关键字数目满足B-树性质，则结束，而对于关键字数目大于m-1，则进行一次分裂，将其中一个结点移到当前结点中。

(e)被删除关键字所在的结点为非叶结点，关键字数目等于[m/2]-1，相邻的左右兄弟关键字数目均等于[m/2]-1，则删除该关键字之后优先判断能否从被删除的关键字的左右孩子中寻找关键字补充，如果左右孩子的关键字数目均为[m/2]-1，如果此结点已经是树的根，则直接将被删除关键字的左右孩子结点合并即可，如果不是树的根，则从自己的双亲补充关键字，然后重复上述判断算法(d)或者(e)。

B+树

B+树的定义

B+树是应文件系统所需而出的一种B-树的变型树。一棵m阶的B+树和m阶的B-树的差异在于：

1.有n棵子树的结点中含有n个关键字。

2.所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

3.所有的非终端结点可以看成是索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字。

通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。

B+树的查找

对B+树可以进行两种查找运算：

1.从最小关键字起顺序查找；

2.从根结点开始，进行随机查找。

在查找时，若非终端结点上的剧组机等于给定值，并不终止，而是继续向下直到叶子结点。因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。其余同B-树的查找类似。

B+树的插入

m阶B树的插入操作在叶子结点上进行，假设要插入关键值a，找到叶子结点后插入a，做如下算法判别：

①如果当前结点是根结点并且插入后结点关键字数目小于等于m，则算法结束；

②如果当前结点是非根结点并且插入后结点关键字数目小于等于m，则判断若a是新索引值时转步骤④后结束，若a不是新索引值则直接结束；

③如果插入后关键字数目大于m(阶数)，则结点先分裂成两个结点X和Y，并且他们各自所含的关键字个数分别为：u=大于(m+1)/2的最小整数，v=小于(m+1)/2的最大整数；

由于索引值位于结点的最左端或者最右端，不妨假设索引值位于结点最右端，有如下操作：

如果当前分裂成的X和Y结点原来所属的结点是根结点，则从X和Y中取出索引的关键字，将这两个关键字组成新的根结点，并且这个根结点指向X和Y，算法结束；

如果当前分裂成的X和Y结点原来所属的结点是非根结点，依据假设条件判断，如果a成为Y的新索引值，则转步骤④得到Y的双亲结点P，如果a不是Y结点的新索引值，则求出X和Y结点的双亲结点P；然后提取X结点中的新索引值a’，在P中插入关键字a’，从P开始，继续进行插入算法；

④提取结点原来的索引值b，自顶向下，先判断根是否含有b，是则需要先将b替换为a，然后从根结点开始，记录结点地址P，判断P的孩子是否含有索引值b而不含有索引值a，是则先将孩子结点中的b替换为a，然后将P的孩子的地址赋值给P，继续搜索，直到发现P的孩子中已经含有a值时，停止搜索，返回地址P。

B+树的删除

B+树的删除也仅在叶子结点进行，当叶子结点中的最大关键字被删除时，其在非终端结点中的值可以作为一个“分界关键字”存在。若因删除而使结点中关键字的个数少于m/2 （m/2结果取上界，如5/2结果为3）时，其和兄弟结点的合并过程亦和B-树类似。

另外的看法，当作补充和丰富吧。B树，B-树和B+树是三个不同的概念。

B树

二叉排序树（Binary Sort Tree）又称二叉查找树，也叫B树。

它或者是一棵空树；或者是具有下列性质的二叉树：

(1)若左子树不空，则左子树上所有结点的值均小于左子树所在树的根结点的值；

(2)若右子树不空，则右子树上所有结点的值均大于右子树所在树的根结点的值；

(3)左、右子树也分别为二叉排序树；

二叉排序树（B树）的查找

时间复杂度与树的深度的有关。

步骤：若根结点的关键字值等于查找的关键字，成功。

否则：若小于根结点的关键字值，递归查左子树。

若大于根结点的关键字值，递归查右子树。

若子树为空，查找不成功。

二叉排序树（B树）的插入和删除

二叉排序树是一种动态树表。其特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的节点时再进行插入。新插入的结点一定是一个新添加的叶子节点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

插入算法：

首先执行查找算法，找出被插结点的父亲结点。

判断被插结点是其父亲结点的左儿子还是右儿子。将被插结点作为叶子结点插入。

若二叉树为空。则首先单独生成根结点。

注意：新插入的结点总是叶子结点，所以算法复杂度是O(h)。

删除算法：

如果删除的结点没有孩子，则删除后算法结束；

如果删除的结点只有一个孩子，则删除后该孩子取代被删除结点的位置；

如果删除的结点有两个孩子，则选择右孩子为根的树，它的左子树中，值最小的点作为新的根，同时在该最小值处开始，执行删除算法，如此继续到删除算法的前两种情况时，删除算法结束。

B树用途：查找信息快速，但是随着查找深度的增加，会影响查找的效率，所以，通常会使用平衡二叉树的平衡算法来进行动态平衡。