計算機的發(fā)展速度很快，CPU捺弦、內存饮寞、顯卡等已不再是計算機性能的瓶頸，SSD硬盤的出現(xiàn)也使得硬盤讀寫速度有了質的飛躍列吼，但和內存相比依然有極大的差距幽崩，這就意味著我們在內存環(huán)境下設計的算法，在涉及到硬盤讀寫時效率會極大地降低寞钥。比如紅黑樹慌申、AVL樹等，因為其每個結點只能存儲一個數(shù)據凑耻，且每個結點最多有兩個子結點太示，這意味著當數(shù)據很多時柠贤，樹的高度會非常大香浩，也就意味著要頻繁地進行IO操作。即使是普通的樹臼勉，每個結點可以有多個孩子邻吭，那它要么度非常大，要么高度特別大宴霸，也可能兩者都特別大囱晴，也無法擺脫頻繁IO操作帶來的性能瓶頸。今天要研究的B樹和B⁺樹就是這種頻繁IO操作場景的解決辦法瓢谢。

B樹

定義

我們首先要知道多路查找樹的概念畸写，它的定義如下：

多路查找樹（multi-way search tree），其每一個結點的孩子數(shù)可以多于兩個氓扛，且每一個結點處可以存儲多個元素枯芬。

和普通的樹相比，多路查找樹一個節(jié)點不再是只能存儲一個元素采郎，這打破了我們對樹的理解千所，但是正是這個特性，使得它能夠出色地解決IO問題蒜埋。我們要研究的B樹就是一棵多路查找樹淫痰，它的定義如下：

B樹是一種平衡的多路查找樹，結點最大的孩子數(shù)目稱為B樹的階（Order）整份。

一個m階的B樹具有如下屬性：

• 如果根結點不是葉結點待错，則其至少有兩棵子樹籽孙。
• 每一個非根的分支結點都有k-1個元素和k個孩子，其中[m/2]≤ k ≤ m火俄。每一個葉子結點 n 都有k-1個元素蚯撩，其中[m/2]≤ k ≤ m。
• 所有葉子結點都位于同一層次烛占。
• 所有分支結點包含下列信息數(shù)據( n, A₀, K₁, A₁, K₂, A₂, …, K_n, A_n )胎挎，其中: K_i( i=1, 2, …, n ) 為關鍵字，且K_i<K_i+1( i=1, 2, …, n-1 ); A_i ( i=0, 2, …, n) 為指向子樹根結點的指針忆家，且指針A_i-1所指子樹中所有結點的關鍵字均小于K_i( i=1, 2, …, n ) 犹菇，A_n 所指子樹中所有結點的關鍵字均大于K_n，n ( [m/2]-1 ≤ n ≤ m-1 ) 為關鍵字的個數(shù)(或 n+1 為子樹的個數(shù))芽卿。

這段定義一定讓人感到費解吧揭芍，那我們就從B樹的一個特例：2-3樹作為切入點，來看看一個B樹是如何構建和操作的卸例。

2-3樹是這樣的一棵多路查找樹：其中的每一個結點都具有兩個孩子（稱為2結點）或三個孩子（稱為3結點）称杨。

它擁有如下屬性：

• 一個2結點包含一個元素和兩個孩子（或沒有孩子），和二叉排序樹一致筷转，左子樹包含的元素小于該元素姑原，右子樹包含的元素大于該元素。但是這個2結點要么有兩個孩子呜舒，要么沒有孩子锭汛，不能只有一個孩子。
• 一個3結點包含兩個元素和三個孩子（或沒有孩子）袭蝗，左子樹唤殴、較小元素、中間子樹到腥、較大元素和右子樹也按照從小到大排序朵逝。一個3結點要么有三個孩子，要么沒有孩子乡范。
• 2-3樹的所有葉子結點都在同一層次上配名。

按照這個描述，一棵正確的2-3樹大概長這個樣子：

2-3樹

插入

