B树、B+树
2019-06-03 10:07:54 0 举报
B树以及B+树
作者其他创作
大纲/内容
B+树只需要在叶子节点组成的链表上遍历即可，比B树要简单的多
1.该叶子节点中元素的数量仍满足B树的性质（如果该叶子节点是根节点，删除D后它仍满足B树性质，不会再往下走了，因此下面的情况叶子节点肯定不是根节点，那么它必然有父节点并且父节点最少有一个元素，按照B树的性质(孩子数量=元素数量+1)，父节点最少有2个孩子，那么该叶子节点一定存在兄弟节点）
15 44
Data
47
11 13
如果父节点元素数量不满足，重新平衡；如果父节点是根节点，则删除原来的根节点并将合并后的节点作为根节点。
15 29
2.所有的叶子节点包含了所有元素的信息，且所有叶子节点根据元素的大小从小到大组成一个链表
删除可以分为两种情况，假设删除的元素为D：
① 如果该节点的右兄弟存在且拥有多余的元素：将父节点的分隔值移到该节点的最后，用右兄弟的第一个元素替换掉父节点的分隔值，树又重新平衡
21 29
以3阶B树为例：
15 47
这里分析一下情况2.③下合并节点后，合并后的节点满不满足B树的性质：
57 65
47 53
B树范围查询需要进行中序遍历；
查询单个元素：
这样两种情况就转化成了一种情况，将D直接从叶子节点中删除：
3.根节点以及所有的中间节点同时存在于子节点，在子节点中是最大(或最小)元素
68 87
删除47后不满足B树性质
21
91 97
29
③ 如果该节点的两个直接兄弟节点都只有最小数量的元素，那么将它的一个直接兄弟与父节点的分隔值以及D合并为一个节点：
范围查询：
47 53
m为偶数时，2*⌈m/2⌉ - 2 = m-2
B+树的插入和删除元素类似于B树，但是要注意：插入和删除后，需要保证B+树的性质：根节点和中间节点的元素同时存在于子节点并且在子节点中是最大(或最小)元素，以及维护叶子节点的链表
1.D是叶子节点上的元素
1.该节点拥有的元素数量小于最大值，那么将新元素添加到该节点，并保持节点中元素有序
插入49后不满足B树性质
65 82 97
m为奇数时，2*⌈m/2⌉ - 2 = 2*⌈(m+1)/2⌉ - 2 = m-1
删除21后不满足B树性质
53
44
一个m阶B+树的性质（和B树有一些共同点，但是B+树具备一些新的特性）：
将父节点的分隔值移到左边的节点（父节点少了一个元素），将右边节点中所有的元素也移到左边的节点（右边节点空了）并且将空的右子树移除；
13 35 50
此时仍不满足B树性质继续调整
一个m阶B树的性质：
m为奇数时，2 * (⌈m/2⌉ - 1) = 2 * ((m+1)/2 - 1) = m-1
5.每个节点的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域的分隔值
47
47 53
m为偶数时，2 * (⌈m/2⌉ - 1) = 2 * (m/2 - 1) = m-2
注意：⌈m/2⌉ 向上取整，例如⌈4/2⌉=2，⌈5/2⌉=3
2.D是非叶子节点上的元素，这种情况可以转化为第1种情况，只需要用D左子树的最大元素或右子树的最小元素（假设为R）替换掉D，然后移除R（R此时肯定在叶子节点上）
15
如图是一个3阶B+树：
47 50
删除：
按照B树的性质，节点最多有m-1个元素，上述计算出来的值都小于等于m-1，因此满足B树的性质
插入53
1.B+树中间节点不存储数据，因此同样大小的磁盘页可以存储更多的元素，当数据量相同的时候，B+树要比B树更加“矮胖”，因此IO次数更少
47 49 53
插入：
② 将该节点分裂为两个节点，将小于中位数的元素放到左边的节点，大于中位数的元素放到右边的节点，中位数作为分隔值插入到父节点中
删除D后，该叶子节点的元素数量为⌈m/2⌉ - 2，它的直接兄弟节点的元素数量为⌈m/2⌉ - 1，再加上父节点的分隔值，合并后的元素数量为：(⌈m/2⌉ - 2) + (⌈m/2⌉ - 1) + 1 = 2*⌈m/2⌉ - 2
③ 如果将中位数插入到父节点中后可能导致父节点也分裂，以此类推，如果没有父节点（这一节点为根节点），就创建一个新的根节点（增加了树的高度）
1.有k个子树的根节点和中间节点包含k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有的数据都保存在叶子节点上
① 从该节点的元素和新添加的元素中找出中位数
这里分析一下第2种情况分裂节点后，分裂后2个节点的元素数量满不满足B树的性质：
21
15 44 49
2.B树查询时只要找到匹配的元素即可，性能不稳定（最好情况是查找根节点，最坏情况是查找叶子节点）；
29 44
63 66
如图是一个3阶B树：
73 82
2.该节点拥有的元素数量刚好为最大值：
71 83
50 97
49
B+树对比B树的优点：
先找到新元素应该被添加到的叶子节点，如果
21 29
删除53后后仍满足B树性质
B+树的查询必须最终查找到叶子节点（元素数据都存在叶子节点中），因此B+树每次查询都是稳定的
2.该叶子节点中元素的数量本来刚好为最小数量，删除D后不满足B树性质了，此时需要调整：
一个节点最少需要⌈m/2⌉-1个元素，2个节点需要的元素数量为2 * (⌈m/2⌉-1)：
29 35
89 92
② 如果该节点的左兄弟存在且拥有多余的元素：将父节点的分隔值移到该节点的第一个元素，用左兄弟的最后一个元素替换掉父节点的分隔值，树又重新平衡
59
4.所有的叶子节点位于同一层
而当前节点除了中位数（中位数要插入到父节点中），剩下的元素数量为m-1，大于等于上述计算出来的两个值，足够分裂为两个节点并且满足B树的性质了
0 条评论
回复 删除
下一页
