数据结构-B树

发表于 2020-08-09 分类于数据结构与算法

本文字数： 14k 阅读时长 ≈ 13 分钟

概述

B 树 是一种自平衡的多叉查找树，它可在对数时间内完成查询、插入、删除操作，常用于大规模数据存取场景，例如：数据库、文件系统。

其结构图大致如下：

图一：B树

当处理大规模数据时，由于内存无法存放所有数据，故而程序运行期间，往往是部分数据位于内存之中，部分数据位于磁盘之中。如果程序访问数据位于磁盘之中，操作系统则调用磁盘内容到内存之中，随后按照内存访问规则进行访问。由于磁盘访问速度远低于内存访问速度，故而此时程序运行时间主要依托于磁盘访问次数。

为降低程序运行时间，我们就要确保磁盘访问次数尽可能的少。为减少磁盘访问次数，我们就需要存储一定信息以实现跳跃搜索，自然而然可以想到二叉查找树。如果直接应用二叉查找树，那么磁盘访问次数基本等于树高。为进一步降低程序运行时间，我们可以使用多叉查找树以降低树高，从而减少磁盘访问次数。同时，为保证磁盘访问次数明确界限于树高，那么就需要对多叉查找树施加平衡条件。

上述所言基本是 B 树原理。接下来，我们将简要定义 B 树。

B 树是一棵满足如下性质的 $t$ 叉树 ($t$ 指代节点所含孩子节点个数，亦称为节点的阶)：

所有叶节点到根节点的路径长度相同，即具有相同高度。
所有非叶节点和非根节点至少含有 $t$ 个孩子节点，根节点至少含有 $2$ 个孩子节点。
每个非叶节点至多含有 $2t$ 个孩子节点。
每个节点内部键值依次递增。
每个非叶节点所含孩子节点数总是比所含键值数多 $1$。

2-3 树、2-3-4 树均为 B 树特例，B+树、B*树均为 B 树扩展。

结构

B 树结构比较复杂，我们在代码中加以描述。

class BTree<K extends Comparable, V> {
    // 二元组，存放键值对。
    private class Entry<K extends Comparable, V> {
        K k;
        V v;

        public Entry() {

        }

        public Entry(K k, V v) {
            this.k = k;
            this.v = v;
        }

        public K getK() {
            return k;
        }

        public void setK(K k) {
            this.k = k;
        }

        public V getV() {
            return v;
        }

        public void setV(V v) {
            this.v = v;
        }

        // 比较键值。
        public int compareTo(K k) {
            return this.k.compareTo(k);
        }
    }

    // 节点结构
    private class Node<K extends Comparable, V> {
        // 关键字键值对(0号位置不使用，方便后续代码编写)
        ArrayList<Entry<K, V>> entries;
        // 孩子节点
        ArrayList<Node<K, V>> childrens;
        // 是否为叶节点
        Boolean leaf;

		// 初始化，占位entries[0]、设非叶节点。
        public Node() {
            this.entries = new ArrayList<>();
            this.entries.add(null);
            this.childrens = new ArrayList<>();
            this.leaf = false;
        }

        public ArrayList<Entry<K, V>> getEntries() {
            return entries;
        }

        public void setEntries(ArrayList<Entry<K, V>> entries) {
            this.entries = entries;
        }

        public ArrayList<Node<K, V>> getChildrens() {
            return childrens;
        }

        public void setChildrens(ArrayList<Node<K, V>> childrens) {
            this.childrens = childrens;
        }

        public Boolean getLeaf() {
            return leaf;
        }

        public void setLeaf(Boolean leaf) {
            this.leaf = leaf;
        }

        // 找到<=key的关键字位置(查找过程也可使用二分)。
        public SearchResult<V> search(K key) {
            int index;

            for (index = 1; index < this.entries.size(); index++) {
                if (this.entries.get(index).compareTo(key) > 0) {
                    break;
                }
            }

            SearchResult<V> searchResult = new SearchResult();
            searchResult.setIndex(index - 1);
            if (index == 1 || this.entries.get(index - 1).compareTo(key) != 0) {
                searchResult.setExist(false);
            } else {
                searchResult.setExist(true);
                searchResult.setValue(this.entries.get(index - 1).getV());
            }

            return searchResult;
        }

    }

