欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

浅析B-树分裂

程序员文章站 2024-03-16 21:59:40
...

一、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
浅析B-树分裂
(2) 再插入45
浅析B-树分裂
(3) 插入9
浅析B-树分裂
(4) 插入78
浅析B-树分裂
(5) 插入60
浅析B-树分裂
(6) 插入55
浅析B-树分裂
(7) 插入58
浅析B-树分裂

四、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值时,则往左子树里面查找;若大于时,往右子树里 面找。一直重复下去,最后返回需要插入的位置。

注意点:搬移元素的时候,孩子节点会比关键字多搬移一个元素

代码没有附上,读者可自行编写!!!

相关标签: B-Tree

上一篇: Java面向对象六大原则

下一篇: