目錄

一、基本介紹

二、重要概念

非葉節(jié)點(diǎn)

葉節(jié)點(diǎn)

三、階數(shù)

四、基本操作

等值查詢(query)

范圍查詢(rangeQuery)

更新(update)

插入(insert)

刪除(remove)

五、知識(shí)小結(jié)

---

一、基本介紹

B+樹(shù)是一種樹(shù)數(shù)據(jù)結(jié)構(gòu)，通常用于數(shù)據(jù)庫(kù)和操作系統(tǒng)的文件系統(tǒng)中。

B+樹(shù)的特點(diǎn)是能夠保持?jǐn)?shù)據(jù)穩(wěn)定有序，其插入與修改擁有較穩(wěn)定的對(duì)數(shù)時(shí)間復(fù)雜度。

B+樹(shù)被用于MySQL數(shù)據(jù)庫(kù)的索引結(jié)構(gòu)。這里為了便于大家理解，我基于內(nèi)存（因?yàn)閿?shù)據(jù)量的原

因，實(shí)際上的B+樹(shù)應(yīng)該基于磁盤(pán)等外存，基于內(nèi)存的比較適合作為Demo，同時(shí)還可以作為一種多

路搜索樹(shù)）實(shí)現(xiàn)了B+樹(shù)的增刪查改操作（包括節(jié)點(diǎn)分裂和節(jié)點(diǎn)合并）

二、重要概念

B+ 樹(shù)是一種樹(shù)數(shù)據(jù)結(jié)構(gòu)(一個(gè)n叉樹(shù))，這里我們首先介紹B+樹(shù)最重要的概念：B+樹(shù)節(jié)點(diǎn)。

一棵B+樹(shù)的節(jié)點(diǎn)包含非葉節(jié)點(diǎn)和葉子節(jié)點(diǎn)兩類

非葉節(jié)點(diǎn)

如上圖所示，非葉節(jié)點(diǎn)包含兩部分信息

• Entry: 索引鍵，用于索引數(shù)據(jù)，它必須是可比較的，在查找時(shí)其實(shí)也是根據(jù)Entry的有序性來(lái)加快查找速度（原理和二分查找類似，通過(guò)有序性來(lái)剪枝搜索空間，所以是對(duì)數(shù)級(jí)的實(shí)際復(fù)雜度）
• Child: 指向其孩子節(jié)點(diǎn)的指針，可以通過(guò)它訪問(wèn)到該非葉節(jié)點(diǎn)的子節(jié)點(diǎn)

對(duì)于非葉節(jié)點(diǎn)來(lái)說(shuō)，Child孩子指針的數(shù)量總是等于Entry的數(shù)量加1，也就是說(shuō)一個(gè)非葉節(jié)點(diǎn)如果

有3個(gè)Entry的話，那么就可以得到它有 3+1=4 個(gè)孩子（子節(jié)點(diǎn)）。

葉節(jié)點(diǎn)

如上圖所示，葉節(jié)點(diǎn)包含三部分信息：

• Entry: 與非葉節(jié)點(diǎn)中的Entry一致，用于索引數(shù)據(jù)
• Data指針: 用于指向具體數(shù)據(jù)的指針（從這里可以發(fā)現(xiàn)，非葉節(jié)點(diǎn)的指針只能找到它的孩子的地址，而真正的數(shù)據(jù)的地址只能通過(guò)葉節(jié)點(diǎn)找到，即可以理解為所有數(shù)據(jù)都存儲(chǔ)在葉節(jié)點(diǎn)上）
• Next指針: 用于指向該葉節(jié)點(diǎn)的后面一個(gè)葉子節(jié)點(diǎn)，最后一個(gè)葉子節(jié)點(diǎn)的Next指針為空（Next指針存在的意義是加快范圍查詢）。

對(duì)于葉節(jié)點(diǎn)來(lái)說(shuō)，Data數(shù)據(jù)指針的數(shù)量總是等于Entry的數(shù)量，也就是說(shuō)一個(gè)葉節(jié)點(diǎn)如果有3個(gè)

Entry的話，那么就可以得到它索引了3個(gè)數(shù)據(jù)項(xiàng)，這里與非葉節(jié)點(diǎn)不同的原因是葉節(jié)點(diǎn)分出了一個(gè)

指針去指向了下一個(gè)葉節(jié)點(diǎn)，所以其實(shí)無(wú)論是非葉節(jié)點(diǎn)還是葉節(jié)點(diǎn)，他們Entry數(shù)量和指針數(shù)量的

關(guān)系都是：指針數(shù)量等于Entry數(shù)量加1。

為了使邏輯更加清晰，后面我在介紹”B+樹(shù)的操作“時(shí)將會(huì)按非葉節(jié)點(diǎn)和葉節(jié)點(diǎn)分別進(jìn)行討論。

