為什麼選擇b+樹作為存儲引擎索引結構

在資料庫或者存儲的世界裡，存儲引擎的角色一直處於核心位置。往簡單了說，存儲引擎主要負責數據如何讀寫。往複雜了說，怎麼快速、高效的完成數據的讀寫，一直是存儲引擎要解決的關鍵問題。在絕大部分介紹、講解存儲引擎的書籍或者文章里，大家都默認了讀多寫少的磁碟存儲引擎採用的就是b+樹，而極少有人來剖析選擇b+樹作為索引結構的背後，到底有著怎樣的思考和權衡？為了解答上述問題，本文嘗試從一個新的視角和大家討論：

在處理讀多寫少的場景下，為什麼基於磁碟的存儲引擎會選擇用b+樹來作為索引結構？希望在看完本文後，讀者能對該問題有一個全新的認識和屬於自己的答案。限於個人能力有限，有表述、理解不正當之處希望批評指正。

本文的內容主要以問答方式展開，層層遞進分析、解決問題，本文涉及內容會圍繞下面三個問題展開。在開始閱讀本文內容前，大家不妨先嘗試自己回答下面三個問題！

為了減少讀者的疑惑，在開始本文的正式內容之前，先和讀者做一些簡要的關鍵名詞的解釋和說明：

1.存儲引擎： 存儲引擎是一個很廣的範疇，有處理讀多寫少的基於頁結構的b+樹存儲引擎，也有後起之秀基於日誌結構(lsm 樹)的存儲引擎。在本文中提到的存儲引擎，如沒有特殊說明，都指的是針對處理讀多寫少場景的基於磁碟的b+樹存儲引擎，這類存儲引擎在關係型資料庫中出現的頻率較高，經典代表就是mysql中的innodb，此外golang編寫的boltdb也屬於本文討論的範疇。

2.擴展內容： 文中標識為擴展內容的章節，對於基礎相對較好的讀者這些內容可以選擇性閱讀，不讀也不會造成本文核心內容理解困難；對於基礎相對一般的小夥伴，可以選擇性的進行閱讀。

下面我們先嘗試回答前兩個問題，因為前兩個問題可以算作是一大類問題。第一個問題主要在於數據結構的選型。第二個問題主要在於因果關係的區分。

1.背景

這個問題的答案，我們從哪裡開始說起呢？想之又想，只有搞清楚了整體的一個背景，我們才能知道當時的工程師面臨的怎樣的一個問題。近而，我們才能嘗試從根上解釋這個問題。從整體的大的環境來看，他們要解決的問題主要面臨的以下四個主要特點：

1. 處理讀多寫少的場景
2. 關係型資料庫按照行組織
3. 存儲千萬級量級數據
4. 採用性價比高的存儲

接下來我們一一對其進行解釋，因為如果上述四個背景如果不成立的話，說明我們一開始的出發點就錯了，後面的回答都是無稽之談。

1.1 處理讀多寫少的場景

提起這個話題，我們就不得不說，在互聯網發展起來的早期，大部分的系統主要處理的是讀多寫少的場景。例如早期的bbs內容、部落格、門戶網站、電商的商品入庫等等，這些場景都可以劃分為讀多寫少。他們通過有限次的寫操作將數據寫入到資料庫中，然後供用戶多次瀏覽、閱讀。發展到今天的互聯網，面向用戶的很多系統仍然是屬於讀多寫少的範疇。所以讀多寫少這是一個早期存儲引擎在數據讀寫時面臨的最大的背景。

1.2 關係型資料庫按照行組織

早期的時候存儲引擎這個概念主要還是出現在關係型資料庫中，大部分人接觸這個概念估計也是因為mysql，mysql中經常提到存儲引擎這個詞。在關係型資料庫中，數據往往通過資料庫->表(多列)–>行 的方式來組織。最終落到存儲引擎這一層時，數據已經按照行的格式來組織了。廣義來看其實也就是類似於key-value的存儲了，只不過在關係型資料庫中，到達存儲引擎這層的value是一行記錄按照指定的格式來扁平化組織而成，具體的格式大同小異。這兒不再展開贅述。大家可以自行搜索資料查閱，此處主要是拋出來在關係型資料庫中數據按照行格式來存儲這個背景。

為了方便介紹，在後續的內容中，存儲引擎存儲的數據我們就統一按照key-value來討論了。此處的key大家暫且可以直觀的理解為主鍵。