    // 搜索结果
    private class SearchResult<V> {
        // 对应关键字是否存在
        boolean exist;
        // 位置信息(如果关键字存在，则表示其在entries中位置下标，否则表示在childrens中待插入子树的位置下标)
        int index;
        // 关键字对应值
        V value;

        public boolean isExist() {
            return exist;
        }

        public void setExist(boolean exist) {
            this.exist = exist;
        }

        public int getIndex() {
            return index;
        }

        public void setIndex(int index) {
            this.index = index;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }
    }

    // B树根节点
    private Node<K, V> root;
    // B树阶(动态调整)
    private int order;
}

实现

辅助方法

当前子树中查找指定键值

private V searchTree(Node<K, V> root, K key) {
    // 获取查询结果
    SearchResult<V> result = root.search(key);
    
    // 如果查询成功，直接返回值。
    if (result.exist) {
        return result.getValue();
    }

    // 当前节点为叶节点，无孩子节点可搜索，故而返回null。
    if (root.getLeaf()) {
        return null;
    }

    // 当前节点为非叶节点，在孩子节点中递归查找即可。
    return searchTree(root.getChildrens().get(result.getIndex()), key);
}

分裂指定节点的某个子节点

如果某个节点所含孩子节点数等于 $2t$，那么就需要分裂该节点。

分裂规则：节点含有 $2t$ 个孩子节点，那么对应含有 $2t - 1$ 个关键字。提升第 $t$ 个关键字到父节点，前 $t - 1$ 个关键字及 $t$ 个孩子节点组成一个节点，后 $t - 1$ 个关键字及 $t$ 个孩子节点组成一个节点。

private void splitNode(Node<K, V> root, int index) {
    // 获取子节点
    Node<K, V> child = root.getChildrens().get(index);

    // 新建一个邻居子节点，该节点与子节点具有相同的节点属性(是否为叶节点)。
    Node<K, V> siblingNode = new Node<>();
    siblingNode.setLeaf(child.getLeaf());

    // 这里通过拆分方式构成两个节点。
    // 转移[order + 1, order * 2 - 1]区间元素至siblingNode。
    for (int i = 1; i < this.order; i++) {
        siblingNode.getEntries().add(child.getEntries().remove(this.order + 1));
    }

    // 获取order位置关键字键值对，并将其从child中删去。
    Entry<K, V> midEntry = child.getEntries().remove(this.order);

    // 如果子节点并非叶节点，则需要转移[order, order * 2 - 1]区间元素至siblingNode。
    if (!child.getLeaf()) {
        for (int i = 0; i < this.order; i++) {
            siblingNode.getChildrens().add(child.getChildrens().remove(this.order));
        }
    }

    // 向指定节点中添加order位置关键字键值对
    root.getEntries().add(index + 1, midEntry);
    // 向指定节点中添加siblingNode子节点
    root.getChildrens().add(index + 1, siblingNode);
}

当前非满子树中添加键值对

为保证 B 树向下搜索过程中不会产生回溯过程，我们会对待插入节点进行预处理：如果待插入节点含有 $2t$ 个孩子节点，则需要拆分该节点。

private void insertNotFull(Node<K, V> root, K key, V value) {
    // 获取查询结果
    SearchResult<V> result = root.search(key);

    // 表明当前节点内部存在该关键字，直接退出即可。
    if (result.isExist()) {
        return ;
    }

    // 当前节点内部不存在该关键字，根据节点是否为叶节点，选择不同方式进行插入。
    if (root.getLeaf()) {
        // 当前节点为叶节点，直接插入即可(注意result.index字段含义)。
        root.getEntries().add(result.getIndex() + 1, new Entry<>(key, value));
    } else {
        // 对待插入节点进行预处理，然后递归插入。
        
        // 获取待插入孩子节点。
        Node<K, V> child = root.getChildrens().get(result.getIndex());
        
        // 孩子节点已满，需进行拆分。
        // 关键字个数为order * 2 - 1时表明已满，又因为代码实现中位置0处并未使用，故而条件判断为order * 2。
        if (child.getEntries().size() == this.order * 2) {
            splitNode(root, result.getIndex());
            // 如果提升的关键字值小于待插入关键字值，则需要更新待插入孩子节点。
            if (root.getEntries().get(result.getIndex() + 1).compareTo(key) < 0) {
                child = root.getChildrens().get(result.getIndex() + 1);
            }
        }

        // 递归插入。
        insertNotFull(child, key, value);
    }
}