三、階數(shù)

一棵B+樹(shù)通常用 m 來(lái)描述它的階數(shù)，它的作用是描述一個(gè)B+樹(shù)節(jié)點(diǎn)中Entry數(shù)量的上限和下限。

在大多數(shù)對(duì)于B+樹(shù)的介紹了，一般描述一個(gè)m階的B樹(shù)具有如下幾個(gè)特征

1. 根結(jié)點(diǎn)至少有兩個(gè)子女。
2. 每個(gè)中間節(jié)點(diǎn)都至少包含ceil(m / 2)個(gè)孩子，最多有m個(gè)孩子。
3. 每一個(gè)葉子節(jié)點(diǎn)都包含k-1個(gè)元素，其中 m/2 <= k <= m。
4. 所有的葉子結(jié)點(diǎn)都位于同一層。
5. 每個(gè)節(jié)點(diǎn)中的元素從小到大排列，節(jié)點(diǎn)當(dāng)中k-1個(gè)元素正好是k個(gè)孩子包含的元素的值域分劃

上面的特征可能看起來(lái)會(huì)比較復(fù)雜，所以這里用我自己的一個(gè)更簡(jiǎn)單的理解來(lái)解釋一下。

我們?cè)O(shè)一個(gè)B+樹(shù)節(jié)點(diǎn)的Entry數(shù)量上限為Key_Bound，簡(jiǎn)寫(xiě)為K,則 K = m - 1。得到K之后，獲取

Entry數(shù)量的下限也變得很簡(jiǎn)單，就是 K / 2 （整型除法，下取整）

根據(jù)我們上面對(duì)B+樹(shù)節(jié)點(diǎn)的介紹，我們可以根據(jù)K得到很輕松地得到節(jié)點(diǎn)中對(duì)應(yīng)指針的數(shù)量: K +

1。

用代碼表示如下：

public BPlusTree(int order) {this.KEY_UPPER_BOUND = order - 1; //Entry 上限this.UNDERFLOW_BOUND = KEY_UPPER_BOUND / 2; //Entry 下限
}

這樣我們拿到了B+樹(shù)中Entry的上限、下限及對(duì)應(yīng)的指針數(shù)量之后，后面我們就可以不必再理會(huì)那

個(gè)計(jì)算更復(fù)雜的m了。

在實(shí)際的應(yīng)用中，B+樹(shù)的階數(shù)其實(shí)越大越好，因?yàn)楫?dāng)B+樹(shù)的階數(shù)越大，B+樹(shù)一個(gè)節(jié)點(diǎn)所能容納的

Entry就會(huì)越多，B+樹(shù)就會(huì)變得更”矮“，而更”矮“意味著更少的磁盤(pán)I/O，所以一般情況下B+樹(shù)的階

數(shù)跟磁盤(pán)塊的大小有關(guān)。

四、基本操作

等值查詢(query)

B+樹(shù)的等值查詢指：找到B+樹(shù)葉節(jié)點(diǎn)Entry與查詢Entry完全相等所對(duì)應(yīng)的數(shù)據(jù)，等值查詢的過(guò)程

主要是依賴于Entry的有序性：設(shè)B+樹(shù)某個(gè)節(jié)點(diǎn)的Entry e 是第index個(gè)Entry，則該節(jié)點(diǎn)的第index

個(gè)孩子中的所有Entry都是小于e的，該節(jié)點(diǎn)的第index+1個(gè)孩子中的所有Entry都是大于等于e的。

所以我們可以根據(jù)這個(gè)有序性，自頂向下逐層查找，最終找到匹配的葉子節(jié)點(diǎn)然后獲取到數(shù)據(jù)。

對(duì)于非葉節(jié)點(diǎn)，只需要找到第一個(gè)大于查詢Entry的子節(jié)點(diǎn)，即 upper bound（如果所有子節(jié)點(diǎn)都

小于等于查詢Entry，則 uppber bound 為子節(jié)點(diǎn)的數(shù)量），然后如此遞歸地讓這個(gè)子節(jié)點(diǎn)進(jìn)行查找

即可。

其中最關(guān)鍵的就是找到第一個(gè)大于查詢Entry的子節(jié)點(diǎn) upper bound，因?yàn)椴樵僂ntry只可能出現(xiàn)在

upper bound 的前一個(gè)位置。由于B+樹(shù)Entry的有序性，在這里我們可以使用二分搜索實(shí)現(xiàn)這一

點(diǎn)，因?yàn)槎炙阉鞯男史浅８?#xff08;O(logN)級(jí)別），代碼實(shí)現(xiàn)如下：

        protected int entryIndexUpperBound(K entry) {int l = 0;int r = entries.size();while (l < r) {int mid = l + ((r - l) >> 1);if (entries.get(mid).compareTo(entry) <= 0) {l = mid + 1;} else {r = mid;}}return l;}