1.3 存儲千萬級量級數據

隨著互聯網的迅速發展，數據存儲的量級日益增長，很快就達到了存儲千萬級量級數據這個量級。很明顯這個背景從需求的角度看，其實是屬於不斷迭代的過程。不可能初期互聯網一起來，馬上就面臨這個量級。但是我們也知道在電腦軟體的世界中，可擴展性是大家耳熟能詳的詞語。所以在設計存儲引擎時，自然而然肯定會考慮這個問題。所以此處，我們將存儲千萬級數據量級這個作為第三個背景。

1.4 採用性價比高的存儲

接著第三個背景，自然而然就引出了數據存儲在哪裡的問題。回答這個問題，必須就得引出一個成本問題了。如果不考慮成本來存儲，那自然問題就簡化了。但是千萬級量級的數據存儲時，有了成本的限制，就得思考了。

我們的目標是要找到一個成本相對廉價，但又能支援千萬級數據量級的存儲介質。

對於電腦中，存儲數據的媒介整體可以分為兩大類：

1.易失性存儲： 典型代表記憶體
2.非易失性存儲： 典型代表硬碟(磁碟)，尤其是早期的機械硬碟

關於二者的詳細對比，大家可以參考下圖：

首先，通過上圖的對比，我們大致可以確定了，我們期望的存儲介質就是硬碟(主要是機械硬碟)了。因為它很符合我們所尋找的幾個特點。但我們都知道硬碟雖然符合我們的要求，但硬碟有著它先天結構的限制。訪問磁碟的速度要比訪問記憶體慢的多。

到這兒也就不得不提一下，關於機械硬碟它的構成了。關於機械硬碟的簡單介紹，我們在下面的擴展內容中進行簡要介紹，大家感興趣可以進行閱讀，已經掌握的讀者可以直接跳過這部分虛線框中的內容。

擴展內容

上圖關於磁碟介紹的圖片摘自本篇文章。

普通的機械硬碟讀寫數據主要是通過移動磁頭到對應的磁軌，然後再旋轉磁頭到對應的扇區。最後進行移動磁頭進行讀寫數據。

簡單說：一次硬碟數據讀寫主要包括三大部分耗時：尋道時間、旋轉時間、傳輸時間。而在這其中尋道時間主要佔大頭，主要是因為磁頭的移動主要是馬達通過驅動磁臂近而移動磁頭，這個運動屬於機械運動，所以速度相對較慢。

對磁碟而言，磁碟的訪問肯定是要比記憶體慢的。但是在磁碟訪問時，又有兩種訪問方式：

1. 隨機IO
2. 順序IO

順序IO的訪問速度要遠遠快於隨機IO，其根本原因是：順序IO主要減少了磁頭的移動頻率，也就是減少了尋道時間。所以它的性能要比隨機IO要快很多。

由於篇幅有限，關於硬碟的介紹我們就不過多展開了，不然就跑題了。有了上述的知識，我們就足以開展我們後續的內容了。關於硬碟的詳細內容介紹，大家可以自行找其他資料學習或者點擊本篇文章進行閱讀。下面我們繼續介紹我們的主要內容。

其次，我們既然選擇了硬碟做存儲媒介，那就必須想辦法克服這個問題。下面這張圖詳細描述了記憶體訪問速度和磁碟訪問速度的對比結果。

下面我們簡單總結下，拋出我們在這塊得出的結論：

> 結論1可以參考擴展內容詳細了解。

1.磁碟訪問時間：尋道時間+旋轉時間+傳輸時間：
> 尋道時間：8ms~12ms
> 旋轉時間：7200轉/min：半周4ms
> 傳輸時間：50M/s，約0.3ms

2.磁碟隨機IO ≪ 磁碟順序IO ≈ 記憶體隨機IO ≪ 記憶體順序IO

3.機械磁碟和固態硬碟構成：

> 機械硬碟：電磁存儲，通過電磁訊號轉變來控制讀寫，磁頭機械臂移動
> 固態硬碟：半導體存儲，用固態電子存儲晶片陣列、由控制單元和存儲單元組成，內部由
> 快閃記憶體顆粒組成。速度較

1.5 總結

本節主要交代了4個大的背景，下面再和大家回顧一下。

1. 處理讀多寫少的場景
2. 關係型資料庫按照行組織
3. 存儲千萬級量級數據
4. 採用性價比高的存儲

