在说B树之前最好先看看2-3树, 2-3树是B树的一种特例, 什么B树, B树就是2-3树, 2-3-4 树 , 2-3-4-5... 树的统称, 而B+树又是B树的一种变形
性质:什么是二节点, 三节点...?
像上图那样,可以有两个子节点的节点叫做二节点, 可以有三个子节点的节点叫做三节点, 并且, 对于二节点来说,可以有节点,也可以,没有节点, 同样对三节点来说,要么有三个节点要么有没节点, 只有这两种情况(不能只有一个节点)
如果一棵树中最大的节点数为m, 我们就称它是m阶的B树
注意点就是B树的所有的子节点全部在同一层, 如果不在同一层了,它肯定不是B树,下文中会讲解调整的技巧
特性:
假设每一个节点能存储的元素的个数为x
对于根节点来说: 根节点能存储的元素的范围是 1<= x <= m-1 (m为阶数)
对于非根节点来说: 他能存储的元素的个数是 ⌈ m/2 ⌉ -1 <= x <= m-1
像下面这样, 如果当前节点有子节点的话, 子节点的个数是当前节点中存储的元素数+1
推论:
如果当前节点是根节点, 那么, 当前节点的子节点的个数为x: 2 <= x <= m
如果当前节点是非根节点, 那么, 当前节点的子节点的个数x : ⌈ m/2 ⌉ <= x <= m
例子:
比如当m=3时, 也就是说,当前树为3阶B树, 通过上面的公式计算它的非根节点的个数是 ⌈ m/2 ⌉ <= x <= 3 即 [2,3] , 此时这棵树就是我们所说的2-3树
构建与上溢:假设我们有这样一个数组: [6,10,4,14,5,11,15,3,2,12,1,7,8] 下面通过画图将它转换成一个3阶B树
在转化的过程中, 严格遵循上面的特性:
先添加node6, 对于二三树来说,最多的节点数是三节点的状态, 于是我们继续添加node10, 得到的下图
因为node4比node6小, 所以我们想把node4添加到node6的左边, 但是此时4,6,10, 三个节点排放在一起就是4节点,不满足2-3的要求,所以我们需要进行上溢调整 , (或者说,当一个节点中存储的元素的个数=m时, 进行上溢处理)
第一步: 先求出需要上溢的节点的中间元素的位置 k (就是下面node6的位置2)
第二步: 将k位置的元素向上移动和父节点合并, 没有父节点,就让他当父节点
第三步: 将[0-k-1] 和 [k-1,m-1] 位置的元素分裂成上溢节点的左右节点
每次上到父节点时,就会导致树长高, 还需要注意的地方就是上溢可能会导致当前节点的父节点满了, 这时候重复这个过程,对其父节点进行上溢的操作
继续添加node5,和node14, 同样可以直接添加进去,且不会打破2-3的平衡
继续添加node11, 按照正常的排序,我们会将他排在node10的右边,但是此时同样,一个节点中三个元素,说明这个节点是4节点, 不符合2-3的三节点特性, 因此需要上溢, 同样是选出中间位置的11,然后和它的上一个父节点进行合并, 剩下的node10, node14当成这个node11的左右子节点
继续添加node15, 按照大小,我们将他排放在node14的右边,且满足二三树的要求
继续添加node3, 按照顺序应该将node3放在node4的左边,但是这个节点里面就回显345三个元素, 也就是说这个节点其实是4节点,因此我们将node4上溢, 和它的父节点合并, 然后我们又发现, 上溢到根节点中,根节点就有了三个元素, 因此我们进行继续上溢, 于是树就会长高一层