手撕B-树

一、概述

1.历史

B树（B-Tree）结构是一种高效存储和查询数据的方法，它的历史可以追溯到1970年代早期。B树的发明人Rudolf Bayer和Edward M. McCreight分别发表了一篇论文介绍了B树。这篇论文是1972年发表于《ACM Transactions on Database Systems》中的，题目为"Organization and Maintenance of Large Ordered Indexes"。

这篇论文提出了一种能够高效地维护大型有序索引的方法，这种方法的主要思想是将每个节点扩展成多个子节点，以减少查找所需的次数。B树结构非常适合应用于磁盘等大型存储器的高效操作，被广泛应用于关系数据库和文件系统中。

B树结构有很多变种和升级版，例如B+树，B*树和SB树等。这些变种和升级版本都基于B树的核心思想，通过调整B树的参数和结构，提高了B树在不同场景下的性能表现。

总的来说，B树结构是一个非常重要的数据结构，为高效存储和查询大量数据提供了可靠的方法。它的历史可以追溯到上个世纪70年代，而且在今天仍然被广泛应用于各种场景。

2.B-树的优势

B树和AVL树、红黑树相比，B树更适合磁盘的增删改查，而AVL和红黑树更适合内存的增删改查。

假设存储100万的数据：

• 使用AVL来存储，树高为：$lo{g}_{2}1000000\approx 20$ （20次的磁盘IO很慢，但是20次的内存操作很快）
• 使用B-树存储，最小度数为500，树高为：3

B树优势：

• 磁盘存储比内存存储慢很多，尤其是访问磁盘的延迟相对较高。每次访问磁盘都需要消耗更多的时间，而B树的设计可以最大化地减少对磁盘的访问次数。
• 磁盘访问一般是按块读取的，而B树的节点通常设计为与磁盘块大小一致。由于B树是多路的，单次磁盘访问通常会加载多个数据项，而不是像AVL树和红黑树那样每次只读取一个节点。
• 在磁盘中存储B树时，操作系统通常会将树的部分结构加载到内存中以便快速查询，避免了频繁的磁盘访问。
• 在数据库和文件系统中，数据通常是大规模的，存储在外部存储介质上。B树特别适合大规模数据的增删改查，因为它减少了不必要的磁盘访问，能够高效地执行复杂的数据操作。

二、特性

1.度和阶

• 度（degree）：节点的孩子数
• 阶（order）：所有节点孩子最大值

2.特性

• 每个节点具有

  • 属性 n，表示节点中 key 的个数
  • 属性 leaf，表示节点是否是叶子节点
  • 节点 key 可以有多个，以升序存储

• 每个非叶子节点中的孩子数是 n + 1、叶子节点没有孩子

• 最小度数t（节点的孩子数称为度）和节点中键数量的关系如下：

最小度数t	键数量范围
2	1 ~ 3
3	2 ~ 5
4	3 ~ 7
…	…
n	(n-1) ~ (2n-1)

其中，当节点中键数量达到其最大值时，即 3、5、7 … 2n-1，需要分裂

• 叶子节点的深度都相同

三、实现

1.定义节点类

static class Node {// 关键字int[] keys;// 关键字数量int keyNum;// 孩子节点Node[] children;// 是否是叶子节点boolean leafFlag = true;// 最小度数：最少孩子数（决定树的高度，度数越大，高度越小）int t;// ≥2public Node(int t) {this.t = t;// 最多的孩子数（约定）this.children = new Node[2 * t];this.keys = new int[2 * t -1];}
}

1.1 节点类相关方法

查找key：查找目标22，在当前节点的关键字数组中依次查找，找到了返回；没找到则从孩子节点找：

• 当前节点是叶子节点：目标不存在
• 非叶子结点：当key循环到25，大于目标22，此时从索引4对应的孩子key数组中继续查找，依次递归，直到找到为止。
  

根据key获取节点

/*** 根据key获取节点* @param key* @return*/
Node get(int key) {// 先从当前key数组中找int i = 0;while (i < keyNum) {if (keys[i] == key) {// 在当前的keys关键字数组中找到了return this;}if (keys[i] > key) {// 当数组比当前key大还未找到时，退出循环break;}i++;}// 如果是叶子节点，没有孩子了，说明key不存在if (leafFlag) {return null;} else {// 非叶子节点，退出时i的值就是对应范围的孩子节点数组的索引，从对应的这个孩子数组中继续找return children[i].get(key);}
}

向指定索引插入key

