GitHub 源码分享
微信搜寻：码农 StayUp
主页地址：https://gozhuyinglong.github.io
源码分享：https://github.com/gozhuyinglong/blog-demos
1. 前言
迄今为止，曾经介绍了《二叉查找树》和《AVL 树》，咱们始终假如能够把整个数据结构存储在内存中。可是，如果数据多到内存装不下，这就意味着必须把数据放在磁盘上，显然这些数据结构不再实用。
问题在于磁盘的 I / O 速度是远远不如内存访问速度的，然而从一棵树中查找到某个元素，必须从根节点一层层往下找，这每一次查找便是一次 I / O 操作。为了进步性能，就必须要缩小查找的次数。
如能缩小树的高度、减少每个节点中的元素数，便是种无效的解决方案。实现这种想法的一种办法是应用 B 树。
2. 术语
在介绍 B 树时会用到一些术语，这里先看一下：
- 根节点（root）：没有父节点的节点叫做根节点
- 叶子节点（leaf）：没有子节点的节点叫做叶子节点
- 外部节点（internal）：除根节点和叶子节点之外的节点叫做外部节点。它们即有父节点，也有子节点。
- 键：B 树中的存储元素是键，是用于指向数据记录的指针。键的值是用于存储真正的数据记录。一个节点中能够领有多个键。
- 阶：B 树的阶为最大子节点数量，其比键的数量大 1。咱们个别称一个 B 树为 M 阶的 B 树，那么该 B 树最多领有 M 个子节点，节点中最多领有 M - 1 个键。
更多术语请参阅之前分享的《树》!
3. B 树（B-Tree）
B 树与[二叉树]()（Binary Tree）不是一个概念，你能够将其翻译成
Balance Tree，或者是Bayer Tree。
B 树是一种自均衡的树，可能保持数据有序。这种数据结构可能让查找数据、程序拜访、插入数据及删除的动作，都在对数工夫内实现。
B 树与 AVL 树不同，能够领有 2 个以上的子节点，并且每个节点能够有多个键值，这些属性缩小了定位记录时所经验的两头过程，放慢了存取速度。B 树更实用于读写绝对较大的数据块存储系统，如磁盘。这种数据结构常被利用在数据库和文件系统的实现上。
对于一个 M 阶 B 树具备以下个性：
- 每个节点最多有
M个子节点；每个外部节点起码有⌈M/2⌉个子节点（⌈x⌉为向上取整符号）；如果根节点不是叶子节点，那么它至多有两个子节点。 - 具备
N个子节点的非叶子节点领有N-1个键。 - 所有叶子节点必须处于同一层上。
注：如下图是一棵 5 阶 B 树的两种画法，最精确的画法应该为图中左 B 树。但为了不便，通常会将节点中键为空的地位省去不画，如图中右 B 树。不能因为右图中最多的键为 3，就判断这是一棵 4 阶 B 树，B 树的阶是事后定义好的。
4. B 树的操作
在对 B 树进行操作时，可能会违反 B 树的个性，如最小子节点数、每个节点最小键数。为了保护 B 树的这些个性，树可能会决裂或合并。
上面咱们会以一棵 5 阶 B 树来讲述其搜寻、插入、删除操作。先来看下 5 阶 B 树的个性：
- 外部节点至多有 3 个子节点（⌈5/2⌉ = 3），最多有 5 个子节点
- 每个节点至多有 2 个键（3-1=2），最多有 4 个键
4.1 搜寻
B 树的搜寻和二叉搜寻树相似，从根节点开始，从上往下递归的遍历树。在每一层节点上，应用二分查找法匹配指标键，或者通过键的范畴来确定子树。
4.2 插入
对于新元素的插入，都是产生在叶子节点上的。所有的插入操作都是从根节点开始，搜寻这棵树，并找到该元素应该被插入的节点。将新元素插入到该节点须要如下步骤：
- 如果该节点上的元素数未满，则将新元素插入到该节点，并放弃节点中元素的程序。
-
如果该节点上的元素已满，则须要将该节点均匀地决裂成两个节点：
- 从该节点中的元素和新元素先出一个中位数
- 小于中位数的元素放到右边节点，大于中位数的元素放到左边节点，中位数做为分隔值。
- 分隔值被插入到父节点中（减少了树的高度），这可能会导致父节点的决裂，决裂父节点时又可能会使它的父节点决裂，以此类推。如果决裂始终回升到根节点，那么就创立一个新的根节点，它有一个分隔值和两个子节点。（这就是根节点并不像外部节点一样有起码子节点数量限度的起因）
下图是一个 5 阶 B 树，咱们通过程序插入 1 到 17，来察看节点的决裂过程。
4.3 删除
B 树的删除就简单了许多，可分为上面几种状况：
- 删除叶子节点中的元素
（1）搜寻要删除的元素
（2）如果它在叶子节点上，间接将其删除
（3）如果删除后产生了下溢出（键数小于最小值），则向其兄弟节点借元素。行将其父节点元素下移至以后节点，将兄弟节点中元素上移至父节点（若是左节点，上移最大元素；若是右节点，上移最小元素）
（4）若兄弟节点也达到上限，则合并兄弟节点与宰割键。 - 删除外部节点中的元素
（1）外部节点中元素为其左右子节点的宰割值，须要从左子节点最大元素或右子节点最小元素中选出一个新的宰割符。被选中的宰割符从原子节点中移除，作为新的分隔值替换掉被删除的元素。
（2）上一步中，若左右子节点元素数均达到上限，则合并左右子节点。
（3）若删除元素后，其中节点元素数小于上限，则持续合并。
下图是一个 5 阶 B 树，咱们通过删除 15、14、17、5 四个键，来察看删除过程（根本涵盖所有状况）。
5. 代码实现
本代码实现了 B 树的搜寻、插入、删除操作，上面看具体介绍。
5.1 键值类
该类用于寄存 B 树每个节点中的键值数据。
- key：节点中的键，用于指向数据记录。
- value：键向指向的数据记录。
因为键在节点中是顺序存储的，所以实现了 Comparable 接口
class Entry implements Comparable<Entry> {
final int key;
String value;
@Override
public int compareTo(Entry o) {return Integer.compare(key, o.getKey());
}
}5.2 节点类
节点类是 B 树中的每个节点，其次要包含：
- entrys：为该节点中所有的键，应用 List 类型存储
- childNodes：为该节点所有的子节点，应用 List 类型存储
- parentNode：为该节点的父节点。
因为 childNodes 须要排序，所以该类也实现了 Comparable 接口。
须要明确的一点是，以后节点中每个键的左右子节点都能够通过 List 汇合的下标进行确定。比方：
entrys[0]的左右子节点别离为 childNodes[0]、childNodes[1]；
entrys[1]的左右子节点别离为 childNodes[1]、childNodes[2]，以此类推。
class Node implements Comparable<Node> {
private final List<Entry> entrys; // 以后节点的键值对
private final List<Node> childNodes; // 子节点，应用数组存储子节点
private Node parentNode; // 父节点
public Node() {entrys = new ArrayList<>();
childNodes = new ArrayList<>();}
public Node add(Entry entry) {entrys.add(entry);
Collections.sort(entrys);
return this;
}
public Node addChild(Node node) {childNodes.add(node);
Collections.sort(childNodes);
return this;
}
@Override
public int compareTo(Node o) {return Integer.compare(entrys.get(0).getKey(), o.getEntrys().get(0).getKey());
}
}5.3 B 树类
B 树类实现比较复杂，其次要属性包含：
- m：为 B 树的阶
- min：为 B 树中元素最小值，通过阶计算出
- root：树的根节点
class BTree {
private final int m; // B 树的阶
private final int min;// 元素最小值
private Node root; // 树根
public BTree(int m) {
this.m = m;
this.min = (int) Math.ceil(m / 2.0) - 1;
}
public Node getRoot() {return root;}
}5.4 搜寻
B 树的搜寻实现较为简单，在 BTree 类中增加上面两个办法。
其二分查找法是通过 Collections 类中的 binarySearch 办法实现，感兴趣的话，能够钻研下源码。前面会专门解说二分查找法，这里就不多说了。
// 搜寻
public Entry searchEntry(int key) {return searchEntry(root, key);
}
// 搜寻 - 递归
private Entry searchEntry(Node node, int key) {if (node == null) {return null;}
// 应用二分查找法定位下标
int index = Collections.binarySearch(node.getEntrys(), new Entry(key, null));
if (index >= 0) {return node.getEntrys().get(index);
} else {if (node.getChildNodes().size() == 0) {return null;}
return searchEntry(node.getChildNodes().get(-index - 1), key);
}
}5.5 插入
B 树的插入实现起来也不难，在 BTree 类中增加上面三个办法。
重要是 split 拆散办法，如果增加一个元素后，其节点中元素值超过限定值，则进行拆散操作，具体看代码。
// 增加元素
public void add(Entry entry) {
// root 为空，间接创立
if (root == null) {Node node = new Node();
node.add(entry);
root = node;
return;
}
add(root, entry);
}
// 增加元素 - 递归
private void add(Node node, Entry entry) {
// 以后节点为叶子节点
if (node.getChildNodes().size() == 0) {
// 如果以后节点元素未满，间接增加元素
if (node.getEntrys().size() < m - 1) {node.add(entry);
return;
}
// 如果以后节点元素已满，则决裂以后节点
node.getEntrys().add(entry);
split(node);
return;
}
// 以后节点为外部节点，持续往下调用（新插入的节点，只能是叶子节点）// 应用二分查找法找到要插入的分支
int index = Collections.binarySearch(node.getEntrys(), entry);
if (index < 0) {add(node.getChildNodes().get(-index - 1), entry);
}
}
// 拆散以后节点
private void split(Node node) {int mid = node.getEntrys().size() / 2;
// 分隔值
Entry separateEntry = node.getEntrys().get(mid);
// 拆散后的左节点
Node leftNode = new Node();
leftNode.getEntrys().addAll(node.getEntrys().subList(0, mid));
// 拆散后的右节点
Node rightNode = new Node();
rightNode.getEntrys().addAll(node.getEntrys().subList(mid + 1, node.getEntrys().size()));
// 分离子节点
if (node.getChildNodes().size() > 0) {List<Node> leftChildNode = node.getChildNodes().subList(0, mid + 1);
for (Node temp : leftChildNode) {temp.setParentNode(leftNode);
}
leftNode.getChildNodes().addAll(leftChildNode);
List<Node> rightChildNode = node.getChildNodes().subList(mid + 1, node.getEntrys().size() + 1);
for (Node temp : rightChildNode) {temp.setParentNode(rightNode);
}
rightNode.getChildNodes().addAll(rightChildNode);
}
// 以后节点为根节点
if (node.parentNode == null) {Node newRoot = new Node();
newRoot.add(separateEntry);
root = newRoot;
leftNode.parentNode = root;
rightNode.parentNode = root;
root.addChild(leftNode).addChild(rightNode);
} else {node.parentNode.add(separateEntry);
leftNode.parentNode = node.parentNode;
rightNode.parentNode = node.parentNode;
node.parentNode.addChild(leftNode).addChild(rightNode);
node.parentNode.getChildNodes().remove(node);
// 若其父节点溢出，持续决裂
if (node.parentNode.getEntrys().size() > m - 1) {split(node.parentNode);
}
}
}5.6 删除
B 树的删除是最麻烦的，呈现的状况太多了。
删除的节点次要为外部节点和叶子节点，每删除后都要判断以后节点中元素数是超出下限值。若超出下限值，须要依据状况进行判断。
若删除的是叶子节点，可能的操作时左旋转、右旋转、合并（以后节点、兄弟节点、两头值进行合并）。合并后又会呈现其父节点超出下限值 ……
若删除的是外部节点，可能的操作时，合并左右兄弟节点、合并左右兄弟节点与两头值、向兄弟节点借元素。同样合并后也会呈现其父节点超出上限 ……
public void remove(int key) {
// 先查问出以后元素所在节点
Node node = searchNode(key);
if (node == null) {return;}
// 删除节点
int keyIndex = Collections.binarySearch(node.getEntrys(), new Entry(key, null));
node.getEntrys().remove(keyIndex);
// 若以后节点的键数小于限定值，删除进行删除后处理
if (node.getEntrys().size() < min) {afterDeletingHandler(node, keyIndex);
}
}
/**
* 删除后处理：以后节点元素数小于限定值，则依据不同场景抉择进行合并、左旋转、右旋转
*
* @param node
*/
private void afterDeletingHandler(Node node, int deletedKeyIndex) {
// 该节点为外部节点
if (node.getChildNodes().size() > 0) {
// 获取删除元素的左右子节点
Node leftChideNode = node.getChildNodes().get(deletedKeyIndex);
Node rightChildNode = node.getChildNodes().get(deletedKeyIndex + 1);
int leftEntrysSize = leftChideNode == null ? 0 : leftChideNode.entrys.size();
int rightEntrysSize = rightChildNode == null ? 0 : rightChildNode.entrys.size();
int maxSize = Math.max(leftEntrysSize, rightEntrysSize);
// 先向左右子节点借
if (maxSize <= min) {
// 若左右子节点达到限定值，则合并左右子节点
merge(leftChideNode, rightChildNode);
return;
}
// 向左子节点借
Entry entry;
if (maxSize == leftEntrysSize) {entry = leftChideNode.getEntrys().get(leftChideNode.getEntrys().size() - 1);
leftChideNode.getEntrys().remove(entry);
} else {
// 向右子节点借
entry = rightChildNode.getEntrys().get(0);
rightChildNode.getEntrys().remove(entry);
}
node.add(entry);
return;
}
// 该节点为叶子节点
Node parentNode = node.parentNode;
// 以后节点在父节点中的下标值
int nodeIndex = parentNode.getChildNodes().indexOf(node);
// 左兄弟节点
Node leftNode = nodeIndex > 0 ? parentNode.getChildNodes().get(nodeIndex - 1) : null;
// 右兄弟节点
Node rightNode = nodeIndex == parentNode.getChildNodes().size() - 1 ? null : parentNode.getChildNodes().get(nodeIndex + 1);
int leftEntrysSize = leftNode == null ? 0 : leftNode.entrys.size();
int rightEntrysSize = rightNode == null ? 0 : rightNode.entrys.size();
int maxSize = Math.max(leftEntrysSize, rightEntrysSize);
// 左右兄弟节点元素数均达到限定值，合并
if (maxSize <= min) {if (leftNode != null) {
// 与左兄弟节点合并
merge(node, leftNode, nodeIndex - 1);
} else if (rightNode != null) {
// 与右兄弟节点合并
merge(node, rightNode, nodeIndex);
}
return;
}
if (maxSize == leftEntrysSize) {
// 向左节点借 --> 右旋转
rightRotate(node, nodeIndex, leftNode);
} else {
// 向右节点借 --> 左旋转
leftRotate(node, nodeIndex, rightNode);
}
}
/**
* 将以后节点与兄弟节点、两头值合并
*
* @param node 以后节点
* @param brotherNode 兄弟节点
* @param parentEntryIndex 两头值
*/
private void merge(Node node, Node brotherNode, int parentEntryIndex) {
// 创立新的节点
Node parentNode = node.getParentNode();
Node newNode = new Node();
newNode.getEntrys().addAll(node.getEntrys());
newNode.getEntrys().addAll(brotherNode.getEntrys());
newNode.add(parentNode.getEntrys().get(parentEntryIndex));
// 删除原节点及关系
parentNode.getEntrys().remove(parentEntryIndex);
parentNode.getChildNodes().remove(node);
parentNode.getChildNodes().remove(brotherNode);
if (node.getChildNodes().size() > 0) {for (Node childNode : node.getChildNodes()) {newNode.addChild(childNode);
childNode.setParentNode(newNode);
}
}
if (brotherNode.getChildNodes().size() > 0) {for (Node childNode : brotherNode.getChildNodes()) {newNode.addChild(childNode);
childNode.setParentNode(newNode);
}
}
// 若原节点为根节点，则以后节点为新的根节点
if (parentNode.getEntrys().size() == 0) {
root = newNode;
return;
} else {parentNode.addChild(newNode);
newNode.setParentNode(parentNode);
}
// 合并后，若父节点的元素小于限定值，则再次合并（原则上是与起码元素数节点合并）if (parentNode.getEntrys().size() < min) {Node grandfatherNode = parentNode.getParentNode();
if (grandfatherNode == null) {return;}
int nodeIndex = Collections.binarySearch(grandfatherNode.getChildNodes(), parentNode);
// 左兄弟节点
Node leftNode = nodeIndex > 0 ? grandfatherNode.getChildNodes().get(nodeIndex - 1) : null;
// 右兄弟节点
Node rightNode = nodeIndex >= grandfatherNode.getChildNodes().size() - 1 ? null : grandfatherNode.getChildNodes().get(nodeIndex + 1);
int leftEntrysSize = leftNode == null ? 0 : leftNode.entrys.size();
int rightEntrysSize = rightNode == null ? 0 : rightNode.entrys.size();
int minSize = Math.min(leftEntrysSize, rightEntrysSize);
if (minSize > 0) {if (leftEntrysSize == minSize) {merge(parentNode, leftNode, nodeIndex - 1);
} else {merge(parentNode, rightNode, nodeIndex);
}
} else if (leftEntrysSize > 0) {merge(parentNode, leftNode, nodeIndex - 1);
} else if (rightEntrysSize > 0) {merge(parentNode, rightNode, nodeIndex);
}
}
}
/**
* 合并两个兄弟节点
*
* @param node 以后节点
* @param brotherNode 兄弟节点
*/
private void merge(Node node, Node brotherNode) {Node parentNode = node.getParentNode();
Node newNode = new Node();
newNode.getEntrys().addAll(node.getEntrys());
newNode.getEntrys().addAll(brotherNode.getEntrys());
Collections.sort(newNode.getEntrys());
newNode.setParentNode(parentNode);
parentNode.getChildNodes().remove(node);
parentNode.getChildNodes().remove(brotherNode);
parentNode.addChild(newNode);
}
/**
* 左旋转
*（1）将父节点的两头值元素删除，并增加到以后节点中
*（2）将右兄弟节点中最小元素删除，并增加到父节点中
*
* @param node 以后节点
* @param nodeIndex 两头值索引
* @param rightNode 右节点
*/
private void leftRotate(Node node, int nodeIndex, Node rightNode) {Entry parentEntry = node.getParentNode().getEntrys().get(nodeIndex);
node.add(parentEntry);
node.getParentNode().getEntrys().remove(parentEntry);
Entry rightEntry = rightNode.getEntrys().get(0);
node.getParentNode().add(rightEntry);
rightNode.getEntrys().remove(rightEntry);
}
/**
* 右旋转
*（1）将父节点的两头值元素删除，并增加到以后节点中
*（2）将左兄弟节点中最大元素删除，并增加到父节点中
*
* @param node 以后节点
* @param nodeIndex 两头值索引
* @param leftNode 左节点
*/
private void rightRotate(Node node, int nodeIndex, Node leftNode) {Entry parentEntry = node.getParentNode().getEntrys().get(nodeIndex - 1);
node.add(parentEntry);
node.getParentNode().getEntrys().remove(parentEntry);
Entry leftEntry = leftNode.getEntrys().get(leftNode.getEntrys().size() - 1);
node.getParentNode().add(leftEntry);
leftNode.getEntrys().remove(leftEntry);
}6. 残缺代码
残缺代码篇幅过长，欢送拜访我的 GitHub 进行查看，若对您有帮忙，也请给个 Star！
代码地址：https://github.com/gozhuyinglong/blog-demos/blob/main/java-data-structures/src/main/java/io/github/gozhuyinglong/datastructures/tree/BTreeDemo.java