多路查找樹：和之前學習的二叉樹不同的是，多路樹的每一個節點的孩子數可以多于兩個！同時每個孩子節點可以存儲多個元素。

多路查找樹有4種特殊形式：2-3樹、2-3-4樹、B樹、B+樹

2-3樹

?

????????每個節點都具有2個孩子（稱之為2節點）或者3個孩子（稱之為3節點）。

????????一個2節點包含一個元素和兩個孩子（或沒有孩子）。

????????一個3節點包含兩個元素和三個孩子（或沒有孩子）。

?

插入操作

• 和二叉搜索樹一樣！插入操作一定是發生在葉子上的；
• 插入分三種情況：
• 空樹，插入一個２結點元素即可；
• 插入結點到一個２結點的葉子上，直接將這個２結點升級為３結點（注意結點元素的順序）；

• 要往３結點中插入一個新元素，破壞２－３樹規則，因此需要拆分

刪除操作

明確一點，插入操作都是發生在葉子節點上！但是刪除操作可以發生在非葉子節點上！

1）所刪元素位于一個3節點的葉子節點上，直接刪除，不會影響樹結構。?

2）所刪元素位于一個2節點上，直接刪除，破壞樹結構。?

分為四種情況：

此節點雙親也是2節點，且擁有一個3節點的右孩子；?

此節點的雙親是2節點，它右孩子也是2節點；?

此節點的雙親是3節點；?

當前樹是一個滿二叉樹，降低樹高；?

3）所刪元素位于非葉子的分支節點。此時按樹中序遍歷得到此元素的前驅或后續元素，補位。

分支節點是2節點?

分支節點是3節點?

?

2-3-4樹：對于2-3樹的擴展

????????每個節點都具有2個孩子（稱之為2節點）或者3個孩子（稱之為3節點）或者4個孩子（稱之為4節點）。

????????一個2節點包含一個元素和兩個孩子（或沒有孩子）。

????????一個3節點包含兩個元素和三個孩子（或沒有孩子）。

????????一個4節點包含三個元素和四個孩子（或沒有孩子）。
?

---

B樹? ? 是一個平衡的多路樹！

2-3樹是3階B樹，2-3-4樹是4階B樹

維基百科對B樹的定義為“在計算機科學中，B樹（B-tree）是一種樹狀數據結構，它能夠存儲數據、對其進行排序并允許以O(log n)的時間復雜度運行進行查找、順序讀取、插入和刪除的數據結構。B樹，概括來說是一個節點可以擁有多于2個子節點的二叉查找樹。與自平衡二叉查找樹不同，B-樹為系統最優化大塊數據的讀和寫操作。B-tree算法減少定位記錄時所經歷的中間過程，從而加快存取速度。普遍運用在數據庫和文件系統?！?/p>

定義

B 樹可以看作是對2-3查找樹的一種擴展，即他允許每個節點有M-1個子節點。

• 根節點至少有兩個子節點
• 每個節點有M-1個key，并且以升序排列
• 位于M-1和M key的子節點的值位于M-1 和M key對應的Value之間
• 其它節點至少有M/2個子節點

下圖是一個M=4 階的B樹:

可以看到B樹是2-3樹的一種擴展，他允許一個節點有多于2個的元素。

B樹的插入及平衡化操作和2-3樹很相似，這里就不介紹了。下面是往B樹中依次插入

6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4

的演示動畫：

?

?

B+樹是對B樹的一種變形樹，它與B樹的差異在于：

• 有k個子結點的結點必然有k個關鍵碼；
• 非葉結點僅具有索引作用，跟記錄有關的信息均存放在葉結點中。
• 樹的所有葉結點構成一個有序鏈表，可以按照關鍵碼排序的次序遍歷全部記錄。

如下圖，是一個B+樹:

下圖是B+樹的插入動畫：

?

B和B+樹的區別在于，B+樹的非葉子結點只包含導航信息，不包含實際的值，所有的葉子結點和相連的節點使用鏈表相連，便于區間查找和遍歷。

B+ 樹的優點在于：