找到這個(gè)子節(jié)點(diǎn)之后，讓它繼續(xù)查找即可：

        @Overridepublic List<E> query(K entry) {return children.get(findChildIndex(findEntryIndex(entry), entry)).query(entry);}

對(duì)于葉節(jié)點(diǎn)，就需要找到與查詢Entry完全相等的Entry:

        @Overridepublic List<E> query(K entry) {int entryIndex = getEqualEntryIndex(entry);return entryIndex == -1 ? Collections.emptyList() : new ArrayList<>(data.get(entryIndex));}

如果沒(méi)有與查詢Entry相等的Entry，則返回空集，否則返回對(duì)應(yīng)的數(shù)據(jù)。

同樣地，在找與查詢Entry相等的Entry，為了提高效率我們也可以使用二分搜索：

        private int getEqualEntryIndex(K entry) {int l = 0;int r = entries.size() - 1;while (l <= r) {int mid = l + ((r - l) >> 1);int compare = entries.get(mid).compareTo(entry);if (compare == 0) {return mid;} else if (compare > 0) {r = mid - 1;} else {l = mid + 1;}}return -1;}

下面是B+樹(shù)等值查詢的一個(gè)例子：

bPlusTree.insert(0, "data record 1");
bPlusTree.insert(0, "data record 2");
bPlusTree.insert(1, "data record 3");
bPlusTree.insert(2, "data record 4");
bPlusTree.insert(3, "data record 5");//query all data records under the entry 0
List<String> queryResult = bPlusTree.query(0);
System.out.println(queryResult); //[data record 2, data record 1]

范圍查詢(rangeQuery)

B+樹(shù)的范圍查詢指：給定查詢上限Entry K1，查詢下限Entry K2, 找到B+樹(shù)葉節(jié)點(diǎn)Entry滿足在

[K1, k2) 范圍內(nèi)。

對(duì)于非葉節(jié)點(diǎn)來(lái)說(shuō)，查詢過(guò)程與等值查詢過(guò)程完全一致：

        @Overridepublic List<E> rangeQuery(K startInclude, K endExclude) {return               children.get(findChildIndex(findEntryIndex(startInclude),startInclude)).rangeQuery(startInclude, endExclude);}

對(duì)于葉節(jié)點(diǎn)來(lái)說(shuō)，將等值查找改為范圍查找即可：

        @Overridepublic List<E> rangeQuery(K startInclude, K endExclude) {List<E> res = new ArrayList<>();int start = findEntryIndex(startInclude);int end = findEntryIndex(endExclude);for (int i = start; i < end; ++i) {res.addAll(data.get(i));}BPlusTreeLeafNode nextLeafNode = next;while (nextLeafNode != null) {for (int i = 0; i < nextLeafNode.entries.size(); ++i) {if (nextLeafNode.entries.get(i).compareTo(endExclude) < 0) {res.addAll(nextLeafNode.data.get(i));} else {return res;}}nextLeafNode = nextLeafNode.next;}return res;}

在進(jìn)行范圍查詢時(shí)，我們利用next指針直接獲取到了下一個(gè)葉子節(jié)點(diǎn)，

而不是從根節(jié)點(diǎn)從上到下又搜索一遍，以此提高了范圍查找的效率。

下面是B+樹(shù)范圍查詢的一個(gè)例子：

//query all data records under the entries [0,3)
List<String> queryResult = bPlusTree.rangeQuery(0, 3);
System.out.println(queryResult); //[data record 2, data record 1, data record 3, data record 4]

更新(update)

B+樹(shù)的更新操作比較簡(jiǎn)單，即通過(guò)查詢找到對(duì)應(yīng)的數(shù)據(jù)之后將舊值更新為新值即可。

非葉節(jié)點(diǎn)的更新操作過(guò)程：

        @Overridepublic boolean update(K entry, E oldValue, E newValue) {return children.get(findChildIndex(findEntryIndex(entry), entry)).update(entry, oldValue, newValue);}

葉節(jié)點(diǎn)的更新操作過(guò)程：

        @Overridepublic boolean update(K entry, E oldValue, E newValue) {int entryIndex = getEqualEntryIndex(entry);if (entryIndex == -1 || !data.get(entryIndex).contains(oldValue)) {return false;}data.get(entryIndex).remove(oldValue);data.get(entryIndex).add(newValue);return true;}

插入(insert)

B+樹(shù)的插入操作相對(duì)于查詢操作和更新操作來(lái)說(shuō)，會(huì)比較復(fù)雜，因?yàn)楫?dāng)插入的數(shù)據(jù)而對(duì)應(yīng)新增的

