M阶B树具有特性

1，每个节点最多有 M 个子节点；
每个内部节点最少有 ⌈M/2⌉ 个子节点（⌈x⌉为向上取整符号）；如果根节点不是叶子节点，那么它至少有两个子节点。
2，具有 N 个子节点的非叶子节点拥有 N-1 个键。
3，所有叶子节点必须处于同一层上。

B树的操作

在对B树进行操作时，可能会违反B树的特性，如最小子节点数、每个节点最小键数。为了维护B树的这些特性，树可能会分裂或合并。

下面我们会以一棵5阶B树来讲述其搜索、插入、删除操作。先来看下5阶B树的特性：

内部节点至少有3个子节点（⌈5/2⌉ = 3），最多有5个子节点
每个节点至少有2个键（3-1=2），最多有4个键

B树的搜索

B树的搜索和二叉搜索树类似，从根节点开始，从上往下递归的遍历树。在每一层节点上，使用二分查找法匹配目标键，或者通过键的范围来确定子树。

B树的插入

对于新元素的插入，都是发生在叶子节点上的。所有的插入操作都是从根节点开始，搜索这棵树，并找到该元素应该被插入的节点。将新元素插入到该节点需要如下步骤：

如果该节点上的元素数未满，则将新元素插入到该节点，并保持节点中元素的顺序。
如果该节点上的元素已满，则需要将该节点平均地分裂成两个节点：
从该节点中的元素和新元素先出一个中位数
小于中位数的元素放到左边节点，大于中位数的元素放到右边节点，中位数做为分隔值。
分隔值被插入到父节点中（增加了树的高度），这可能会导致父节点的分裂，分裂父节点时又可能会使它的父节点分裂，以此类推。如果分裂一直上升到根节点，那么就创建一个新的根节点，它有一个分隔值和两个子节点。（这就是根节点并不像内部节点一样有最少子节点数量限制的原因）
下图是一个5阶B树，我们通过顺序插入1到17，来观察节点的分裂过程。

B树的删除

B树的删除就复杂了许多，可分为下面几种情况：

删除叶子节点中的元素 （1）搜索要删除的元素 （2）如果它在叶子节点上，直接将其删除 （3）如果删除后产生了下溢出（键数小于最小值），则向其兄弟节点借元素。即将其父节点元素下移至当前节点，将兄弟节点中元素上移至父节点（若是左节点，上移最大元素；若是右节点，上移最小元素） （4）若兄弟节点也达到下限，则合并兄弟节点与分割键。
删除内部节点中的元素 （1）内部节点中元素为其左右子节点的分割值，需要从左子节点最大元素或右子节点最小元素中选出一个新的分割符。被选中的分割符从原子节点中移除，作为新的分隔值替换掉被删除的元素。 （2）上一步中，若左右子节点元素数均达到下限，则合并左右子节点。 （3）若删除元素后，其中节点元素数小于下限，则继续合并。
下图是一个5阶B树，我们通过删除15、14、17、5四个键，来观察删除过程（基本涵盖所有情况）。

键值类

该类用于存放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());
    }
}
1
2
3
4
5
6
7
8
9
10

节点类

节点类是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());
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

搜索

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);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

参考链接：https://zhuanlan.zhihu.com/p/340721689