我用例子说明算法吧.(假设你懂得B+树的定义)
[插入算法] 假设有一棵3阶B+树
[59 97]
/ /
[15 44 59] [72 97]
/ | / / /
[10 15] [21 37 44] [51 59] [63 72] [85 91 97]
Eg.1 插入9,首先查找9应插入的叶节点(最左下角的那一个),插入发现没有破坏B+树的性质,完毕
[59 97]
/ /
[15 44 59] [72 97]
/ | / / /
[9 10 15] [21 37 44] [51 59] [63 72] [85 91 97]
Eg.2 插入20,首先查找20应插入的叶节点(第二个叶子节点),插入
[59 97]
/ /
[15 44 59] [72 97]
/ | / / /
[10 15] [20 21 37 44] [51 59] [63 72] [85 91 97]
发现第二个叶子节点已经破坏了B+树的性质,则把之分解成[20 21], [37 44]两个,并把21往父节点移
[59 97]
/ /
[15 21 44 59] [72 97]
/ | | / / /
[10 15] [20 21] [37 44] [51 59] [63 72] [85 91 97]
发现父节点也破坏了B+树的性质,则把之再分解成[15 21], [44 59]两个,并把21往其父节点移
[21 59 97]
/ | /
[15 21] [44 59] [72 97]
/ / / / / /
[10 15] [20 21] [37 44] [51 59] [63 72] [85 91 97]
这次没有破坏B+树的性质(如果还是不满足B+树的性质,可以递归上去,直到满足为至),插入完毕
Eg.3 插入100,首先查找100应插入的叶节点(最后一个节点),插入
[59 97]
/ /
[15 44 59] [72 97]
/ | / / /
[10 15] [21 37 44] [51 59] [63 72] [85 91 97 100]
修改其所有父辈节点的键值为100(只有插入比当前树的最大数大的数时要做此步)
[59 100]
/ /
[15 44 59] [72 100]
/ | / / /
[10 15] [21 37 44] [51 59] [63 72] [85 91 97 100]
然后重复Eg.2的方法拆分节点,最后得
[59 100]
/ /
[15 44 59] [72 91 100]
/ | / / | /
[10 15] [21 37 44] [51 59] [63 72] [85 91] [97 100]
[删除算法] 以插入算法的B+树为例
Eg.1 删除91,首先找到91所在叶节点(最后一个节点),删除之
[59 97]
/ /
[15 44 59] [72 97]
/ | / / /
[10 15] [21 37 44] [51 59] [63 72] [85 97]
没有破坏B+树的性质,删除完毕
Eg.2 删除97,首先找到97所在叶节点(最后一个节点),删除之
[59 97]
/ /
[15 44 59] [72 97]
/ | / / /
[10 15] [21 37 44] [51 59] [63 72] [85 91]
修改该节点的父辈的键字为91(只有删除树中最大数时要做此步)
[59 91]
/ /
[15 44 59] [72 91]
/ | / / /
[10 15] [21 37 44] [51 59] [63 72] [85 91]
判断没有破坏B+树的性质,删除完毕
Eg.3 删除51,首先找到51所在节点(第三个节点),删除之
[59 97]
/ /
[15 44 59] [72 97]
/ | / / /
[10 15] [21 37 44] [59] [63 72] [85 91 97]
破坏了B+树的性质,从该节点的兄弟节点(左边或右边)借节点44
[59 97]
/ /
[15 37 59] [72 97]
/ | / / /
[10 15] [21 37] [44 59] [63 72] [85 91 97]
并修改相应键值,判断没有破坏B+树,完毕
Eg.4 在Eg.3的基础上删除59,首先找到59所在叶节点(第三个节点),删除之
[59 97]
/ /
[15 37 59] [72 97]
/ | / / /
[10 15] [21 37] [44] [63 72] [85 91 97]
破坏B+树性质,尝试借节点,无效(因为左兄弟节点被借也会破坏B+树性质),合并第二第三叶节点并调整键值
[44 97]
/ /
[15 44] [72 97]
/ / / /
[10 15] [21 37 44] [63 72] [85 91 97]
完毕
Eg.5 在Eg.2的基础上删除63,
[59 91]
/ /
[15 44 59] [72 91]
/ | / / /
[10 15] [21 37 44] [51 59] [72] [85 91]
合并第四五叶节点并调整键值
[59 91]
/ /
[15 44 59] [91]
/ | / |
[10 15] [21 37 44] [51 59] [72 85 91]
发现第二层的第二个节点不满足B+树性质,从第二层的第一个节点借59,并调整键值
[44 91]
/ /
[15 44] [59 91]
/ / / /
[10 15] [21 37 44] [51 59] [72 85 91]