当前子树中删除指定键值

删除过程主要涉及如下情景：

情景1：关键字 $key$ 位于节点 $x$ 之中，并且节点为叶节点，则直接从节点 $x$ 中删除 $key$ 表示的键值对即可。

情景2：关键字 $key$ 位于节点 $x$ 之中，但是节点为非叶节点，则进行如下操作：

如果节点 $x$ 中位于关键字 $key$ 之前的子节点 $y$ 中至少含有 $t$ 个关键字，则使用 $y$ 的最后一个关键字替换节点 $x$ 中的关键字 $key$，并递归调用子节点 $y$ 以删除它的最后一个关键字。
如果节点 $x$ 中位于关键字 $key$ 之后的子节点 $z$ 中至少含有 $t$ 个关键字，则使用 $z$ 的第一个关键字替换节点 $x$ 中的关键字 $key$ ，并递归调用子节点 $z$ 以删除它的第一个关键字。
子节点 $y$ 和 $z$ 均仅含有 $t - 1$ 个关键字，则融合 $z$ 中关键字及关键字 $key$ 至子节点 $y$，随后递归调用子节点 $y$ 以删除关键字 $key$ 。

情景3：关键字并不位于节点 $x$ 之中，此时需进入孩子节点以期删除关键字 $key$，故而需格外注意孩子节点状态，故而需进行如下操作：

孩子节点至少含有 $t$ 个关键字，直接进入孩子节点，递归删除关键字 $key$。
孩子节点仅含有 $t - 1$ 个关键字，如果左兄弟孩子节点或右兄弟孩子节点至少含有 $t$ 个关键字，则借调一个关键字使得孩子节点含有 $t$ 个关键字，随后进入孩子节点，递归删除关键字 $key$。
孩子节点仅含有 $t - 1$ 个关键字，并且左兄弟孩子节点或右兄弟孩子节点也仅有 $t - 1$ 个关键字，则融合一个兄弟节点中关键字及节点 $x$ 中位于关键字 $x$ 之前的关键字至孩子节点，从而使得孩子节点含有 $2t - 1$ 个关键字，随后进入孩子节点，递归删除关键字 $key$。

