GitHub源碼分享

微信搜索：碼農(nóng)StayUp

主頁地址：https://gozhuyinglong.github.io

源碼分享：https://github.com/gozhuyinglong/blog-demos

1. 前言

迄今為止，已經(jīng)介紹了《 二叉查找樹 》和《 AVL樹 》，我們始終假設(shè)可以把整個數(shù)據(jù)結(jié)構(gòu)存儲在內(nèi)存中。可是，如果數(shù)據(jù)多到內(nèi)存裝不下，這就意味著必須把數(shù)據(jù)放在磁盤上，顯然這些數(shù)據(jù)結(jié)構(gòu)不再適用。

問題在于磁盤的I/O速度是遠遠不如內(nèi)存訪問速度的，然而從一棵樹中查找到某個元素，必須從根節(jié)點一層層往下找，這每一次查找便是一次I/O操作。為了提高性能，就必須要減少查找的次數(shù)。

如能減少樹的高度、增加每個節(jié)點中的元素數(shù)，便是種有效的解決方案。實現(xiàn)這種想法的一種方法是使用B樹。

2. 術(shù)語

在介紹B樹時會用到一些術(shù)語，這里先看一下：

• 根節(jié)點（root）：沒有父節(jié)點的節(jié)點叫做根節(jié)點
• 葉子節(jié)點（leaf）：沒有子節(jié)點的節(jié)點叫做葉子節(jié)點
• 內(nèi)部節(jié)點（internal）：除根節(jié)點和葉子節(jié)點之外的節(jié)點叫做內(nèi)部節(jié)點。它們即有父節(jié)點，也有子節(jié)點。
• 鍵：B樹中的存儲元素是鍵，是用于指向數(shù)據(jù)記錄的指針。鍵的值是用于存儲真正的數(shù)據(jù)記錄。一個節(jié)點中可以擁有多個鍵。
• 階：B樹的階為最大子節(jié)點數(shù)量，其比鍵的數(shù)量大1。我們一般稱一個B樹為M階的B樹，那么該B樹最多擁有M個子節(jié)點，節(jié)點中最多擁有M-1個鍵。

更多術(shù)語請參閱之前分享的《 樹 》!

3. B樹（B-Tree）

B樹與二叉樹（Binary Tree）不是一個概念，你可以將其翻譯成Balance Tree，或者是Bayer Tree。

B樹是一種自平衡的樹，能夠保持數(shù)據(jù)有序。這種數(shù)據(jù)結(jié)構(gòu)能夠讓查找數(shù)據(jù)、順序訪問、插入數(shù)據(jù)及刪除的動作，都在對數(shù)時間內(nèi)完成。

B樹與AVL樹不同，可以擁有2個以上的子節(jié)點，并且每個節(jié)點可以有多個鍵值，這些屬性減少了定位記錄時所經(jīng)歷的中間過程，加快了存取速度。B樹更適用于讀寫相對較大的數(shù)據(jù)塊存儲系統(tǒng)，如磁盤。這種數(shù)據(jù)結(jié)構(gòu)常被應(yīng)用在數(shù)據(jù)庫和文件系統(tǒng)的實現(xiàn)上。

對于一個M階B樹具有以下特性：

• 每個節(jié)點最多有 M 個子節(jié)點；每個內(nèi)部節(jié)點最少有 ?M/2? 個子節(jié)點（?x?為向上取整符號）；如果根節(jié)點不是葉子節(jié)點，那么它至少有兩個子節(jié)點。
• 具有 N 個子節(jié)點的非葉子節(jié)點擁有 N-1 個鍵。
• 所有葉子節(jié)點必須處于同一層上。

注：如下圖是一棵5階B樹的兩種畫法，最準確的畫法應(yīng)該為圖中左B樹。但為了方便，通常會將節(jié)點中鍵為空的位置省去不畫，如圖中右B樹。不能因為右圖中最多的鍵為3，就判斷這是一棵4階B樹，B樹的階是預(yù)先定義好的。

B樹的兩種畫法

4. B樹的操作

在對B樹進行操作時，可能會違反B樹的特性，如最小子節(jié)點數(shù)、每個節(jié)點最小鍵數(shù)。為了維護B樹的這些特性，樹可能會分裂或合并。

下面我們會以一棵5階B樹來講述其搜索、插入、刪除操作。先來看下5階B樹的特性：

• 內(nèi)部節(jié)點至少有3個子節(jié)點（?5/2? = 3），最多有5個子節(jié)點
• 每個節(jié)點至少有2個鍵（3-1=2），最多有4個鍵

4.1 搜索