/*** 向keys数组中指定的索引位置插入key* @param key* @param index*/
void insertKey(int key,int index) {/*** [0,1,2,3]* src:源数组* srcPos：起始索引* dest：目标数组* destPos: 目标索引* length：拷贝的长度*/System.arraycopy(keys, index, keys, index + 1, keyNum - index);keys[index] = key;keyNum++;
}

向指定索引插入child

/*** 向children指定索引插入child** @param child* @param index*/
void insertChild(Node child, int index) {System.arraycopy(children, index, children, index + 1, keyNum - index);children[index] = child;
}

2.定义树

public class BTree {// 根节点private Node root;// 树中节点最小度数int t;// 最小key数量 在创建树的时候就指定好final int MIN_KEY_NUM;// 最大key数量final int MAX_KEY_NUM;public BTree() {// 默认度数设置为2this(2);}public BTree(int t) {this.t = t;root = new Node(t);MIN_KEY_NUM = t - 1;MAX_KEY_NUM = 2 * t - 1;}
}    

判断key在树中是否存在

/*** 判断key在树中是否存在* @param key* @return*/
public boolean contains(int key) {return root.get(key) != null;
}

3.新增key：

• 1.查找插入位置：从根节点开始，沿着树向下查找，直到找到一个叶子节点，这个叶子节点包含的键值范围覆盖了要插入的键值。
• 2.插入键值：在找到的叶子节点中插入新的键值。如果叶子节点中的键值数量没有超过B树的阶数（即每个节点最多可以包含的键值数量），则插入操作完成。
• 3.分裂节点：如果叶子节点中的键值数量超过了B树的阶数，那么这个节点需要分裂。

如果度为3，最大key数量为：2*3-1=5，当插入了8后，此时达到了最大数量5，需要分裂：

分裂逻辑：
分裂节点数据一分为三：

• 左侧数据：本身左侧的数据留在该节点
• 中间数据：中间索引2（度-1）的数据6移动到父节点的索引1（被分裂节点的索引）处
• 右侧数据：从索引3（度）开始的数据，移动到新节点，新节点的索引值为分裂节点的index+1

如果分裂的节点是非叶子节点：
需要多一步操作：右侧数据需要和孩子一起连带到新节点去:

分裂的是根节点：
需要再创建多一个节点来当做根节点，此根节点为父亲，存入中间的数据。
其他步骤同上。

分裂方法：

/*** 节点分裂* 左侧数据：本身左侧的数据留在该节点* 中间数据：中间索引2（度-1）的数据6移动到父节点的索引1（被分裂节点的索引）处* 右侧数据：从索引3（度）开始的数据，移动到新节点，新节点的索引值为分裂节点的index+1* @param node 要分裂的节点* @param index 分裂节点的索引* @param parent 要分裂节点的父节点**/
public void split(Node node, int index, Node parent) {// 没有父节点，当前node为根节点if (parent == null) {// 创建出新的根来存储中间数据Node newRoot = new Node(t);newRoot.leafFlag = false;newRoot.insertChild(node, 0);// 更新根节点为新创建的newRootthis.root = newRoot;parent = newRoot;}// 1.处理右侧数据：创建新节点存储右侧数据Node newNode = new Node(t);// 新创建的节点跟原本分裂节点同级newNode.leafFlag = node.leafFlag;// 新创建节点的数据从 原本节点【度】位置索引开始拷贝 拷贝长度：t-1System.arraycopy(node.keys, t, newNode.keys, 0, t - 1);// 如果node不是叶子节点，还需要把node的一部分孩子也同时拷贝到新节点的孩子中if (!node.leafFlag) {System.arraycopy(node.children, t, newNode.children, 0, t);}// 更新新节点的keyNumnewNode.keyNum = t - 1;// 更新原本节点的keyNumnode.keyNum = t - 1;// 2.处理中间数据：【度-1】索引处的数据 移动到父节点【分裂节点的索引】索引处// 要插入父节点的数据：int midKey = node.keys[t - 1];parent.insertKey(midKey, index);// 3. 新创建的节点作为父亲的孩子parent.insertChild(newNode, index + 1);// parent的keyNum在对应的方法中已经更新了
}

新增key：

