淺談多路查找樹（B樹）

文章目錄

1、序言

2、2-3樹

2.1、2-3樹的插入

2.2 2-3樹的刪除

3、B樹

4、B樹的典型應(yīng)用

1、序言

曾今我不知道多叉樹有上面用，所以對于多叉樹并沒有過多的關(guān)注，或者說，基本沒關(guān)注。

直到我了解到了多路查找樹（B樹），我知道，是我淺薄了。

先不說那些高深莫測的內(nèi)容，我們就通俗的聊聊。

我們現(xiàn)在常說大數(shù)據(jù)大數(shù)據(jù)，就算沒說過也聽過不少了。但是我們的系統(tǒng)的內(nèi)存就那么大，而外部硬盤卻可以達(dá)到成千上百個(gè)G。

我們之前聊的數(shù)據(jù)結(jié)構(gòu)，都是基于內(nèi)存的，因此考慮的是內(nèi)存中的運(yùn)算時(shí)間復(fù)雜度。但是如果我們操作的數(shù)據(jù)集非常大，大到內(nèi)存已經(jīng)無法處理了，這也是很正常的現(xiàn)象，比方說某個(gè)程序要從文件系統(tǒng)中取一個(gè)文件出來，這個(gè)時(shí)間復(fù)雜度就會(huì)發(fā)生變化了。

試想一下，要在一個(gè)擁有幾十萬個(gè)文件的文件系統(tǒng)中查找一個(gè)文件，你所設(shè)計(jì)的算法需要讀取磁盤上千次還是幾十次，這是有本質(zhì)上的差異的，后者可能是幾秒，前者可能就要幾分鐘了，你能忍？找個(gè)文件都要等幾分鐘！！！

2、2-3樹

這是一個(gè)簡單的多路查找樹，學(xué)新東西嘛，自然從最簡單的開始。什么是多路查找樹？和二叉樹做個(gè)比較可能會(huì)比較直觀：二叉樹，你可以叫它二路查找樹。明白了吧。

那么2-3樹是一顆怎樣的樹？長這樣：

1、其中每一個(gè)節(jié)點(diǎn)都有兩個(gè)孩子（稱為2節(jié)點(diǎn)）或三個(gè)孩子（三節(jié)點(diǎn)）或者沒有。

2、子節(jié)點(diǎn)排序參考二叉樹

3、一個(gè)二節(jié)點(diǎn)包含一個(gè)元素和兩個(gè)子節(jié)點(diǎn)（或沒有子節(jié)點(diǎn)），一個(gè)三節(jié)點(diǎn)包含兩個(gè)元素和三個(gè)子節(jié)點(diǎn)（或沒有子節(jié)點(diǎn)）

4、2-3樹中所有的葉子節(jié)點(diǎn)都在同一層次上。

這個(gè)比較開始復(fù)雜了，不過咱就隨便聊聊，聊到哪兒算哪兒。

首先，要明白每個(gè)新插入的節(jié)點(diǎn)都是二節(jié)點(diǎn)。

插入情景1：

插入空樹，直接插入，完事兒。

插入情景2：

插入到一個(gè)二節(jié)點(diǎn)的葉子上，這也沒什么，就像上面最左葉子節(jié)點(diǎn)，在“1"旁邊給新節(jié)點(diǎn)“3”留個(gè)位置就好了。

插入情景3：

插入到一個(gè)三節(jié)點(diǎn)的葉子上，這就很尷尬了，2-3樹的節(jié)點(diǎn)極限就是3，比方說上面要插個(gè)5進(jìn)去。

那怎么弄？

先看一下，要插入節(jié)點(diǎn)的父節(jié)點(diǎn)是個(gè)二節(jié)點(diǎn)，那就好辦了，把那個(gè)二節(jié)點(diǎn)變成三節(jié)點(diǎn)，自然就有地方插入了。怎么變？把“6”提上去啊，圖自己畫。

如果要插入節(jié)點(diǎn)的父節(jié)點(diǎn)是個(gè)三節(jié)點(diǎn)，那就比較尷尬一點(diǎn)。比方說我現(xiàn)在要插個(gè)“11”進(jìn)去。

