在前面的文章中我們已經(jīng)介紹了B-Tree的一些特性，以及B-Tree的插入及刪除操作。今天我們介紹一下B-Tree的一個(gè)變種 --> B+Tree。B+Tree是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，它廣泛應(yīng)用于文件系統(tǒng)，及數(shù)據(jù)庫索引中。既然它是B-Tree的一個(gè)變種，自然他有很多特性和B-Tree就是一樣的，但它們也有以下兩點(diǎn)不同：

第一：在 B-Tree中一個(gè)含有n個(gè)子樹的節(jié)點(diǎn)有n-1個(gè)關(guān)鍵字(key)。而在 B+Tree中一個(gè)含有n個(gè)子樹的節(jié)點(diǎn)有n個(gè)關(guān)鍵字(key)。為什么在擁有同樣子樹的情況下B+Tree的節(jié)點(diǎn)多需要一個(gè)key呢？那是因?yàn)?B+Tree的節(jié)點(diǎn)會存儲該節(jié)點(diǎn)的子樹中最小的key。

第二：B-Tree的每個(gè)節(jié)點(diǎn)都包含了關(guān)鍵字(key)以及指向包含這些關(guān)鍵字記錄的指針。而 B+Tree在葉子節(jié)點(diǎn)中存儲了所有的關(guān)鍵字信息，以及指向包含這些關(guān)鍵字記錄的指針。而且這些葉子節(jié)點(diǎn)構(gòu)成一個(gè)有序鏈表，即每個(gè)葉子節(jié)點(diǎn)會有一個(gè)指針指向其兄弟節(jié)點(diǎn)。在非葉子節(jié)點(diǎn)中只存儲了關(guān)鍵字信息。下面這張圖畫的非常好，是我從百度圖片搜索而來。相信我們對照這張圖看就非常清楚了。

了解了B-Tree和B+Tree的結(jié)構(gòu)后，我們來看看為什么文件系統(tǒng)和數(shù)據(jù)庫索引大量采用這種數(shù)據(jù)結(jié)構(gòu)。就拿數(shù)據(jù)庫的索引來說，需要?jiǎng)?chuàng)建索引一般數(shù)據(jù)量都較大，那么創(chuàng)建出來的索引文件也會很大，所以索引一般不可能直接存儲在內(nèi)存中，而是存儲在硬盤上(這里我們考慮的是機(jī)械硬盤)。我們都知道硬盤的讀寫速度是遠(yuǎn)遠(yuǎn)趕不上內(nèi)存的，一般都差了幾個(gè)數(shù)量級(機(jī)械硬盤讀寫速度慢主要就是因?yàn)樗枰ㄟ^機(jī)械臂將磁頭移動到數(shù)據(jù)所在的磁道上，要詳細(xì)了解磁盤的原理可以閱讀這篇文章Code-lover's Learning Notes)。而我們根據(jù)索引來查詢就會產(chǎn)生硬盤 I/O，所以要提高查詢的性能就必須降低 I/O 的次數(shù)(就是要減少磁頭移動的次數(shù))。那么B樹相對于其它的數(shù)據(jù)結(jié)構(gòu)如AVL樹，紅黑樹，在降低 I/O 的次數(shù)方面有什么優(yōu)勢呢？很明顯由于B樹的每一個(gè)節(jié)點(diǎn)能存儲多個(gè)關(guān)鍵字信息(實(shí)際應(yīng)用中每個(gè)節(jié)點(diǎn)都能存儲幾百個(gè)關(guān)鍵字信息，當(dāng)然這個(gè)數(shù)字也不會非常大，因?yàn)樗枰ＷC每個(gè)節(jié)點(diǎn)的所有關(guān)鍵字能在一次 I/O中就全部讀取到內(nèi)存中，如果需要多次 I/O 的話，那就反而會降低性能。一次 I/O 讀取的數(shù)據(jù)一般為1頁，而在大多數(shù)操作系統(tǒng)中1也=頁的大小為 4 K，所以每個(gè)節(jié)點(diǎn)存儲的關(guān)鍵字信息的總大小不能超過 4K)而二叉樹每個(gè)節(jié)點(diǎn)只能存儲一個(gè)關(guān)鍵字信息，所以在數(shù)據(jù)量很大的情況下，二叉樹的高度會很大。例如根據(jù)我們前面推導(dǎo)的B樹的一個(gè)公式，N = 1 + s * ((m/2) - 1) = 2 * (

) - 1，一個(gè)200階的高度為4的B樹最少能存儲2百萬個(gè)關(guān)鍵字信息。而同樣存儲2百萬個(gè)關(guān)鍵字信息則需要一顆高度為21的二叉樹。所以在這個(gè)200階的包含2百萬個(gè)關(guān)鍵字信息的B樹中查詢 I/O 的次數(shù)不會超過3次(因?yàn)楦?jié)點(diǎn)是常駐內(nèi)存的)，而同樣存儲2百萬個(gè)關(guān)鍵字信息的二叉樹則可能需要好幾倍次數(shù)的 I/O 性能就會差很多。

在數(shù)據(jù)庫索引的實(shí)現(xiàn)中，大部分采用的是B+Tree而不是B-Tree，這又是為什么呢？

原因有二，其一是由于B+Tree 在非葉子節(jié)點(diǎn)中只存儲了關(guān)鍵字信息，而沒有存儲指向包含這些關(guān)鍵字記錄的指針，所以在樹的高度相同時(shí)，B+Tree往往能比B-Tree存儲更多的關(guān)鍵字信息。更最要的原因是因?yàn)?B+Tree在葉子節(jié)點(diǎn)中存儲了所有的關(guān)鍵字信息，以及指向包含這些關(guān)鍵字記錄的指針。而且這些葉子節(jié)點(diǎn)構(gòu)成一個(gè)有序鏈表，這樣B+Tree在實(shí)現(xiàn)范圍查詢的時(shí)候就比較容易，只需要遍歷這個(gè)有序鏈表就行。而B-tree要實(shí)現(xiàn)范圍查詢則比較困難，但范圍查詢又是數(shù)據(jù)庫中比較常用的功能，所以數(shù)據(jù)庫中大部分采用的是B+Tree而不是B-Tree。當(dāng)然B-Tree也有強(qiáng)于B+tree的地方，例如在隨機(jī)查詢中，由于B-Tree的每個(gè)節(jié)點(diǎn)都包含了關(guān)鍵字(key)以及指向包含這些關(guān)鍵字記錄的指針，所以B-Tree可能中途就查詢到需要的數(shù)據(jù)，不需要遍歷到葉子節(jié)點(diǎn)。而B+Tree由于只在葉子節(jié)點(diǎn)中存儲了所有的關(guān)鍵字信息，以及指向包含這些關(guān)鍵字記錄的指針。在非葉子節(jié)點(diǎn)中只存儲了關(guān)鍵字信息，沒有存儲指向包含這些關(guān)鍵字記錄的指針，所以B+Tree一定要遍歷到葉子節(jié)點(diǎn)才能獲取到包含這些關(guān)鍵字記錄的指針。所以B-Tree的隨機(jī)查詢性能會高于B+Tree。

在B+樹的基礎(chǔ)上又演變出B*樹，B*Tree在非葉子結(jié)點(diǎn)中也增加了指向兄弟節(jié)點(diǎn)的指針，并且它將非葉子節(jié)點(diǎn)上存儲的關(guān)鍵字個(gè)數(shù)的最小值提高到 (2/3) * m，這樣的話就提高了空間利用率。

總結(jié)

以上是生活随笔為你收集整理的b+tree数据结构可视化_数据结构: B+Tree及其应用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。