B-樹(shù)是一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)。和他一起的還有B+樹(shù)。

在這里，需要澄清一下概念。B樹(shù)，B-樹(shù)，B+樹(shù)有什么區(qū)別？他們有什么關(guān)系呢？

其實(shí)，從數(shù)據(jù)結(jié)構(gòu)來(lái)講只有2種，也就是B-樹(shù)和B+樹(shù)。有時(shí)候，B-樹(shù)又稱為B樹(shù)，他們是一個(gè)東西。請(qǐng)注意，B-樹(shù)中間的“-”是連字符，而不是“減號(hào)”。英文中是B-Tree，翻譯成中文后，也就是B樹(shù)，有的翻譯喜歡把連字符“-”也帶著，于是就成了B-樹(shù)，而B(niǎo)-樹(shù)被有些讀者誤讀為B減樹(shù)。

介紹B-樹(shù)之前，首先看一下一個(gè)重要的概念：階。

一個(gè)樹(shù)的階，就是這個(gè)樹(shù)中各個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)的最大值。也就是說(shuō)，如果有的節(jié)點(diǎn)有2個(gè)子節(jié)點(diǎn)，有的節(jié)點(diǎn)有4個(gè)子節(jié)點(diǎn)，最多的有5個(gè)子節(jié)點(diǎn)，那么，這個(gè)樹(shù)的階就是5.

從這個(gè)角度來(lái)講，二叉樹(shù)的階是2.

接下來(lái)，我們介紹一下B-樹(shù)的主要性質(zhì)。我們假定B-樹(shù)的階為m。一個(gè)m階的B-樹(shù)，要么是一個(gè)空樹(shù)，要么是具有如下性質(zhì)的樹(shù)：

1，每個(gè)節(jié)點(diǎn)最多有m個(gè)子節(jié)點(diǎn)。最少有m/2（向上取整）個(gè)節(jié)點(diǎn)?；蛘哌@么表述：m/2 = 子節(jié)點(diǎn)個(gè)數(shù)= m。但是根節(jié)點(diǎn)是例外的，根節(jié)點(diǎn)可以最少有2個(gè)子節(jié)點(diǎn)。

2，每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)的個(gè)數(shù)，比該節(jié)點(diǎn)中保存的關(guān)鍵字的個(gè)數(shù)多1. 也就是，當(dāng)節(jié)點(diǎn)中保存k個(gè)關(guān)鍵字時(shí)，該節(jié)點(diǎn)會(huì)有k + 1個(gè)子節(jié)點(diǎn)（子樹(shù)）。

3，每個(gè)節(jié)點(diǎn)中的k個(gè)關(guān)鍵字是按照從小到到排列的，分別記為k1，k2，k3，......kk。那么該節(jié)點(diǎn)會(huì)有k+1個(gè)指針，記為p0，p1，p2，......pk。并且，p3所指向的子節(jié)點(diǎn)中的所有元素，都大于k3，且都小于k4. 如下圖所示。這一點(diǎn)也比較容易理解和記憶，各個(gè)指針p整好位于關(guān)鍵字k的插空的位置，所以，插空處的指針指向的子節(jié)點(diǎn)的元素的值，就理所當(dāng)然的應(yīng)該大于指針左邊的元素，小于指針右邊的元素。

4，B-樹(shù)是嚴(yán)格的平衡查找樹(shù)，它的左右子樹(shù)的高度是相等的。且葉子節(jié)點(diǎn)處于同一層，并且可以用空節(jié)點(diǎn)表示。

一個(gè)B-樹(shù)的例子：

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對(duì)腳本之家的支持。如果你想了解更多相關(guān)內(nèi)容請(qǐng)查看下面相關(guān)鏈接