词条 | B树 |
释义 | § 定义 其定义如下: 一棵m阶的B树满足下列条件: ⑴ 树中每个结点至多有m个孩子; ⑵ 除根结点和叶子结点外,其它每个结点至少有m/2个孩子; ⑶ 若根结点不是叶子结点,则至少有2个孩子; ⑷ 所有叶子结点都出现在同一层,叶子结点不包含任何关键字信息; ⑸ 有k个孩子的非终端结点恰好包含有k-1个关键字。 在B树中,每个结点中关键字从小到大排列,并且当该结点的孩子是非叶子结点时,该k-1个关键字正好是k个孩子包含的关键字的值域的分划。 因为叶子结点不包含关键字,所以可以把叶子结点看成在树里实际上并不存在外部结点,指向这些外部结点的指针为空,叶子结点的数目正好等于树中所包含的关键字总个数加1。 B树中的一个包含n个关键字,n+1个指针的结点的一般形式为: (n,P0,K1,P1,K2,P2,…,Kn,Pn) 其中,Ki为关键字,K1<K2<…<Kn, Pi 是指向包括Ki到Ki+1之间的关键字的子树的指针。 § 2. B树的查找 : 在B树中查找给定关键字的方法是,首先把根结点取来,在根结点所包含的关键字K1,…,kj查找给定的关键字(可用顺序查找或二分查找法),若找到等于给定值的关键字,则查找成功;否则,一定可以确定要查的关键字在某个Ki或Ki+1之间,于是取Pi所指的结点继续查找,直到找到,或指针Pi为空时查找失败。 查找算法演示 性能分析: 设B树包含N个关键字,因此有N+1个叶子结点,叶子都在第I层。因为根至少有两个孩子,因此第二层至少有两个结点。除根和叶子外,其它结点至少有┌m/2┐个孩子,因此在第三层至少有2*┌m/2┐个结点,在第四层至少有2*┌m/2┐2个结点,...,在第I层至少有2*┌m/2┐I-1 个结点,于是有: N+1 ≥ 2*┌m/2┐I-1 即: I ≥ log┌m/2┐( ) 这个公式保证了B树的查找效率是相当高的。 § 3. B树的插入 : 当在叶子结点处于第L+1层的B树中插入关键字时,被插入的关键字总是进入第L层的结点。 若在一个包含j<m-1个关键字的结点中插入一个新的关键字,则把新的关键字直接插入该结点即可;但若把一个新的关键字插入到包含m-1(m为B树的阶)个关键字的结点中,则将引起结点的分裂。在这种情况下,要把这个结点分裂为两个,并把中间的一个关键字拿出来插到该结点的双亲结点中去,双亲结点也可能是满的,就需要再分裂、再往上插,从而可能导致B树可能朝着根的方向生长。 插入算法演示 § 4. B树的删除: 当从B树中删除一个关键字Ki时,总的分为以下两种情况: 如果该关键字所在的结点不是最下层的非叶子结点,则先需要把此关键字与它在B树中后继对换位置,即以指针Pi所指子树中的最小关键字Y代替Ki,然后在相应的结点中删除Y。 如果该关键字所在的结点正好是最下层的非叶子结点,这种情况下,会有以下两种可能: ① 若该关键字Ki所在结点中的关键字个数不小于┌m/2┐,则可以直接从该结点中删除该关键字和相应指针即可。 ② 若该关键字Ki所在结点中的关键字个数小于┌m/2┐,则直接从结点中删除关键字会导致此结点中所含关键字个数小于┌m/2┐-1 。这种情况下,需考察该结点在B树中的左或右兄弟结点,从兄弟结点中移若干个关键字到该结点中来(这也涉及它们的双亲结点中的一个关键字要作相应变化),使两个结点中所含关键字个数基本相同;但如果其兄弟结点的关键字个数也很少,刚好等于┌m/2┐-1 ,这种移动则不能进行,这种情形下,需要把删除了关键字Ki的结点、它的兄弟结点及它们双亲结点中的一个关键字合并为一个结点。 |
随便看 |
百科全书收录594082条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。