什么是 B 樹(shù)？
一、面試被懟
面試官：你知道文件索引、數(shù)據(jù)庫(kù)索引一般用什么數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)嗎？
小秋：知道啊，一般都是用樹(shù)形結(jié)構(gòu)來(lái)存儲(chǔ)的。
面試官：可以說(shuō)說(shuō)為啥用樹(shù)形結(jié)構(gòu)來(lái)存儲(chǔ)嗎？
小秋：樹(shù)形結(jié)構(gòu)例如想 B 樹(shù)，B+ 樹(shù)，二叉查找樹(shù)都是有序的，所以查詢(xún)效率很高，可以再 O(logn) 的時(shí)間復(fù)雜度查找到目標(biāo)數(shù)據(jù)。
面試官：那可以問(wèn)問(wèn)文件索引，例如數(shù)據(jù)庫(kù)索引一般用哪種樹(shù)形結(jié)構(gòu)嗎？
小秋：大部分用 B+ 樹(shù)，少部分用 B 樹(shù)。（B和B+樹(shù)太他么復(fù)雜了，幸好背了下面試題，嘻嘻）
面試官：想問(wèn)下為什么要用 B 樹(shù)而不用二叉查找樹(shù)啊？或者為啥不用哈希表啊？哈希表的查找速度也很快呀。
小秋：哈希表雖然能夠再 O(1) 查找到目標(biāo)數(shù)據(jù)，不過(guò)如果我們要進(jìn)行模糊查找的話(huà)，卻只能遍歷所有數(shù)據(jù)，并且如果出現(xiàn)了極端情況，哈希表沖突的元素太多，也會(huì)導(dǎo)致線(xiàn)性時(shí)間的查找效率的。
面試官：那為啥不用二叉查找樹(shù)呢？
小秋：這個(gè)…..其實(shí)我也不知道，當(dāng)時(shí)是在某個(gè)面試題中看到的答案的，嘻嘻。
面試官：那你可以回去等通知了….
二、為啥不用二叉查找樹(shù)呢？
小秋被懟后有點(diǎn)沮喪，跑過(guò)來(lái)問(wèn)帥地關(guān)于 B 樹(shù)的一些知識(shí)以及心中的疑問(wèn)。
小秋：今天去面試，面試問(wèn)我，為啥文件索引要用 B 樹(shù)而不用二叉查找樹(shù)，然后我想了下，感覺(jué)如果這是一顆比較平衡的二叉查找樹(shù)的話(huà)，那么查找效率是非常快的，難度 B 樹(shù)還能比它更快嗎？
帥地：確實(shí)，如果是查找效率（即比較次數(shù)）的話(huà)，實(shí)際上二叉樹(shù)可以說(shuō)是最快的了，但是，我們的文件索引是存放在磁盤(pán)上的，所以我們不僅要考慮查找效率，還要考慮磁盤(pán)的尋址加載次數(shù)哦，而這也是我們?yōu)槭裁匆?B 樹(shù)的原因。
小秋：難道二叉查找樹(shù)會(huì)導(dǎo)致磁盤(pán)的加載次數(shù)更多嗎？可以給我詳細(xì)講講嗎？
帥地：這就安排！
三、什么是 B 樹(shù)？
帥地：要講懂這個(gè)問(wèn)題，我們先來(lái)了解一下什么是 B 樹(shù)，其實(shí)，B 樹(shù)和二叉查找樹(shù)一樣，都是樹(shù)，B 樹(shù)相當(dāng)于是一棵多叉查找樹(shù)，對(duì)于一棵 m 階的 B 樹(shù)具有如下特性：
1、根節(jié)點(diǎn)至少有兩個(gè)孩子。
2、每個(gè)中間節(jié)點(diǎn)都包含 k - 1 個(gè)元素和 k 個(gè)孩子，其中 m/2 <= k <= m。
3、每一個(gè)葉子節(jié)點(diǎn)都包含 k - 1 個(gè)元素，其中 m/2 <= k <= m。
4、所有的葉子節(jié)點(diǎn)都位于同一側(cè)。
5、每個(gè)節(jié)點(diǎn)中的元素從小到大排列，節(jié)點(diǎn)當(dāng)中的 k - 1 個(gè)元素正好是 k 個(gè)孩子包含的元素的值域劃分。
小秋：我去，這么復(fù)雜，鬼才記得住，我還是選擇不學(xué)了，嗚嗚。
帥地：你別著急，這些規(guī)則我也記不住，只是讓你大致知道一些這些規(guī)則，一般情況下，我們并不需要把它的規(guī)則完全背起來(lái)滴。為了加深理解，我給你舉個(gè) B 樹(shù)的例子吧。例如：
圖中是一棵m = 3 的 3 階 B 樹(shù)，可以看出，樹(shù)中有些節(jié)點(diǎn)是有多個(gè)元素的，并且和二叉查找樹(shù)一樣，左節(jié)點(diǎn)的所有元素的值都比父親元素小。例如對(duì)于(3, 7)這個(gè)節(jié)點(diǎn)。兩個(gè)元素把這個(gè)節(jié)點(diǎn)分割成三個(gè)值域，即可以有 3 個(gè)孩子。2 相當(dāng)于 3 的左孩子節(jié)點(diǎn)，而 （4，6）相當(dāng)于 3 的右孩子，同時(shí)也是 7 的左孩子，而 9 是 7 的右孩子。
和二叉查找樹(shù)還是很相似滴，都是有序，且左孩子小，右孩子大，只是 B 樹(shù)的一個(gè)節(jié)點(diǎn)可以有多個(gè)元素，并且有多個(gè)分支。而這些分支以及元素的數(shù)量規(guī)則，可以從上面的五個(gè)規(guī)則中查找哈。說(shuō)實(shí)話(huà)，我也懶的記那些規(guī)則，只知道個(gè)大概以及 B 樹(shù)的應(yīng)用即可。
四、小秋的疑惑
小秋：我知道了，不過(guò)這種多叉的樹(shù)，真的可以比二叉查找樹(shù)效率更好嗎，我怎么覺(jué)得不可以呢？
帥地：那你可以說(shuō)說(shuō)哦。
小秋：例如，上面的 B 樹(shù)有 11 個(gè)元素，按照這 11 個(gè)元素，我們建立一個(gè)如下的二叉查找樹(shù)，如圖（我去，這個(gè)圖片了好長(zhǎng)時(shí)間，ppt 畫(huà)的）
下面我們來(lái)進(jìn)行查詢(xún)效率比較
1、在 B 樹(shù)中的查找次數(shù)。
現(xiàn)在假如我們要查詢(xún)?cè)?9,對(duì)于 B 樹(shù)，我們需要進(jìn)行4次比較，例如：
第一次比較：10 比較，比 10 小，所以再 10 的左孩子找。
第二、三次比較：和 3 比較，比 3 大，這個(gè)時(shí)候我們還得和 7 比較。
第四次比較：和 9 比較，相等，找到目標(biāo)樹(shù)，返回。
所以最終的結(jié)果需要 4 次比較。
2、在二叉樹(shù)的比較結(jié)果
為了節(jié)省篇幅，我就不逐個(gè)比較了，相信你也一眼就看出來(lái)了，也是需要 4 次比較。如圖
小秋：同樣都是四次比較，而且，B 樹(shù)的每一個(gè)節(jié)點(diǎn)，如果存放的元素比較多，那么 B 樹(shù)的比較次數(shù)會(huì)更多，為什么就說(shuō) B 的效率比 二叉查找樹(shù)快呢？
五、解決疑惑
帥地：確實(shí)，如果單單從比較次數(shù)看的話(huà)，二叉查找樹(shù)確實(shí)不比 B 樹(shù)差，不過(guò)你忽略了一個(gè)很重要的點(diǎn)，那就是磁盤(pán)的尋址加載次數(shù)。
我們知道，在把磁盤(pán)里的數(shù)據(jù)加載到內(nèi)存中的時(shí)候，是以頁(yè)為單位來(lái)加載的，而我們也知道，節(jié)點(diǎn)與節(jié)點(diǎn)之間的數(shù)據(jù)是不連續(xù)的，所以不同的節(jié)點(diǎn)，很有可能分布在不同的磁盤(pán)頁(yè)中。所以對(duì)于上面的二叉查找樹(shù)，我們可能需要進(jìn)行 4 次尋址加載，如圖：
而對(duì)于 B 樹(shù)，由于 B 樹(shù)的每一個(gè)節(jié)點(diǎn)，可以存放多個(gè)元素，所以磁盤(pán)尋址加載的次數(shù)會(huì)比較少，例如上面的例子中，用 B 樹(shù)的話(huà)，只需要加載 3 次，如圖：
我們都知道，在內(nèi)存的運(yùn)算速度是非常快的，至少比磁盤(pán)的尋址加載速度，快了幾百倍，而我們進(jìn)行數(shù)值比較的時(shí)候，是在內(nèi)存中進(jìn)行的，雖然 B 樹(shù)的比較次數(shù)可能比二叉查找樹(shù)多，但是磁盤(pán)操作次數(shù)少，所以總體來(lái)說(shuō)，還是 B 樹(shù)快的多，這也是為什么我們用使用 B 樹(shù)來(lái)存儲(chǔ)的原因。
小秋：原來(lái)這樣啊，以前一直蒙在鼓里。
帥地：不知道你發(fā)現(xiàn)沒(méi)有，實(shí)際上磁盤(pán)的加載次數(shù)，基本上是和樹(shù)的高度相關(guān)聯(lián)的，高度越高，加載次數(shù)越多，越矮，加載次數(shù)越少。所以對(duì)于這種文件索引的存儲(chǔ)，我們一般會(huì)選擇矮胖的樹(shù)形結(jié)構(gòu)。例如有 1000 個(gè)元素，如果是二叉查找樹(shù)的話(huà)，高度可能高達(dá) 10 層,而如果用 10 階 B 樹(shù)的話(huà)，只需要三四層即可。
小秋：終于搞懂了，不過(guò)我還有個(gè)疑問(wèn)，大部分文件索引或者數(shù)據(jù)庫(kù)索引都是用 B+ 樹(shù)的，而只有小部分才用 B 樹(shù)，可以問(wèn)下為什要用 B+ 樹(shù)而不用 B 樹(shù)嗎？還有，B 樹(shù)還有其他的應(yīng)用嗎？
帥地：B 樹(shù)除了會(huì)用在少部分的文件索引（數(shù)據(jù)庫(kù)索引）外，應(yīng)用的最多的就是文件系統(tǒng)了。至于為什么要用 B 樹(shù)而不用 B+ 樹(shù)，為什么數(shù)據(jù)庫(kù)索引大部分用 B+ 樹(shù)而不用 B 樹(shù)，可以看這篇：【面試現(xiàn)場(chǎng)】為什么MySQL數(shù)據(jù)庫(kù)要用B+樹(shù)存儲(chǔ)索引？
總結(jié)
關(guān)于 B 樹(shù)和 B+ 樹(shù)，在面試的過(guò)程中，還是問(wèn)的挺多滴，特別是問(wèn)到數(shù)據(jù)庫(kù)的時(shí)候，基本會(huì)問(wèn)索引，進(jìn)而問(wèn)到 B+ 樹(shù)，從而也會(huì)扯到 B 樹(shù)。所以掌握著兩種樹(shù)的應(yīng)用以及原理，是非常重要的，雖然他們的規(guī)則很復(fù)雜，但是如果是應(yīng)付面試等，其實(shí)不需要背那些規(guī)則，只需要知道大概以及知道他們的原理即可。