下面我們通過構造一棵2-3樹來演示它的增刪過程篓足，假定初始數(shù)據為：{1, 7, 4, 9, 15, 13, 6, 5, 8, 10, 3, 12, 14, 2, 11}《翁埽現(xiàn)在樹為空，要把1插入進去只需要構建一個2結點即可栈拖，如下所示：

插入1

接下來插入元素7连舍，只要把當前結點升級為3結點即可，如下所示：

插入7

接下來插入4，可以發(fā)現(xiàn)根結點已經是3結點了索赏，因為必須是平衡的盼玄，所以只能把根結點拆開，變?yōu)?個2結點潜腻，如下所示：

插入4

插入9時埃儿，因為9比4大，所以插入到右側融涣，而7所在結點可以升級為3結點童番，所以插入結果如下所示：

插入9

接下來要插入15，因為9所在結點已經是3結點威鹿，但是它的父結點4是2結點剃斧，所以可以把4所在結點升級，因為3結點必須有三個孩子忽你，所以7和9所在結點需要拆分幼东，如下所示：

插入15

接下來插入13和6時，對應節(jié)點都可以升級科雳，所以插入結果如下：

插入13和6

接下來插入元素5時根蟹，發(fā)現(xiàn)6所在結點已經是3結點，而父結點糟秘，也就是根結點也是3結點了简逮，這時只能再次拆分。首先蚌堵，5买决、6沛婴、7中間的數(shù)是6吼畏，我們把它提出來，它應該位于4和9中間嘁灯，如下所示：

插入5步驟1

因為3結點只能有兩個元素泻蚊，所以根結點也必須拆分，結果如下：

插入5步驟2

可以發(fā)現(xiàn)丑婿，根結點拆分后使得樹的高度增加了性雄。接下來插入8，10羹奉，3也是重復步驟秒旋，結果如下：

插入

至此，再插入元素12诀拭、14迁筛、2時也變得十分簡單了，結果如下：

插入

最后插入11耕挨，可以發(fā)現(xiàn)它在10和12之間细卧，而父結點也是3結點尉桩，所以10和12要拆分，9和13也要拆分贪庙，11應該和6一起升級為3結點蜘犁，結果如下：

插入11

刪除

現(xiàn)在，我們已經建立了一棵2-3樹止邮，我們按照插入順序这橙，再演示刪除的過程。首先刪除元素1导披，因為1是2結點析恋，刪除后會影響平衡，但是我們發(fā)現(xiàn)它的父結點是一個3結點盛卡，所以可以把父結點拆開助隧，2和3合并成一個3結點，結果如下：

刪除1

現(xiàn)在滑沧，要刪除7并村，因為7是葉節(jié)點也是3結點，直接刪除就可以滓技，結果如下：

刪除7

刪除結點4哩牍，因為它的左孩子是3結點，只要把它拆開就可以了令漂，結果如下：

刪除4

刪除9時比較復雜膝昆，因為它的左右孩子都是2結點，首先把它的兩個孩子合并為3結點并代替它叠必，結果如下：

刪除9步驟1

此時樹是不平衡的荚孵，此時發(fā)現(xiàn)左側3和6可以合并為3結點，結果如下：

刪除9步驟2

接下來刪除15纬朝，直接刪除即可收叶，結果如下：

刪除15

刪除13也比較復雜，首先需要把它的兩個孩子合并共苛，然后以11為根結點判没，做類似右旋的操作，具體做法是6的右孩子成為11的左孩子隅茎，然后6成為11的父結點澄峰，這和AVL樹等的右旋操作是一致的，結果如下：

刪除13

接下來要刪除的元素6是根結點辟犀，做法是先找到它的前驅（第一個比它小的元素）5代替它俏竞，此時2、3結點需要合并，合并后左右子樹不再平衡胞此，所以還需要5和11合并臣咖，結果如下：

刪除6

其余的刪除操作其實和前面的都類似，這里不再演示了漱牵，感興趣的可以自己試一試夺蛇，很快就可以發(fā)現(xiàn)規(guī)律。

總結