B樹的搜索和二叉搜索樹類似，從根節(jié)點開始，從上往下遞歸的遍歷樹。在每一層節(jié)點上，使用二分查找法匹配目標鍵，或者通過鍵的范圍來確定子樹。

4.2 插入

對于新元素的插入，都是發(fā)生在葉子節(jié)點上的。所有的插入操作都是從根節(jié)點開始，搜索這棵樹，并找到該元素應(yīng)該被插入的節(jié)點。將新元素插入到該節(jié)點需要如下步驟：

• 如果該節(jié)點上的元素數(shù)未滿，則將新元素插入到該節(jié)點，并保持節(jié)點中元素的順序。
• 如果該節(jié)點上的元素已滿，則需要將該節(jié)點平均地分裂成兩個節(jié)點：
  • 從該節(jié)點中的元素和新元素先出一個中位數(shù)
  • 小于中位數(shù)的元素放到左邊節(jié)點，大于中位數(shù)的元素放到右邊節(jié)點，中位數(shù)做為分隔值。
  • 分隔值被插入到父節(jié)點中（增加了樹的高度），這可能會導(dǎo)致父節(jié)點的分裂，分裂父節(jié)點時又可能會使它的父節(jié)點分裂，以此類推。如果分裂一直上升到根節(jié)點，那么就創(chuàng)建一個新的根節(jié)點，它有一個分隔值和兩個子節(jié)點。（這就是根節(jié)點并不像內(nèi)部節(jié)點一樣有最少子節(jié)點數(shù)量限制的原因）

下圖是一個5階B樹，我們通過順序插入1到17，來觀察節(jié)點的分裂過程。

B樹的插入

4.3 刪除

B樹的刪除就復(fù)雜了許多，可分為下面幾種情況：

• 刪除葉子節(jié)點中的元素
  （1）搜索要刪除的元素
  （2）如果它在葉子節(jié)點上，直接將其刪除
  （3）如果刪除后產(chǎn)生了下溢出（鍵數(shù)小于最小值），則向其兄弟節(jié)點借元素。即將其父節(jié)點元素下移至當(dāng)前節(jié)點，將兄弟節(jié)點中元素上移至父節(jié)點（若是左節(jié)點，上移最大元素；若是右節(jié)點，上移最小元素）
  （4）若兄弟節(jié)點也達到下限，則合并兄弟節(jié)點與分割鍵。

• 刪除內(nèi)部節(jié)點中的元素
  （1）內(nèi)部節(jié)點中元素為其左右子節(jié)點的分割值，需要從左子節(jié)點最大元素或右子節(jié)點最小元素中選出一個新的分割符。被選中的分割符從原子節(jié)點中移除，作為新的分隔值替換掉被刪除的元素。
  （2）上一步中，若左右子節(jié)點元素數(shù)均達到下限，則合并左右子節(jié)點。
  （3）若刪除元素后，其中節(jié)點元素數(shù)小于下限，則繼續(xù)合并。

下圖是一個5階B樹，我們通過刪除15、14、17、5四個鍵，來觀察刪除過程（基本涵蓋所有情況）。

B樹的刪除

5. 代碼實現(xiàn)

本代碼實現(xiàn)了B樹的搜索、插入、刪除操作，下面看詳細介紹。

5.1 鍵值類

該類用于存放B樹每個節(jié)點中的鍵值數(shù)據(jù)。

• key：節(jié)點中的鍵，用于指向數(shù)據(jù)記錄。
• value：鍵向指向的數(shù)據(jù)記錄。

由于鍵在節(jié)點中是順序存儲的，所以實現(xiàn)了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 節(jié)點類

節(jié)點類是B樹中的每個節(jié)點，其主要包括：

• entrys：為該節(jié)點中所有的鍵，使用List類型存儲
• childNodes：為該節(jié)點所有的子節(jié)點，使用List類型存儲
• parentNode：為該節(jié)點的父節(jié)點。

由于childNodes需要排序，所以該類也實現(xiàn)了Comparable接口。

需要明白的一點是，當(dāng)前節(jié)點中每個鍵的左右子節(jié)點都可以通過List集合的下標進行確定。比如：
entrys[0]的左右子節(jié)點分別為childNodes[0]、childNodes[1]；
entrys[1]的左右子節(jié)點分別為childNodes[1]、childNodes[2]，以此類推。

class Node implements Comparable<Node> {

