B-Tree定义

B-树是一种用于外查找的数据结构，其数据存放在外存中
B-树又称为多路平衡查找树，是一种组织和维护外存文件系统非常有效的数据结构。
B_树中可以有多个数据元素多个关键字
B- 树就是B树，中间的横线并不是减号。

什么是外存

外存磁盘结构

磁盘是个圆形光盘，一圈圈的圆周跑道称为轨道，分割圆的扇形称为扇区，轨道与扇区相交区域称为块

可以使用轨道号和扇区号对磁盘进行寻址到每个块，称为地址，通常将块大小取为512字节

每个块的第一个字节地址为0，最后一个字节地址为511，其中每个地址都有自己的地址，可以使用第一个字节地址加上偏移量来引用该块的任何一个字节

对外存进行查找

数据无法直接在磁盘上处理，对数据的处理总是将其读取到内存，在内存中处理完成后再将数据写回磁盘中

阶的概念

B_树中所有结点的孩子结点的最大值称为B_树的阶，通常用m表示

B树性质

一个m（设为3)阶的B树具有如下几个特征：

1. 根结点如果不是叶子结点则至少有两个子女。
2. 树中每个结点至多有m个孩子结点（即至多有m-1个关键字（存储数据的数量））
   最多关键字个数Max = m-1
3. 除根结点外，其他非叶子节子点至少填充一半即至少有[m/2]（取上界)个孩子结点（即至少有[m/2]-1（取上界)个关键字）
   • 最少关键字个数Min = [m/2]-1
   • 每个非叶子结点的结构如下：
     
     • 存放在一个数组中，第一个元素为n即该结点关键字个数。n满足[m/2]-1<=n<=m-1
       p0为指向第一个子树结点的指针数组（从0-n），k1为该子树(第一个子树)关键字数组（从1-n）
     • 结点中按升序顺序排列
       • 首先明确,孩子结点指针数组p[0…keynum]起始下标为0，存放关键字数组k[1…keynum]起始下标为1，所以pi相当于ki+1
       • ki(1<=i<=n)为该节点关键字，且满足ki<ki+1
       • pi(0<=i<=n)为该节点子节点的指针，且满足pi(0<=i<=n-1)所指向的子树上结点关键字均大于ki，且小于ki+1
       • B-树又称为多路平衡查找树，也是基于查找树也就是搜索树性质的（小于根节点在左子树，大于根节点在右子树）
       • pn所指向的子树上结点关键字均大于kn
     • 每个关键字递增的进行放置，即k1<k2<k3
4. 每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
5. 所有外部结点都在同一层上，并且不带有任何信息
   • 在计算B-树的高度时，需要计入最底层的外部结点
   • 一棵B树中总有n个关键字，则外部结点个数为n+1。
     • 外部结点就是失败结点，指向它的指针为空，不含有任何信息，是虚设的。
     • 关键字说明查找到了，好比在绳子上断开了n份，这样就会出现n+1段绳子，即n+1段失败取值的区间
6. B-树是所有结点的平衡因子均等于0的多路查找树。

B-树的存储结构中，结点的类型定义

B-树的查找

将查找元素k与根结点中的key[i]进行比较：

1. 若k=key[i]，则查找成功；
2. 若k＜key[1]，则沿着指针ptr[0]所指的子树继续查找；
   • 关键字数组是按照升序顺序排序的，如果该节点小于其子树
3. 若key[i]＜k＜key[i+1]，则沿着指针ptr[i]所指的子树继续查找；
4. 若k＞key[n]，则沿着指针ptr[n]所指的子树继续查找。

• 说明：
  当查找到某个叶结点时，若相应的指针为空，落入一个外部结点区间，表示查找失败。

B-树的插入

将关键字k插入到B-树的过程分两步完成：

（1）查找该关键字的插入结点。

• 查找插入该关键字的位置
• 注意B-树的插入结点一定是叶子结点层的结点（非外部结点）

（2）插入关键字。

• 在某个叶子结点中插入关键字分两种情况：
• 若插入后，不破会m阶二叉树的定义，即插入后结点关键字个数在区间[[m/2-1, m-1]范围内，则直接插入;
  • 直接插入时需要注意升序排序
• 插入结点没有空位置，关键字数量大于等于m-1，则对插入后的结点进行分裂（平衡二叉树的调整）操作；

分裂过程：

1. 插入后的结点（将待插元素放置到插入元素中一起算）中间位置([ m/2|)（取上界）关键字并入父结点中
   （因为插入后依然需要其保持有序状态，所以将中间结点插入父节点（没有父节点就创建一个新的结点作为父节点），保证左子树小于中间结点右子树大于中间结点）

2. 中间结点左侧结点留在原先的结点中

3. 右侧结点放入新的节点中（新的结点应该被放置在父节点下）
   

4. 若并入父节点后，父结点关键字数量超出范围或创建的新结点数量超出范围，继续想上分裂，直到符合要求为止。

B-树的删除

在B-树上删除关键字k的过程分两步完成：
（1）查找关键字k所在的结点。
（2）删除关键字k。

1. 在叶子结点层上删除关键字k。

首先明确：非根、非叶子结点的关键字最少个数Min=[m/2]-1

1.直接删除

若被删除关键字所在结点关键字个数>[m/2]-1（满足结点最低关键字个数要求），则直接删除

2.兄弟够借

若被删除关键字所在结点关键字总数=[m/2]-1(取上界)，且与此结点邻近的兄弟结点的关键字个数>=[m/2]，则需要从兄弟结点借一个关键字

左兄弟够借

若左面兄弟结点关键字个数>=[m/2]，则从中父节点中选取符合在左兄弟最右侧（最大）结点与删除节点中间的结点，将之补到删除节点位置，再将左兄弟最右侧节点放置到父节点空出位置
选取左兄弟最右侧节点是因为需要保证补到父节点之后依然符合搜索树的有序性

右兄弟够借

若右面兄弟结点关键字个数>=[m/2]，则从中父节点中选取符合在右兄弟最左侧（最小）结点与删除节点中间的结点，将之补到删除节点位置，再将右兄弟最左侧节点放置到父节点空出位置
选取右兄弟最左侧节点是因为需要保证补到父节点之后依然符合搜索树的有序性

3.兄弟不够借

若被删除关键字所在结点关键字总数>=[m/2]-1，且与此结点邻近的兄弟结点的关键字个数也>= [m/2|-1，则该结点删除关键字，并与一个不够借的兄弟结点以及双亲结点中符合与合并兄弟子树关键字中间值的关键字合并

合并后若双亲结点因减少一个结点导致不符合定义，则继续执行2、3步强。

在非叶子结点层上删除关键字k。

1.若小于k的子树中关键字个数>[m/2]-1,则找出k的前驱值k’，并用k’来取代k，再递归地删除k’即可。

前驱值是指从小到大进行排列后比k小的树中最大的数

2.若大于k的子树中关键字个数>「m/2]-1,则找出k的后继值k’，并用k’来取代k，再递归地删除k’即可。

后继值是指从小到大进行排列后比k大的树中最小的数

3.若k值前后（大于k的子树和小于k的子树）两子树关键字个数均为[m/2]-1,则直接将两个子结点合并,然后删除k即可。