這里介紹的2-3樹是B樹的一個特例酣胀，B樹就是把2-3樹的階擴展到了m刁赦，它的每個結點特性和2-3樹一致，除葉結點外每個結點的指針域和數(shù)據域都必須填充闻镶。那么B樹是如何解決IO訪問問題的呢甚脉？假設我們有一棵階為1001的B樹，也就是每個結點可以存儲1000個數(shù)據和1001個指針铆农，那么在高度為2的層上牺氨，可以存儲的數(shù)據是1001X1000個，而它的指針數(shù)量為1001X1001個墩剖，這些指針可以指向的數(shù)據為1001X1001X1000個猴凹，大概有10億條數(shù)據。這意味著岭皂，只要我們把根結點保存在內存中郊霎，訪問這10億條數(shù)據最多需要兩次IO操作，這是其他結構無法比擬的爷绘。

那么B樹的問題在哪里呢书劝？在實際使用時，通常階數(shù)是和磁盤頁面大小匹配的土至，也就是每次都會讀取一頁的數(shù)據购对，因為磁盤在頁面內連續(xù)讀取速度非常快毙籽，但在頁間就相對慢些洞斯。這是它的優(yōu)點，也恰恰是它的問題所在坑赡。假設每個結點都在不同的頁面，我們要對它進行中序遍歷么抗，其經過大概如下：

遍歷

其中序遍歷為頁面2->頁面1->頁面3->頁面1->頁面4毅否。可以發(fā)現(xiàn)位于頁面1的結點會被多次訪問蝇刀，且位于該結點的元素也會被多次遍歷螟加，這樣一來效率會變得很低，所以B樹對遍歷是不友好的。接下來介紹的B⁺樹就是對此問題的優(yōu)化捆探。

B⁺樹

遍歷的需求主要來源于“掃庫”然爆，比如網站大量充斥著各種列表，如果使用B樹遍歷黍图，效率實在太低了曾雕。B⁺樹在B樹的基礎上做了改進，在B⁺樹中助被，出現(xiàn)在分支結點中的元素會被當作它們在該分支結點位置的中序后繼者（葉子結點）中再次列出剖张，且每一個葉子結點都會保存一個指向后一葉子結點的指針。如下就是一棵B⁺樹：

B+樹示例

為了簡化揩环，葉子結點的左右兩側指針域省略搔弄。它的特點就是任何非葉子結點都會在葉結點上再次出現(xiàn)一次，并且所有葉子結點從左到右鏈接了起來丰滑」擞蹋總體來說，它也具備B樹的特性褒墨，只是在兩個方面有所區(qū)別蹦渣。第一就是查找元素時，即使在非葉子結點找到了目標值貌亭，它也只是用來索引的柬唯，還需要繼續(xù)找到它在葉子結點的位置。第二就是如果要遍歷圃庭，只需要遍歷一次葉子結點即可锄奢。B⁺樹的結構也十分適合范圍查找，只需要找到范圍的最小值所在位置剧腻，然后沿鏈表遍歷即可拘央。

B樹與B⁺樹對比

B樹與B⁺樹都是對磁盤友好的數(shù)據結構，能大幅降低磁盤訪問次數(shù)书在。B樹的優(yōu)點在于數(shù)據存儲在每個結點中灰伟，可以更快訪問到，而不必須走到葉子結點儒旬，B樹更多的用在文件系統(tǒng)中栏账。B⁺樹的每個非葉子結點都只充當索引，所以查詢必須到葉子結點結束栈源，但它十分適合“掃庫”和區(qū)間查找挡爵，而且因為大多結點只用于索引，所以并不會存儲真正的數(shù)據甚垦，在內存上會更緊湊茶鹃，相同的內存就可以存放更多的索引數(shù)據了涣雕。比如字典的拼音和漢字是分離的，只需要幾十頁就能得到完整的拼音表闭翩，但是如果拼音和漢字摻雜在一起挣郭，要得到完整的索引（拼音）表就需要整個字典。B⁺樹的這些特性使得它更適合用來做數(shù)據庫的索引疗韵。

我是飛機醬兑障，如果您喜歡我的文章，可以關注我~

編程之路伶棒，道阻且長旺垒。唯，路漫漫其修遠兮肤无，吾將上下而求索先蒋。