這篇文章主要介紹“java中B樹的定義及用法”，在日常操作中，相信很多人在java中B樹的定義及用法問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”java中B樹的定義及用法”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！
創(chuàng)新互聯(lián)公司的客戶來自各行各業(yè)，為了共同目標(biāo)，我們在工作上密切配合，從創(chuàng)業(yè)型小企業(yè)到企事業(yè)單位，感謝他們對我們的要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團隊有機會用頭腦與智慧不斷的給客戶帶來驚喜。專業(yè)領(lǐng)域包括網(wǎng)站制作、成都網(wǎng)站制作、電商網(wǎng)站開發(fā)、微信營銷、系統(tǒng)平臺開發(fā)。
計算機的發(fā)展速度很快，CPU、內(nèi)存、顯卡等已不再是計算機性能的瓶頸，SSD硬盤的出現(xiàn)也使得硬盤讀寫速度有了質(zhì)的飛躍，但和內(nèi)存相比依然有極大的差距，這就意味著我們在內(nèi)存環(huán)境下設(shè)計的算法，在涉及到硬盤讀寫時效率會極大地降低。比如紅黑樹、AVL樹等，因為其每個結(jié)點只能存儲一個數(shù)據(jù)，且每個結(jié)點最多有兩個子結(jié)點，這意味著當(dāng)數(shù)據(jù)很多時，樹的高度會非常大，也就意味著要頻繁地進行IO操作。即使是普通的樹，每個結(jié)點可以有多個孩子，那它要么度非常大，要么高度特別大，也可能兩者都特別大，也無法擺脫頻繁IO操作帶來的性能瓶頸。今天要研究的B樹和B+樹就是這種頻繁IO操作場景的解決辦法。
我們首先要知道多路查找樹的概念，它的定義如下：
多路查找樹（multi-way search tree），其每一個結(jié)點的孩子數(shù)可以多于兩個，且每一個結(jié)點處可以存儲多個元素。
和普通的樹相比，多路查找樹一個節(jié)點不再是只能存儲一個元素，這打破了我們對樹的理解，但是正是這個特性，使得它能夠出色地解決IO問題。我們要研究的B樹就是一棵多路查找樹，它的定義如下：
B樹是一種平衡的多路查找樹，結(jié)點最大的孩子數(shù)目稱為B樹的階（Order）。
一個m階的B樹具有如下屬性：
如果根結(jié)點不是葉結(jié)點，則其至少有兩棵子樹。
每一個非根的分支結(jié)點都有k-1個元素和k個孩子，其中[m/2]≤ k ≤ m。每一個葉子結(jié)點 n 都有k-1個元素，其中[m/2]≤ k ≤ m。
所有葉子結(jié)點都位于同一層次。
所有分支結(jié)點包含下列信息數(shù)據(jù)( n, A0, K1, A1, K2, A2, …, Kn, An )，其中: Ki( i=1, 2, …, n ) 為關(guān)鍵字，且Ki < Ki+1( i=1, 2, …, n-1 ); Ai ( i=0, 2, …, n) 為指向子樹根結(jié)點的指針，且指針Ai-1所指子樹中所有結(jié)點的關(guān)鍵字均小于Ki( i=1, 2, …, n ) ，An 所指子樹中所有結(jié)點的關(guān)鍵字均大于Kn，n ( [m/2]-1 ≤ n ≤ m-1 ) 為關(guān)鍵字的個數(shù)(或 n+1 為子樹的個數(shù))。
這段定義一定讓人感到費解吧，那我們就從B樹的一個特例：2-3樹作為切入點，來看看一個B樹是如何構(gòu)建和操作的。
2-3樹是這樣的一棵多路查找樹：其中的每一個結(jié)點都具有兩個孩子（稱為2結(jié)點）或三個孩子（稱為3結(jié)點）。
它擁有如下屬性：
一個2結(jié)點包含一個元素和兩個孩子（或沒有孩子），和二叉排序樹一致，左子樹包含的元素小于該元素，右子樹包含的元素大于該元素。但是這個2結(jié)點要么有兩個孩子，要么沒有孩子，不能只有一個孩子。
一個3結(jié)點包含兩個元素和三個孩子（或沒有孩子），左子樹、較小元素、中間子樹、較大元素和右子樹也按照從小到大排序。一個3結(jié)點要么有三個孩子，要么沒有孩子。
2-3樹的所有葉子結(jié)點都在同一層次上。
按照這個描述，一棵正確的2-3樹大概長這個樣子：
下面我們通過構(gòu)造一棵2-3樹來演示它的增刪過程，假定初始數(shù)據(jù)為：{1, 7, 4, 9, 15, 13, 6, 5, 8, 10, 3, 12, 14, 2, 11}?，F(xiàn)在樹為空，要把1插入進去只需要構(gòu)建一個2結(jié)點即可，如下所示：
接下來插入元素7，只要把當(dāng)前結(jié)點升級為3結(jié)點即可，如下所示：
接下來插入4，可以發(fā)現(xiàn)根結(jié)點已經(jīng)是3結(jié)點了，因為必須是平衡的，所以只能把根結(jié)點拆開，變?yōu)?個2結(jié)點，如下所示：
插入9時，因為9比4大，所以插入到右側(cè)，而7所在結(jié)點可以升級為3結(jié)點，所以插入結(jié)果如下所示：
接下來要插入15，因為9所在結(jié)點已經(jīng)是3結(jié)點，但是它的父結(jié)點4是2結(jié)點，所以可以把4所在結(jié)點升級，因為3結(jié)點必須有三個孩子，所以7和9所在結(jié)點需要拆分，如下所示：
接下來插入13和6時，對應(yīng)節(jié)點都可以升級，所以插入結(jié)果如下：
接下來插入元素5時，發(fā)現(xiàn)6所在結(jié)點已經(jīng)是3結(jié)點，而父結(jié)點，也就是根結(jié)點也是3結(jié)點了，這時只能再次拆分。首先，5、6、7中間的數(shù)是6，我們把它提出來，它應(yīng)該位于4和9中間，如下所示：
因為3結(jié)點只能有兩個元素，所以根結(jié)點也必須拆分，結(jié)果如下：
可以發(fā)現(xiàn)，根結(jié)點拆分后使得樹的高度增加了。接下來插入8，10，3也是重復(fù)步驟，結(jié)果如下：
至此，再插入元素12、14、2時也變得十分簡單了，結(jié)果如下：
最后插入11，可以發(fā)現(xiàn)它在10和12之間，而父結(jié)點也是3結(jié)點，所以10和12要拆分，9和13也要拆分，11應(yīng)該和6一起升級為3結(jié)點，結(jié)果如下：
現(xiàn)在，我們已經(jīng)建立了一棵2-3樹，我們按照插入順序，再演示刪除的過程。首先刪除元素1，因為1是2結(jié)點，刪除后會影響平衡，但是我們發(fā)現(xiàn)它的父結(jié)點是一個3結(jié)點，所以可以把父結(jié)點拆開，2和3合并成一個3結(jié)點，結(jié)果如下：
現(xiàn)在，要刪除7，因為7是葉節(jié)點也是3結(jié)點，直接刪除就可以，結(jié)果如下：
刪除結(jié)點4，因為它的左孩子是3結(jié)點，只要把它拆開就可以了，結(jié)果如下：
刪除9時比較復(fù)雜，因為它的左右孩子都是2結(jié)點，首先把它的兩個孩子合并為3結(jié)點并代替它，結(jié)果如下：
此時樹是不平衡的，此時發(fā)現(xiàn)左側(cè)3和6可以合并為3結(jié)點，結(jié)果如下：
接下來刪除15，直接刪除即可，結(jié)果如下：
刪除13也比較復(fù)雜，首先需要把它的兩個孩子合并，然后以11為根結(jié)點，做類似右旋的操作，具體做法是6的右孩子成為11的左孩子，然后6成為11的父結(jié)點，這和AVL樹等的右旋操作是一致的，結(jié)果如下：
接下來要刪除的元素6是根結(jié)點，做法是先找到它的前驅(qū)（第一個比它小的元素）5代替它，此時2、3結(jié)點需要合并，合并后左右子樹不再平衡，所以還需要5和11合并，結(jié)果如下：
其余的刪除操作其實和前面的都類似，這里不再演示了，感興趣的可以自己試一試，很快就可以發(fā)現(xiàn)規(guī)律。
這里介紹的2-3樹是B樹的一個特例，B樹就是把2-3樹的階擴展到了m，它的每個結(jié)點特性和2-3樹一致，除葉結(jié)點外每個結(jié)點的指針域和數(shù)據(jù)域都必須填充。那么B樹是如何解決IO訪問問題的呢？假設(shè)我們有一棵階為1001的B樹，也就是每個結(jié)點可以存儲1000個數(shù)據(jù)和1001個指針，那么在高度為2的層上，可以存儲的數(shù)據(jù)是1001X1000個，而它的指針數(shù)量為1001X1001個，這些指針可以指向的數(shù)據(jù)為1001X1001X1000個，大概有10億條數(shù)據(jù)。這意味著，只要我們把根結(jié)點保存在內(nèi)存中，訪問這10億條數(shù)據(jù)最多需要兩次IO操作，這是其他結(jié)構(gòu)無法比擬的。
那么B樹的問題在哪里呢？在實際使用時，通常階數(shù)是和磁盤頁面大小匹配的，也就是每次都會讀取一頁的數(shù)據(jù)，因為磁盤在頁面內(nèi)連續(xù)讀取速度非?？?，但在頁間就相對慢些。這是它的優(yōu)點，也恰恰是它的問題所在。假設(shè)每個結(jié)點都在不同的頁面，我們要對它進行中序遍歷，其經(jīng)過大概如下：
其中序遍歷為頁面2->頁面1->頁面3->頁面1->頁面4?？梢园l(fā)現(xiàn)位于頁面1的結(jié)點會被多次訪問，且位于該結(jié)點的元素也會被多次遍歷，這樣一來效率會變得很低，所以B樹對遍歷是不友好的。接下來介紹的B+樹就是對此問題的優(yōu)化。
遍歷的需求主要來源于“掃庫”，比如網(wǎng)站大量充斥著各種列表，如果使用B樹遍歷，效率實在太低了。B+樹在B樹的基礎(chǔ)上做了改進，在B+樹中，出現(xiàn)在分支結(jié)點中的元素會被當(dāng)作它們在該分支結(jié)點位置的中序后繼者（葉子結(jié)點）中再次列出，且每一個葉子結(jié)點都會保存一個指向后一葉子結(jié)點的指針。如下就是一棵B+樹：
為了簡化，葉子結(jié)點的左右兩側(cè)指針域省略。它的特點就是任何非葉子結(jié)點都會在葉結(jié)點上再次出現(xiàn)一次，并且所有葉子結(jié)點從左到右鏈接了起來?？傮w來說，它也具備B樹的特性，只是在兩個方面有所區(qū)別。第一就是查找元素時，即使在非葉子結(jié)點找到了目標(biāo)值，它也只是用來索引的，還需要繼續(xù)找到它在葉子結(jié)點的位置。第二就是如果要遍歷，只需要遍歷一次葉子結(jié)點即可。B+樹的結(jié)構(gòu)也十分適合范圍查找，只需要找到范圍的最小值所在位置，然后沿鏈表遍歷即可。
B樹與B+樹都是對磁盤友好的數(shù)據(jù)結(jié)構(gòu)，能大幅降低磁盤訪問次數(shù)。B樹的優(yōu)點在于數(shù)據(jù)存儲在每個結(jié)點中，可以更快訪問到，而不必須走到葉子結(jié)點，B樹更多的用在文件系統(tǒng)中。B+樹的每個非葉子結(jié)點都只充當(dāng)索引，所以查詢必須到葉子結(jié)點結(jié)束，但它十分適合“掃庫”和區(qū)間查找，而且因為大多結(jié)點只用于索引，所以并不會存儲真正的數(shù)據(jù)，在內(nèi)存上會更緊湊，相同的內(nèi)存就可以存放更多的索引數(shù)據(jù)了。比如字典的拼音和漢字是分離的，只需要幾十頁就能得到完整的拼音表，但是如果拼音和漢字摻雜在一起，要得到完整的索引（拼音）表就需要整個字典。B+樹的這些特性使得它更適合用來做數(shù)據(jù)庫的索引。
到此，關(guān)于“java中B樹的定義及用法”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>
文章名稱：java中B樹的定義及用法
文章地址：http://www.weahome.cn/article/gdjjid.html
重慶分公司
重慶分公司