private void deleteTree(Node<K, V> root, K key) {
    // 获取查询结果。
    SearchResult<V> result = root.search(key);

    // 关键字存在于当前节点之中。
    if (result.isExist()) {
        // 当前节点为叶节点，直接删除即可，对应情景1。
        if (root.getLeaf()) {
            root.getEntries().remove(result.getIndex());
            return ;
        }

        // 当前节点为非叶节点，那么删除就需要考虑替换策略，对应情景2。
        // 获取key对应的左右孩子。
        Node<K, V> leftChild = root.getChildrens().get(result.getIndex() - 1);
        Node<K, V> rightChild = root.getChildrens().get(result.getIndex());
        // 左孩子含有关键字个数大于order-1，则可用其最后一个关键字替换key，并递归调用左孩子以删除该关键字，对应情景2.1。
        if (leftChild.getEntries().size() > this.order) {
            // 获取左孩子的最后一个关键字。
            Entry<K, V> next = leftChild.getEntries().get(leftChild.getEntries().size() - 1);

            // 替换key。
            root.getEntries().remove(result.getIndex());
            root.getEntries().add(result.getIndex(), next);

            // 递归删除。
            deleteTree(leftChild, next.getK());
        } else if (rightChild.getEntries().size() > this.order) {
            // 右孩子含有关键字个数大于order-1，则可用其第一个关键字替换key，并递归调用左孩子以删除该关键字，对应情景2.2。
            // 获取右孩子的第一个关键字。
            Entry<K, V> pre = rightChild.getEntries().get(1);

            // 替换key。
            root.getEntries().remove(result.getIndex());
            root.getEntries().add(result.getIndex(), pre);

            // 递归删除。
            deleteTree(rightChild, pre.getK());
        } else {
            // 此时左右孩子所含关键字个数均为order-1，则合并左右孩子关键字及当前关键字为一个节点，对应情景2.3。
            // 从当前节点中删除该关键字及其右孩子。
            Entry<K, V> deleteKV = root.getEntries().remove(result.getIndex());
            root.getChildrens().remove(result.getIndex());

            // 合并关键字。
            leftChild.getEntries().add(deleteKV);
            for (int i = 1; i < this.order; i++) {
                leftChild.getEntries().add(rightChild.getEntries().remove(1));
            }

            // 如若右孩子为非叶节点，则需合并孩子节点。
            if (!rightChild.getLeaf()) {
                for (int i = 0; i < this.order; i++) {
                    leftChild.getChildrens().add(rightChild.getChildrens().remove(0));
                }
            }

            // 合并可能导致树高降1，从而使得根节点发生变化。
            if (root == this.root && root.getEntries().size() == 1) {
                this.root = leftChild;
            }

            // 递归删除。
            deleteTree(leftChild, key);
        }
    } else {
        // 当前节点不存在关键字，对应情景3。
        // 当前节点为叶节点，表明不存在该关键字，直接返回即可。
        if (root.getLeaf()) {
            return ;
        }

        // 获取待搜索孩子节点
        Node<K, V> childNode = root.getChildrens().get(result.getIndex());
        
        // 待搜索孩子节点所含关键字个数大于order-1，则直接递归删除即可，对应情景3.1。
        if (childNode.getEntries().size() > this.order) {
            deleteTree(childNode, key);
        } else {
            // 待搜索孩子节点所含关键字个数等于order-1，则需预处理使其所含关键字个数大于order-1。
            
            // 尝试获取待搜索孩子节点的左右兄弟节点
            Node<K, V> leftChild = null;
            Node<K, V> rightChild = null;
            // 是否存在一个兄弟节点所含关键字个数大于order-1
            Boolean flag = false;

            if (result.getIndex() > 0) {
                leftChild = root.getChildrens().get(result.getIndex() - 1);
                if (leftChild.getEntries().size() > this.order) {
                    flag = true;
                }
            }
            if (result.getIndex() < root.getChildrens().size() - 1) {
                rightChild = root.getChildrens().get(result.getIndex() + 1);
                if (rightChild.getEntries().size() > this.order) {
                    flag = true;
                }
            }

            // flag=true表明至少一个兄弟节点所含关键字个数大于order-1，则调用借调一个关键字给待搜索孩子节点，对应情景3.2，否则需要将待搜索孩子节点与一个兄弟节点进行合并，对应情景3.3。
            if (flag) {
                // 左兄弟节点存在，且其所含关键字个数大于order-1，则将其一个关键字转移到待搜索孩子节点
                if (leftChild != null && leftChild.getEntries().size() > this.order) {
                    // 将当前节点中小于指定关键字的第一个关键字下放至待搜索孩子节点的第一个关键字。
                    childNode.getEntries().add(1, root.getEntries().remove(result.getIndex()));
                    // 将左兄弟节点的最后一个关键字上升至当前节点
                    root.getEntries().add(result.getIndex(), leftChild.getEntries().remove(leftChild.getEntries().size() - 1));

                    // 左兄弟节点不为叶节点，则需要转移它的最后一个孩子节点到待搜索孩子节点
                    if (!leftChild.getLeaf()) {
                        childNode.getChildrens().add(0, leftChild.getChildrens().remove(leftChild.getChildrens().size() - 1));
                    }
                } else {
                    // 右兄弟节点存在，且其所含关键字个数大于order-1，则将其一个关键字转移到待搜索孩子节点。
                    // 将当前节点中大于指定关键字的第一个关键字下放至待搜索孩子节点的最后一个关键字。
                    childNode.getEntries().add(root.getEntries().remove(result.getIndex() + 1));
                    // 将右兄弟节点的第一个关键字上升至当前节点。
                    root.getEntries().add(result.getIndex() + 1, rightChild.getEntries().remove(1));

                    // 右兄弟节点不为叶节点，则需要转移它的第一个孩子节点到待搜索孩子节点。
                    if (!rightChild.getLeaf()) {
                        childNode.getChildrens().add(rightChild.getChildrens().remove(0));
                    }
                }
                
                // 递归删除。
                deleteTree(childNode, key);
            } else {
                // 左右兄弟节点都含有order-1个关键字，此时选择一个非空兄弟节点合并即可。
                if (null != leftChild) {
                    // 左兄弟节点不为空
                    // 当前节点中删除小于指定关键字的第一个关键字及其右孩子，并将该关键字下放至待搜索孩子节点。
                    childNode.getEntries().add(1, root.getEntries().remove(result.getIndex()));
                    root.getChildrens().remove(result.getIndex() - 1);
                    
                    // 合并关键字。
                    for (int i = this.order - 1; i > 0; i--) {
                        childNode.getEntries().add(1, leftChild.getEntries().remove(i));
                    }
                    
                    // 待搜索孩子节点不为叶节点，则合并孩子节点。
                    if (!childNode.getLeaf()) {
                        for (int i = this.order - 1; i >= 0; i--) {
                            childNode.getChildrens().add(0, leftChild.getChildrens().remove(i));
                        }
                    }
                } else if (null != rightChild){
                    // 右兄弟节点不为空
                    // 当前节点中删除大于指定关键字的第一个关键字及其右孩子，并将该关键字下放至待搜索孩子节点。
                    childNode.getEntries().add(root.getEntries().remove(result.getIndex() + 1));
                    root.getChildrens().remove(result.getIndex() + 1);
                    
                    // 合并关键字。
                    for (int i = 1; i < this.order; i++) {
                        childNode.getEntries().add(rightChild.getEntries().remove(1));
                    }
                    
                    // 待搜索孩子节点不为叶节点，则合并孩子节点。
                    if (!childNode.getLeaf()) {
                        for (int i = 0; i < this.order; i++) {
                            childNode.getChildrens().add(rightChild.getChildrens().remove(0));
                        }
                    }
                }

                // 合并可能导致树高降1，从而使根节点发生变化。
                if (root == this.root && root.getEntries().size() == 1) {
                    this.root = childNode;
                }

                // 递归删除。
                deleteTree(childNode, key);
            }
        }
    }
}