最後我們結合實際的場景選擇以硬碟這種介質來存儲數據，同時在存儲引擎層，數據按照抽象層面的key-value來組織讀取和寫入。了解了大的背景，下面得了解我們的目標是啥了。沒有目標就沒有方向，搞清楚目標對我們至關重要。

2.目標

在第一節中，我們介紹了四大基本背景。並分析出來了我們最終需要採取硬碟來存儲數據。在本節中，我們將重點關注我們的要達到的目標，只有明確了目標，我們才能更好的進行自頂向下分解任務並解決問題。

在介紹我們的目標前，我們先來看看我們在基於磁碟存儲數據的條件下，一次常規的用戶請求大概是怎樣的？

2.1 常規的一次用戶請求響應過程

我們都知道，我們的數據存儲在硬碟上，因此當用戶的請求(讀/寫)進來後，首先會到作業系統管理的記憶體中，在記憶體中進行一些邏輯處理，然後cpu會發送指令從硬碟讀取數據到記憶體中，最後就會響應上層用戶(讀：讀取的數據、寫：寫數據是否成功等)。

上面描述的一個大概的流程。從中我們可以看到整個過程經歷三個階段：

請求過程：
用戶請求->記憶體->硬碟

響應過程:
響應用戶<-記憶體<-硬碟

理清楚了整個用戶的請求響應流程後，我們就來看看，我們最終的目標是啥呢？

2.2 目標

其實互聯網的應用，有個潛移默化的潛規則，那就是高效、快速，對存儲引擎而言也不例外，我們的目標就是要在上述背景下進行快速、高效的數據讀寫請求。

問題來了！ 快速、高效這都屬於定性分析的一類描述用語，怎麼樣算快速呢？怎麼樣又算高效呢？怎麼定量分析這個需求呢？

到這兒，大伙兒可以想想如果這個需求是你來負責的，那麼你會從哪些角度出發來思考這個問題呢？

這個問題應該難不倒聰明的你，還記得數據結構與演算法里有一個指標嗎！時間複雜度，這就是一個很重要的核心指標呀，衡量數據結構或者演算法處理效率的一個關鍵指標。我們想想，我們的數據最終要存儲，怎麼存儲，怎麼組織，這不就涉及到選擇哪種數據結構了嗎！那上述問題我們也就進一步延伸到了，採用哪種數據結構來組織我們的數據，並儘可能使得其讀寫比較快速、高效。具體的快速、高效通過時間複雜度來判定。

2.3 總結

本小節我們對前面介紹的兩部分內容通過一個框圖來進行總結回顧。具體的選擇哪種數據結構這個問題我們放到下一節來進行介紹。

3.數據結構選型

在2.2節提到，我們最終將快速、高效讀寫這個問題轉化成了選擇採用哪種數據結構來組織數據、並通過其時間複雜度來定量的判定我們的目標。下面我們就從數據結構這個方面著手看看。

3.1 數據結構方案對比

我們詳細的分析下，快速、高效那也就意味著讀寫的平均時間複雜度，要儘可能的低。在數據結構中我們學習過很多的數據結構，例如：平均時間複雜度是O(1)的數據結構，典型代表是哈希表(hash table)。哈希表主要在點對點的映射讀寫上衝突比較低時效率很高，但其原生的數據結構在面對範圍查找、排序等操作時時間複雜度會相對較高，這也算是哈希表的一大缺陷；其次平均時間複雜度比O(1)稍慢的是平均時間複雜度為O(logn)，這類數據結構有二叉查找/排序樹(bst tree)、平衡二叉樹(avl tree)、紅黑樹(rb tree)、b樹(b/b- tree)、b+樹(b+ tree)、跳錶(skiplist)等。他們天然就支援排序、範圍查找操作；再其次比O(logn)還慢的時間複雜度為O(n)、O(n^2)等等。 O(n)的平均時間複雜度的典型代表有數組。其他類型我們這兒就不過多展開了。

下圖是我們根據平均時間複雜度依次從O(1)->O(logn)->O(n)->…由快到慢的一個對比結果。

我們都知道互聯網的應用中，排序、範圍查找是一個再普遍不過的需求了。例如在電商網站購物時，大部分用戶都會下意識的點擊按照銷量從高到低排序；再比如在門戶新聞網站上，我們會關注過去一周某個新聞被閱讀的次數，按照時間來排序；再比如推薦系統中，我們會按照內容的一類或者多類屬性對物品進行排序，還有很多很多例子。所以我們在選擇數據結構時，必須考慮支援範圍查找、排序等操作。