Entry讓B+樹(shù)節(jié)點(diǎn)容納不下時(shí)（即發(fā)生上溢），會(huì)觸發(fā)分裂操作，而分裂操作則會(huì)導(dǎo)致生成新的

B+樹(shù)節(jié)點(diǎn)，這就需要操作對(duì)應(yīng)的父節(jié)點(diǎn)的孩子指針，以滿足父節(jié)點(diǎn)Entry和孩子指針的有序性，同

時(shí)如果這個(gè)新增的節(jié)點(diǎn)會(huì)導(dǎo)致這個(gè)父節(jié)點(diǎn)也上溢的話就需要遞歸地進(jìn)行分裂操作。

為了實(shí)現(xiàn)這一點(diǎn)，最簡(jiǎn)單的方法是每個(gè)B+樹(shù)節(jié)點(diǎn)都維護(hù)一個(gè)父指針指向它的父親，這樣當(dāng)分裂出

新的節(jié)點(diǎn)時(shí)就可以通過(guò)這個(gè)父指針獲取對(duì)應(yīng)的父節(jié)點(diǎn)，獲取到之后就可以對(duì)這個(gè)父節(jié)點(diǎn)的孩子指針

進(jìn)行相應(yīng)的操作了。

這個(gè)方法雖然簡(jiǎn)單，但是在空間上會(huì)有一點(diǎn)額外的損耗，比如在32位機(jī)器上，一個(gè)指針的大小是4

字節(jié)，假如一棵B+樹(shù)有N個(gè)節(jié)點(diǎn)，那么因?yàn)榫S護(hù)整個(gè)父指針就會(huì)額外損耗 4 * N 字節(jié)的空間。

那么有沒(méi)有什么辦法既可以不需要父指針，又可以完成這個(gè)分裂操作呢？答案是利用返回值，當(dāng)子

節(jié)點(diǎn)分裂出新的節(jié)點(diǎn)時(shí)，可以將這個(gè)節(jié)點(diǎn)返回，因?yàn)椴迦氩僮饕彩亲皂斚蛳掳磳舆M(jìn)行的，所以對(duì)應(yīng)

的父節(jié)點(diǎn)可以通過(guò)返回值拿到這個(gè)新增的節(jié)點(diǎn)，然后再進(jìn)行對(duì)應(yīng)的孩子指針的操作就可以了。

而如果在插入的時(shí)候沒(méi)有觸發(fā)分裂操作，這個(gè)時(shí)候我們只需要返回 null 即可，這樣也相當(dāng)于告訴了

父節(jié)點(diǎn)，下面沒(méi)有發(fā)生分裂，所以父節(jié)點(diǎn)就自然不可能再觸發(fā)分裂操作了。

由于數(shù)據(jù)是要插入在葉節(jié)點(diǎn)里面的，所以最開(kāi)始一定是葉節(jié)點(diǎn)開(kāi)始分裂，分裂出新的節(jié)點(diǎn)之后再向

上傳遞，所以我們先從葉節(jié)點(diǎn)的分裂操作開(kāi)始介紹：

        protected boolean isFull() {return entries.size() == KEY_UPPER_BOUND;}@Overridepublic BPlusTreeNode insert(K entry, E value) {int equalEntryIndex = getEqualEntryIndex(entry);if (equalEntryIndex != -1) {data.get(equalEntryIndex).add(value);return null;}int index = findEntryIndex(entry);if (isFull()) {BPlusTreeLeafNode newLeafNode = split();int medianIndex = getMedianIndex();if (index < medianIndex) {entries.add(index, entry);data.add(index, asSet(value));} else {int rightIndex = index - medianIndex;newLeafNode.entries.add(rightIndex, entry);newLeafNode.data.add(rightIndex, asSet(value));}return newLeafNode;}entries.add(index, entry);data.add(index, asSet(value));return null;}

首先，我們先判斷如果之前的葉節(jié)點(diǎn)就有這個(gè)Entry，那么我們直接將數(shù)據(jù)插入這個(gè)Entry對(duì)應(yīng)的數(shù)

據(jù)集里面就可以了，同時(shí)由于Entry數(shù)量沒(méi)有發(fā)生變化，所以肯定不會(huì)發(fā)生分裂，直接返回null即

可。

其次，如果沒(méi)有發(fā)生上溢(isFull()返回false)，則我們插入對(duì)應(yīng)的Entry，再添加對(duì)應(yīng)的數(shù)據(jù)即可。