初始化

要点： 根节点需要初始化为叶节点。

public BTree(int order, Comparator<? super K> comparator) {
    this.root = new Node<>();
    this.root.setLeaf(true);
    this.order = order;
}

查询

查询指定关键字

1
2
3

public V search(K key) {
    return searchTree(this.root, key);
}

操纵

B 树中添加键值对

根节点分裂涉及重新设置 root，我们将其单独处理。

ublic void add(K key, V value) {
    // 根节点已满，需分裂并重新设置根节点。
    if (this.root.getEntries().size() == this.order * 2) {
        Node<K, V> newRoot = new Node<>();
        newRoot.getChildrens().add(this.root);
        splitNode(newRoot, 0);
        this.root = newRoot;
    }
    
    insertNotFull(this.root, key, value);
}

B 树中删除键值对

1
2
3

public void delete(K key) {
    deleteTree(this.root, key);
}

扩展

B+ 树是 B 树的一种重要变体。相比于 B 树而言，其查询性能更为高效、更为稳定。

各种资料中 B+ 树的定义略有差异，我们采用维基百科上提供的定义。基于此定义，我们首先给出 B+ 树与 B 树之间的差异：

在 B+ 树中，节点分为两种类型——内部节点 (索引节点) 和叶节点。内部节点 (索引节点) 存放关键字及孩子指针，叶节点存放关键字及其对应数据。在B 树中，节点只具有一种类型，它存放关键字、对应数据及孩子指针。基于此差异，我们可知：相比 B 树而言，B+ 树更为矮胖。
在 B+ 树中，对于索引节点中关键字而言，其左子树中节点均小于该关键字，右子树中节点均大于等于该关键字 (以此保证能够索引至相应叶节点)。在 B 树中，对于节点中关键字而言，其左子树中节点均小于该关键字，右子树中节点均大于该关键字，此关键字及对应数据亦存于此节点之中。基于此差异，我们可知：B+ 树中同一关键字可能出现在多个节点之中。
在 B+ 树中，叶节点依关键字大小顺序进行链接。在 B 树中，叶节点之间并无任何关系。基于此差异，我们可知：B+ 树中可高效实现范围查询。
在 B+ 树中，需要存储根节点及最小关键字节点引用。在 B 树中，仅需存储根节点引用。

