一、面試被懟
面試官：你知道文件索引、數據庫索引一般用什麼數據結構來存儲嗎？
小秋：知道啊，一般都是用樹形結構來存儲的。
面試官：可以說說為啥用樹形結構來存儲嗎？
小秋：樹形結構例如想 B 樹，B+ 樹，二叉查找樹都是有序的，所以查詢效率很高，可以再 O(logn) 的時間複雜度查找到目標數據。
面試官：那可以問問文件索引，例如數據庫索引一般用哪種樹形結構嗎？
小秋：大部分用 B+ 樹，少部分用 B 樹。（B和B+樹太他麼複雜了，幸好背了下面試題，嘻嘻）
面試官：想問下為什麼要用 B 樹而不用二叉查找樹啊？或者為啥不用哈希表啊？哈希表的查找速度也很快呀。
小秋：哈希表雖然能夠再 O(1) 查找到目標數據，不過如果我們要進行模糊查找的話，卻只能遍歷所有數據，並且如果出現了極端情況，哈希表衝突的元素太多，也會導致線性時間的查找效率的。
面試官：那為啥不用二叉查找樹呢？
小秋：這個…..其實我也不知道，當時是在某個面試題中看到的答案的，嘻嘻。
面試官：那你可以回去等通知了….
二、為啥不用二叉查找樹呢？
小秋被懟後有點沮喪，跑過來問帥地關於 B 樹的一些知識以及心中的疑問。
小秋：今天去面試，面試問我，為啥文件索引要用 B 樹而不用二叉查找樹，然後我想了下，感覺如果這是一顆比較平衡的二叉查找樹的話，那麼查找效率是非常快的，難度 B 樹還能比它更快嗎？
帥地：確實，如果是查找效率（即比較次數）的話，實際上二叉樹可以說是最快的了，但是，我們的文件索引是存放在磁盤上的，所以我們不僅要考慮查找效率，還要考慮磁盤的尋址加載次數哦，而這也是我們為什麼要用 B 樹的原因。
小秋：難道二叉查找樹會導致磁盤的加載次數更多嗎？可以給我詳細講講嗎？
帥地：可以呀，不過聽懂了，覺得我講的不錯，你要記得給我多點贊，轉發哦。
小秋：絕對沒問題。
三、什麼是 B 樹？
帥地：要講懂這個問題，我們先來了解一下什麼是 B 樹，其實，B 樹和二叉查找樹一樣，都是樹，B 樹相當於是一棵多叉查找樹，對於一棵 m 階的 B 樹具有如下特性：
1、根節點至少有兩個孩子。
2、每個中間節點都包含 k - 1 個元素和 k 個孩子，其中 m/2 <= k <= m。
3、每一個葉子節點都包含 k - 1 個元素，其中 m/2 <= k <= m。
4、所有的葉子節點都位於同一側。
5、每個節點中的元素從小到大排列，節點當中的 k - 1 個元素正好是 k 個孩子包含的元素的值域劃分。
小秋：我去，這麼複雜，鬼才記得住，我還是選擇不學了，嗚嗚。
帥地：你彆著急，這些規則我也記不住，只是讓你大致知道一些這些規則，一般情況下，我們並不需要把它的規則完全背起來滴。為了加深理解，我給你舉個 B 樹的例子吧。例如：
圖中是一棵m = 3 的 3 階 B 樹，可以看出，樹中有些節點是有多個元素的，並且和二叉查找樹一樣，左節點的所有元素的值都比父親元素小。例如對於(3, 7)這個節點。兩個元素把這個節點分割成三個值域，即可以有 3 個孩子。2 相當於 3 的左孩子節點，而 （4，6）相當於 3 的右孩子，同時也是 7 的左孩子，而 9 是 7 的右孩子。
和二叉查找樹還是很相似滴，都是有序，且左孩子小，右孩子大，只是 B 樹的一個節點可以有多個元素，並且有多個分支。而這些分支以及元素的數量規則，可以從上面的五個規則中查找哈。說實話，我也懶的記那些規則，只知道個大概以及 B 樹的應用即可。
四、小秋的疑惑
小秋：我知道了，不過這種多叉的樹，真的可以比二叉查找樹效率更好嗎，我怎麼覺得不可以呢？
帥地：那你可以說說哦。
小秋：例如，上面的 B 樹有 11 個元素，按照這 11 個元素，我們建立一個如下的二叉查找樹，如圖（我去，這個圖片了好長時間，ppt 畫的）
下面我們來進行查詢效率比較
1、在 B 樹中的查找次數。
現在假如我們要查詢元素 9,對於 B 樹，我們需要進行4次比較，例如：
第一次比較：10 比較，比 10 小，所以再 10 的左孩子找。
第二、三次比較：和 3 比較，比 3 大，這個時候我們還得和 7 比較。
第四次比較：和 9 比較，相等，找到目標樹，返回。
所以最終的結果需要 4 次比較。
2、在二叉樹的比較結果
為了節省篇幅，我就不逐個比較了，相信你也一眼就看出來了，也是需要 4 次比較。如圖
小秋：同樣都是四次比較，而且，B 樹的每一個節點，如果存放的元素比較多，那麼 B 樹的比較次數會更多，為什麼就說 B 的效率比 二叉查找樹快呢？
五、解決疑惑
帥地：確實，如果單單從比較次數看的話，二叉查找樹確實不比 B 樹差，不過你忽略了一個很重要的點，那就是磁盤的尋址加載次數。
我們知道，在把磁盤裡的數據加載到內存中的時候，是以頁為單位來加載的，而我們也知道，節點與節點之間的數據是不連續的，所以不同的節點，很有可能分佈在不同的磁盤頁中。所以對於上面的二叉查找樹，我們可能需要進行 4 次尋址加載，如圖：
而對於 B 樹，由於 B 樹的每一個節點，可以存放多個元素，所以磁盤尋址加載的次數會比較少，例如上面的例子中，用 B 樹的話，只需要加載 3 次，如圖：
我們都知道，在內存的運算速度是非常快的，至少比磁盤的尋址加載速度，快了幾百倍，而我們進行數值比較的時候，是在內存中進行的，雖然 B 樹的比較次數可能比二叉查找樹多，但是磁盤操作次數少，所以總體來說，還是 B 樹快的多，這也是為什麼我們用使用 B 樹來存儲的原因。
小秋：原來這樣啊，以前一直矇在鼓裡。
帥地：不知道你發現沒有，實際上磁盤的加載次數，基本上是和樹的高度相關聯的，高度越高，加載次數越多，越矮，加載次數越少。所以對於這種文件索引的存儲，我們一般會選擇矮胖的樹形結構。例如有 1000 個元素，如果是二叉查找樹的話，高度可能高達 10 層,而如果用 10 階 B 樹的話，只需要三四層即可。
小秋：終於搞懂了，不過我還有個疑問，大部分文件索引或者數據庫索引都是用 B+ 樹的，而只有小部分才用 B 樹，可以問下為什要用 B+ 樹而不用 B 樹嗎？還有，B 樹還有其他的應用嗎？
帥地：B 樹除了會用在少部分的文件索引（數據庫索引）外，應用的最多的就是文件系統了。至於為什麼要用 B 樹而不用 B+ 樹，為什麼數據庫索引大部分用 B+ 樹而不用 B 樹，我們下節再講了。
小秋：那我期待著。
帥地：如果覺得有收穫，可以幫忙多多轉發，點贊，分享哦，這也是我寫文章的動力來源。
總結
關於 B 樹和 B+ 樹，在面試的過程中，還是問的挺多滴，特別是問到數據庫的時候，基本會問索引，進而問到 B+ 樹，從而也會扯到 B 樹。所以掌握著兩種樹的應用以及原理，是非常重要的，雖然他們的規則很複雜，但是如果是應付面試等，其實不需要背那些規則，只需要知道大概以及知道他們的原理即可。
閱讀更多 Java的小本家 的文章
