B 树

2-3 树

一、定义

2–3树是一种树型数据结构)，内部节点（存在子节点的节点）要么有2个孩子和1个数据元素，要么有3个孩子和2个数据元素，叶子节点没有孩子，并且有1个或2个数据元素。

• 如果一个内部节点拥有一个数据元素、两个子节点，则此节点为2节点。
• 如果一个内部节点拥有两个数据元素、三个子节点，则此节点为3节点。

• 当且仅当以下叙述中有一条成立时，T为2–3树：

  • T为空。即T不包含任何节点。

  • T为拥有数据元素a的2节点。若T的左孩子为L、右孩子为R，则

    • L和R是等高的非空2–3树；
    • a大于L中的所有数据元素；
    • a小于等于R中的所有数据元素。

  • T为拥有数据元素a和b的3节点，其中a < b。若T的左孩子为L、中孩子为M、右孩子为R，则

    • L、M、和R是等高的非空2–3树；
    • a大于L中的所有数据元素，并且小于等于M中的所有数据元素；
    • b大于M中的所有数据元素，并且小于等于R中的所有数据元素。

二、代码

1. 构造

    /**
     * B树中的节点。
     */
    private static class BTreeNode<K, V> {
        /**
         * 节点的项，按键非降序存放
         */
        private List<Entry<K, V>> entries;
        /**
         * 内节点的子节点
         */
        private List<BTreeNode<K, V>> children;
        /**
         * 是否为叶子节点
         */
        private boolean leaf;
        /**
         * 键的比较函数对象
         */
        private Comparator<K> kComparator;
        private BTreeNode() {
            entries = new ArrayList<>();
            children = new ArrayList<>();
            leaf = false;
        }
        ...

entry

    private static class Entry<K, V> {
        private K key;
        private V value;
        public Entry(K k, V v) {
            this.key = k;
            this.value = v;
        }
        // getter/setter
        @Override
        public String toString() {
            return key + ":" + value;
        }
    }

2. 查找

和排序二叉树的搜索很类似，只是换成多叉和多项。
输入key，记住每个节点的key都是有序的

1. 从根节点开始找，如果根节点里有，则返回；否则找到对应的下标去子节点递归搜索；
2. 如果到了叶子节点还没找到，那就找不到。

    public V search(K key) {
        return search(root, key);
    }
    private V search(BTreeNode<K, V> node, K key) {
        // 在一个节点内搜索
        SearchResult<V> result = node.searchKey(key);
        if (result.isExist()) {
            return result.getValue();
        } else {
            if (node.isLeaf()) {
                return null;
            } else {
                // 进入递归
                search(node.childAt(result.getIndex()), key);
            }
        }
        return null;
    }

3.插入

对于2-3树的插入操作一般分为以下几种情况：
1.往一个2-node节点插入新键。（树的初始态）
2.向一棵只含有一个3-节点的树中插入新键。（树的初始态）
3.向一个父节点为2-节点的3-节点中插入新键。（子树的分裂1）
4.向一个父节点为3-节点的3-节点中插入新建。（子树的分类2）
5.分解根节点。（树的向上生长态）

往一个2-node节点插入

往2-3树中插入元素和往二叉查找树中插入元素一样，首先要进行查找，然后将节点挂到未找到的节点上。2-3树之所以能够保证在最差的情况下的效率的原因在于其插入之后仍然能够保持平衡状态。如果查找后未找到的节点是一个2-node节点，那么很容易，我们只需要将新的元素放到这个2-node节点里面使其变成一个3-node节点即可。但是如果查找的节点结束于一个3-node节点，那么可能有点麻烦。

往一个3-node节点插入

往一个3-node节点插入一个新的节点可能会遇到很多种不同的情况，下面首先从一个最简单的只包含一个3-node节点的树开始讨论。

操作1：只包含一个3-node节点

如上图，假设2-3树只包含一个3-node节点，这个节点有两个key，没有空间来插入第三个key了，最自然的方式是我们假设这个节点能存放三个元素，暂时使其变成一个4-node节点，同时他包含四个子节点。然后，我们将这个4-node节点的中间元素提升，左边的节点作为其左节点，右边的元素作为其右节点。插入完成，变为平衡2-3查找树，树的高度从0变为1。

操作2：父节点：2-节点，子节点：3-节点
和第一种情况一样，我们也可以将新的元素插入到3-node节点中，使其成为一个临时的4-node节点，然后，将该节点中的中间元素提升到父节点即2-node节点中，使其父节点成为一个3-node节点，然后将左右节点分别挂在这个3-node节点的恰当位置。操作如下图：

操作3：父节点：3-节点，子节点：3-节点
当我们插入的节点是3-node的时候，我们将该节点拆分，中间元素提升至父节点，但是此时父节点是一个3-node节点，插入之后，父节点变成了4-node节点，然后继续将中间元素提升至其父节点，直至遇到一个父节点是2-node节点，然后将其变为3-node，不需要继续进行拆分。

此处子节点分裂后，把一个元素加入到了它的父节点，但也超过了父节点的存储能力，所以还要继续向上分裂，直到有容下它的父节点。

上述操作2和操作3是不会影响树的深度的，正影响树的深度的情况是：只有当根节点为3-节点时，此时有元素插入沉底后，不断向上裂变，很不幸如果影响到根节点。也就是下面根节点分裂的情况。

根节点分裂

当根节点到子节点都是3-node节点的时候，这是如果我们要在字节点插入新的元素的时候，会一直查分到跟节点，在最后一步的时候，跟节点变成了一个4-node节点，这个时候，就需要将跟节点查分为两个2-node节点，树的高度加1，这个操作过程如下：

本地转换

将一个4-node拆分为2-3node涉及到6种可能的操作。这4-node可能在跟节点，也可能是2-node的左子节点或者右子节点。或者是一个3-node的左，中，右子节点。所有的这些改变都是本地的，不需要检查或者修改其他部分的节点。所以只需要常数次操作即可完成2-3树的平衡。

性质

这些本地操作保持了2-3树的平衡。对于4-node节点变形为2-3节点，变形前后树的高度没有发生变化。只有当跟节点是4-node节点，变形后树的高度才加一。如下图所示：

4. 删除

删除节点比插入节点麻烦一些，先来看删除底部节点，在搜索过程中就需要对节点做相应的变化，以保证搜索路径上的都是3-node或临时的4-node，在删除当前节点T时，T一定是3-node或4-node，就可以安全删除了，删除之后树的变化规则与插入一致。删除其他节点可以转化为删除底部节点，只需要将删除元素与底部节点元素交换即可。

5. 总结

2-3树作为一种平衡查找树，查询效率比普通的二叉排序树要稳定许多，其操作逻辑也非常清晰。2-3树可以采用红黑树实现，使用二叉树结构从逻辑上模拟了2-3树，在插入删除节点时，又具有二叉平衡树的便利。

2-3-4树

1、2-3-4 树介绍

2-3-4树每个节点最多有四个字节点和三个数据项，名字中 2,3,4 的数字含义是指一个节点可能含有的子节点的个数。对于非叶节点有三种可能的情况：

①、有一个数据项的节点总是有两个子节点；

②、有二个数据项的节点总是有三个子节点；

③、有三个数据项的节点总是有四个子节点；

简而言之，非叶节点的子节点数总是比它含有的数据项多1。如果子节点个数为L，数据项个数为D，那么：L = D + 1

叶节点（上图最下面的一排）是没有子节点的，然而它可能含有一个、两个或三个数据项。空节点是不会存在的。

树结构中很重要的一点就是节点之间关键字值大小的关系。在二叉树中，所有关键字值比某个节点值小的节点都在这个节点左子节点为根的子树上；所有关键字值比某个节点值大的节点都在这个节点右子节点为根的子树上。2-3-4 树规则也是一样，并且还加上以下几点：

为了方便描述，用从0到2的数字给数据项编号，用0到3的数字给子节点编号，如下图：

①、根是child0的子树的所有子节点的关键字值小于key0；

②、根是child1的子树的所有子节点的关键字值大于key0并且小于key1；

③、根是child2的子树的所有子节点的关键字值大于key1并且小于key2；

④、根是child3的子树的所有子节点的关键字值大于key2。

简化关系如下图，由于2-3-4树中一般不允许出现重复关键值，所以不用考虑比较关键值相同的情况。

2、搜索2-3-4树

查找特定关键字值的数据项和在二叉树中的搜索类似。从根节点开始搜索，除非查找的关键字值就是根，否则选择关键字值所在的合适范围，转向那个方向，直到找到为止。

比如对于下面这幅图，我们需要查找关键字值为 64 的数据项。

首先从根节点开始，根节点只有一个数据项50，没有找到，而且因为64比50大，那么转到根节点的子节点child1。60|70|80 也没有找到，而且60<64<70，所以我们还是找该节点的child1,62|64|66，我们发现其第二个数据项正好是64，于是找到了。

3、插入

新的数据项一般要插在叶节点里，在树的最底层。如果你插入到有子节点的节点里，那么子节点的编号就要发生变化来维持树的结构，因为在2-3-4树中节点的子节点要比数据项多1。

插入操作有时比较简单，有时却很复杂。

①、当插入没有满数据项的节点时是很简单的，找到合适的位置，只需要把新数据项插入就可以了，插入可能会涉及到在一个节点中移动一个或其他两个数据项，这样在新的数据项插入后关键字值仍保持正确的顺序。如下图：

②、如果往下寻找插入位置的途中，节点已经满了，那么插入就变得复杂了。发生这种情况时，节点必须分裂，分裂能保证2-3-4树的平衡。

ps：这里讨论的是自顶向下的2-3-4树，因为是在向下找到插入点的路途中节点发生了分裂。把要分裂的数据项设为A,B,C，下面是节点分裂的情况（假设分裂的节点不是根节点）：

1、节点分裂

一、创建一个新的空节点，它是要分裂节点的兄弟，在要分裂节点的右边；

二、数据项C移到新节点中；

三、数据项B移到要分裂节点的父节点中；

四、数据项A保留在原来的位置；

五、最右边的两个子节点从要分裂处断开，连到新节点上。

上图描述了节点分裂的例子，另一种描述节点分裂的说法是4-节点变成了两个 2- 节点。节点分裂是把数据向上和向右移动，从而保持了数的平衡。一般插入只需要分裂一个节点，除非插入路径上存在不止一个满节点时，这种情况就需要多重分裂。

2、根的分裂

如果一开始查找插入节点时就碰到满的根节点，那么插入过程更复杂：

①、创建新的根节点，它是要分裂节点的父节点。

②、创建第二个新的节点，它是要分裂节点的兄弟节点；

③、数据项C移到新的兄弟节点中；

④、数据项B移到新的根节点中；

⑤、数据项A保留在原来的位置；

⑥、要分裂节点最右边的两个子节点断开连接，连到新的兄弟节点中。

上图便是根分裂的情况，分裂完成之后，整个树的高度加1。另外一种描述根分裂的方法是说4-节点变成三个2-节点。

注意：插入时，碰到没有满的节点时，要继续向下寻找其子节点进行插入。如果直接插入该节点，那么还要进行子节点的增加，因为在2-3-4树中节点的子节点个数要比数据项多1；如果插入的节点满了，那么就要进行节点分裂。下图是一系列插入过程，有4个节点分裂了，两个是根，两个是叶节点：

B树

一. B树定义

• 所有叶子节点到根节点的路径长度相同，即具有相同的高度；
• 每个非叶子和非根节点（即内部节点）至少有t-1个孩子节点；根至少2个孩子
• 每个节点最多有2t个孩子节点。
• 每个节点内的键都是递增的
• 每个节点的孩子比key的个数多1
• 这次用 t tt 来表示B树的最小度数（任意节点最少有 t 个孩子），看下图就明白了：

    /**
     * B树中的节点。
     */
    private static class BTreeNode<K, V> {
        /**
         * 节点的项，按键非降序存放
         */
        private List<Entry<K, V>> entries;
        /**
         * 内节点的子节点
         */
        private List<BTreeNode<K, V>> children;
        /**
         * 是否为叶子节点
         */
        private boolean leaf;
        /**
         * 键的比较函数对象
         */
        private Comparator<K> kComparator;
        private BTreeNode() {
            entries = new ArrayList<>();
            children = new ArrayList<>();
            leaf = false;
        }
        ...