數據結構 4 時間複雜度、B-樹 B+樹具體應用與理解

2020 年 3 月 11 日
筆記

前言

面試中，經常會問到有關於MYSQL 索引的相關概念，我們之前也都學過有關樹的概念、以及二叉樹、二叉查找樹、紅黑樹等。這一節，來關注經常是資料庫索引中使用的B-樹

在說這些之前，我們需要了解時間複雜度以及空間複雜度。

時間複雜度

時間複雜度，用於鑒定一個演算法的好壞、很多時候，比如跑一個for 循環一個數組排序，有冒泡、二分法等方法。相比於冒泡。二分法很佔優勢，為什麼呢?因為比較的次數少、並且做的無用功少、所以這個演算法就好。

時間複雜度就是為了表示一個頻繁度，這個頻繁度怎麼說呢。就是每執行一次循環，這就是一個頻繁。

O(頻度) 用O大寫字元O表示，而不是零。

常見時間複雜度依次從小到大：

O(1) 常數階
O(logn) 對數階
O(n) 線性階
O(n的平方) 平方階
O(n的立方) 立方階
O(2的n次方) (指數階)

空間複雜度

空間複雜度，一般指佔用的記憶體

時間換空間、空間換時間

這兩個完全是可以等價交換的。比如我們想用

消耗時間長、換取佔用空間少 這樣會使應用程式響應變慢。但是佔用記憶體少
消耗大量空間、換取快速的響應 例子：Google瀏覽器

B-樹

切記，這裡不念做B減數 這裡的橫崗沒有任何意思，就是B樹。

來說這個問題之前，首先了解一下：有關索引的簡單內容。
我們都知道，索引，就是儲存在本地磁碟上的一塊數據結構，通過索引，我們能夠快速查找資料庫指定數據所在的位置。因為需要快速的查找出來。所以性能需要好的數據結構；例如：

二叉查找樹時間複雜度 O(logN)

一般情況下，二叉查找樹以二分法查找，時間能夠大大減少、一般遍歷的最多次數就是二叉樹的層級高度。

我們在上面已經了解過有關時間換空間、空間換時間的概念了。所以資料庫的索引必須讓其快起來，那就必須使用空間去換取時間，一般的索引庫都是很大的。幾個G甚至更多。

一般情況下，這麼大的索引，我們沒辦法一次性讀入到記憶體中。必須逐一載入的記憶體當中才可以。

因為是磁碟，就會有讀取和寫入（IO）,使用二叉樹雖然性能很高，但是不得不考慮磁碟的IO性能。

假設在使用二叉樹來實現索引。我們查找的數字是7 最壞的情況下。也需要讀取3次才可找到這個數字，那麼有沒有情況，就是把這個樹的層級減少一些，我們讀取的IO次數也就能減少。性能也就能提升。B-樹就出來了

概念

將原來瘦高的二叉樹變為矮胖的B-樹。

B樹是一種多路平衡查找樹。每一個節點最多包含K個孩子，而K又被稱為是B樹的階。這個階取決於磁碟頁大小。

特點

假設這個磁碟決定的B樹階為m

根節點至少有兩個子女。
中間節點都包含（k-1）個元素和K個孩子，其中 m/2 <= k <= m

總結上面的話，就是說，這個k 就是節點的元素數量的範圍取值範圍在於

總是不能大於階，並且也不能少於階的一半。

每一個葉子節點都包含(k-1)個元素，其中 m/2 <= k <= m
所有葉子節點都是位於同一層的
每一個節點的元素從小到大排列，它的第（k-1）個元素正好是其k個孩子所包含元素的值域。（有點難以理解）

理解一下

畫出一個B樹，按照上面的條條框框我們來說一下：

B樹根節點9 確實有兩個子節點
中間的節點都會包含的元素數=子節點數-1。
比如2 6 這個元素的位置。

我們假設當前的k=2,所以當前節點的k-1=1 第一個元素2 正好是第2個子元素3,5的值域劃分。因為

2 < 3 < 6
2 < 5 < 6

畫個圖，你就理解了。拿出原來的一小部分，我們來分析

通過箭頭的指向，將子元素插入到指定的位置，你會發現什麼？？

看到了么？變成了一個線性數組，並且已經排序好了的。

B- 優勢

