浅析B-树分裂
一、B-树的定义(适合查找的平衡的多叉树。)
一颗M阶(M>2)的B-树,是一颗平衡的M路平衡搜索树,可以是空树或者满足B-树的性质
二、B-树的性质?
(1) 根节点至少有两个孩子
(2) 每个非根节点至少有M/2(上取整)个孩子,至多有M个孩子
(3) 每个非根节点至少有M/2-i个关键字,至多有M-1个关键字,并且以升序排列
(4) key[i]和key[i+1]之间的孩子节点的值介于key[i]、key[i+1]之间
(5) 所有叶子节点都在同一层
三、B-树分裂图示
给定一组数:{12 45 9 78 60 55 58}
(1) 先插入12
(2) 再插入45
(3) 插入9
(4) 插入78
(5) 插入60
(6) 插入55
(7) 插入58
四、B-树的基本操作
1、 创建
2、 插入
(1) 若B树的根为空,则直接插入(new上一个新的节点,插入,更新size )
(2)0当B树不为空时
a、在B树中查找插入位置的key,若找到则不插入返回;若没找到,则插入到叶子结点。
b、检测当前插入节点是否满足B树的性质,若满足则返回,不满足时则需要分裂。(分裂如上所示)
3、查找(主要查找两个方向:一是找key在不在;二是若key不在则找位置)
(1)从B树的根节点开始查找(中序遍历查找或者折半查找),若找到则返回;若无则进行下一步
(2)找不到key值时,则需要将key与节点中的key值作比较,小于节点的key值时,则往左子树里面查找;若大于时,往右子树里 面找。一直重复下去,最后返回需要插入的位置。
注意点:搬移元素的时候,孩子节点会比关键字多搬移一个元素
代码没有附上,读者可自行编写!!!
上一篇: Java面向对象六大原则