B+树的插入和删除策略.[急]

分类: 电脑/网络 >>程序设计 >>其他编程语言

问题描述:

B+树的插入和删除策略.

好多书上说的都不一样

什么重新分布指针啊?搞不懂

解析:

我上学时做过B+树的project,的确比较复杂

插入的时候,当一个节点满了就会引起节点分裂,同时可能引起父节点分裂,最终指向根结点

删除的时候,当一个节点包含的个数小于一半时需要合并节点,同时要考虑其他节点的相应变化

B+树是一种平衡多叉树,跟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之间的关键字的子树的指针。

如图删除过程，删除80之后，里面空掉了：

左兄弟不存在，右兄弟存在借不起，这个时候就拿走双亲90的关键字，将空掉的结点，该关键字和右兄弟结点合并：

但是发现双亲空了，和一开始一样，准备向兄弟结点去借，它的右兄弟不存在，左兄弟存在但是不够，只能向双亲拿了，这个时候将空结点、关键字50和右兄弟合并：

双亲有一个键，所以删除到此结束

---