B-树¶
一、B-树是什么？¶
B-树是一棵所有叶子节点高度都相同的平衡多叉树。
其结构类似这样：
____ ___ ___
| 24 | | |
|
---------------------------------------------
| |
____ ____ ___ ____ ___ ___
| 15 | 20 | | | 33 | | |
| |
----------------------------------- -------------------
| | | | |
____ ____ ___ ____ ___ ___ ____ ____ ___ ____ ____ ___ ____ ___ ___
| 10 | 12 | | | 18 | | | | 21 | 23 | | | 30 | 31 | | | 38 | | |
B-树的一些性质：
- 树节点中，子节点数量的最大值称为B-树的阶
- m 阶B-树的节点，最多拥有 m - 1 个元素
- B-树的所有叶子节点都在同一层，是高度平衡的
- 除根节点外，所有节点的元素个数不少于 Math.ceil(m/2) - 1，也即子节点数量不少于 Math.ceil(m/2）
- 节点的大小，始终满足
左子节点 < 父节点 < 右子节点，即和二叉查找树类似
简单来说，B-树的结构是节点的子节点数量要半满，叶子节点的高度要始终一样。
二、为什么要用B-树？¶
- B-树或B-树变体被广泛应用于需要进行插入、删除、范围检索等的应用程序，比如 MySQL 数据库索引
- 更新和检索操作只影响部分节点，对于基于磁盘的检索，可以减少 I/O 请求，提升性能
- B-树保证至少有一定比例的节点是满的，能改进空间利用率
三、怎么实现一棵B-树？¶
B-树主要包含几种操作：
- 检索元素：在树中搜索指定的元素
- 插入元素：往树中插入新的元素
- 删除元素：从树中删除指定的元素
其中插入和删除会对B-树的结构产生影响，稍微麻烦亿点。
3.1 检索元素¶
B-树和二叉搜索树类似，二叉搜索树使用的是二分查找，而B-树也是类似的：
- B-树检索元素采用的是二分查找的升级版本 —— 多路查找
比如说，上面的B-树中，要寻找元素 23，那么它的搜索路线就是：
24 -> 20 -> 23
在B-树中查找的话，就是这样子：
____ ___ ___
| 24 | | |
|
---------------------------------------------
| |
____ ____ ___ ____ ___ ___
| | 20 | | | | | |
| |
----------------------------------- -------------------
| | | | |
____ ____ ___ ____ ___ ___ ____ ____ ___ ____ ____ ___ ____ ___ ___
| | | | | | | | | | 23 | | | | | | | | | |
对应到伪代码的话，差不多是这样的：
private V get(BTNode<K, V> root, K key) {
int index = root.findIndex(key);
if (key.equals(root.getKey(index))) {
// 找到 key 对应的节点
return root.getValue(index);
} else {
// 往子树继续找 key 对应的节点
return get(root.getChild(index), key);
}
}
实际就是从上往下多路递归查找元素。
3.2 插入元素¶
B-树和二叉搜索树的插入类似：
- B-树插入新元素，始终是在叶子节点插入
插入元素，可以分为 2 种情况处理：
- 节点空间足够，直接插入元素
- 节点空间不足，1 个节点分裂成 3 个节点，执行上溢操作
这 2 种情况的效果如下。
3.2.1 叶子节点-直接插入¶
当叶子节点空间足够时，可以直接插入新元素，而且不会影响到B-树的高度平衡：
____ ____ ___
| 12 | | |
| 插入 20
v
____ ____ ___
| 12 | 20 | |
| 插入 9
v
____ ____ ____
| 9 | 12 | 20 |
空间足够时，直接插入元素就行了。
3.2.2 叶子节点-上溢分裂¶
当叶子节点空间不足时，此时再插入新元素，会导致节点空间上溢，然后分裂：
___ ____ ____
| 9 | 12 | 20 |
| 插入 25
v
____ ___ ___
| 20 | | |
|
---------------------
| |
___ ____ ___ ____ ____ ____
| 9 | 12 | | | 25 | | |
节点元素上溢后，1 个节点会分裂成 3 个节点。
3.2.3 内部节点-直接插入¶
为了保持B-树的高度平衡，叶子节点会将分裂后的父节点，往上插入之前的父节点：
____ ___ ___
| 20 | | |
|
----------------------
| |
___ ____ ____ ____ ____ ____
| 9 | 12 | 18 | | 25 | | |
| 插入 10
v
____ ____ ___
| 12 | 20 | |
|
--------------------------------------------
| | |
___ ____ ____ ____ ____ ____ ____ ____ ____
| 9 | 10 | | | 18 | | | | 25 | | |
左子节点 [9, 12, 18] 插入新节点 10 会产生上溢，节点 12 会上溢父节点中。
因为内部节点 [20] 空间足够，所以 12 直接插入即可。
3.2.4 内部节点-分裂上溢¶
子节点上溢后，如果父节点空间也满了，那么父节点也会出现分裂上溢：
____ ____ ____
| 20 | 30 | 45 |
|
-------------------------------------------------------------------
| | | |
___ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____
| 9 | 12 | 18 | | 25 | | | | 37 | 39 | | | 62 | 85 | |
| 插入 10
v
____ ____ ____
| 30 | | |
|
----------------------------------------------------------
| |
____ ____ ___ ____ ___ ___
| 12 | 20 | | | 45 | | |
| |
-------------------------------------------- ------------------------
| | | | |
___ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____
| 9 | 10 | | | 18 | | | | 25 | | | | 37 | 39 | | | 62 | 85 | |
插入元素 10 之后，会传递性地导致节点 [9, 12, 18] 和节点 [20, 30, 45] 都产生分裂上溢。
这种分裂上溢可以一直持续到根节点，最后可能会导致B-树提升一层（如上）。
上述的 4 种情况，实际就 2 种：
- 空间足够时，直接插入
- 空间不足时，分裂上溢
对应的伪代码类似这样：
/**- 插入新元素 -*/
private BTNode<K, V> put(BTNode<K, V> root, K key, V value) {
int index = root.findIndex(key);
// 叶子节点
if (root.isLeaf()) {
// 叶子节点添加元素后，可能发生了分裂
return root.add(key, value);
}
// 内部节点
BTNode<K, V> child = root.getChild(index);
child = put(child, key, value);
// 子树添加元素后，可能发生了分裂
return root.overflow(index, child);
}
/**- 直接插入和分裂上溢（叶子节点和内部节点的插入逻辑一样） -*/
public BTNode<K, V> overflow(int index, BTNode<K, V> node) {
// 子节点没上溢
if (getChild(index) == node) {
return this;
}
// 子节点上溢了
// 1. 空间足够，直接插入
if (size + node.size() < m) {
return insertNode(index, node);
}
// 2. 空间不足，分裂节点
return splitNodes(index, node);
}
3.3 删除元素¶
删除元素，可以分为 3 种情况：
- 删除后元素数量仍然满足要求，直接删除
- 删除后元素数量不满足要求，看兄弟节点是否可以借一个过来
- 兄弟节点不能借，那就将父子节点合并成 1 个节点，产生下溢
这几种情况如下。
3.3.1 直接删除¶
如果节点删除元素后，元素数量仍然处于半满状态，则直接返回即可：
____ ___ ___
| 20 | | |
|
----------------------
| |
___ ____ ____ ____ ____ ____
| 9 | 12 | 18 | | 25 | | |
| 删除 12
v
____ ___ ___
| 20 | | |
|
----------------------
| |
___ ____ ____ ____ ____ ____
| 9 | 18 | | | 25 | | |
叶子节点 [9, 12, 18] 删除 12 以后，元素数量依旧满足半满状态，则可以直接删除并返回。
3.3.2 从兄弟借¶
如果删除元素后，元素数量少于一半，不满足要求，则看一下兄弟节点能不能借一下：
____ ___ ___
| 20 | | |
|
----------------------
| |
___ ____ ____ ____ ____ ____
| 9 | 12 | 18 | | 25 | | |
| 删除 25
v
____ ___ ___
| 18 | | |
|
----------------------
| |
___ ____ ____ ____ ____ ____
| 9 | 12 | | | 20 | | |
右子节点 [25] 删除 25 以后，元素数量不满足要求了，找兄弟节点 [9, 12, 18] 借一个。
但是不能直接把左子节点的元素移到右子节点中，因为B-树是要求满足 左子节点 < 父节点 < 右子节点。
所以“借用”实际上是一种旋转操作，父节点转到需要借用元素的节点，而兄弟节点元素则转到父节点中。
3.3.3 父子合并¶
如果兄弟节点借不了元素，那就将父节点 + 左子节点 + 右子节点合并在一起：
____ ___ ___
| 20 | | |
|
----------------------
| |
___ ____ ____ ____ ____ ____
| 9 | | | | 25 | | |
| 删除 25
v
___ ____ ___
| 9 | 20 | |
删除元素 25 后，由于兄弟节点没办法借用，所以将父子节点都合并成 1 个节点，这个合并称为下溢。
下溢和上溢一样，也可能会持续下溢，一直持续到根节点，最终导致树的层级下降。
上述情况的伪代码如下：
/**- 删除元素 -*/
private BTNode<K, V> remove(BTNode<K, V> root, K key) {
int index = root.findIndex(key);
// 找到对应节点后移除元素
if (key.equals(root.getKey(index))) {
// 直接删除元素后，可能导致父节点下溢
return root.delete(index);
}
// 在子树内递归移除元素
remove(root.getChild(index), key);
// 子树删除元素后，可能导致父节点下溢
return root.underflow(index);
}
/** 从兄弟借和父子合并（叶子节点和内部节点的下溢逻辑是一样的） */
public BTNode<K, V> underflow(int index) {
// 子节点合法，无需下溢
if (isLegal(getChild(index))) {
return this;
}
// 子节点不合法，需修正
// 1. 从兄弟节点借一个元素
if (borrowLeft(index) || borrowRight(index)) {
return this;
}
// 2. 合并父元素 + 左右子节点
return mergeNodes(index);
}
总结¶
- 性质
- m 阶B-树的节点，最多拥有 m - 1 个元素
- B-树的所有叶子节点都在同一层，是高度平衡的
- 除根节点外，所有节点的元素个数不少于 Math.ceil(m/2) - 1，也即子节点数量不少于 Math.ceil(m/2）
- 节点的大小，始终满足
左子节点 < 父节点 < 右子节点
- 检索
- 多路查找：二分查找的升级版本
- 插入
- 空间足够，直接插入
- 空间不足，分裂上溢
- 删除
- 元素够多，直接删除
- 元素不够，从兄弟借
- 兄弟节点无法借用，合并父子节点，执行下溢
参考¶
《数据结构与算法分析（第三版）》
https://www.cnblogs.com/nullzx/p/8729425.html
https://github.com/LiuXianghai-coder/Test-Repo/blob/master/DataStructure/BTree.java
https://blog.csdn.net/u011711997/article/details/80420392
https://blog.csdn.net/c630843901/article/details/121423196
https://blog.csdn.net/oooooorz/article/details/112297554
https://blog.csdn.net/cdnight/article/details/11772621
附录¶
B-树接口¶
/**
* B-树
*
* @author weijiaduo
* @since 2023/1/2
*/
public interface BTree<K extends Comparable<K>, V> {
/**
* 查找指定 key 的值
*
* @param key key
* @return value
*/
V get(K key);
/**
* 添加指定 key-value 的节点
*
* @param key key
* @param value value
*/
void put(K key, V value);
/**
* 删除指定 key 的节点
*
* @param key key
*/
void remove(K key);
}
B-树实现¶
/**
* B-树实现类
*
* @author weijiaduo
* @since 2023/1/2
*/
public class BTreeImpl<K extends Comparable<K>, V> implements BTree<K, V> {
/**
* 根节点
*/
private BTNode<K, V> root;
/**
* m 阶 B 树
*/
private final int m;
public BTreeImpl(int m) {
this.m = m;
}
@Override
public V get(K key) {
return get(root, key);
}
/**
* 从当前节点开始找指定 key 的值
*
* @param root 当前根节点
* @param key key
* @return value
*/
private V get(BTNode<K, V> root, K key) {
if (root == null) {
return null;
}
// 查找当前 key 所在的位置
int index = root.findIndex(key);
if (key.equals(root.getKey(index))) {
// 找到 key 对应的节点
return root.getValue(index);
} else {
// 往子树继续找 key 对应的节点
return get(root.getChild(index), key);
}
}
@Override
public void put(K key, V value) {
root = put(root, key, value);
}
/**
* 在当前树内添加指定的 key-value
*
* @param root 当前根节点
* @param key key
* @param value value
* @return 新的根节点
*/
private BTNode<K, V> put(BTNode<K, V> root, K key, V value) {
// 1. 整棵树为空时，插入新节点
if (root == null) {
BTNode<K, V> node = new BTNode<>(m);
return node.add(key, value);
}
// 验证是否已存在，存在则只需更新
int index = root.findIndex(key);
if (key.equals(root.getKey(index))) {
// 更新节点
root.setValue(index, value);
return root;
}
// 2. 叶子节点，直接添加
if (root.isLeaf()) {
// 添加到叶子节点中，有可能发生分裂
return root.add(key, value);
}
// 3. 内部节点，添加到子树的叶子节点中
BTNode<K, V> child = root.getChild(index);
child = put(child, key, value);
// 添加元素后子树可能发生了分裂
return root.overflow(index, child);
}
@Override
public void remove(K key) {
root = remove(root, key);
if (root != null && root.isEmpty()) {
// 树的高度下降
root = root.firstChild();
}
}
/**
* 在当前树内删除指定 key 的节点
*
* @param root 当前根节点
* @param key key
* @return 新的根节点
*/
private BTNode<K, V> remove(BTNode<K, V> root, K key) {
if (root == null) {
return null;
}
// 找到对应节点后移除元素
int index = root.findIndex(key);
if (key.equals(root.getKey(index))) {
return root.delete(index);
}
// 在子树内递归移除元素
remove(root.getChild(index), key);
// 移除后可能需要父节点下溢
return root.underflow(index);
}
}
B-树节点¶
/**
* B-树节点
*
* @author weijiaduo
* @since 2023/1/2
*/
public class BTNode<K extends Comparable<K>, V> {
/**
* m 阶 B 树
*/
private final int m;
/**
* 节点元素阈值
*/
private final int threshold;
/**
* 节点元素数组
* <p>
* 元素的第 0 位始终是一个占位元素，专门用于存放最左子节点
* <p>
* 所以一个节点能拥有的元素个数最多是 m - 1
*/
private final Object[] elements;
/**
* 实际元素数量
* <p>
* 取值范围是 [0, m - 1]
*/
private int size;
public BTNode(int m) {
this.m = m;
this.threshold = half(m);
elements = new Object[m];
// 最左元素占位，用于存放最左子节点指针
elements[0] = new Entry<K, V>(null, null);
size = 0;
}
/**
* @return 元素数量
*/
public int size() {
return size;
}
/**
* 半数阈值 ceil(m / 2) - 1
*
* @param m 当前值
* @return 半数阈值
*/
private int half(int m) {
return (m + 1) / 2 - 1;
}
/**
* 是否已满
*
* @return true已满/false未满
*/
public boolean isFull() {
return size == m - 1;
}
/**
* 是否为空
*
* @return true为空/false非空
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 节点是否合法
* <p>
* 节点的元素数量要求大于等于阈值
*
* @return true合法/false非法
*/
public boolean isLegal() {
return size >= threshold;
}
/**
* 是否可借用元素给别的节点
* <p>
* 当节点的元素数量大于阈值时，才可以外借元素
*
* @return true可借用/false不可借用
*/
private boolean canBorrow() {
return size > threshold;
}
/**
* 是否是叶子节点
* <p>
* 没有任何一个非空子节点时才是叶子节点
*
* @return true叶子节点/false内部节点
*/
public boolean isLeaf() {
for (int i = 0; i <= size; i++) {
if (getChild(i) != null) {
return false;
}
}
return true;
}
/**
* 获取所有的元素
*
* @return 元素集合
*/
public List<Entry<K, V>> entries() {
List<Entry<K, V>> entries = new ArrayList<>(size);
// 元素从索引 1 开始
for (int i = 1; i <= size; i++) {
entries.add(getEntry(i));
}
return entries;
}
/**
* 获取所有的 key
*
* @return key 集合
*/
public List<K> keys() {
List<K> keys = new ArrayList<>(size);
// 元素从索引 1 开始
for (int i = 1; i <= size; i++) {
keys.add(getKey(i));
}
return keys;
}
/**
* 获取所有的 value
*
* @return value 集合
*/
public List<V> values() {
List<V> values = new ArrayList<>(size);
// 元素从索引 1 开始
for (int i = 1; i <= size; i++) {
values.add(getValue(i));
}
return values;
}
/**
* 获取指定位置的 key
*
* @param index 索引
* @return key
*/
public K getKey(int index) {
return getEntry(index).key;
}
/**
* 获取指定位置的 value
*
* @param index 索引
* @return value
*/
public V getValue(int index) {
return getEntry(index).value;
}
/**
* 设置指定位置的 value
*
* @param index 索引
* @param value 值
*/
public void setValue(int index, V value) {
getEntry(index).value = value;
}
/**
* 获取所有的子节点
* <p>
* 注意：是所有可能的子节点，也包括了 null 子节点
*
* @return 子节点集合
*/
public List<BTNode<K, V>> children() {
List<BTNode<K, V>> children = new ArrayList<>(size + 1);
// 子节点从索引 0 开始
for (int i = 0; i <= size; i++) {
children.add(getChild(i));
}
return children;
}
/**
* 返回第一个子节点
* <p>
* 注意：不是第一个非空子节点，而是第 1 个元素的左子节点
*
* @return 第一个子节点
*/
public BTNode<K, V> firstChild() {
return getChild(0);
}
/**
* 返回最后一个子节点
* <p>
* 注意：不是最后一个非空子节点，而是最后 1 个元素的右子节点
*
* @return 最后一个子节点
*/
public BTNode<K, V> lastChild() {
return getChild(size);
}
/**
* 获取指定位置的下一层子节点
*
* @param index 指定位置
* @return 下一层子树根节点
*/
public BTNode<K, V> getChild(int index) {
return getEntry(index).pointer;
}
/**
* 更新指定位置的子节点
*
* @param index 索引
* @param node 子节点
*/
public void setChild(int index, BTNode<K, V> node) {
getEntry(index).pointer = node;
}
/**
* 查找指定 key 的位置
* <p>
* 返回最后一个小于等于 key 的位置
*
* @param key key
* @return key 的位置
*/
public int findIndex(K key) {
// 第 0 位是占位元素，还没算在内
return 1 + binaryle(keys(), key);
}
/**
* 二分查找，返回最后一个小于等于 key 的位置
*
* @param keys key 集合
* @param key 指定 key
* @return 最后一个小于等于 key 的位置/-1
*/
private int binaryle(List<K> keys, K key) {
int size = keys.size();
int l = 0, r = size - 1;
while (l <= r) {
int m = l + (r - l) / 2;
K k = keys.get(m);
if (k.compareTo(key) <= 0) {
if (m == size - 1 || keys.get(m + 1).compareTo(key) > 0) {
return m;
}
l = m + 1;
} else {
r = m - 1;
}
}
return -1;
}
/**
* 添加新元素
*
* @param key key
* @param value value
*/
public BTNode<K, V> add(K key, V value) {
BTNode<K, V> node = new BTNode<>(m);
node.addEntry(new Entry<>(key, value));
int index = findIndex(key);
return overflow(index, node);
}
/**
* 节点上溢处理
* <p>
* 子树添加新元素后，可能会分裂成新节点，替代原有的子节点
*
* @param index 索引
* @param node 新节点
* @return 添加后的当前节点
*/
public BTNode<K, V> overflow(int index, BTNode<K, V> node) {
if (node == null || node.isEmpty()) {
return this;
}
// 还是旧节点，说明子节点没有上溢，无需处理
BTNode<K, V> cur = getChild(index);
if (cur == node) {
return this;
}
// 1. 当前空间足够插入
if (size + node.size() < m) {
// 新子节点的左子节点替代旧子节点的位置
setChild(index, node.firstChild());
for (Entry<K, V> entry : node.entries()) {
insertEntry(++index, entry);
}
return this;
}
// 2. 当前空间不够，需要分裂成 3 个节点
return splitNodes(index, node);
}
/**
* 子节点上溢后，父节点已满，则需要分裂节点，将 1 个节点拆分成 3 个节点
*
* @param index 上溢子节点的父元素索引
* @param newNode 上溢的子节点
* @return 分裂后新的父节点
*/
private BTNode<K, V> splitNodes(int index, BTNode<K, V> newNode) {
// 新子节点的左子节点替代旧子节点的位置
setChild(index, newNode.firstChild());
int newSize = size + newNode.size();
List<Entry<K, V>> allEntries = new ArrayList<>(newSize);
List<Entry<K, V>> curEntries = entries();
for (int i = 0; i < index && i < size; i++) {
allEntries.add(curEntries.get(i));
}
allEntries.addAll(newNode.entries());
for (int i = index; i < size; i++) {
allEntries.add(curEntries.get(i));
}
// 根节点
int mid = newSize / 2;
BTNode<K, V> root = new BTNode<>(m);
for (int i = mid; i <= mid; i++) {
root.addEntry(allEntries.get(i));
}
// 左子节点
BTNode<K, V> left = new BTNode<>(m);
for (int i = 0; i < mid; i++) {
left.addEntry(allEntries.get(i));
}
// 右子节点
BTNode<K, V> right = new BTNode<>(m);
for (int i = mid + 1; i < newSize; i++) {
right.addEntry(allEntries.get(i));
}
// 边界指针
left.setChild(0, firstChild());
right.setChild(0, root.lastChild());
root.setChild(0, left);
root.setChild(root.size, right);
return root;
}
/**
* 删除指定位置的元素
* <p>
* 删除元素后，节点可能会产生下溢，从而返回了一个空元素节点
*
* @param index 索引
* @return 删除后的根节点
*/
public BTNode<K, V> delete(int index) {
if (isEmpty() || index == 0) {
throw new IllegalStateException(String.format("index: %d, size: %d", index, size));
}
if (isLeaf()) {
// 叶子节点
// 直接删除，删除后可能会变成元素为空的空节点
// 空节点将由父节点的 underflow 处理掉，或者由根节点处理掉
removeEntry(index);
return this;
}
// 内部节点
// 使用前驱或后驱进行替换
int rpIndex = getReplacer(this, index);
BTNode<K, V> child = getChild(rpIndex);
BTNode<K, V> newChild;
if (rpIndex < index) {
// 前驱元素替换
Entry<K, V> max = max(child);
newChild = removeMax(child);
setChild(rpIndex, newChild);
setEntry(index, max);
} else {
// 后驱元素替换
Entry<K, V> min = min(child);
newChild = removeMin(child);
setChild(rpIndex, newChild);
setEntry(index, min);
}
// 移除后可能需要父节点下溢
return underflow(rpIndex);
}
/**
* 节点下溢处理
* <p>
* 存在非法子节点时，可能需要对父节点进行下溢操作
*
* @param index 父节点索引
* @return 根节点
*/
public BTNode<K, V> underflow(int index) {
// 验证子节点是否合法
BTNode<K, V> cur = getChild(index);
if (cur == null || cur.isLegal()) {
return this;
}
// 1. 从兄弟节点借一个元素
BTNode<K, V> left = null;
if (index > 0) {
left = getChild(index - 1);
if (left != null && left.canBorrow()) {
return borrowLeft(index);
}
}
BTNode<K, V> right = null;
if (index < size) {
right = getChild(index + 1);
if (right != null && right.canBorrow()) {
return borrowRight(index);
}
}
if (left == null && right == null) {
return this;
}
// 2. 合并父元素 + 左右子节点
// 始终把当前节点作为合并时的右子节点
return mergeNodes(left != null ? index : index + 1);
}
/**
* 借用左子节点的值
* <p>
* 实际就是右旋，将父节点转到右子节点，左子节点的元素转到父节点
*
* @param index 父节点索引
*/
private BTNode<K, V> borrowLeft(int index) {
BTNode<K, V> left = getChild(index - 1);
BTNode<K, V> right = getChild(index);
Entry<K, V> parentEntry = getEntry(index);
Entry<K, V> leftEntry = left.getEntry(left.size);
BTNode<K, V> leftRight = left.lastChild();
// 父节点转到右子节点
right.insertEntry(1, parentEntry);
right.setChild(1, right.firstChild());
// 左子节点转到父节点
left.removeEntry(left.size);
setEntry(index, leftEntry);
setChild(index, right);
right.setChild(0, leftRight);
return this;
}
/**
* 借用右子节点的值
* <p>
* 实际就是左旋，将父元素转到左子节点，右子节点的元素转到父节点
*
* @param index 父节点索引
*/
private BTNode<K, V> borrowRight(int index) {
BTNode<K, V> right = getChild(index + 1);
BTNode<K, V> left = getChild(index);
Entry<K, V> parentEntry = getEntry(index + 1);
Entry<K, V> rightEntry = right.getEntry(1);
BTNode<K, V> rightLeft = right.firstChild();
// 父节点转到左子节点
left.addEntry(parentEntry);
// 右子节点转到父节点
right.setChild(0, right.getChild(1));
right.removeEntry(1);
setEntry(index + 1, rightEntry);
setChild(index + 1, right);
left.setChild(left.size, rightLeft);
return this;
}
/**
* 父节点元素 + 右子节点，全都合并到左子节点
* <p>
* 因为父节点元素和右子节点是一一对应的，所以都是按照“父 + 右 --> 左”进行合并
* <p>
* 方便同时删除父节点元素和右子节点
*
* @param index 父元素索引
*/
private BTNode<K, V> mergeNodes(int index) {
BTNode<K, V> left = getChild(index - 1);
BTNode<K, V> right = getChild(index);
// 父节点元素合并到左子节点
Entry<K, V> parentEntry = getEntry(index);
left.addEntry(parentEntry);
// 右子节点合并到左子节点
left.setChild(left.size, right.firstChild());
for (Entry<K, V> entry : right.entries()) {
left.addEntry(entry);
}
// 移除父节点元素
removeEntry(index);
return this;
}
/**
* 获取可替换子节点索引（前驱/后驱）
*
* @param root 当前根节点
* @param index 当前索引
* @return 可替换子节点索引
*/
private int getReplacer(BTNode<K, V> root, int index) {
BTNode<K, V> right = null;
if (index <= root.size) {
right = root.getChild(index);
}
if (right == null) {
return index - 1;
}
BTNode<K, V> left = null;
if (index > 0) {
left = root.getChild(index - 1);
}
if (left == null) {
return index;
}
if (left.canBorrow()) {
return index - 1;
} else {
return index;
}
}
/**
* 获取最大值
*
* @param root 当前根节点
* @return 最大值
*/
private Entry<K, V> max(BTNode<K, V> root) {
if (root == null) {
return null;
}
if (root.isLeaf()) {
return root.getEntry(root.size);
}
return max(root.lastChild());
}
/**
* 移除最大值
*
* @param root 当前根节点
* @return 移除后的根节点
*/
private BTNode<K, V> removeMax(BTNode<K, V> root) {
if (root == null) {
return null;
}
if (root.isLeaf()) {
root.removeEntry(root.size);
return root;
}
int index = root.size;
removeMax(root.getChild(index));
return root.underflow(index);
}
/**
* 获取最小值
*
* @param root 当前根节点
* @return 最小值
*/
private Entry<K, V> min(BTNode<K, V> root) {
if (root == null) {
return null;
}
if (root.isLeaf()) {
return root.getEntry(1);
}
return min(root.firstChild());
}
/**
* 移除最小值
*
* @param root 当前根节点
* @return 移除值后的根节点
*/
private BTNode<K, V> removeMin(BTNode<K, V> root) {
if (root == null) {
return null;
}
if (root.isLeaf()) {
root.removeEntry(1);
return root;
}
int index = 0;
removeMin(root.getChild(index));
return root.underflow(index);
}
/**
* 获取指定位置的元素
*
* @param index 索引
* @return 元素
*/
private Entry<K, V> getEntry(int index) {
return (Entry<K, V>) elements[index];
}
/**
* 更新指定位置的元素
* <p>
* 要求原始元素必须存在，否则应该使用 {@code insertEntry()}
*
* @param index 索引
* @param entry 元素
*/
private void setEntry(int index, Entry<K, V> entry) {
Entry<K, V> oldEntry = getEntry(index);
if (oldEntry == null || index == 0) {
throw new IllegalStateException(String.format("index: %d, size: %d", index, size));
}
// 保留子节点，只替换元素的 key-value
elements[index] = entry;
entry.pointer = oldEntry.pointer;
}
/**
* 追加新元素
* <p>
* 此方法不会产生节点分裂，需要分裂时应调用 {@code overflow()} 方法
*
* @param entry 元素
*/
private void addEntry(Entry<K, V> entry) {
if (isFull()) {
throw new IllegalStateException(String.format("size: %d", size));
}
elements[++size] = entry;
}
/**
* 插入新元素
* <p>
* 此方法不会产生节点分裂，需要分裂时应调用 {@code overflow()} 方法
*
* @param index 插入索引
* @param entry 元素
*/
private void insertEntry(int index, Entry<K, V> entry) {
if (isFull() || index == 0) {
throw new IllegalStateException(String.format("index: %d, size: %d", index, size));
}
if (size >= index) {
System.arraycopy(elements, index, elements, index + 1, size - index + 1);
elements[index] = entry;
size++;
} else {
elements[index] = entry;
size = index;
}
}
/**
* 移除指定位置的元素
*
* @param index 索引
*/
private void removeEntry(int index) {
if (isEmpty() || index == 0) {
throw new IllegalStateException(String.format("index: %d, size: %d", index, size));
}
if (size > index) {
System.arraycopy(elements, index + 1, elements, index, size - index);
}
elements[size] = null;
size--;
}
@Override
public String toString() {
String[] s = new String[size];
for (int i = 1; i <= size; i++) {
s[i - 1] = elements[i].toString();
}
return "[" + String.join(", ", s) + "]";
}
/**
* 单个元素
*/
static class Entry<K extends Comparable<K>, V> {
/**
* key
*/
K key;
/**
* value
*/
V value;
/**
* 右子节点指针，即大于 key 的子树
*/
BTNode<K, V> pointer;
public Entry(K key, V value) {
this.key = key;
this.value = value;
pointer = null;
}
@Override
public String toString() {
return "{" + key + " : " + value + "}";
}
}
}