/*** 新增key** @param key*/
public void put(int key) {doPut(root, key, 0, null);
}/*** 执行新增key* 1.查找插入位置：从根节点开始，沿着树向下查找，直到找到一个叶子节点，这个叶子节点包含的键值范围覆盖了要插入的键值。* 2.插入键值：在找到的叶子节点中插入新的键值。如果叶子节点中的键值数量没有超过B树的阶数（即每个节点最多可以包含的键值数量），则插入操作完成。* 3.分裂节点：如果叶子节点中的键值数量超过了B树的阶数，那么这个节点需要分裂。* @param node 待插入元素的节点* @param key 插入的key* @param nodeIndex  待插入元素节点的索引* @param nodeParent 待插入节点的父节点*/
public void doPut(Node node, int key, int nodeIndex, Node nodeParent) {// 查找插入位置int index = 0;while (index < node.keyNum) {if (node.keys[index] == key ) {// 找到了 做更新操作 （因为没有维护value，所以就不用处理了）return;}if (node.keys[index] > key) {// 没找到该key, 退出循环，index的值就是要插入的位置break;}index++;}// 如果是叶子节点，直接插入if (node.leafFlag) {node.insertKey(key, index);} else {// 非叶子节点，继续从孩子中找到插入位置 父亲的这个待插入的index正好就是元素要插入的第x个孩子的位置doPut(node.children[index], key , index, node);}// 处理节点分裂逻辑 : keyNum数量达到上限，节点分裂if (node.keyNum == MAX_KEY_NUM) {split(node, nodeIndex, nodeParent);}
}

4.删除key

情况一：删除的是叶子节点的key

节点是叶子节点，找到了直接删除，没找到返回。

情况二：删除的是非叶子节点的key

没有找到key，继续在孩子中找。
找到了，把要删除的key和替换为后继key，删掉后继key。

平衡树：该key被删除后，key数目<key下限（t-1），树不平衡，需要调整

• 如果左边兄弟节点的key是富裕的，可以直接找他借：右旋，把父亲一个节点的旋转下来（在父亲中找到失衡节点的前驱节点），把兄弟的一个节点旋转上去（旋转上去的是兄弟中最大的key）。
  
• 如果右边兄弟节点的key是富裕的，可以直接找他借：左旋，把父亲的旋转下来，把兄弟的旋转上去。
• 当没有兄弟是富裕时，没办法借，采用向左合并：父亲和失衡节点都合并到左侧的节点中。
  
  右旋详细流程：
  
  处理孩子：
  

向左合并详细流程：

根节点调整的情况：

调整平衡代码：