• 由于B+樹在內部節點上不包含數據信息，因此在內存頁中能夠存放更多的key。 數據存放的更加緊密，具有更好的空間局部性。因此訪問葉子節點上關聯的數據也具有更好的緩存命中率。
• B+樹的葉子結點都是相鏈的，因此對整棵樹的便利只需要一次線性遍歷葉子結點即可。而且由于數據順序排列并且相連，所以便于區間查找和搜索。而B樹則需要進行每一層的遞歸遍歷。相鄰的元素可能在內存中不相鄰，所以緩存命中性沒有B+樹好。

但是B樹也有優點，其優點在于，由于B樹的每一個節點都包含key和value，因此經常訪問的元素可能離根節點更近，因此訪問也更迅速。下面是B 樹和B+樹的區別圖：

分析

對B樹和B+樹的分析和對前面講解的2-3樹的分析類似，

對于一顆節點為N度為M的子樹，查找和插入需要logM-1N ~ logM/2N次比較。這個很好證明，對于度為M的B樹，每一個節點的子節點個數為M/2 到 M-1之間，所以樹的高度在logM-1N至logM/2N之間。

這種效率是很高的，對于N=62*1000000000個節點，如果度為1024，則logM/2N <=4，即在620億個元素中，如果這棵樹的度為1024，則只需要小于4次即可定位到該節點，然后再采用二分查找即可找到要找的值。

B/B+樹性能分析　

·????????n個節點的平衡二叉樹的高度為H(即logn),而n個節點的B/B+樹的高度為logt((n+1)/2)+1;

·????????若要作為內存中的查找表,B樹卻不一定比平衡二叉樹好,尤其當m較大時更是如此.因為查找操作CPU的時間在B-樹上是O(mlogtn)=O(lgn(m/lgt)),而m/lgt>1;所以m較大時O(mlogtn)比平衡二叉樹的操作時間大得多. 因此在內存中使用B樹必須取較小的m.（通常取最小值m=3，此時B-樹中每個內部結點可以有2或3個孩子，這種3階的B-樹稱為2-3樹）。

為什么說B+tree比B樹更適合實際應用中操作系統的文件索引和數據索引.　

·????????B+-tree的內部節點并沒有指向關鍵字具體信息的指針,因此其內部節點相對B樹更小,如果把所有同一內部節點的關鍵字存放在同一盤塊中,那么盤塊所能容納的關鍵字數量也越多,一次性讀入內存的需要查找的關鍵字也就越多,相對IO讀寫次數就降低了.

·????????由于非終結點并不是最終指向文件內容的結點，而只是葉子結點中關鍵字的索引。所以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導致每一個數據的查詢效率一樣。?

ps:我在知乎上看到有人是這樣說的,我感覺說的也挺有道理的:?

他們認為數據庫索引采用B+樹的主要原因是:

B樹在提高了IO性能的同時并沒有解決元素遍歷效率低下的問題,正是為了解決這個問題,B+樹應用而生.B+樹只需要去遍歷葉子節點就可以實現整棵樹的遍歷（線性）.而且在數據庫中基于范圍的查詢（塊狀數據）是非常頻繁的，而B樹不支持這樣的操作（或者說效率太低）.

?

應用

B樹和B+廣泛應用于文件存儲系統以及數據庫系統中，在講解應用之前，我們看一下常見的存儲結構：

我們計算機的主存基本都是隨機訪問存儲器(Random-Access Memory，RAM)，他分為兩類：靜態隨機訪問存儲器（SRAM）和動態隨機訪問存儲器（DRAM）。SRAM比DRAM快，但是也貴的多，一般作為CPU的高速緩存（cache），DRAM通常作為內存。這類存儲器他們的結構和存儲原理比較復雜，基本是使用電信號來保存信息的，不存在機器操作，所以訪問速度非?？?#xff0c;具體的訪問原理可以查看CSAPP，另外，他們是易失的，即如果斷電，保存DRAM和SRAM保存的信息就會丟失。

我們使用的更多的是使用磁盤，磁盤能夠保存大量的數據，從GB一直到TB級，但是 他的讀取速度比較慢，因為涉及到機器操作，讀取速度為毫秒級，從DRAM讀速度比從磁盤度快10萬倍，從SRAM讀速度比從磁盤讀快100萬倍。下面來看下磁盤的結構：