基於這點的話，看來哈希表就不太符合我們的需求了。那我們退而求其次，再來看看O(logn)的時間複雜度中，我們選擇哪種數據結構呢？這幾種數據結構粗略一看貌似都能滿足我們的需求，同時上述幾種數據結構:二叉查找/排序樹(bst tree)、平衡二叉樹(avl tree)、紅黑樹(rb tree)、b樹(b/b- tree)、b+樹(b+ tree)、跳錶(skiplist)在記憶體中都可以實現，我們如何選擇呢？直觀來看我們選哪種好像都可以，但我們別忘了，我們的數據最終要落到硬碟，既然這兒得不出結論，那我們就從硬碟的維度來看看，硬碟上哪種數據結構好維護呢？

3.2 目光轉向磁碟

根據前面的介紹，我們的數據流向分為三個階段，以讀取操作舉例：磁碟->記憶體->用戶。既然這樣的話，我們的直觀想法是，如果能在記憶體和硬碟這兩種介質上維護同一種數據結構，那就最完美了，這樣當用戶請求進來後，從磁碟載入數據後，可以直接載入到記憶體中，然後做一些處理就返回用戶了。如果直觀想法走不通的話(找不到這樣一種數據結構)。那我們就只能按照間接思路來出發了，硬碟上維護一種數據結構存儲我們的數據，記憶體中選擇另外一種數據結構保存數據。當從硬碟讀取數據到記憶體中時，中間做一層轉換。間接思路這種做法是下策，因為中間數據的轉換避免不了會引入一些性能的損耗。

那就先按照直觀想法出發來找找看，是否存在這樣一類數據結構呢？

3.3 直觀思路出發

我們先想想，既然我們的目標仍然是快速、高效讀寫，那對應到磁碟上，怎麼做到對磁碟快速、高效讀寫呢？

根據前面的鋪墊介紹，大夥應該都知道了那就儘可能的利用磁碟的順序IO唄。提到順序IO，腦子裡第一時間蹦出來的自然就是追加寫，因為這種方式就是一種典型的順序寫、順序IO，性能挺高的。我們假設用戶每個寫請求進來，都採用追加寫的方式來保存數據。在這種方式下寫操作是快了、高效了。那怎麼來讀呢？

根據前面的介紹，數據是按照key-value來扁平化存儲的。每條記錄長度各不相同，既然要保證讀，那就得額外保存一些資訊來輔助處理用戶的讀請求。這些額外保存的數據，我們暫且稱為索引。我們思索一下，在這種追加寫的場景下，我們需要保存哪些資訊才可以完成正常的讀請求呢？其實每條記錄我們只要知道了它寫在磁碟的哪個位置(偏移量)offset、佔了多長size這兩個資訊。我們就可以對其進行讀了。簡而言之，一條記錄對應一個這樣的二元組索引資訊。簡單示意圖如下所以：

到這兒，高效寫可以了，維護了索引後，單個記錄的讀也可以了；但是有個問題我們得想想怎麼辦？那就是我們前面提到的排序、範圍查找操作。

在這種場景下，每來一條記錄我們都是直接追加的，所以數據在磁碟上本身就是亂序存儲的，既然需要排序、範圍查找的話。那就得把磁碟上的所有記錄都載入到記憶體中，然後再挨個挨個遍歷判斷，最後過濾出來滿足條件的記錄返回用戶。這種方式能實現功能，但顯然效率太低了。同時磁碟上存儲的數據可能都遠遠超過記憶體大小了，所以這種方式根本就不可取。那有沒有辦法解決該問題呢？

我們做一點假設：假設我們寫磁碟的時候能保證順序寫的同時，寫入的數據是有序的。比如，我們寫入了三條數據，這三條數據本身寫入的時候是排好序的，那麼此時範圍查找時，我們只要定位到第一條數據，後面的數據是有序的，就可以很快進行按序讀取了。如果假設條件成立的話，那排序、範圍查找這個問題就從根本上得到簡化了。我們也就不用這麼大費周折了。我們先基於這個簡單假設來看一下，在假設條件成立的情況下，我們還需要解決哪些問題呢？

在這種模式下，我們訪問每條記錄同時還是需要保留之前的結論：每條數據都維護一個索引項：offset、size。