最后，如果發(fā)生了上溢，則我們需要進(jìn)行分裂操作：

        private BPlusTreeLeafNode split() {int medianIndex = getMedianIndex();List<K> allEntries = entries;List<Set<E>> allData = data;this.entries = new ArrayList<>(allEntries.subList(0, medianIndex));this.data = new ArrayList<>(allData.subList(0, medianIndex));List<K> rightEntries = new ArrayList<>(allEntries.subList(medianIndex, allEntries.size()));List<Set<E>> rightData = new ArrayList<>(allData.subList(medianIndex, allData.size()));BPlusTreeLeafNode newLeafNode = new BPlusTreeLeafNode(rightEntries, rightData);newLeafNode.next = this.next;this.next = newLeafNode;return newLeafNode;}

簡(jiǎn)單說(shuō)，分裂就是插入這個(gè)數(shù)據(jù)及其對(duì)應(yīng)的Entry之后，將這個(gè)節(jié)點(diǎn)的Entry和相應(yīng)指針一分為二，

一半繼續(xù)留在這個(gè)節(jié)點(diǎn)，另一半生成一個(gè)新的節(jié)點(diǎn)來(lái)容納它們，同時(shí)更新一下next指針的指向。

葉節(jié)點(diǎn)分裂完之后會(huì)將分裂的信息（如果沒(méi)有分裂則返回null，已經(jīng)分裂了就返回這個(gè)新生成的葉

節(jié)點(diǎn)）

通過(guò)返回值傳遞給父節(jié)點(diǎn)，即非葉節(jié)點(diǎn)，所以下面我們繼續(xù)介紹非葉節(jié)點(diǎn)的插入操作：

        @Overridepublic BPlusTreeNode insert(K entry, E value) {BPlusTreeNode newChildNode = children.get(findChildIndex(findEntryIndex(entry), entry)).insert(entry, value);if (newChildNode != null) {K newEntry = findLeafEntry(newChildNode);int newEntryIndex = findEntryIndex(newEntry);if (isFull()) {BPlusTreeNonLeafNode newNonLeafNode = split();int medianIndex = getMedianIndex();if (newEntryIndex < medianIndex) {entries.add(newEntryIndex, newEntry);children.add(newEntryIndex + 1, newChildNode);} else {int rightIndex = newNonLeafNode.findEntryIndex(newEntry);newNonLeafNode.entries.add(rightIndex, newEntry);newNonLeafNode.children.add(rightIndex, newChildNode);}newNonLeafNode.entries.remove(0);return newNonLeafNode;}entries.add(newEntryIndex, newEntry);children.add(newEntryIndex + 1, newChildNode);}return null;}

由于數(shù)據(jù)是插入在葉節(jié)點(diǎn)中，所以在非葉節(jié)點(diǎn)中我們只需要處理有新的孩子節(jié)點(diǎn)生成的情況，而新

生成的孩子節(jié)點(diǎn)又可以分為兩種情況：

一是加入新生成的孩子節(jié)點(diǎn)之后沒(méi)有發(fā)生上溢，這個(gè)時(shí)候只需要維護(hù)一下Entry和孩子指針，保持

其有序性即可。

二是加入新生成的孩子節(jié)點(diǎn)之后發(fā)生了上溢，這個(gè)時(shí)候跟葉節(jié)點(diǎn)類似，我們需要生成一個(gè)新的非葉

節(jié)點(diǎn)，插入這個(gè)新的子節(jié)點(diǎn)及其對(duì)應(yīng)的Entry之后，將這個(gè)節(jié)點(diǎn)的Entry和相應(yīng)的孩子指針一分為

二，一半繼續(xù)留在這個(gè)節(jié)點(diǎn)，另一半生成一個(gè)新的非葉節(jié)點(diǎn)來(lái)容納它們:

private BPlusTreeNonLeafNode split() {int medianIndex = getMedianIndex();List<K> allEntries = entries;List<BPlusTreeNode> allChildren = children;this.entries = new ArrayList<>(allEntries.subList(0, medianIndex));this.children = new ArrayList<>(allChildren.subList(0, medianIndex + 1));List<K> rightEntries = new ArrayList<>(allEntries.subList(medianIndex, allEntries.size()));List<BPlusTreeNode> rightChildren = new ArrayList<>(allChildren.subList(medianIndex + 1, allChildren.size()));return new BPlusTreeNonLeafNode(rightEntries, rightChildren);}

這里的分裂跟葉節(jié)點(diǎn)的分裂是類似的，不同是非葉節(jié)點(diǎn)的分裂不需要維護(hù)next指針。

刪除(remove)

B+樹(shù)的刪除操作我覺(jué)得可以算是B+樹(shù)中實(shí)現(xiàn)起來(lái)最復(fù)雜的操作，因?yàn)楫?dāng)刪除發(fā)生下溢時(shí)，會(huì)涉及