/*** 树的平衡* @param node 失衡节点* @param index 失衡节点索引* @param parent 失衡节点父节点*/
public void balance(Node node, int index, Node parent) {if (node == root) {// 如果是根节点 当调整到根节点只剩下一个key时，要替换根节点 (根节点不能为null，要保证右孩子才替换)if (root.keyNum == 0 && root.children[0] != null) {root = root.children[0];}return;}// 拿到该节点的左右兄弟，判断节点是不是富裕的,如果富裕，则找兄弟借Node leftBrother = parent.childLeftBrother(index);Node rightBrother = parent.childRightBrother(index);// 左边的兄弟富裕:右旋if (leftBrother != null && leftBrother.keyNum > MIN_KEY_NUM) {// 1.要旋转下来的key：父节点中【失衡节点索引-1】的key：parent.keys[index-1]；插入到失衡节点索引0位置// （这里父亲节点旋转走的不用删除，因为等会左侧的兄弟旋转上来会覆盖掉）node.insertKey(parent.keys[index - 1], 0);// 2.0 如果左侧节点不是叶子节点，有孩子，当旋转一个时，只需要留下原本孩子数-1 ，把最大的孩子过继给失衡节点的最小索引处(先处理后事)if (!leftBrother.leafFlag) {node.insertChild(leftBrother.removeRightMostChild(), 0);}// 2.1 要旋转上去的key：左侧兄弟最大的索引key，删除掉，插入到父节点中【失衡节点索引-1】位置（此位置就是刚才在父节点旋转走的key的位置）// 这里要直接覆盖，不能调插入方法，因为这个是当初旋转下去的key。parent.keys[index - 1] = leftBrother.removeRightMostKey();return;}// 右边的兄弟富裕：左旋if (rightBrother != null && rightBrother.keyNum > MIN_KEY_NUM) {// 1.要旋转下来的key：父节点中【失衡节点索引】的key：parent.keys[index]；插入到失衡节点索引最大位置keyNum位置// （这里父亲节点旋转走的不用删除，因为等会右侧的兄弟旋转上来会覆盖掉）node.insertKey(parent.keys[index], node.keyNum);// 2.0 如果右侧节点不是叶子节点，有孩子，当旋转一个时，只需要留下原本孩子数-1 ，把最小的孩子过继给失衡节点的最大索引处（孩子节点的索引比父亲要多1）if (!rightBrother.leafFlag) {node.insertChild(rightBrother.removeLeftMostChild(), node.keyNum + 1);}// 2.1 要旋转上去的key：右侧兄弟最小的索引key，删除掉，插入到父节点中【失衡节点索引-1】位置（此位置就是刚才在父节点旋转走的key的位置）// 这里要直接覆盖，不能调插入方法，因为这个是当初旋转下去的key。parent.keys[index] = rightBrother.removeLeftMostKey();return;}// 左右兄弟都不够，往左合并if (leftBrother != null) {// 向左兄弟合并// 1.把失衡节点从父亲中移除parent.removeChild(index);// 2.插入父节点的key到左兄弟 将父节点中【失衡节点索引-1】的key移动到左侧leftBrother.insertKey(parent.removeKey(index - 1), leftBrother.keyNum);// 3.插入失衡节点的key及其孩子到左兄弟node.moveToTarget(leftBrother);} else {// 右兄弟向自己合并// 1.把右兄弟从父亲中移除parent.removeChild(index + 1);// 2.把父亲的【失衡节点索引】 处的key移动到自己这里node.insertKey(parent.removeKey(index), node.keyNum);// 3.把右兄弟完整移动到自己这里rightBrother.moveToTarget(node);}
}

删除key：

/*** 删除指定key* @param node 查找待删除key的起点* @param parent 待删除key的父亲* @param nodeIndex 待删除的key的索引* @param key 待删除的key*/
public void doRemove(Node node, Node parent, int nodeIndex, int key) {// 找到被删除的keyint index = 0;// 循环查找待删除的keywhile (index < node.keyNum) {if (node.keys[index] >= key) {//找到了或者没找到break;}index++;}// 如果找到了 index就是要删除的key索引；// 如果没找到，index就是要在children的index索引位置继续找// 一、是叶子节点if (node.leafFlag) {// 1.1 没找到if (!found(node, key, index)) {return;}// 1.2 找到了else {// 删除当前节点index处的keynode.removeKey(index);}}// 二、不是叶子节点else {// 1.1 没找到if (!found(node, key, index)) {// 继续在孩子中找 查找的孩子的索引就是当前indexdoRemove(node.children[index], node, index, key);}// 1.2 找到了else {// 找到后继节点，把后继节点复制给当前的key，然后删除后继节点。// 在索引+1的孩子里开始,一直往左找，直到节点是叶子节点为止，就找到了后继节点Node deletedSuccessor = node.children[index + 1];while (!deletedSuccessor.leafFlag) {// 更新为最左侧的孩子deletedSuccessor = deletedSuccessor.children[0];}// 1.2.1 当找到叶子节点之后，最左侧的key就是后继keyint deletedSuccessorKey = deletedSuccessor.keys[0];// 1.2.2 把后继key赋值给待删除的keynode.keys[index] = deletedSuccessorKey;// 1.2.3 删除后继key 再调用该方法，走到情况一，删除掉该后继key： 起点为索引+1的孩子处，删除掉后继keydoRemove(node.children[index + 1], node, index + 1, deletedSuccessorKey);}}// 树的平衡：if (node.keyNum < MIN_KEY_NUM) {balance(node, nodeIndex, parent);}
}

节点相关方法：

        /*** 移除指定索引处的key* @param index* @return*/int removeKey(int index) {int deleted = keys[index];System.arraycopy(keys, index + 1, keys, index, --keyNum - index);return deleted;}/*** 移除最左索引处的key* @return*/int removeLeftMostKey(){return removeKey(0);}/*** 移除最右边索引处的key* @return*/int removeRightMostKey() {return removeKey(keyNum - 1);}/*** 移除指定索引处的child* @param index* @return*/Node removeChild(int index) {Node deleted = children[index];System.arraycopy(children, index + 1, children, index, keyNum - index);children[keyNum] = null;return deleted;}/*** 移除最左边的child* @return*/Node removeLeftMostChild() {return removeChild(0);}/*** 移除最右边的child* @return*/Node removeRightMostChild() {return removeChild(keyNum);}/*** 获取指定children处左边的兄弟* @param index* @return*/Node childLeftBrother(int index) {return index > 0 ? children[index - 1] : null;}/*** 获取指定children处右边的兄弟* @param index* @return*/Node childRightBrother(int index) {return index == keyNum ? null : children[index + 1];}/*** 复制当前节点到目标节点（key和child）* @param target*/void moveToTarget(Node target) {int start = target.keyNum;// 当前节点不是叶子节点 说明有孩子if (!leafFlag) {// 复制当前节点的孩子到目标节点的孩子中for (int i = 0; i <= keyNum; i++) {target.children[start + i] = children[i];}}// 复制key到目标节点的keys中for (int i = 0; i < keyNum; i++) {target.keys[target.keyNum++] = keys[i];}}