B树
一棵 2t (t>=2)阶(此处阶数表示每个节点最大的孩子数量)B树是一棵平衡的 2t 路搜索树。它或者是空树,或者是满足下列性质的树:
1、根节点至少有两个子女;
2、每个非根节点所包含的关键字个数j满足:t-1<=j<=2t-1;
3、每个节点都包含了目前节点内key数量+1个孩子指针,叶子节点除外;
4、节点孩子树中的key与当前节点中key的值存在大小关系;
5、所有的叶子节点都位于同一层,其深度为树高。
t=2时的B树也被称为2-3-4树
节点拆分要求当且仅当节点内关键字数量等于(注意是等于)2t-1,拆分时需注意插入新节点后不再检查本节点和父节点是否需要拆分,插入下一个节点时
1