注意：首先需要说明的一点是：B-树就是B树，没有所谓的B减树
引言
这样就引出来了一个新的查找树结构 ——多路查找树。 根据AVL给我们的启发，一颗平衡多路查找树(B~树)自然可以使得数据的查找效率保证在O(logN)这样的对数级别上。
下面来具体介绍一下B树（Balance Tree），
Ｂ树
一个m阶的B树具有如下几个特征：B树中所有结点的孩子结点最大值称为B树的阶，通常用m表示。一个结点有k个孩子时，必有k-1个关键字才能将子树中所有关键字划分为k个子集。
1.根结点至少有两个子女。 2.每个中间节点都包含k-1个元素和k个孩子，其中 ceil（m/2） ≤ k ≤ m 3.每一个叶子节点都包含k-1个元素，其中 ceil（m/2） ≤ k ≤ m 4.所有的叶子结点都位于同一层。 5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划分 6.每个结点的结构为：（n，A0，K1，A1，K2，A2，… ，Kn，An） 其中，Ki(1≤i≤n)为关键字，且Ki
查询
插入
例如：在下面的B树中插入key：4
第一步：检索key插入的节点位置如上图所示，在3,5之间；
最终结果如下图：虽然插入比较麻烦，但是这也能确保Ｂ树是一个自平衡的树
删除
（1）找出该关键字所在的结点。然后根据 k所在结点是否为叶子结点有不同的处理方法。 （2）若该结点为非叶结点，且被删关键字为该结点中第i个关键字key[i]，则可从指针son[i]所指的子树中 找出最小关键字Y，代替key[i]的位置，然后在叶结点中删去Y。 因此，把在非叶结点删除关键字k的问题就变成了删除叶子结点中的关键字的问题了。
（1）如果被删关键字所在结点的原关键字个数n>=ceil(m/2)，说明删去该关键字后该结点仍满足B树的定义。 这种情况最为简单，只需从该结点中直接删去关键字即可。 （2）如果被删关键字所在结点的关键字个数n等于ceil(m/2)-1，说明删去该关键字后该结点将不满足B树的定义， 需要调整。 调整过程为： 如果其左右兄弟结点中有“多余”的关键字,即与该结点相邻的右（左）兄弟结点中的关键字数目大于 ceil(m/2)-1。则可将右（左）兄弟结点中最小（大）关键字上移至双亲结点。而将双亲结点中小（大）于该上 移关键字的关键字下移至被删关键字所在结点中。 如果左右兄弟结点中没有“多余”的关键字，即与该结点相邻的右（左）兄弟结点中的关键字数目均等于 ceil(m/2)-1。这种情况比较复杂。需把要删除关键字的结点与其左（或右）兄弟结点以及双亲结点中分割二者 的关键字合并成一个结点,即在删除关键字后，该结点中剩余的关键字加指针，加上双亲结点中的关键字Ki一起， 合并到Ai（是双亲结点指向该删除关键字结点的左（右）兄弟结点的指针）所指的兄弟结点中去。如果因此使双亲 结点中关键字个数小于ceil(m/2)-1，则对此双亲结点做同样处理。以致于可能直到对根结点做这样的处理而使 整个树减少一层。 总之，设所删关键字为非终端结点中的Ki，则可以指针Ai所指子树中的最小关键字Y代替Ki，然后在相应结点中删除Y。对任意关键字的删除都可以转化为对最下层关键字的删除。
注意
B+ 树
Ｂ＋树是Ｂ树的变种，有着比Ｂ树更高的查询效率。下面，我们就来看看B+树和B树有什么不同
特点
一个m阶的B+树具有如下几个特征：
1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据 都保存在叶子节点。 2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小 自小而大顺序链接。 3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。 查找
B+树的优势在于查找效率上，下面我们做一具体说明：
首先，Ｂ＋树的查找和Ｂ树一样，类似于二叉查找树。起始于根节点，自顶向下遍历树，选择其分离值在要查找值的任意一边的子指针。在节点内部典型的使用是二分查找来确定这个位置。
（1）、不同的是，Ｂ＋树中间节点没有卫星数据（索引元素所指向的数据记录），只有索引，而Ｂ树每个结点中的每个关键字都有卫星数据；这就意味着同样的大小的磁盘页可以容纳更多节点元素，在相同的数据量下，Ｂ＋树更加“矮胖”，ＩＯ操作更少
B树的卫星数据：
B+树的卫星数据：
需要补充的是，在数据库的聚集索引（Clustered Index）中，叶子节点直接包含卫星数据。在非聚集索引（NonClustered Index）中，叶子节点带有指向卫星数据的指针。
（2）、其次，因为卫星数据的不同，导致查询过程也不同；Ｂ树的查找只需找到匹配元素即可，最好情况下查找到根节点，最坏情况下查找到叶子结点，所说性能很不稳定，而Ｂ＋树每次必须查找到叶子结点，性能稳定
（3）、在范围查询方面，B+树的优势更加明显
B树的范围查找需要不断依赖中序遍历。首先二分查找到范围下限，在不断通过中序遍历，知道查找到范围的上限即可。整个过程比较耗时。
而B+树的范围查找则简单了许多。首先通过二分查找，找到范围下限，然后同过叶子结点的链表顺序遍历，直至找到上限即可，整个过程简单许多，效率也比较高。
例如：同样查找范围[3-11]，两者的查询过程如下：
B树的查找过程：
B+树的查找过程：
插入
B+树的插入与B树的插入过程类似。不同的是B+树在叶结点上进行，如果叶结点中的关键码个数超过m，就必须分裂成关键码数目大致相同的两个结点，并保证上层结点中有这两个结点的最大关键码。
删除
B+树中的关键码在叶结点层删除后，其在上层的复本可以保留，作为一个”分解关键码”存在，如果因为删除而造成结点中关键码数小于ceil(m/2)，其处理过程与B-树的处理一样。在此，我就不多做介绍了。
总结
B+树相比B树的优势：
1.单一节点存储更多的元素，使得查询的IO次数更少；
2.所有查询都要查找到叶子节点，查询性能稳定；
3.所有叶子节点形成有序链表，便于范围查询。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/226186.html原文链接：https://javaforall.net