我們要存儲的是千萬級量級的數據，每一條記錄都需要一個索引項，那麼千萬條的記錄就需要維護千萬條索引項。問題就接著產生了，這千萬條的索引項怎麼組織？選哪種數據結構組織? 存哪裡？…

針對千萬條索引項這個問題，我們來看看這個問題有沒有解。直觀的想法可能就分為兩大類：

能否減少索引項的個數？索引項個數減少，自然問題就好解決了
不能減少索引項個數的情況下，是否可以找到合理的數據結構來組織。這兒的「合理」可以理解成：空間壓縮、優化等等。

我們先從按照第一個思路來看看吧！

Q:為什麼會產生千萬條索引項呢？

W:因為每一條記錄都需要維護一個索引項，我們需要保存千萬條記錄，所以就得存儲千萬條索引項。

Q:為什麼每一條記錄需要維護一個索引項呢？

W:因為每一條記錄都是從用戶請求傳遞進來的，每條記錄在按照行格式扁平化存儲時，長度是不固定的，所以需要每一條記錄維護一個索引項。

到這兒我們知道了問題的核心原因了。

到這兒我們將上面層層推導的內容用一張圖來總結一下：

3.4 索引矛盾點

索引核心矛盾點: 根據前面的分析，每條記錄是變長的，所以需要每條記錄都維護一個索引項。變長、變長、變長，我們能從變長這個維度切入做一些改進或者優化嗎？既然每條記錄的長度我們無法控制，那是否可以將磁碟轉化一下呢？

我們如果將磁碟劃分成一段一段的固定大小的連續塊，對於每一塊的話，我們記錄一個塊編號no來區分不同的塊，假設我們的塊大小是100個位元組，那麼第0塊對應的範圍是0_{99，第1塊對應的是100}199，依次類推。做了這樣的改變後會發生什麼呢？我們詳細分析一下。

將磁碟劃分成一個一個的固定大小連續塊後，每個塊內仍然保留原先過程中的兩大特性：數據有序並且順序寫。大致的結果如下圖所以：

這樣改造以後，關鍵我們看看怎麼保證讀寫呢？

我們先假設我們的塊空間足夠大，這樣的話就能避免出現一個塊存不下一條記錄的問題。

正常情況下，我們的一個塊會保存多條記錄，並且塊內的記錄是有序存儲的。我們在讀取一條記錄的時候，一條記錄肯定是位於其中一塊上，首先我們得解決這個定位問題。當定位到具體的塊後，將當前塊的數據從磁碟載入到記憶體中，塊內部的數據是有序存儲的，那自然就可以通過二分的方式來找到我們的具體數據對應的索引項了。最後再根據索引項來讀取數據即可。同理寫的過程雖然對外來看是對單條記錄進行寫，但內部是按照塊作為單位來寫磁碟。

那問題就轉化成了如何確定一條記錄保存在哪一塊上了？

針對這個問題，我們就需要確定一塊上具體存儲的多條記錄的具體範圍。例如第0塊保存的是id從0_{10的記錄；第1塊保存的是id從11}23的記錄。等等

這樣的話，當查詢id為7的記錄時，我們就很快可以知道該條記錄存儲在第0塊上，然後再從第0塊內部查找具體id為7的記錄的索引項，最後再讀取數據。

怎麼確定呢？自然就需要在原先只保存一個塊編號no的基礎上，再多保存兩個資訊：該塊保存的記錄最小值min、該塊保存的記錄的最大值max。

每一塊都對應這樣一個三元組block->(no,min,max)。
這個三元組表達的含義是：第no塊保存的記錄範圍是min~max

我們仔細再回想一下，其實這個三元組還是有改進空間的。因為我們寫入的時候，每個塊都是順序寫的並且塊內數據是有序的，塊間也是有序的。那也就是說：對於第i塊而言，第i塊存儲的記錄範圍就是第i塊的最小值拼接上第i+1塊的最小值。其根本原因也就是存儲的時候塊間是有序的。那進一步我們就可以將上述三元組簡化成一個二元組了block->(no,min)。同時附加保證每塊之間保存的數據是邏輯有序的。

前面啰里啰嗦說了一大堆，我們最後總結一下：

