注意:首先需要说明的一点是:B-树就是B树,没有所谓的B减树 引言 我们都知道二叉查找树的查找的时间复杂度是O(log N),其查找效率已经足够高了,那为什么还有B树和B+树的出现呢?难道它两的时间复杂度比二叉查找树还小吗? 这样就引出来了一个新的查找树结构 ——多路查找树。 根据AVL给我们的启发,一颗平衡多路查找树(B~树)自然可以使得数据的查找效率保证在O(logN)这样的对数级别上。 下面来具体介绍一下B树(Balance Tree), B树一个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<Ki+1(1≤i≤n-1)。 Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的关键字均小于Ki+1。 n为结点中关键字的个数,满足ceil(m/2)-1≤n≤m-1。 示例:三阶B树(实际中节点中元素很多) 查询 以上图为例:若查询的数值为5: 插入 对高度为k的m阶B树,新结点一般是插在叶子层。通过检索可以确定关键码应插入的结点位置。然后分两种情况讨论: 例如:在下面的B树中插入key:4 第一步:检索key插入的节点位置如上图所示,在3,5之间; 第二步:判断节点中的关键码个数: 第三步:结点分裂: 最终结果如下图:虽然插入比较麻烦,但是这也能确保B树是一个自平衡的树 删除 B树中关键字的删除比插入更复杂,在这里,只介绍其中的一种方法: (1)找出该关键字所在的结点。然后根据 k所在结点是否为叶子结点有不同的处理方法。 (2)若该结点为非叶结点,且被删关键字为该结点中第i个关键字key[i],则可从指针son[i]所指的子树中 找出最小关键字Y,代替key[i]的位置,然后在叶结点中删去Y。 因此,把在非叶结点删除关键字k的问题就变成了删除叶子结点中的关键字的问题了。 在B-树叶结点上删除一个关键字的方法: (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。对任意关键字的删除都可以转化为对最下层关键字的删除。 下面举一个简单的例子:删除元素11. 第一步:判断该元素是否在叶子结点上。 第二步:判断其左右兄弟结点中有“多余”的关键字,即:原关键字个数n>=ceil(m/2) - 1; 注意 ①、B树主要用于文件系统以及部分数据库索引,例如: MongoDB。而大部分关系数据库则使用B+树做索引,例如:mysql数据库; B+ 树B+树是B树的变种,有着比B树更高的查询效率。下面,我们就来看看B+树和B树有什么不同 特点一个m阶的B+树具有如下几个特征: 1.有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据 都保存在叶子节点。 2.所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小 自小而大顺序链接。 3.所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素。 下面是一棵3阶的B+树: 查找 B+树的优势在于查找效率上,下面我们做一具体说明: 插入B+树的插入与B树的插入过程类似。不同的是B+树在叶结点上进行,如果叶结点中的关键码个数超过m,就必须分裂成关键码数目大致相同的两个结点,并保证上层结点中有这两个结点的最大关键码。 删除B+树中的关键码在叶结点层删除后,其在上层的复本可以保留,作为一个”分解关键码”存在,如果因为删除而造成结点中关键码数小于ceil(m/2),其处理过程与B-树的处理一样。在此,我就不多做介绍了。 总结B+树相比B树的优势: |
|