java中B樹的定義及用法

這篇文章主要介紹“java中B樹的定義及用法”，在日常操作中，相信很多人在java中B樹的定義及用法問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”java中B樹的定義及用法”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

B樹與B⁺樹

計算機的發展速度很快，CPU、內存、顯卡等已不再是計算機性能的瓶頸，SSD硬盤的出現也使得硬盤讀寫速度有了質的飛躍，但和內存相比依然有極大的差距，這就意味著我們在內存環境下設計的算法，在涉及到硬盤讀寫時效率會極大地降低。比如紅黑樹、AVL樹等，因為其每個結點只能存儲一個數據，且每個結點最多有兩個子結點，這意味著當數據很多時，樹的高度會非常大，也就意味著要頻繁地進行IO操作。即使是普通的樹，每個結點可以有多個孩子，那它要么度非常大，要么高度特別大，也可能兩者都特別大，也無法擺脫頻繁IO操作帶來的性能瓶頸。今天要研究的B樹和B⁺樹就是這種頻繁IO操作場景的解決辦法。

B樹

定義

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

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

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

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

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

• 如果根結點不是葉結點，則其至少有兩棵子樹。

• 每一個非根的分支結點都有k-1個元素和k個孩子，其中[m/2]≤ k ≤ m。每一個葉子結點 n 都有k-1個元素，其中[m/2]≤ k ≤ m。

• 所有葉子結點都位于同一層次。

• 所有分支結點包含下列信息數據( 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 ) 為關鍵字的個數(或 n+1 為子樹的個數)。

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

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

它擁有如下屬性：

• 一個2結點包含一個元素和兩個孩子（或沒有孩子），和二叉排序樹一致，左子樹包含的元素小于該元素，右子樹包含的元素大于該元素。但是這個2結點要么有兩個孩子，要么沒有孩子，不能只有一個孩子。

• 一個3結點包含兩個元素和三個孩子（或沒有孩子），左子樹、較小元素、中間子樹、較大元素和右子樹也按照從小到大排序。一個3結點要么有三個孩子，要么沒有孩子。

• 2-3樹的所有葉子結點都在同一層次上。

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

插入

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

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

接下來插入4，可以發現根結點已經是3結點了，因為必須是平衡的，所以只能把根結點拆開，變為3個2結點，如下所示：

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

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

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

接下來插入元素5時，發現6所在結點已經是3結點，而父結點，也就是根結點也是3結點了，這時只能再次拆分。首先，5、6、7中間的數是6，我們把它提出來，它應該位于4和9中間，如下所示：

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

可以發現，根結點拆分后使得樹的高度增加了。接下來插入8，10，3也是重復步驟，結果如下：

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

最后插入11，可以發現它在10和12之間，而父結點也是3結點，所以10和12要拆分，9和13也要拆分，11應該和6一起升級為3結點，結果如下：

刪除

現在，我們已經建立了一棵2-3樹，我們按照插入順序，再演示刪除的過程。首先刪除元素1，因為1是2結點，刪除后會影響平衡，但是我們發現它的父結點是一個3結點，所以可以把父結點拆開，2和3合并成一個3結點，結果如下：

現在，要刪除7，因為7是葉節點也是3結點，直接刪除就可以，結果如下：

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

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

此時樹是不平衡的，此時發現左側3和6可以合并為3結點，結果如下：

接下來刪除15，直接刪除即可，結果如下：

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

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

其余的刪除操作其實和前面的都類似，這里不再演示了，感興趣的可以自己試一試，很快就可以發現規律。

總結

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

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

其中序遍歷為頁面2->頁面1->頁面3->頁面1->頁面4。可以發現位于頁面1的結點會被多次訪問，且位于該結點的元素也會被多次遍歷，這樣一來效率會變得很低，所以B樹對遍歷是不友好的。接下來介紹的B⁺樹就是對此問題的優化。

B⁺樹

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

為了簡化，葉子結點的左右兩側指針域省略。它的特點就是任何非葉子結點都會在葉結點上再次出現一次，并且所有葉子結點從左到右鏈接了起來。總體來說，它也具備B樹的特性，只是在兩個方面有所區別。第一就是查找元素時，即使在非葉子結點找到了目標值，它也只是用來索引的，還需要繼續找到它在葉子結點的位置。第二就是如果要遍歷，只需要遍歷一次葉子結點即可。B⁺樹的結構也十分適合范圍查找，只需要找到范圍的最小值所在位置，然后沿鏈表遍歷即可。

B樹與B⁺樹對比

B樹與B⁺樹都是對磁盤友好的數據結構，能大幅降低磁盤訪問次數。B樹的優點在于數據存儲在每個結點中，可以更快訪問到，而不必須走到葉子結點，B樹更多的用在文件系統中。B⁺樹的每個非葉子結點都只充當索引，所以查詢必須到葉子結點結束，但它十分適合“掃庫”和區間查找，而且因為大多結點只用于索引，所以并不會存儲真正的數據，在內存上會更緊湊，相同的內存就可以存放更多的索引數據了。比如字典的拼音和漢字是分離的，只需要幾十頁就能得到完整的拼音表，但是如果拼音和漢字摻雜在一起，要得到完整的索引（拼音）表就需要整個字典。B⁺樹的這些特性使得它更適合用來做數據庫的索引。

到此，關于“java中B樹的定義及用法”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！