到向兄弟節(jié)點(diǎn)借數(shù)據(jù)，同時(shí)還會(huì)涉及到合并兩個(gè)相鄰的節(jié)點(diǎn)。

在B+樹(shù)的某些工業(yè)級(jí)實(shí)現(xiàn)中，刪除可能是僅僅通過(guò)增加一個(gè)刪除標(biāo)記來(lái)實(shí)現(xiàn)，因?yàn)榇蠖鄶?shù)數(shù)據(jù)的

變化比較平衡，盡管有時(shí)會(huì)出現(xiàn)下溢的情況，但這個(gè)節(jié)點(diǎn)可能很快就會(huì)增長(zhǎng)以至于不再下溢，而且

這樣還可以節(jié)約空間釋放過(guò)程的成本，提高整個(gè)刪除操作的效率。

但是考慮到本文主要側(cè)重于對(duì)B+樹(shù)的理解，所以這里的刪除操作，我們?nèi)匀皇褂孟蛐值芄?jié)點(diǎn)借數(shù)

據(jù)和合并相鄰節(jié)點(diǎn)的方式來(lái)進(jìn)行處理。

與插入操作類似，我們?cè)谶M(jìn)行刪除后可以將刪除結(jié)果通過(guò)返回值的形式返回給父節(jié)點(diǎn)，父節(jié)點(diǎn)就可

以根據(jù)這個(gè)信息判斷自身會(huì)不會(huì)因此發(fā)生下溢從而進(jìn)行相應(yīng)的操作。

在刪除信息中，我們一般想知道兩點(diǎn)信息：1.是否刪除成功；2.子節(jié)點(diǎn)刪除完成之后是否發(fā)生下

溢。

由于返回時(shí)要返回這兩點(diǎn)信息，所以我們可以封裝一個(gè)刪除結(jié)果類：

    private static class RemoveResult {public boolean isRemoved;public boolean isUnderflow;public RemoveResult(boolean isRemoved, boolean isUnderflow) {this.isRemoved = isRemoved;this.isUnderflow = isUnderflow;}}

如果對(duì)是否刪除成功不敢興趣的話，在刪除中就可以只返回一個(gè)布爾變量，以此向父節(jié)點(diǎn)傳遞該節(jié)點(diǎn)是

否下溢的信息。

同樣的，由于數(shù)據(jù)都是在葉節(jié)點(diǎn)中，所以在刪除數(shù)據(jù)時(shí)，下溢一定最先發(fā)生在葉節(jié)點(diǎn)中，所以我們

先從葉節(jié)點(diǎn)中的刪除操作進(jìn)行介紹。

        protected boolean isUnderflow() {return entries.size() < UNDERFLOW_BOUND;}@Overridepublic RemoveResult remove(K entry) {int entryIndex = getEqualEntryIndex(entry);if (entryIndex == -1) {return new RemoveResult(false, false);}this.entries.remove(entryIndex);this.data.remove(entryIndex);return new RemoveResult(true, isUnderflow());}

首先，如果我們?cè)贐+樹(shù)中沒(méi)有找到要?jiǎng)h除的數(shù)據(jù)，那么我們直接返回即可，由于刪除操作沒(méi)有實(shí)

際發(fā)生，所以肯定也不會(huì)產(chǎn)生下溢。

然后，我們可以發(fā)現(xiàn)，在葉節(jié)點(diǎn)中，刪除數(shù)據(jù)之后，并沒(méi)有真正地去處理下溢，而只是簡(jiǎn)單地將該

節(jié)點(diǎn)目前是否下溢的信息的傳遞給父節(jié)點(diǎn)。

這是因?yàn)楫?dāng)下溢發(fā)生時(shí)，會(huì)涉及到節(jié)點(diǎn)的合并，而節(jié)點(diǎn)的合并會(huì)影響到父節(jié)點(diǎn)的Child指針，同時(shí)

由于父節(jié)點(diǎn)可以通過(guò)Child指針輕松訪問(wèn)到子節(jié)點(diǎn)，而子節(jié)點(diǎn)沒(méi)有可以直接拿到父節(jié)點(diǎn)的方式，所

以綜合這兩點(diǎn)，下溢的處理交給父節(jié)點(diǎn)的比較合適的。

由于葉節(jié)點(diǎn)只可能存在于最后一層，所以任何節(jié)點(diǎn)的父節(jié)點(diǎn)都一定是非葉節(jié)點(diǎn)，下面我們來(lái)介紹非

葉節(jié)點(diǎn)的刪除操作：

        @Overridepublic RemoveResult remove(K entry, E value) {int entryIndex = findEntryIndex(entry);int childIndex = findChildIndex(entryIndex, entry);BPlusTreeNode childNode = children.get(childIndex);RemoveResult removeResult = childNode.remove(entry, value);if (!removeResult.isRemoved) {return removeResult;}if (removeResult.isUnderflow) {this.handleUnderflow(childNode, childIndex, entryIndex);}return new RemoveResult(true, isUnderflow());}