引入了將磁碟劃分成一個一個固定大小連續塊的概念
塊內數據仍然按照有序、順序寫存儲：塊內仍然對每條記錄保存兩個資訊：該記錄寫到磁碟的哪個位置offset、該條記錄佔多長size
塊間數據有序，每塊需要保存兩個資訊：塊編號no、該塊保存的最小記錄值min

在引入這個塊的概念後，我們看看當執行範圍查找、排序等操作時，大部分情況下可以減少IO的次數，因為一次讀取的一塊數據，而一塊中的數據包含多條記錄。如果所涉及的數據在一塊內的話，多條數據就只需要讀取一次磁碟。所以在這種場景下，性能也會有所改善。

整體大致的結構如下圖所示：

同時，我們還有兩個遺留問題需要解決:

1. 塊的大小定多大呢？

2. 塊索引存不存？怎麼存？

針對第一個問題:塊大小定多大？，我們可以辯證的來看。

如果塊大小越大，那麼一塊能保存的數據就越多，因此同等數據量級的條件下我們需要的塊就越少，近而需要維護的塊索引也就越少。但讀寫每條記錄的時候額外讀寫的空間會越大(按照塊讀寫)，因此讀寫效率越低。
如果塊大小越小，那麼一塊能保存的數據就越少，因此同等數據量級的條件下我們需要的塊就越多，近而需要維護的塊索引也就越多。但讀寫每條記錄的時候額外讀寫的空間會越小(按照塊讀寫)，因此讀寫效率越高。

到這兒總算看出來了，其實塊大小定多大就是一個折中問題。那我們怎麼來選擇呢？

別忘了，我們的數據存儲在磁碟，同時我們的應用時跑在作業系統上層，我們在這兒就想怎麼讓作業系統為我們的應用服務的更好呢？簡而言之就是更好的利用作業系統的特性，讓其發揮出最大的價值。我們每次讀寫數據都會涉及到磁碟操作，例如讀寫磁碟、刷盤等，而在數據寫到磁碟前，數據會先寫到記憶體中，在作業系統中管理記憶體時，有一個頁的概念。作業系統讀寫磁碟、刷盤時機都和管理記憶體的頁有不可分割的關係。因此那我們這塊要不為了更好利用作業系統，就將作業系統頁做為基本單位來確定塊的大小，最簡單也就是一塊大小等於一頁大小(默認4k)。更大也可以是8k、16k、32k等等。

其實到這兒，我們也就回想起來了，innodb中默認的頁大小就是16k；而在boltdb中，默認的頁大小就是作業系統的頁大小4k。

既然選擇的作業系統頁作為塊大小基本單位，那我們也不引入一個新的概念塊了，我們也稱塊為頁唄。減少大家對新名詞的理解成本。

第一個問題，到這兒我們也就解答完了。接下來我們看第二個問題。

塊索引存不存？怎麼存？

我們的答案是存，因為不存的話，當我們的應用重啟時，就需要重新建塊索引，當存儲的數據量很大時，重建塊索引是相當耗時的一件事情，在重建索引期間，可能會導致服務對外不可用。所以我們需要存塊索引。那具體怎麼存儲呢？

第一種：最簡單劃分獨立的塊來保存快索引
該種方式在mysql中也被稱為聚簇索引,索引和記錄數據存儲在一起，存儲在一個文件中。

第二種：將快索引採用單獨的文件來保存
該種方式在mysql中也被稱為非聚簇索引,索引和記錄數據分開存儲，存儲在不同的文件中。

3.5 b樹還是b+樹

到此，我們的整體推導已經差不多接近尾聲了，我們將上述推導做一個匯總，最終得到的結果如下圖所示。

上圖中每個虛線框表示一頁，其中每一頁都保存數據(數據項或者索引項)，每一頁之間也可以有指針指向確保頁之間是邏輯有序的。其次每個頁內部都包含多個數據項或者索引項，而且數據是有序存儲的。如果我們把其中的黑線去掉後，剩餘的這種結構是一種啥結構呢？

答案是:多叉樹，其中每頁可以看做一個節點，該節點內部有多項，同時一個節點可以多有個孩子節點

接下來我們再來回想個問題。現在我們可以基於這樣的結構進行讀寫了。那我們來看看，當我們讀取的時候，如果讀取的數據正好是其中某一頁保存的最小記錄，那這時候如果我們的最小記錄保存了數據的話，就可以直接返回了。而不用再往下遍歷了。如果只保存一個最小記錄關鍵字的話，那就還需要一直往下遍歷。那我們就來看看每頁中的索引項存或者不存該條記錄的原始數據會有哪些差異點呢？