    private final List<Entry> entrys; // 當(dāng)前節(jié)點的鍵值對
    private final List<Node> childNodes; // 子節(jié)點，使用數(shù)組存儲子節(jié)點
    private Node parentNode; // 父節(jié)點

    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樹類實現(xiàn)比較復(fù)雜，其主要屬性包括：

• m：為B樹的階
• min：為B樹中元素最小值，通過階計算出
• root：樹的根節(jié)點

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樹的搜索實現(xiàn)較為簡單，在BTree類中添加下面兩個方法。

其二分查找法是通過Collections類中的binarySearch方法實現(xiàn)，感興趣的話，可以研究下源碼。后面會專門講解二分查找法，這里就不多說了。

    // 搜索
    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樹的插入實現(xiàn)起來也不難，在BTree類中添加下面三個方法。

重要是split分離方法，如果添加一個元素后，其節(jié)點中元素值超過限定值，則進行分離操作，詳細看代碼。

    // 添加元素
    public void add(Entry entry) {
        // root為空，直接創(chuàng)建
        if (root == null) {
            Node node = new Node();
            node.add(entry);
            root = node;
            return;
        }
        add(root, entry);
    }

    // 添加元素 - 遞歸
    private void add(Node node, Entry entry) {

        // 當(dāng)前節(jié)點為葉子節(jié)點
        if (node.getChildNodes().size() == 0) {

            // 如果當(dāng)前節(jié)點元素未滿，直接添加元素
            if (node.getEntrys().size() < m - 1) {
                node.add(entry);
                return;
            }
            // 如果當(dāng)前節(jié)點元素已滿，則分裂當(dāng)前節(jié)點
            node.getEntrys().add(entry);
            split(node);
            return;
        }

        // 當(dāng)前節(jié)點為內(nèi)部節(jié)點，繼續(xù)往下調(diào)用（新插入的節(jié)點，只能是葉子節(jié)點）
        // 使用二分查找法找到要插入的分支
        int index = Collections.binarySearch(node.getEntrys(), entry);
        if (index < 0) {
            add(node.getChildNodes().get(-index - 1), entry);
        }
    }

    // 分離當(dāng)前節(jié)點
    private void split(Node node) {
        int mid = node.getEntrys().size() / 2;
        // 分隔值
        Entry separateEntry = node.getEntrys().get(mid);
        // 分離后的左節(jié)點
        Node leftNode = new Node();
        leftNode.getEntrys().addAll(node.getEntrys().subList(0, mid));
        // 分離后的右節(jié)點
        Node rightNode = new Node();
        rightNode.getEntrys().addAll(node.getEntrys().subList(mid + 1, node.getEntrys().size()));
        // 分離子節(jié)點
        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);
        }

        // 當(dāng)前節(jié)點為根節(jié)點
        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);
            // 若其父節(jié)點溢出，繼續(xù)分裂
            if (node.parentNode.getEntrys().size() > m - 1) {
                split(node.parentNode);
            }
        }
    }

5.6 刪除

B樹的刪除是最麻煩的，出現(xiàn)的情況太多了。
刪除的節(jié)點主要為內(nèi)部節(jié)點和葉子節(jié)點，每刪除后都要判斷當(dāng)前節(jié)點中元素數(shù)是超出下限值。若超出下限值，需要根據(jù)情況進行判斷。

若刪除的是葉子節(jié)點，可能的操作時左旋轉(zhuǎn)、右旋轉(zhuǎn)、合并（當(dāng)前節(jié)點、兄弟節(jié)點、中間值進行合并）。合并后又會出現(xiàn)其父節(jié)點超出下限值......

若刪除的是內(nèi)部節(jié)點，可能的操作時，合并左右兄弟節(jié)點、合并左右兄弟節(jié)點與中間值、向兄弟節(jié)點借元素。同樣合并后也會出現(xiàn)其父節(jié)點超出下限......

