用字符“画”b-tree(b-树，直接读作“b树”)的基本结构。
b-tree是为了磁盘（减少磁盘IO次数）或其它存储设备而设计的一种多叉平衡查找树。
b-tree节点结构
struct BTNode
{
struct BTNode* parent;
Vector<T> key; /**< 关键码，即节点数据 */
Vector<BTNode*> child; /**< 分支，即子节点 */
}
key为关键码节点，也即数据节点，child为子节点；
key和child排列如下：
key [0] [1] [2] [3] => *[k0]*[k1]*[k2]*[k3]*
child [0] [1] [2] [3] [4] 紧凑表示：'*'代表key两则的子节点child
b-tree阶次为m(这里为5)， 则分支数(子节点) <= m，关键码 <= m-1；
且 分支数(子节点) = 关键码数+1 恒成立。
【分支数(子节点)-1 = 关键码数】
约定关键码数为n，则分支数为n+1，
内部节点的分支数n+1不能太少，即有
树根： 2 <= n+1 <= m
其余：⌈m/2⌉ <= n+1 <= m ，⌈⌉为取上整
故 b-tree 也称做 (⌈m/2⌉，m)-tree 。
b-tree结构
对于叶节点(以5阶b-tree为例)：
key [0] [1] [2] [3] -> 最低层叶节点
child [0] [1] [2] [3] [4] -> 叶节点的子节点为external nodes，
即只是在vector(child)有一个BTNode指针，值为nullptr;
也只有external nodes指向nullptr。
r ---
/ \ |
/ \ internal nodes |
/ \ |
/_______\ (__为叶节点) ---
||||||||||| external nodes |
b-tree节点插入
以4阶b-tree为例，则有 2 <= 分支数 <= 4， 1 <= 关键码数 <= 3；
- 插入节点示意图
r r+1(新插入关键码)
\ /
key [k] [k] [k] ...
child [c] [c] [c] [c] ...
/ \
r+1 r+2(新插入子节点，作为external node)
当节点关键码数>3时，则该节点发生上溢。
- 使用分裂修复上溢
取中位数分裂，s = ⌊m/2⌋ (即向下取整，m为b-tree的阶)，如下图所示：
即m为奇数时，s为key正中间位置，m为偶数时，s为key均分后左侧的最后一个位置。
*[k0]*[k1]*[k2]* ... *[k(m-1)]*
|
V
*[k0]*[k1]*k(s-1)] * [ks] * [k(s+1)]* ... *[k(m-1)]*
------------------ ---- -----------------------
作为ks左子节点 上移至父节点 作为ks右子节点
以4阶b-tree为例，演示分裂操作：
将[3]上移至父节点
*[0]*[10]* *[0]*[3]*[10]*
\ / \
\ => / \
\ / \
*[1]*[2]*[3]*[5]* *[1]*[2]* *[5]*
----------------- --------- -----
原node节点 分裂后的node 新节点rc
[3]的新左右两侧节点的分支数分别为3和2(3+2=5>4)，均会满足>=⌈m/2⌉=2
[3]之后的关键码和分支节点(即*和[])将转移到rc中;
根节点上溢时，分裂出的新根节点，且新的根节点只有2个分支;
根据分裂特性，可知非叶节点的子节点不可指向nullptr。
b-tree节点删除
以4阶b-tree为例，则有 2 <= 分支数 <= 4， 1 <= 关键码数 <= 3；
当节点关键码数>3时，则该节点发生下溢；
- 修复下溢
(1)通过旋转(向左侧子节点借)修复下溢(#也是子节点，方便对比观看)：
*[0]*[5]*[10]* *[0]*[3]*[10]*
/ \ / \
/ \ => / \
/ \ / \
*[1]*[2]*[3]# * *[1]*[2]* #[5]*
---
下溢节点
旋转前后，节点#均在[3]和[5]之间
(2)通过合并修复下溢(#也是子节点，方便对比观看)：
*[0]*[5]#[10]* *[0]*[10]*
/ \ |
/ \ => |
/ \ |
*[1]* * *[1]*[5]*
---
下溢节点
合并后，将删除节点#
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 [ yehuohan@gmail.com ]