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://smister.com/post-36/b-tree.html