图二：B+ 树(前者定义)

不同 B+ 树定义的差异点在于：如何处理节点内部关键字个数与孩子节点个数之间的关系。一种定义方式为：节点内部孩子节点个数等于关键字个数加一 (就是B 树原始定义)，另一种定义方式为：节点内部关键字个数与孩子节点个数相等。

我们很容易将基于前者定义的 B+ 树改造为基于后者的 B+ 树。在前者定义中，对于索引节点中关键字而言，其左子树中节点均小于该关键字，右子树中节点均大于等于该关键字。将其改造为后者定义便是，对于索引节点中关键字而言，其对应子树中节点均大于等于该关键字。在该种定义中，我们舍弃小于当前节点中最小关键字的子树，这一点可使用如下操作进行替代：如果待插入关键字小于当前节点中最小关键字，我们就将当前节点中最小关键字修改为待插入关键字，随后进行插入。

当采用第二种定义方式时，基于 B+ 树的一种变体 B* 树被定义。相比于 B+ 树，B* 树具有如下特点：1. 如果节点不为叶节点或根节点，则其内部需要存储一个指向右邻居关键字的引用。2. 节点内部所含关键字个数至少为 $\frac{2}{3}t$ (这使得其节点空间使用率更高)。由于节点所含最小关键字个数定义发生变动，故而其分裂规则亦发生变动：当插入关键字之时，如果当前节点所含关键字个数为 $2t - 1$ (已满)，则会判断右邻居节点所含关键字个数是否已满，如果未满则转移部分关键字至右邻居节点，否则新建一个右邻居节点，并将当前节点及原先右邻居节点的$\frac{1}{3}t$ 个关键字转移至其内。

B+ 树肯定是很重要的，因为维基百科有定义且广泛应用于数据库之中；B* 树未必有用，因为维基百科没有定义且基本搜不到资料，了解就行了。

接下来，我们简单描述 B+ 树结构及其相关操作：

结构

B+ 树涉及两种节点类型——内部节点和叶节点。对于内部节点而言，需使用数组存储关键字及孩子指针；对于叶节点，需使用数组存储关键字、对应数据及右邻居关键字引用。对于这两种节点而言，它们均需使用一个引用存储父节点、一个布尔值表示当前节点是否为叶节点。

对于 B+ 树而言，它需要存储根节点及具有最小关键字节点的引用，同时需要存储树阶。
查询

查询操作与 B 树基本一致，只是必须递归至叶节点完成查询。
插入

插入操作与 B 树存在较大差异，但是思路基本不变。

首先需要根据关键字索引至叶节点，然后将该数据插入其中。如果叶节点所含关键字个数已到达上限 (即含有 $2t$ 个关键字)，此时需要拆分为两个叶节点，前 $t$ 关键字位于左叶节点，后 $t$ 关键字位于右叶节点，并将右叶节点的第一个关键字插入至父节点。如果父节点所含关键字个数已达上限，此时需要拆分为两个索引节点，前 $t - 1$ 个关键字位于左索引节点，后 $t$ 个关键字位于右索引节点，并将第 $t$ 个关键字插入于父节点之中，随后递归更新父节点。
删除

删除操作与 B 树基本相同。

首先需要根据关键字索引至叶节点，随后删除该关键字。如果叶节点所含关键字个数已到达下限 (即含有 $t - 2$ 个关键字)，此时需要从左右邻居节点中借调一个关键字、或者合并邻居节点，随后更新父节点相应位置的关键字。