如上圖，磁盤由盤片構成,每個盤片有兩面，又稱為盤面(Surface)，這些盤面覆蓋有磁性材料。盤片中央有一個可以旋轉的主軸(spindle)，他使得盤片以固定的旋轉速率旋轉，通常是5400轉每分鐘(Revolution Per Minute,RPM)或者是7200RPM。磁盤包含一個多多個這樣的盤片并封裝在一個密封的容器內。上圖左，展示了一個典型的磁盤表面結構。每個表面是由一組成為磁道(track)的同心圓組成的，每個磁道被劃分為了一組扇區(sector).每個扇區包含相等數量的數據位，通常是（512）子節。扇區之間由一些間隔(gap)隔開,不存儲數據。

以上是磁盤的物理結構，現在來看下磁盤的讀寫操作：

如上圖，磁盤用讀/寫頭來讀寫存儲在磁性表面的位，而讀寫頭連接到一個傳動臂的一端。通過沿著半徑軸前后移動傳動臂，驅動器可以將讀寫頭定位到任何磁道上，這稱之為尋道操作。一旦定位到磁道后，盤片轉動，磁道上的每個位經過磁頭時，讀寫磁頭就可以感知到位的值，也可以修改值。對磁盤的訪問時間分為?尋道時間，旋轉時間，以及傳送時間。

由于存儲介質的特性，磁盤本身存取就比主存慢很多，再加上機械運動耗費，因此為了提高效率，要盡量減少磁盤I/O，減少讀寫操作。為了達到這個目的，磁盤往往不是嚴格按需讀取，而是每次都會預讀，即使只需要一個字節，磁盤也會從這個位置開始，順序向后讀取一定長度的數據放入內存。這樣做的理論依據是計算機科學中著名的局部性原理：

當一個數據被用到時，其附近的數據也通常會馬上被使用。

程序運行期間所需要的數據通常比較集中。

由于磁盤順序讀取的效率很高（不需要尋道時間，只需很少的旋轉時間），因此對于具有局部性的程序來說，預讀可以提高I/O效率。

預讀的長度一般為頁（page）的整倍數。頁是計算機管理存儲器的邏輯塊，硬件及操作系統往往將主存和磁盤存儲區分割為連續的大小相等的塊，每個存儲塊稱為一頁（在許多操作系統中，頁得大小通常為4k），主存和磁盤以頁為單位交換數據。當程序要讀取的數據不在主存中時，會觸發一個缺頁異常，此時系統會向磁盤發出讀盤信號，磁盤會找到數據的起始位置并向后連續讀取一頁或幾頁載入內存中，然后異常返回，程序繼續運行。

文件系統及數據庫系統的設計者利用了磁盤預讀原理，將一個節點的大小設為等于一個頁，這樣每個節點只需要一次I/O就可以完全載入。為了達到這個目的，在實際實現B-Tree還需要使用如下技巧：

每次新建一個節點的同時，直接申請一個頁的空間( 512或者1024)，這樣就保證一個節點物理上也存儲在一個頁里，加之計算機存儲分配都是按頁對齊的，就實現了一個node只需一次I/O。如，將B樹的度M設置為1024，這樣在前面的例子中，600億個元素中只需要小于4次查找即可定位到某一存儲位置。

同時在B+樹中，內節點只存儲導航用到的key，并不存儲具體值，這樣內節點個數較少，能夠全部讀取到主存中，外接點存儲key及值，并且順序排列，具有良好的空間局部性。所以B及B+樹比較適合與文件系統的數據結構。下面是一顆B樹，用來進行內容存儲。

另外B/B+樹也經常用做數據庫的索引，這方面推薦您直接看張洋的MySQL索引背后的數據結構及算法原理?這篇文章，這篇文章對MySQL中的如何使用B+樹進行索引有比較詳細的介紹，推薦閱讀。

總結

在前面兩篇文章介紹了平衡查找樹中的2-3樹，紅黑樹之后，本文介紹了文件系統和數據庫系統中常用的B/B+ 樹，他通過對每個節點存儲個數的擴展，使得對連續的數據能夠進行較快的定位和訪問，能夠有效減少查找時間，提高存儲的空間局部性從而減少IO操作。他廣泛用于文件系統及數據庫中，如：

• Windows：HPFS文件系統
• Mac：HFS，HFS+文件系統
• Linux：ResiserFS，XFS，Ext3FS，JFS文件系統
• 數據庫：ORACLE，MYSQL，SQLSERVER等中

希望本文對您了解B/B+ 樹有所幫助。

?

總結

以上是生活随笔為你收集整理的B树和B+树的不同的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。