B 樹是很基礎的概念，也是面試裡面的常考題，一定要掌握。今天我們就來聊聊這個話題。

要弄明白B 數，首先要了解B-樹

B-樹就是B樹，中間的橫線不是減号。千萬别念成：B減樹，那就丢人現眼了

既然這樣，為什麼索引不直接使用二叉樹來實現呢？二叉樹的查詢複雜度是O(logN)，性能已經足夠高，難道B-樹可以更快？

其實從算法上進，二叉樹确實可以。但是，我們不得不考慮一個現實問題：

數據庫索引是存儲在磁盤上的，當數據量比較大時，索引的大小可能有幾個G，甚至更多。

當我們利用索引查詢時，不可能把索引全部加載到内存裡。隻能逐一加載每一個磁盤頁。這裡的磁盤頁對應着索引樹的節點。

如果我們使用二叉樹，會怎麼樣呢？假設樹的高度是4，要查找的值是10，那麼流程如下：

第1次磁盤IO：

第2次磁盤IO：

第3次磁盤IO：

第4次磁盤IO：

我們可以看到：磁盤的IO次數，是由樹的高度決定的

既然如此，為了減少磁盤IO次數，我們就需要把原本“瘦高”的樹，變得“矮胖”一些，這就是B-樹。

B樹是一種多路平衡查找樹，它的一個節點最多包含K個孩子，K稱為樹的階。這裡，K的大小取決于磁盤頁的大小。

下面具體介紹一下B-樹（Balance Tree），一個K階的B-樹具有以下幾個特征：

（1）根結點至少有兩個孩子。

（2）每個中間節點都包含m-1個元素和m個孩子，其中 k/2 <= m <= k

（3）每一個葉子節點都包含m-1個元素，其中 k/2 <= m <= k

（4）所有的葉子結點都位于同一層。

（5）每個節點中的元素從小到大排列，節點當中m-1個元素正好是m個孩子包含的元素的值域分劃。

我們以一個3階的B-數為例，來看一下B-樹的具體結構。樹中的具體元素和剛才的二叉樹一樣。

我們重點看一下（2, 6）這個節點。該節點有2和6兩個元素。又有3個孩子：1，（3, 5）和8。其中 1 < 2，（3, 5）在2, 6之間，8大于（3, 5）。剛好符合上面的幾條特征。

假設要查詢的值是5：

第1次磁盤IO：

在内存中定位（和9比較）：

第2次磁盤IO：

在内存中定位（和2，6比較）：

第3次磁盤IO：

在内存中定位（和3，5比較）：

可以看出，B-樹在查找中的比較次數其實不比二叉數少，尤其是當單一節點中的元素數量很多時。但是，相對比磁盤IO的速度，内存的比較耗時可以忽略不計。所以，隻要數的高度足夠低，IO次數足夠少，就可以提高查找性能！

至于節點内部的元素數量，多一點無非是多幾次内存計算，隻要不超過磁盤頁大小就可以。這就是B-樹最核心的思想！

B-樹主要應用于文件系統，另外非關系型數據庫MongoDB，就使用了B-樹來做索引。

而大部分關系型數據庫，比如MySQL，則使用B 樹來做索引，關于B 樹，我們明天接着聊！

---

關注【老張聊架構】，成為百萬年薪架構師！

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部