1.B树简介
B树是一个搜索树,数据结构可以抽象成如二叉树一样的树,不过它有平衡、有序、多路的特点。
- 平衡:所有叶子节点都在同一层。
- 有序:任一元素的左子树都小于它,右子树都大于它。
- 多路:B树的每个节点最多有m个子节点,m即为B数的阶数,同时由阶数可以得到另一个概念:B树的度数,它决定了每个节点最多存在的元素个数。
其结构图如下:
2.代码实现
2.1 B树节点类设计
首先定义一个节点,代码结构如下,它的成员变量以及函数定义如下。
- curKeyNums记录当前节点元素个数,用于判断节点是否需要分裂的操作等。
- keys数组接收每个节点的元素,初始化时定义一个B树度数的数组,表示最多能容纳n个元素。
- children数组负责存储对应keys数组中每个元素对应的左子树、右子树,初始化时定义一个B树度数长度+1的数组,表示该节点最多有B树度数+1的子节点。
- isLeaf()方法判断当前节点是否是叶子节点,判断依据就是看它有没有“孩子”。
public class BtreeNode {int curKeyNums;Integer[] keys;BtreeNode[] children;public BtreeNode(int degrees){curKeyNums = 0;keys = new Integer[degrees];children = new BtreeNode[degrees+1];}public boolean isLeaf(){return children[0] == null;}
}
假设某个key在keys数组中的下标是i,那么在children数组中小于等于i的子树都是该key的左子树,都小于key,同理大于i的子树都是该key的右子树,都大于key。这个结论非常重要,务必要记住,因为将会在后面的合并节点中使用到。
2.2 B树类设计
B树是一颗树,因此它的设计如下:
- degress表示一颗B树的度数,即任一节点最多容纳的key数量。
- root根节点,因为本质上是一颗结构树,B树的增删查操作都是通过根节点作为入口完成的。
public class Btree {int degrees; // 度数BtreeNode root; // B树的根节点public Btree(int degrees){this.degrees = degrees;root = new BtreeNode(degrees);}
}
2.3 增加元素到B树
这个小节将用Java手动实现怎么将一个元素添加到B树。
增加元素要考虑的场景其实也比较复杂,从上面定义的B树度数、任一元素的左右子树均小于、大于该元素,因此会涉及一个节点拆分的过程,此过程不是太复杂,复杂的是拆分以后的节点合并工作。
2.3.1 二分查找确定插入key的位置
当添加一个新的key到B树时,假设此时找到了需要添加的节点(keys数组也没满),那么如何确定待插入的key应该放在keys数组的哪里吗?
通过二分查找(时间复杂度O(logN))的方法确定插入下标,二分查找的特点是根据中间元素和待插入key判断,随时调整每一次遍历的起始下标,具体代码如下:
private int binarySearchInsertIdx(int key, BtreeNode node){// 二分查找的特点是随时调整左右下标int left = 0;int right = node.curKeyNums-1;while (left<=right){int mid = (right-left)/2 + left;// 再加上left的意思是补充移位if (node.keys[mid]>key){// 往左边查找right = mid-1;} else if (node.keys[mid]<key) {// 往右边查找left = mid+1;}else {return mid;}}return left;}
2.3.2 节点分裂操作
当插入元素,找到一个插入节点时,若发现此时的keys数组已满,则需要进行节点的拆分。
由于keys数组的元素插入都是通过二分查找的方式找到插入下标完成,因此keys数组是有序的。
因此这里我们用 (keys.length/2)计数出中间元素的下标即为midIdx,即此时下标小于midIdx的元素都小于中间元素,提取为左子树,大于midIdx的元素都大于中间元素,提取为右子树。此外中间元素将升级为一个新的父节点,将中间元素值直接存入keys[0]中,该新父节点的curKeyNums为1,这是后面插入方法中判断是否分裂成了一个新节点的判断依据(因为B树的度数一般都大于1)。
具体代码如下:
private BtreeNode splitNode(BtreeNode node){// 拆分节点,进到这里的node的keys数量肯定是刚好等于B树的度数了int midIdx = (node.curKeyNums)/2;int extractVal = node.keys[midIdx];BtreeNode newFatherNode = new BtreeNode(degrees);newFatherNode.keys[0] = extractVal;newFatherNode.curKeyNums++;// 小于midIdx的作为新父节点的左子树BtreeNode leftNode = new BtreeNode(degrees);for (int i=0;i<midIdx;i++){leftNode.curKeyNums++;leftNode.keys[i] = node.keys[i];}// 大于midIdx的作为新父节点的右子树,右子树的填充使用倒序更加明确BtreeNode rightNode = new BtreeNode(degrees);for (int i= node.curKeyNums-1;i>midIdx;i--){rightNode.curKeyNums++;rightNode.keys[i-midIdx-1] = node.keys[i];}newFatherNode.children[0]=leftNode;newFatherNode.children[1]=rightNode;return newFatherNode;}
2.3.3 插入元素操作
插入元素的操作,切入点都是B树的root根节点。因为后面的插入操作都是通过递归完成的,需要有较强的递归回溯思维才能更好理解。
首先 insert(int key)方法是外界添加元素到B树的唯一入口,里面调用了insertKeyToNode(key, root)方法,表示每一次的插入元素都是以root根节点为入口。在insertKeyToNode方法中,会存在递归调用自己的情况。
首先,我们分析以下这几种情况:
①keys数组还没有满并且是叶子节点:
(新元素必须添加到叶子节点中)将key插入到二分查找的插入下标位置中。如度数为3的B树,有这么一个节点的keys=【2,5】,要插入的key是1,则最终找到的插入下标是0,那么将变成keys=【1,2,5】。
private void insert(int key){root = insertKeyToNode(key, root);}// 插入key到叶子节点private BtreeNode insertKeyToNode(int key, BtreeNode node){int curNodeKeyNums = node.curKeyNums;if (curNodeKeyNums == degrees){// 如果插入节点的key数量达到了度数,则需要拆分该节点并返回新的父节点node = splitNode(node);}if (node.keys[0]!=null && node.keys[0]==key){return node;}int possibleInsertIdx = binarySearchInsertIdx(key, node);// 然后再判断当前的node是不是叶子节点if (node.isLeaf()){// 如果插入节点的key数量还没有达到度数,直接添加即可insertKeyToArray(possibleInsertIdx, key, node);}else {// 如果不是叶子节点,且节点数是1的话说明分裂成了新节点BtreeNode t = insertKeyToNode(key, node.children[possibleInsertIdx]);if(t.curKeyNums==1){// 需要将当前的t的key以及左右子树都并入到node中// 首先需要将node的key移动位置,比如node的keys=[5],此时t的keys[0]为2,那么// 插入下标就是0,从0+1开始for (int i = node.curKeyNums; i>possibleInsertIdx;i--){node.keys[i] = node.keys[i-1];}// 合并t的keys[0]node.keys[possibleInsertIdx] = t.keys[0];// 配合上面的insertKeyToNode(key, node.children[possibleInsertIdx])// 更好理解for (int i=node.curKeyNums+1;i>possibleInsertIdx+1;i--){node.children[i] = node.children[i-1];}node.children[possibleInsertIdx] = t.children[0];node.children[possibleInsertIdx+1] = t.children[1];node.curKeyNums++;}}return node;}
②keys数组还没有满并且不是叶子节点:
由于按照B树的定义,元素必须先插入到叶子节点中。不过此时需要回顾的一点是,初始化的root根节点是叶子节点,也就是说当root节点的keys数组满了并且经过节点分裂操作,此时的root节点升级为非叶子节点,因为root根节点有了“孩子”。
即无法直接添加到如今的root根节点时,根据此时root.keys数组和待插入key通过二分查找方式找到插入下标possibleInsertIdx,通过它可以知道这个key应该插入到root根节点的哪个子树,左子树还是右子树?
其实这个左右子树的判断光从代码上看挺难分析出来的,还是以具体例子去理解:B树度数为3,此时root.keys=【1,4,7】,准备插入元素5,此时需要将root节点拆分为root.keys=【4】,root.children=【【1】,【7】】,那么此时再添加5的时候,发现插入下标是1,则将5添加到的子树就是root的右子树【7】...最终将变成root.keys=【4】,root.children=【【1】,【5,7】】。
通过上面的例子,知道了如果找到的第一层节点不是叶子节点,则还是先通过二分查找找到待插入key的下标,再次递归调用insertKeyToNode方法,不过传入的插入节点此时是第一层节点的对应子树节点。
③新的分裂节点与旧的分裂节点合并:
由于在递归调用insertKeyToNode方法的时候,有可能又分裂了节点,那么就需要对新分裂的节点t和原来的节点node做合并操作。这个合并操作理解起来并不是那么容易。
如果新节点t的curKeyNums是1则肯定是一个新分裂出来的节点,此时待插入的key已经存入到了t节点,并且注意到BtreeNode t = insertKeyToNode(key, node.children[possibleInsertIdx])这行代码,是将node节点的某个插入子树传入调用了,即当调用栈回溯到这里时,可以认为node的这个子树已经死了、消亡了。记住这个概念对后面做子树合并会有非常大的帮助!
- 新旧分裂节点的key元素合并,将新分裂节点t的key转移到老分裂节点node的keys中,由于新分裂节点的key只有一个,而且是没递归调用insertKeyToNode方法时就确定的插入下标,因此直接将从插入下标后面开始,将元素移动到后一位,最后再将t.keys[0]赋值给node.keys[possibleInsertIdx]中即完成了新旧分裂节点key元素的合并。
- 新分裂节点的子树合并到老节点的子树中,子树合并的情况似乎更复杂一点,但是我们要记住的一点时,此时的旧节点其实只剩下一个子树了(只剩下一个子树的说法不严谨,但是由于是递归实现的,以第一次的情况描述好像也无问题,因为从数学归纳法角度看,一次递归和n次递归的效果都是一样的)。
- 由于插入key的下标是possibleInsertIdx,并且node.children[possibleInsertIdx]也已经“死了”,那么新分裂节点的左子树t.children[0]应该被安置在哪里呢?安置在node.children[possibleInsertIdx]对应空间中。因为,t.keys[0]被安置在了node.keys[possibleInsertIdx]中,前面也介绍了小于等于元素下标的子树中都是小于该元素的。同理,新分裂节点的右子树t.children[1]应该分配在下标大于possibleInsertIdx、即possibleInsertIdx+1的老节点的子树数组中。
- 由于最终子树合并占用了possibleInsertIdx、possibleInsertIdx+1两个下标空间,因此需要先在老分裂节点的子树数组中先从possibleInsertIdx+2下标开始将子树节点往后挪。(ps:往后挪动的子树是跟着挪动的旧节点key 同步进行的,可以尝试想象出这个画面~似乎更好理解)
总结,插入元素非常烧脑,需要对递归很熟悉才能理解整个流程操作。