非葉節(jié)點(diǎn)的整體處理邏輯比較簡(jiǎn)單，當(dāng)沒(méi)有刪除成功時(shí)，我們直接將刪除失敗的結(jié)果向上傳遞即

可。

如果刪除成功，則我們需要判斷子節(jié)點(diǎn)是否發(fā)生下溢，如果發(fā)生下溢，則需要處理這個(gè)下溢，下面

是下溢的處理過(guò)程：

        private void handleUnderflow(BPlusTreeNode childNode, int childIndex, int entryIndex) {BPlusTreeNode neighbor;if (childIndex > 0 && (neighbor = this.children.get(childIndex - 1)).entries.size() > UNDERFLOW_BOUND) {//如果左邊的鄰居可以借childNode.borrow(neighbor, this.entries.get(reviseEntryIndex(entryIndex)), true);this.entries.set(reviseEntryIndex(entryIndex), childNode.getClass().equals(BPlusTreeNonLeafNode.class) ? findLeafEntry(childNode) : childNode.entries.get(0));} else if (childIndex < this.children.size() - 1 && (neighbor = this.children.get(childIndex + 1)).entries.size() > UNDERFLOW_BOUND) {//如果右邊的鄰居可以借childNode.borrow(neighbor, this.entries.get(entryIndex), false);this.entries.set(entryIndex, childNode.getClass().equals(BPlusTreeNonLeafNode.class) ? findLeafEntry(neighbor) : neighbor.entries.get(0));} else {//左右鄰居都借不了就只能合并相鄰節(jié)點(diǎn)了if (childIndex > 0) {// combine current child to left childneighbor = this.children.get(childIndex - 1);neighbor.combine(childNode, this.entries.get(reviseEntryIndex(entryIndex)));this.children.remove(childIndex);} else {// combine right child to current childneighbor = this.children.get(childIndex + 1);childNode.combine(neighbor, this.entries.get(entryIndex));this.children.remove(childIndex + 1);}this.entries.remove(reviseEntryIndex(entryIndex));}}

下溢的處理的大體流程也比較簡(jiǎn)單，首先先嘗試向左鄰居借，左鄰居不能借就向右鄰居借，如果右

鄰居不能借就意味著已經(jīng)沒(méi)有鄰居可以借給它了，所以這個(gè)時(shí)候就只能進(jìn)行合并了。

合并時(shí)有一個(gè)小細(xì)節(jié)需要注意，就是如果這個(gè)節(jié)點(diǎn)是第一個(gè)節(jié)點(diǎn)，那么就只能把這個(gè)節(jié)點(diǎn)的右鄰居

合并過(guò)來(lái)（因?yàn)樗鼪](méi)有左鄰居），否則我們就可以將左鄰居合并過(guò)來(lái)

（對(duì)于最后一個(gè)節(jié)點(diǎn)也如此）。

下面我們看看具體的借數(shù)據(jù)以及合并是如何實(shí)現(xiàn)的，首頁(yè)是葉節(jié)點(diǎn)：

        @Overridepublic void borrow(BPlusTreeNode neighbor, K parentEntry, boolean isLeft) {BPlusTreeLeafNode leafNode = (BPlusTreeLeafNode) neighbor;int borrowIndex;if (isLeft) {borrowIndex = leafNode.entries.size() - 1;this.entries.add(0, leafNode.entries.get(borrowIndex));this.data.add(0, leafNode.data.get(borrowIndex));} else {borrowIndex = 0;this.entries.add(leafNode.entries.get(borrowIndex));this.data.add(leafNode.data.get(borrowIndex));}leafNode.entries.remove(borrowIndex);leafNode.data.remove(borrowIndex);}@Overridepublic void combine(BPlusTreeNode neighbor, K parentEntry) {BPlusTreeLeafNode leafNode = (BPlusTreeLeafNode) neighbor;this.entries.addAll(leafNode.entries);this.data.addAll(leafNode.data);this.next = leafNode.next;}

借數(shù)據(jù)的話我們只需要判斷這個(gè)數(shù)據(jù)是從左鄰居借來(lái)的還是從右鄰居借來(lái)的，如果是從左鄰居借來(lái)

的，根據(jù)Entry的有序性，我們需要把左鄰居的最后一個(gè)Entry接出來(lái)作為當(dāng)前節(jié)點(diǎn)的第一個(gè)Entry，

而從右鄰居借來(lái)的剛好相反，需要把右鄰居的第一個(gè)Entry借出來(lái)作為當(dāng)前節(jié)點(diǎn)的最后一個(gè)Entry