根據上圖的分析，我們可以看到，如果對應的頁索引項中保存了原始數據，則它對應的就是b樹的數據結構；如果不存儲原始數據，則它對應的就是b+樹的數據結構。分析清楚了存和不存的區別，那我們到底選擇存還是不存呢？

答案是:不存，因為同樣大小的一頁，如果頁索引項存儲了額外的原始數據的話，必然一頁中存儲的頁索引個數就會減少。同時進一步會導致存儲同等數據量級的情況下，存儲時的樹的高度會比不存時高太多。而樹的高度在我們這個場景里其實對應的就是磁碟IO的次數。顯然我們要快速、高效，那就要儘可能減少不必要的磁碟IO次數。所以不存。近而，我們也就確定了我們選擇的數據結構就是b+樹了。

到此，我們就從最初的直觀思路出發，找到了在磁碟上容易維護的數據結構：b+樹。

在我們的抽象和改進中，引入了頁的概念，磁碟中按照頁的單位來組織數據，頁內部保存的數據有序存儲，頁間數據也是有序存儲。
同時在磁碟上的b+樹中，非葉子節點保存頁索引資訊。其中包括(頁編號no、該頁保存的數據最小記錄min)；葉子節點保存具體的記錄數據。

既然磁碟上選擇了b+樹存儲，那自然記憶體中也就選擇b+樹實現咯。我們來看看二者之間如何相互轉化。

記憶體中b+樹的節點對應磁碟上的一頁。記憶體中一個節點內部的多項對應磁碟上每一頁中保存每一個元素(每條記錄數據or每個頁索引項)。

這兒再強調下：我們選擇用b+樹作為索引而不是b樹作為索引的核心點在於，在存儲同等數據量級的情況下，選擇用b+樹做索引時，要比用b樹做索引。平均的磁碟IO次數要少。同時對b+樹而言，不同請求的時間複雜度都比較平均。因為每條記錄的數據都保存在葉子節點上。

3.6 總結

到此我們嘗試回答為什麼選擇b+樹作為存儲引擎索引結構這個問題就回答完畢了。我們用一張圖來總結下：

最後我們看一下數據結構的b+樹長啥樣，我們磁碟+記憶體中的b+樹又長啥樣。

下圖是數據結構中的b+樹，此處我們就不再過多解釋其b+樹的特性了。

下圖是磁碟+記憶體中最後對應的b+樹示意圖。

最後，我們在接下來的一節內容中嘗試通過回答第三個問題來我們來佐證一下我們選擇的這個方案。

4.反向論證

既然選擇了用b+樹來存儲千萬級數據量級的索引結構，那對於一個指定頁大小的存儲引擎，3層或者4層的b+樹能存儲多少條數據呢？
通過這個問題，我們再來證明下，我們選擇的方案是否能解決我們當初提到的存儲千萬級數據量級的數據這個問題。

4.1 3層、4層b+樹(innodb為例)各能存儲多少數據?

針對這個問題，我們如何做一個粗略的估算呢？

我們都知道innodb中，默認的一頁大小是16k，此處我們也就以16k來做近似的估算。

在估算前，我們需要事先假設兩個數據:

假設非葉子節點中保存的頁索引項，每一項的大小佔16個位元組。對於16k的一頁而言，大約可以存儲1000(16k/16)條索引項。
假設葉子節點中保存的每條記錄數據的平均大小為160個位元組。對於16k的一頁而言，大約可以存儲100(16k/160)條記錄。

綜上：

對於3層的b+樹而言，其所能存儲的數據量級：1000 *1000 * 100，大概10^8條

對於4層的b+樹而言，其所能存儲的數據量級：1000 * 1000 * 1000 * 100，大概10^11條

也就是說，一個3層的b+樹，在此種場景下，大約可以存儲的數據量級就在千萬級。因此該解決方案是可以解決我們最初提出來的問題的。下圖是一個簡單的總結。

4.2 總結

到此，我們也就回答完了三個問題。並通過回答這三個問題，探討了面對讀多寫少場景時選擇的b+樹存儲引擎背後的一些選型過程。值得說明的是本文純屬個人學習過程中的一點思考和琢磨。有理解或表達不正確之處還請各位指正。

Tags: 資料庫面試數據結構和演算法面試