1、B树的基本了解
1) [40, 60]、[10]、[50]、[70]都是一个结点
2) [10]、[50]、[70]的上级是[40,60],也可以说[40, 60]为[10]、[50]、[70]父亲,[10]、[50]、[70]是[40, 60]的孩子
3) [40, 60]没有父亲,所以[40, 60]为根
4) [10]、[50]、[70]没有孩子(都指向NULL),[10]、[50]、[70]都为叶子结点
5) 图中树的度(t)为3(对应[10]、[50]、[70]三个,如果只有[10]、[50]度则为2)
再添加一些B树的关键概念所以
6) 图中40、60、10、50、70都是一个关键字(keys)
7) 每个结点至少有一个关键字(keys)
8) 每个结点下的子节点个数(Children) = 关键字(keys)个数 + 1
9) 关键的最大个数为2t - 1
2、B树的插入
插入数据分别为40、20、80、70、10、15、75七个数字,我们关键字(Keys)个数的最大和最小设置为2
1) 写入40,生成根节点,将40放入关键字(keys)中,生成2个子结点(Children)
2) 写入20,找到合适存放20的区间叶子结点(也是root结点), 直接存放到叶子结点关键字(Keys)中,追加一个子结点(保持keys个数 + 1 = 子结点个数 ),关键字(Keys)的个数没有超过2, 完成
3) 写入80,找到合适存放20的区间叶子结点(也是root结点),加入关键字(keys)中,发觉个数超过2个进行拆分,找到中间点40分成[20][80]结点和40关键字,将40放到父级结点(父级结点不存在,新建一个),将结点[20][80]的父级指向新的父级结点
4) 写入70,找到合适存放的区间叶子结点([80]),直接放到[80]结点关键字中
5) 写入10,找到合适存放的区间叶子结点([20]),直接放到[20]结点关键字中
6) 写入15,找到合适存放的区间叶子结点([10,20]),插入之后关键字(keys)个数大于最大个数2,进行拆分成[10][20]结点和15 , 将15放到父级[40]结点结束
7) 写入75,,找到合适存放的区间叶子结点([70,80]),关键字(keys)个数满了,进行拆分
成[70][80]结点和75, 将75放到父级结点[15,40],结点[70][80]的父级指向[15, 40, 75], 父级结点关键字(keys)个数也满了,进行再次进行拆分,成[15][75]和40,[15, 40, 75]的父级不存在,创建一个新父级,将40放入,结点[15][75]的父级指向新结点[40]
3、删除B树结点
1) 删除一个叶子结点[10]中的关键字10
① 首先找到10所在的结点[10], 然后删除关键字(keys)10, 删除之后[10]变成空结点
② 处理空结点,找到左右两边的兄弟结点拥有关键字(keys)个数最多的,这里左边没有兄弟结点,所以选择[20]结点,再借父结点的一个关键字(取的是右边的兄弟结点,parent[keys][index],如果取的是左边兄弟结点,则parent[keys][index-1]),生成一个新结点, 由于新结点不需要任何操作,所以从父级借的keys不需要归还,需要删除父级对应的keys
③ 由于上级[15]结点的15被借出之后,变成空结点,所以需要再执行上面操作,找到兄弟结点[75],再往父级借关键字(keys)40,组合新的结点,因为新的结点符合,所以上级结点(根结点)又为空结点, 需要继续操作
④ 根结点为空结点,子结点[0]作为根结点
2) 删除以上面的B数为基础,删除中间结点15
① 找到删除节点[15],找到子结点跟删除15一样的位置的结点,查找其中最大的叶子结点(例如[10]),并且交换15跟10的位置
② 根据1)中删除叶子结点的操作,删除交换到叶子节点的15
版权声明:未经博主允许不得转载。http://www.smister.com/post-36/b-tree.html