那怎么弄？

那就一直往上找，找到二節(jié)點(diǎn)為止，然后該怎么做上面已經(jīng)講了。

還是剛剛最后一種場景，如果往上找，找到根節(jié)點(diǎn)都是三節(jié)點(diǎn)，那怎么辦？

那就意味著當(dāng)前=層次已經(jīng)無法滿足我們的需要了，從根開始，全拆成二節(jié)點(diǎn)吧。

也不要去鉆牛角尖了，咱就隨便聊聊，要鉆牛角尖咱往后去把代碼實(shí)現(xiàn)寫一下。現(xiàn)在知道是這么回事兒就好。

刪除其實(shí)就是增加的逆過程，如果增加看懂了，刪除就很簡單。

以下場景針對刪除節(jié)點(diǎn)為葉子節(jié)點(diǎn)：

刪除場景1：要?jiǎng)h除的節(jié)點(diǎn)位于一個(gè)三節(jié)點(diǎn)上，直接刪了。

刪除場景2：刪除根節(jié)點(diǎn)，也是直接刪了吧。

刪除場景3：刪除的節(jié)點(diǎn)位于一個(gè)二節(jié)點(diǎn)上。就像插入節(jié)點(diǎn)在三節(jié)點(diǎn)上一樣的尷尬。不，更尷尬。

刪除場景3.1：該節(jié)點(diǎn)的父節(jié)點(diǎn)為三節(jié)點(diǎn)：將父節(jié)點(diǎn)拆開下放一個(gè)節(jié)點(diǎn)。

刪除場景3.2：上面場景不存在，但是 該節(jié)點(diǎn)的兄弟節(jié)點(diǎn)是三節(jié)點(diǎn)，將它的兄弟節(jié)點(diǎn)拆開，然后做單旋轉(zhuǎn)。

其他的刪除場景嘛，日后深入研究的時(shí)候再行探討，過于復(fù)雜。

3、B樹

B樹是一種平衡的多路查找樹。

節(jié)點(diǎn)最大的孩子的數(shù)量的樹叫做m階B數(shù)。

所以2-3樹就是3階B樹，二叉樹就是2階B樹。

B樹有如下性質(zhì)：

如果根節(jié)點(diǎn)不是葉節(jié)點(diǎn)，那么B樹至少有兩叉。

所有葉子節(jié)點(diǎn)都位于同一層次。

每一個(gè)非根的分支結(jié)點(diǎn)都有k-1個(gè)元素和k個(gè)孩子，其中[m/2]

在B樹上的查找過程是一個(gè)順指針查找節(jié)點(diǎn)和在節(jié)點(diǎn)中查找關(guān)鍵字的交叉過程。

關(guān)于B樹的插入刪除，和2-3樹一樣，只不過階數(shù)可能會(huì)大了些。

4、B樹的典型應(yīng)用

我們的外存，比如硬盤，是將所有的信息分割成相等大小的頁面，每次硬盤讀寫的都是一個(gè)或多個(gè)完整的頁面，對于一個(gè)硬盤來說，-頁的長度可能是 211到214個(gè)字節(jié)。

在一個(gè)典型的B樹應(yīng)用中，要處理的硬盤數(shù)據(jù)量很大，因此無法一次全部裝入內(nèi)存。因此我們會(huì)對 B樹進(jìn)行調(diào)整， 使得B樹的階數(shù) (或結(jié)點(diǎn)的元素)與硬盤存儲(chǔ)的頁面大小相匹配。比如說一棵B樹的階為1001 (即1個(gè)結(jié)點(diǎn)包含1000個(gè)關(guān)鍵字)，高度為2,它可以儲(chǔ)存超過10億個(gè)關(guān)鍵字，我們只要讓根結(jié)點(diǎn)持久地保留在內(nèi)存中，那么在這棵樹上，尋找某一個(gè)關(guān)鍵字至多需要兩次硬盤的讀取即可。

B樹查找的時(shí)間復(fù)雜度：O(log n).

下次再深挖的時(shí)候我一定帶上B+樹的！！！

大數(shù)據(jù) 數(shù)據(jù)結(jié)構(gòu)

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。