相比於二叉查找樹，我們的B-樹在縮短與硬碟的交互次數IO ,提升性能。每次只需要讀取一個節點，通過本節點在記憶體中的交互，即可通過值域的方式確定當前的值在那個節點下，依次找尋即可。

B-樹插入元素

假設我們插入一個4,通過遍歷，我們發現，必須要插入到這個位置：

若這樣插入，其實是違反規則的，因為父節點3，5有兩個元素，所以它應該有三個兒子節點才對，所以這樣行不通，需要改變！

往上方觀察，2,6 已經是滿節點的狀態，並且根節點最多包含兩個節點，那隻能在根節點入手了。

就需要拆分節點和發生一系列的改變，其實還是很繁瑣的。
這裡只需要了解這個過程即可。不需要鑽牛角尖

B樹優勢

B樹最大的優勢就是自平衡
以及始終能夠維持多路平衡，能夠最大程度減少磁碟的IO次數而達到性能提升

應用場景

那就是資料庫索引了。以及文件系統。資料庫這裡常見的就是MongoDB 一款非關係型資料庫。

而我們常用的Mysql資料庫則用的是B+樹作為索引的。我們下來說一說。

B+樹

所謂B+樹，其實就是B樹的Plus版本，更加牛皮，所以牛皮在哪兒呢？那無非就是查詢性能上，查詢快唄。

既然是B樹的一種擴展，那麼肯定的，也包含B樹該有的性質它都有，B+樹有的一些性質，我們這裡羅列一下：

特徵

假設這裡存在一個m階的B+樹，

有K個子節點的中間節點包含有K個元素，(B樹這裡是k-1),中間節點的元素不保存數據，只用來索引，所有的數據都保存在葉子節點。
所有的葉子節點包含了全部的元素資訊，以及指向這些元素的指針。葉子節點本身按照關鍵詞的大小自小而大順序排列。
所有的中間節點元素都同時存在與子節點中。在子節點元素中是最大或者最小的元素。

是不是很懵逼？懵逼就對了

待會兒我們來解釋一下，不要慌

中間節點有三個元素，所以它有三個子節點。沒毛病
每個子節點都會包含父節點的一個元素，或者是最大。或者是最小。
它的所有數據都是儲存與葉子節點的，並且使用指針指向下一個葉子節點，形成一個鏈表

為什麼查詢性能更優？

我們知道，B樹是為了減少磁碟IO而創建出來的，因為二叉樹雖然快，但是記憶體空間有限，一下子讀取不了那麼多。那就必須按照磁碟頁的大小，依次讀取節點到記憶體中。在數據量相同的情況下，因為B樹每個節點上都存在數據。而不一樣的是，B+樹只有在葉子節點才會存在數據，所以呢同樣的情況下，B+樹的這種結構，一次性能夠放入記憶體的節點數量就可以增加了。因為B+樹中間節點放的是引用地址嘛，這樣讀取性能又能夠翻一翻。

單一節點儲存了更多的元素。使得樹更加矮胖，讀取次數更少
查詢都需要到達葉子節點，而後通過鏈表遍歷、更加迅速。

小結

總結一下：為了什麼發明出B樹，因為通過空間換取時間的概念，索引是一個非常龐大的數據結構。而且

電腦的記憶體大小有限 不能一次性把二叉查找樹讀取進去，只能一點個節點一個節點的讀取到裡面。記憶體考慮完了。

硬碟IO 速度 因為索引的龐大，所以，在磁碟讀取的時候，盡量使用少次的IO讀取出我們需要的值，那就是最優解，所以呢，這個二叉樹看起來很瘦高，要讀取的IO數量太多了。所以呢？

B樹就被發明出來了。為了啥？讓二叉查找樹變得矮胖。減少IO次數

B+樹呢？作為B樹的一個Plus版本。還是由於磁碟頁的大小限制，只能讀取少量的B樹節點到記憶體中。因為B樹節點就帶有數據。而B+樹就不一樣了。因為中間節點不帶數據，能夠一次性讀取好幾個節點進去處理。所以呢，性能又提升了！

奧利給！

其實說了這麼多，我們可以發現，所有的優化，是建立在當前磁碟不夠、IO不夠、記憶體不夠大的基礎上改善的。

參考

https://mp.weixin.qq.com/s/jRZMMONW3QP43dsDKIV9VQ