（因?yàn)镋ntry都是從左到右依次增大的）。

葉節(jié)點(diǎn)的合并也比較簡(jiǎn)單，就是把鄰居的Entry和數(shù)據(jù)都添加過(guò)來(lái)然后再維護(hù)一下next指針即可，

不過(guò)需要注意的是合并時(shí)仍然需要保持有序性，所以如果是合并左鄰居，那么就需要用左鄰居來(lái)調(diào)

用combine方法，否則如果合并的是右鄰居，那么就需要當(dāng)前節(jié)點(diǎn)來(lái)調(diào)用combine方法。

下面我們來(lái)看非葉節(jié)點(diǎn)的借數(shù)據(jù)和合并是如何實(shí)現(xiàn)的：

        @Overridepublic void borrow(BPlusTreeNode neighbor, K parentEntry, boolean isLeft) {BPlusTreeNonLeafNode nonLeafNode = (BPlusTreeNonLeafNode) neighbor;if (isLeft) {this.entries.add(0, parentEntry);this.children.add(0, nonLeafNode.children.get(nonLeafNode.children.size() - 1));nonLeafNode.children.remove(nonLeafNode.children.size() - 1);nonLeafNode.entries.remove(nonLeafNode.entries.size() - 1);} else {this.entries.add(parentEntry);this.children.add(nonLeafNode.children.get(0));nonLeafNode.entries.remove(0);nonLeafNode.children.remove(0);}}@Overridepublic void combine(BPlusTreeNode neighbor, K parentEntry) {BPlusTreeNonLeafNode nonLeafNode = (BPlusTreeNonLeafNode) neighbor;this.entries.add(parentEntry);this.entries.addAll(nonLeafNode.entries);this.children.addAll(nonLeafNode.children);}

與葉節(jié)點(diǎn)不同，非葉節(jié)點(diǎn)的借數(shù)據(jù)和合并操作都會(huì)涉及到一個(gè)父節(jié)點(diǎn)的Entry，因?yàn)樵诜侨~節(jié)點(diǎn)

中，Entry是從左邊的節(jié)點(diǎn)到 父Entry 再到右邊的節(jié)點(diǎn)依次增大的，如下圖所示的兩層非葉節(jié)點(diǎn)，

Entry的順序是從左節(jié)點(diǎn)的13 到父Entry的23 再到右節(jié)點(diǎn)的31、43依次增大。

如果我們直接把鄰居的Entry借過(guò)來(lái)的話，則會(huì)破壞Entry的有序性，比如直接把第二個(gè)節(jié)點(diǎn)的31借

過(guò)來(lái)，就變成了13 31 23，破壞了有序性（即23的第一個(gè)孩子指針指向的節(jié)點(diǎn)包含了比當(dāng)前Entry

更大的Entry，這是與B+樹(shù)特征相違背的）。

所以為了依然能夠保證Entry的有序性，在非葉節(jié)點(diǎn)進(jìn)行借數(shù)據(jù)操作時(shí)：

如果是向左鄰居借，則我們應(yīng)該先把父Entry借過(guò)來(lái)作為當(dāng)前節(jié)點(diǎn)的第一個(gè)Entry，然后把左鄰居的

最后一個(gè)Entry借過(guò)來(lái)填補(bǔ)父Entry的位置；

如果是向右鄰居借，則我們應(yīng)該先把父Entry借過(guò)來(lái)作為當(dāng)前節(jié)點(diǎn)的最后一個(gè)Entry，然后把左鄰居

的第一個(gè)Entry借過(guò)來(lái)填補(bǔ)父Entry的位置。

同樣的道理，在非葉節(jié)點(diǎn)進(jìn)行合并操作時(shí)，為了保證有序性，我們依然要先加入父節(jié)點(diǎn)，然后再添

加鄰居的數(shù)據(jù)。

至此，B+樹(shù)的增刪查改四種操作就都介紹完了。

五、知識(shí)小結(jié)

本篇B+樹(shù)的實(shí)現(xiàn)在存儲(chǔ)上是直接基于內(nèi)存的，不涉及到磁盤(pán)I/O，如果要改成基于外存的也并不

難，做一下葉節(jié)點(diǎn)和非葉節(jié)點(diǎn)的序列化，然后映射到磁盤(pán)上即可。相對(duì)于真實(shí)的基于外存的

B+樹(shù)，基于內(nèi)存的實(shí)現(xiàn)可以更簡(jiǎn)潔地表示出B+樹(shù)的核心概念和方法，同時(shí)基于內(nèi)存的B+樹(shù)也可以

作為二叉搜索樹(shù)的一種擴(kuò)展，即多路搜索樹(shù)。