public void remove(int key) {
        // 先查詢出當(dāng)前元素所在節(jié)點
        Node node = searchNode(key);
        if (node == null) {
            return;
        }

        // 刪除節(jié)點
        int keyIndex = Collections.binarySearch(node.getEntrys(), new Entry(key, null));
        node.getEntrys().remove(keyIndex);
        // 若當(dāng)前節(jié)點的鍵數(shù)小于限定值，刪除進行刪除后處理
        if (node.getEntrys().size() < min) {
            afterDeletingHandler(node, keyIndex);
        }


    }

    /**
         * 刪除后處理：當(dāng)前節(jié)點元素數(shù)小于限定值，則根據(jù)不同場景選擇進行合并、左旋轉(zhuǎn)、右旋轉(zhuǎn)
         *
         * @param node
         */
    private void afterDeletingHandler(Node node, int deletedKeyIndex) {

        // 該節(jié)點為內(nèi)部節(jié)點
        if (node.getChildNodes().size() > 0) {
            // 獲取刪除元素的左右子節(jié)點
            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);

            // 先向左右子節(jié)點借
            if (maxSize <= min) {
                // 若左右子節(jié)點達到限定值，則合并左右子節(jié)點
                merge(leftChideNode, rightChildNode);
                return;
            }
            // 向左子節(jié)點借
            Entry entry;
            if (maxSize == leftEntrysSize) {
                entry = leftChideNode.getEntrys().get(leftChideNode.getEntrys().size() - 1);
                leftChideNode.getEntrys().remove(entry);
            } else {
                // 向右子節(jié)點借
                entry = rightChildNode.getEntrys().get(0);
                rightChildNode.getEntrys().remove(entry);
            }
            node.add(entry);
            return;
        }

        // 該節(jié)點為葉子節(jié)點
        Node parentNode = node.parentNode;
        // 當(dāng)前節(jié)點在父節(jié)點中的下標值
        int nodeIndex = parentNode.getChildNodes().indexOf(node);
        // 左兄弟節(jié)點
        Node leftNode = nodeIndex > 0 ? parentNode.getChildNodes().get(nodeIndex - 1) : null;
        // 右兄弟節(jié)點
        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);

        // 左右兄弟節(jié)點元素數(shù)均達到限定值，合并
        if (maxSize <= min) {
            if (leftNode != null) {
                // 與左兄弟節(jié)點合并
                merge(node, leftNode, nodeIndex - 1);
            } else if (rightNode != null) {
                // 與右兄弟節(jié)點合并
                merge(node, rightNode, nodeIndex);
            }
            return;
        }

        if (maxSize == leftEntrysSize) {
            // 向左節(jié)點借--> 右旋轉(zhuǎn)
            rightRotate(node, nodeIndex, leftNode);
        } else {
            // 向右節(jié)點借--> 左旋轉(zhuǎn)
            leftRotate(node, nodeIndex, rightNode);
        }
    }

    /**
         * 將當(dāng)前節(jié)點與兄弟節(jié)點、中間值合并
         *
         * @param node             當(dāng)前節(jié)點
         * @param brotherNode      兄弟節(jié)點
         * @param parentEntryIndex 中間值
         */
    private void merge(Node node, Node brotherNode, int parentEntryIndex) {
        // 創(chuàng)建新的節(jié)點
        Node parentNode = node.getParentNode();
        Node newNode = new Node();
        newNode.getEntrys().addAll(node.getEntrys());
        newNode.getEntrys().addAll(brotherNode.getEntrys());
        newNode.add(parentNode.getEntrys().get(parentEntryIndex));
        // 刪除原節(jié)點及關(guān)系
        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);
            }
        }
        // 若原節(jié)點為根節(jié)點，則當(dāng)前節(jié)點為新的根節(jié)點
        if (parentNode.getEntrys().size() == 0) {
            root = newNode;
            return;
        } else {
            parentNode.addChild(newNode);
            newNode.setParentNode(parentNode);
        }


        // 合并后，若父節(jié)點的元素小于限定值，則再次合并（原則上是與最少元素數(shù)節(jié)點合并）
        if (parentNode.getEntrys().size() < min) {
            Node grandfatherNode = parentNode.getParentNode();
            if (grandfatherNode == null) {
                return;
            }
            int nodeIndex = Collections.binarySearch(grandfatherNode.getChildNodes(), parentNode);
            // 左兄弟節(jié)點
            Node leftNode = nodeIndex > 0 ? grandfatherNode.getChildNodes().get(nodeIndex - 1) : null;
            // 右兄弟節(jié)點
            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);
            }
        }

    }

    /**
         * 合并兩個兄弟節(jié)點
         *
         * @param node        當(dāng)前節(jié)點
         * @param brotherNode 兄弟節(jié)點
         */
    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);
    }

    /**
         * 左旋轉(zhuǎn)
         * （1）將父節(jié)點的中間值元素刪除，并添加到當(dāng)前節(jié)點中
         * （2）將右兄弟節(jié)點中最小元素刪除，并添加到父節(jié)點中
         *
         * @param node      當(dāng)前節(jié)點
         * @param nodeIndex 中間值索引
         * @param rightNode 右節(jié)點
         */
    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);
    }

    /**
         * 右旋轉(zhuǎn)
         * （1）將父節(jié)點的中間值元素刪除，并添加到當(dāng)前節(jié)點中
         * （2）將左兄弟節(jié)點中最大元素刪除，并添加到父節(jié)點中
         *
         * @param node      當(dāng)前節(jié)點
         * @param nodeIndex 中間值索引
         * @param leftNode  左節(jié)點
         */
    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