B+树简介

B+树简介

B+树是B-树的变体，也是一棵多路搜索树

特点

• 每个节点至多有m个子女;
• 非根节点关键值个数范围：[m/2] <= k <= m-1
• 相邻叶子节点是通过指针连起来的，并且是关键字大小排序的

插入数据的步骤

• B+树插入都是在叶子节点进行的，就是插入前，需要先找到要插入的叶子节点
• 如果被插入关键字的叶子节点，当前含有的关键字数量是小于阶数m，则直接插入
• 如果插入关键字后，叶子节点当前含有的关键字数目等于阶数m，该节点开始分裂为两个新的节点，一个节点包含⌊m/2⌋ 个关键字，另外一个关键字包含⌈m/2⌉个关键值。（⌊m/2⌋表示向下取整，⌈m/2⌉表示向上取整，如⌈3/2⌉=2）
• 分裂后，需要将第⌈m/2⌉的关键字上移到父节点。如果这时候父节点中包含的关键字个数小于m，则插入操作完成
• 分裂后，需要将⌈m/2⌉的关键字上移到父节点。如果父节点中包含的关键字个数等于m，则继续分裂父节点

删除数据的步骤

• 找到包含关键值的节点，如果关键字个数大于⌈m/2⌉-1，直接删除即可
• 找到包含关键值的节点，如果关键字个数大于⌈m/2⌉-1，并且关键值是当前节点的最大（小）值，并且该关键值存在父子节点中，那么删除该关键字，同时需要相应调整父节点的值
• 找到包含关键值的节点，如果删除该关键字后，关键字个数小于⌈m/2⌉，并且其兄弟节点有多余的关键字，则从其兄弟节点借用关键字
• 找到包含关键值的节点，如果删除该关键字后，关键字个数小于⌈m/2⌉，并且其兄弟节点没有多余的关键字，则与兄弟节点合并

B+树和B-树的区别

• B-树内部节点是保存数据的;而B+树内部节点是不保存数据的，只作索引作用，它的叶子节点才保存数据
• B+树相邻的叶子节点之间是通过双向链表指针连起来的，B-树却不是
• 查找过程中，B-树在找到具体的数值以后就结束，而B+树则需要通过索引找到叶子节点中的数据才结束
• B-树中任何一个关键字出现且只出现在一个节点中，而B+树可以出现多次
• B-树中的非叶节点，记录数比子节点少1；而B+树中记录数与子节点个数相同