為什么磁盤存儲(chǔ)引擎用 b+樹來作為索引結(jié)構(gòu)？
在數(shù)據(jù)庫或者存儲(chǔ)的世界里，存儲(chǔ)引擎的角色一直處于核心位置。往簡(jiǎn)單了說，存儲(chǔ)引擎主要負(fù)責(zé)數(shù)據(jù)如何讀寫。往復(fù)雜了說，怎么快速、高效的完成數(shù)據(jù)的讀寫，一直是存儲(chǔ)引擎要解決的關(guān)鍵問題。在絕大部分介紹、講解存儲(chǔ)引擎的書籍或者文章里，大家都默認(rèn)了讀多寫少的磁盤存儲(chǔ)引擎采用的就是 b+樹，而極少有人來剖析選擇 b+樹作為索引結(jié)構(gòu)的背后，到底有著怎樣的思考和權(quán)衡？為了解答上述問題，本文嘗試從一個(gè)新的視角和大家討論：
在處理讀多寫少的場(chǎng)景下，為什么基于磁盤的存儲(chǔ)引擎會(huì)選擇用 b+樹來作為索引結(jié)構(gòu)？
希望在看完本文后，讀者能對(duì)該問題有一個(gè)全新的認(rèn)識(shí)和屬于自己的答案。限于個(gè)人能力有限，有表述、理解不正當(dāng)之處希望批評(píng)指正。
本文的內(nèi)容主要以問答方式展開，層層遞進(jìn)分析、解決問題，本文涉及內(nèi)容會(huì)圍繞下面三個(gè)問題展開。在開始閱讀本文內(nèi)容前，大家不妨先嘗試自己回答下面三個(gè)問題！
為了減少讀者的疑惑，在開始本文的正式內(nèi)容之前，先和讀者做一些簡(jiǎn)要的關(guān)鍵名詞的解釋和說明：
1.存儲(chǔ)引擎： 存儲(chǔ)引擎是一個(gè)很廣的范疇，有處理讀多寫少的基于頁結(jié)構(gòu)的 b+樹存儲(chǔ)引擎，也有后起之秀基于日志結(jié)構(gòu)(lsm 樹)的存儲(chǔ)引擎。在本文中提到的存儲(chǔ)引擎，如沒有特殊說明，都指的是針對(duì)處理讀多寫少場(chǎng)景的基于磁盤的 b+樹存儲(chǔ)引擎，這類存儲(chǔ)引擎在關(guān)系型數(shù)據(jù)庫中出現(xiàn)的頻率較高，經(jīng)典代表就是 mysql 中的 innodb，此外 golang 編寫的 boltdb 也屬于本文討論的范疇。
2.擴(kuò)展內(nèi)容： 文中標(biāo)識(shí)為擴(kuò)展內(nèi)容的章節(jié)，對(duì)于基礎(chǔ)相對(duì)較好的讀者這些內(nèi)容可以選擇性閱讀，不讀也不會(huì)造成本文核心內(nèi)容理解困難；對(duì)于基礎(chǔ)相對(duì)一般的小伙伴，可以選擇性的進(jìn)行閱讀。
下面我們先嘗試回答前兩個(gè)問題，因?yàn)榍皟蓚€(gè)問題可以算作是一大類問題。第一個(gè)問題主要在于數(shù)據(jù)結(jié)構(gòu)的選型。第二個(gè)問題主要在于因果關(guān)系的區(qū)分。
1.背景
這個(gè)問題的答案，我們從哪里開始說起呢？想之又想，只有搞清楚了整體的一個(gè)背景，我們才能知道當(dāng)時(shí)的工程師面臨的怎樣的一個(gè)問題。近而，我們才能嘗試從根上解釋這個(gè)問題。從整體的大的環(huán)境來看，他們要解決的問題主要面臨的以下四個(gè)主要特點(diǎn)：
1. 處理讀多寫少的場(chǎng)景
2. 關(guān)系型數(shù)據(jù)庫按照行組織
3. 存儲(chǔ)千萬級(jí)量級(jí)數(shù)據(jù)
4. 采用性價(jià)比高的存儲(chǔ)
接下來我們一一對(duì)其進(jìn)行解釋，因?yàn)槿绻鲜鏊膫€(gè)背景如果不成立的話，說明我們一開始的出發(fā)點(diǎn)就錯(cuò)了，后面的回答都是無稽之談。
1.1 處理讀多寫少的場(chǎng)景
提起這個(gè)話題，我們就不得不說，在互聯(lián)網(wǎng)發(fā)展起來的早期，大部分的系統(tǒng)主要處理的是讀多寫少的場(chǎng)景。例如早期的 bbs 內(nèi)容、博客、門戶網(wǎng)站、電商的商品入庫等等，這些場(chǎng)景都可以劃分為讀多寫少。他們通過有限次的寫操作將數(shù)據(jù)寫入到數(shù)據(jù)庫中，然后供用戶多次瀏覽、閱讀。發(fā)展到今天的互聯(lián)網(wǎng)，面向用戶的很多系統(tǒng)仍然是屬于讀多寫少的范疇。所以讀多寫少這是一個(gè)早期存儲(chǔ)引擎在數(shù)據(jù)讀寫時(shí)面臨的最大的背景。
1.2 關(guān)系型數(shù)據(jù)庫按照行組織
早期的時(shí)候存儲(chǔ)引擎這個(gè)概念主要還是出現(xiàn)在關(guān)系型數(shù)據(jù)庫中，大部分人接觸這個(gè)概念估計(jì)也是因?yàn)?mysql，mysql 中經(jīng)常提到存儲(chǔ)引擎這個(gè)詞。在關(guān)系型數(shù)據(jù)庫中，數(shù)據(jù)往往通過數(shù)據(jù)庫->表(多列)-->行 的方式來組織。最終落到存儲(chǔ)引擎這一層時(shí)，數(shù)據(jù)已經(jīng)按照行的格式來組織了。廣義來看其實(shí)也就是類似于 key-value 的存儲(chǔ)了，只不過在關(guān)系型數(shù)據(jù)庫中，到達(dá)存儲(chǔ)引擎這層的 value 是一行記錄按照指定的格式來扁平化組織而成，具體的格式大同小異。這兒不再展開贅述。大家可以自行搜索資料查閱，此處主要是拋出來在關(guān)系型數(shù)據(jù)庫中數(shù)據(jù)按照行格式來存儲(chǔ)這個(gè)背景。
為了方便介紹，在后續(xù)的內(nèi)容中，存儲(chǔ)引擎存儲(chǔ)的數(shù)據(jù)我們就統(tǒng)一按照 key-value 來討論了。此處的 key 大家暫且可以直觀的理解為主鍵。
1.3 存儲(chǔ)千萬級(jí)量級(jí)數(shù)據(jù)
隨著互聯(lián)網(wǎng)的迅速發(fā)展，數(shù)據(jù)存儲(chǔ)的量級(jí)日益增長(zhǎng)，很快就達(dá)到了存儲(chǔ)千萬級(jí)量級(jí)數(shù)據(jù)這個(gè)量級(jí)。很明顯這個(gè)背景從需求的角度看，其實(shí)是屬于不斷迭代的過程。不可能初期互聯(lián)網(wǎng)一起來，馬上就面臨這個(gè)量級(jí)。但是我們也知道在計(jì)算機(jī)軟件的世界中，可擴(kuò)展性是大家耳熟能詳?shù)脑~語。所以在設(shè)計(jì)存儲(chǔ)引擎時(shí)，自然而然肯定會(huì)考慮這個(gè)問題。所以此處，我們將存儲(chǔ)千萬級(jí)數(shù)據(jù)量級(jí)這個(gè)作為第三個(gè)背景。
1.4 采用性價(jià)比高的存儲(chǔ)
接著第三個(gè)背景，自然而然就引出了數(shù)據(jù)存儲(chǔ)在哪里的問題。回答這個(gè)問題，必須就得引出一個(gè)成本問題了。如果不考慮成本來存儲(chǔ)，那自然問題就簡(jiǎn)化了。但是千萬級(jí)量級(jí)的數(shù)據(jù)存儲(chǔ)時(shí)，有了成本的限制，就得思考了。
我們的目標(biāo)是要找到一個(gè)成本相對(duì)廉價(jià)，但又能支持千萬級(jí)數(shù)據(jù)量級(jí)的存儲(chǔ)介質(zhì)。
對(duì)于計(jì)算機(jī)中，存儲(chǔ)數(shù)據(jù)的媒介整體可以分為兩大類：
1.易失性存儲(chǔ)： 典型代表內(nèi)存
2.非易失性存儲(chǔ)： 典型代表硬盤(磁盤)，尤其是早期的機(jī)械硬盤
關(guān)于二者的詳細(xì)對(duì)比，大家可以參考下圖：
首先， 通過上圖的對(duì)比，我們大致可以確定了，我們期望的存儲(chǔ)介質(zhì)就是硬盤(主要是機(jī)械硬盤)了。因?yàn)樗芊衔覀兯鶎ふ业膸讉€(gè)特點(diǎn)。但我們都知道硬盤雖然符合我們的要求，但硬盤有著它先天結(jié)構(gòu)的限制。訪問磁盤的速度要比訪問內(nèi)存慢的多。
到這兒也就不得不提一下，關(guān)于機(jī)械硬盤它的構(gòu)成了。關(guān)于機(jī)械硬盤的簡(jiǎn)單介紹，我們?cè)谙旅娴臄U(kuò)展內(nèi)容中進(jìn)行簡(jiǎn)要介紹，大家感興趣可以進(jìn)行閱讀，已經(jīng)掌握的讀者可以直接跳過這部分虛線框中的內(nèi)容。
擴(kuò)展內(nèi)容
上圖關(guān)于磁盤介紹的圖片摘自本篇文章。
普通的機(jī)械硬盤讀寫數(shù)據(jù)主要是通過移動(dòng)磁頭到對(duì)應(yīng)的磁道，然后再旋轉(zhuǎn)磁頭到對(duì)應(yīng)的扇區(qū)。最后進(jìn)行移動(dòng)磁頭進(jìn)行讀寫數(shù)據(jù)。
簡(jiǎn)單說：一次硬盤數(shù)據(jù)讀寫主要包括三大部分耗時(shí)：尋道時(shí)間、旋轉(zhuǎn)時(shí)間、傳輸時(shí)間。而在這其中尋道時(shí)間主要占大頭，主要是因?yàn)榇蓬^的移動(dòng)主要是馬達(dá)通過驅(qū)動(dòng)磁臂近而移動(dòng)磁頭，這個(gè)運(yùn)動(dòng)屬于機(jī)械運(yùn)動(dòng)，所以速度相對(duì)較慢。
對(duì)磁盤而言，磁盤的訪問肯定是要比內(nèi)存慢的。但是在磁盤訪問時(shí)，又有兩種訪問方式：
1. 隨機(jī) IO
2. 順序 IO
順序 IO 的訪問速度要遠(yuǎn)遠(yuǎn)快于隨機(jī) IO，其根本原因是：順序 IO 主要減少了磁頭的移動(dòng)頻率，也就是減少了尋道時(shí)間。所以它的性能要比隨機(jī) IO 要快很多。
由于篇幅有限，關(guān)于硬盤的介紹我們就不過多展開了，不然就跑題了。有了上述的知識(shí)，我們就足以開展我們后續(xù)的內(nèi)容了。關(guān)于硬盤的詳細(xì)內(nèi)容介紹，大家可以自行找其他資料學(xué)習(xí)或者點(diǎn)擊本篇文章進(jìn)行閱讀。下面我們繼續(xù)介紹我們的主要內(nèi)容。
其次，我們既然選擇了硬盤做存儲(chǔ)媒介，那就必須想辦法克服這個(gè)問題。下面這張圖詳細(xì)描述了內(nèi)存訪問速度和磁盤訪問速度的對(duì)比結(jié)果。
下面我們簡(jiǎn)單總結(jié)下，拋出我們?cè)谶@塊得出的結(jié)論：
結(jié)論 1 可以參考擴(kuò)展內(nèi)容詳細(xì)了解。
1.磁盤訪問時(shí)間：尋道時(shí)間+旋轉(zhuǎn)時(shí)間+傳輸時(shí)間：
尋道時(shí)間：8ms~12ms
旋轉(zhuǎn)時(shí)間：7200 轉(zhuǎn)/min：半周 4ms
傳輸時(shí)間：50M/s，約 0.3ms
2.磁盤隨機(jī) IO ? 磁盤順序 IO ≈ 內(nèi)存隨機(jī) IO ? 內(nèi)存順序 IO
3.機(jī)械磁盤和固態(tài)硬盤構(gòu)成：
機(jī)械硬盤： 電磁存儲(chǔ)，通過電磁信號(hào)轉(zhuǎn)變來控制讀寫，磁頭機(jī)械臂移動(dòng)
固態(tài)硬盤： 半導(dǎo)體存儲(chǔ)，用固態(tài)電子存儲(chǔ)芯片陣列、由控制單元和存儲(chǔ)單元組成，內(nèi)部由 閃存顆粒組成。速度較
1.5 總結(jié)
本節(jié)主要交代了 4 個(gè)大的背景，下面再和大家回顧一下。
1. 處理讀多寫少的場(chǎng)景
2. 關(guān)系型數(shù)據(jù)庫按照行組織
3. 存儲(chǔ)千萬級(jí)量級(jí)數(shù)據(jù)
4. 采用性價(jià)比高的存儲(chǔ)
最后我們結(jié)合實(shí)際的場(chǎng)景選擇以硬盤這種介質(zhì)來存儲(chǔ)數(shù)據(jù)，同時(shí)在存儲(chǔ)引擎層，數(shù)據(jù)按照抽象層面的 key-value 來組織讀取和寫入。了解了大的背景，下面得了解我們的目標(biāo)是啥了。沒有目標(biāo)就沒有方向，搞清楚目標(biāo)對(duì)我們至關(guān)重要。
2.目標(biāo)
在第一節(jié)中，我們介紹了四大基本背景。并分析出來了我們最終需要采取硬盤來存儲(chǔ)數(shù)據(jù)。在本節(jié)中，我們將重點(diǎn)關(guān)注我們的要達(dá)到的目標(biāo)，只有明確了目標(biāo)，我們才能更好的進(jìn)行自頂向下分解任務(wù)并解決問題。
在介紹我們的目標(biāo)前，我們先來看看我們?cè)?strong>基于磁盤存儲(chǔ)數(shù)據(jù)的條件下，一次常規(guī)的用戶請(qǐng)求大概是怎樣的？
2.1 常規(guī)的一次用戶請(qǐng)求響應(yīng)過程
我們都知道，我們的數(shù)據(jù)存儲(chǔ)在硬盤上，因此當(dāng)用戶的請(qǐng)求(讀/寫)進(jìn)來后，首先會(huì)到操作系統(tǒng)管理的內(nèi)存中，在內(nèi)存中進(jìn)行一些邏輯處理，然后 cpu 會(huì)發(fā)送指令從硬盤讀取數(shù)據(jù)到內(nèi)存中，最后就會(huì)響應(yīng)上層用戶(讀：讀取的數(shù)據(jù)、寫：寫數(shù)據(jù)是否成功等)。
上面描述的一個(gè)大概的流程。從中我們可以看到整個(gè)過程經(jīng)歷三個(gè)階段：
請(qǐng)求過程：
用戶請(qǐng)求->內(nèi)存->硬盤
響應(yīng)過程:
響應(yīng)用戶<-內(nèi)存<-硬盤
理清楚了整個(gè)用戶的請(qǐng)求響應(yīng)流程后，我們就來看看，我們最終的目標(biāo)是啥呢？
2.2 目標(biāo)
其實(shí)互聯(lián)網(wǎng)的應(yīng)用，有個(gè)潛移默化的潛規(guī)則，那就是高效、快速，對(duì)存儲(chǔ)引擎而言也不例外，我們的目標(biāo)就是要在上述背景下進(jìn)行快速、高效的數(shù)據(jù)讀寫請(qǐng)求。
問題來了！快速、高效這都屬于定性分析的一類描述用語，怎么樣算快速呢？怎么樣又算高效呢？怎么定量分析這個(gè)需求呢？
到這兒，大伙兒可以想想如果這個(gè)需求是你來負(fù)責(zé)的，那么你會(huì)從哪些角度出發(fā)來思考這個(gè)問題呢？
這個(gè)問題應(yīng)該難不倒聰明的你，還記得數(shù)據(jù)結(jié)構(gòu)與算法里有一個(gè)指標(biāo)嗎！時(shí)間復(fù)雜度，這就是一個(gè)很重要的核心指標(biāo)呀，衡量數(shù)據(jù)結(jié)構(gòu)或者算法處理效率的一個(gè)關(guān)鍵指標(biāo)。我們想想，我們的數(shù)據(jù)最終要存儲(chǔ)，怎么存儲(chǔ)，怎么組織，這不就涉及到選擇哪種數(shù)據(jù)結(jié)構(gòu)了嗎！那上述問題我們也就進(jìn)一步延伸到了，采用哪種數(shù)據(jù)結(jié)構(gòu)來組織我們的數(shù)據(jù)，并盡可能使得其讀寫比較快速、高效。具體的快速、高效通過時(shí)間復(fù)雜度來判定。
2.3 總結(jié)
本小節(jié)我們對(duì)前面介紹的兩部分內(nèi)容通過一個(gè)框圖來進(jìn)行總結(jié)回顧。具體的選擇哪種數(shù)據(jù)結(jié)構(gòu)這個(gè)問題我們放到下一節(jié)來進(jìn)行介紹。
3.數(shù)據(jù)結(jié)構(gòu)選型
在 2.2 節(jié)提到，我們最終將快速、高效讀寫這個(gè)問題轉(zhuǎn)化成了選擇采用哪種數(shù)據(jù)結(jié)構(gòu)來組織數(shù)據(jù)、并通過其時(shí)間復(fù)雜度來定量的判定我們的目標(biāo)。下面我們就從數(shù)據(jù)結(jié)構(gòu)這個(gè)方面著手看看。
3.1 數(shù)據(jù)結(jié)構(gòu)方案對(duì)比
我們?cè)敿?xì)的分析下，快速、高效那也就意味著讀寫的平均時(shí)間復(fù)雜度，要盡可能的低。在數(shù)據(jù)結(jié)構(gòu)中我們學(xué)習(xí)過很多的數(shù)據(jù)結(jié)構(gòu)，例如：平均時(shí)間復(fù)雜度是 O(1)的數(shù)據(jù)結(jié)構(gòu)，典型代表是哈希表(hash table)。哈希表主要在點(diǎn)對(duì)點(diǎn)的映射讀寫上沖突比較低時(shí)效率很高，但其原生的數(shù)據(jù)結(jié)構(gòu)在面對(duì)范圍查找、排序等操作時(shí)時(shí)間復(fù)雜度會(huì)相對(duì)較高，這也算是哈希表的一大缺陷。
其次平均時(shí)間復(fù)雜度比 O(1)稍慢的是平均時(shí)間復(fù)雜度為 O(logn)，這類數(shù)據(jù)結(jié)構(gòu)有二叉查找/排序樹(bst tree)、平衡二叉樹(avl tree)、紅黑樹(rb tree)、b 樹(b/b- tree)、b+樹(b+ tree)、跳表(skiplist)等。他們天然就支持排序、范圍查找操作；再其次比 O(logn)還慢的時(shí)間復(fù)雜度為 O(n)、O(n^2)等等。O(n)的平均時(shí)間復(fù)雜度的典型代表有數(shù)組。其他類型我們這兒就不過多展開了。
下圖是我們根據(jù)平均時(shí)間復(fù)雜度依次從O(1)->O(logn)->O(n)->... 由快到慢的一個(gè)對(duì)比結(jié)果。
我們都知道互聯(lián)網(wǎng)的應(yīng)用中，排序、范圍查找是一個(gè)再普遍不過的需求了。例如在電商網(wǎng)站購物時(shí)，大部分用戶都會(huì)下意識(shí)的點(diǎn)擊按照銷量從高到低排序；再比如在門戶新聞網(wǎng)站上，我們會(huì)關(guān)注過去一周某個(gè)新聞被閱讀的次數(shù)，按照時(shí)間來排序；再比如推薦系統(tǒng)中，我們會(huì)按照內(nèi)容的一類或者多類屬性對(duì)物品進(jìn)行排序，還有很多很多例子。所以我們?cè)谶x擇數(shù)據(jù)結(jié)構(gòu)時(shí)，必須考慮支持范圍查找、排序等操作。
基于這點(diǎn)的話，看來哈希表就不太符合我們的需求了。那我們退而求其次，再來看看 O(logn)的時(shí)間復(fù)雜度中，我們選擇哪種數(shù)據(jù)結(jié)構(gòu)呢？這幾種數(shù)據(jù)結(jié)構(gòu)粗略一看貌似都能滿足我們的需求，同時(shí)上述幾種數(shù)據(jù)結(jié)構(gòu):二叉查找/排序樹(bst tree)、平衡二叉樹(avl tree)、紅黑樹(rb tree)、b 樹(b/b- tree)、b+樹(b+ tree)、跳表(skiplist) 在內(nèi)存中都可以實(shí)現(xiàn)，我們?nèi)绾芜x擇呢？直觀來看我們選哪種好像都可以，但我們別忘了，我們的數(shù)據(jù)最終要落到硬盤，既然這兒得不出結(jié)論，那我們就從硬盤的維度來看看，硬盤上哪種數(shù)據(jù)結(jié)構(gòu)好維護(hù)呢？
3.2 目光轉(zhuǎn)向磁盤
根據(jù)前面的介紹，我們的數(shù)據(jù)流向分為三個(gè)階段，以讀取操作舉例：磁盤->內(nèi)存->用戶。既然這樣的話，我們的直觀想法是，如果能在內(nèi)存和硬盤這兩種介質(zhì)上維護(hù)同一種數(shù)據(jù)結(jié)構(gòu)，那就最完美了，這樣當(dāng)用戶請(qǐng)求進(jìn)來后，從磁盤加載數(shù)據(jù)后，可以直接加載到內(nèi)存中，然后做一些處理就返回用戶了。如果直觀想法走不通的話(找不到這樣一種數(shù)據(jù)結(jié)構(gòu))。那我們就只能按照間接思路來出發(fā)了，硬盤上維護(hù)一種數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)我們的數(shù)據(jù)，內(nèi)存中選擇另外一種數(shù)據(jù)結(jié)構(gòu)保存數(shù)據(jù)。當(dāng)從硬盤讀取數(shù)據(jù)到內(nèi)存中時(shí)，中間做一層轉(zhuǎn)換。間接思路這種做法是下策，因?yàn)橹虚g數(shù)據(jù)的轉(zhuǎn)換避免不了會(huì)引入一些性能的損耗。
那就先按照直觀想法出發(fā)來找找看，是否存在這樣一類數(shù)據(jù)結(jié)構(gòu)呢？
3.3 直觀思路出發(fā)
我們先想想，既然我們的目標(biāo)仍然是快速、高效讀寫，那對(duì)應(yīng)到磁盤上，怎么做到對(duì)磁盤快速、高效讀寫呢？
根據(jù)前面的鋪墊介紹，大伙應(yīng)該都知道了那就盡可能的利用磁盤的順序 IO唄。提到順序 IO，腦子里第一時(shí)間蹦出來的自然就是追加寫，因?yàn)檫@種方式就是一種典型的順序?qū)?、順?IO，性能挺高的。我們假設(shè)用戶每個(gè)寫請(qǐng)求進(jìn)來，都采用追加寫的方式來保存數(shù)據(jù)。在這種方式下寫操作是快了、高效了。那怎么來讀呢？
根據(jù)前面的介紹，數(shù)據(jù)是按照 key-value 來扁平化存儲(chǔ)的。每條記錄長(zhǎng)度各不相同，既然要保證讀，那就得額外保存一些信息來輔助處理用戶的讀請(qǐng)求。這些額外保存的數(shù)據(jù)，我們暫且稱為索引。我們思索一下，在這種追加寫的場(chǎng)景下，我們需要保存哪些信息才可以完成正常的讀請(qǐng)求呢？其實(shí)每條記錄我們只要知道了它寫在磁盤的哪個(gè)位置(偏移量)offset、占了多長(zhǎng) size 這兩個(gè)信息。我們就可以對(duì)其進(jìn)行讀了。簡(jiǎn)而言之，一條記錄對(duì)應(yīng)一個(gè)這樣的二元組索引信息。簡(jiǎn)單示意圖如下所以：
到這兒，高效寫可以了，維護(hù)了索引后，單個(gè)記錄的讀也可以了；但是有個(gè)問題我們得想想怎么辦？那就是我們前面提到的排序、范圍查找操作。
在這種場(chǎng)景下，每來一條記錄我們都是直接追加的，所以數(shù)據(jù)在磁盤上本身就是亂序存儲(chǔ)的，既然需要排序、范圍查找的話。那就得把磁盤上的所有記錄都加載到內(nèi)存中，然后再挨個(gè)挨個(gè)遍歷判斷，最后過濾出來滿足條件的記錄返回用戶。這種方式能實(shí)現(xiàn)功能，但顯然效率太低了。同時(shí)磁盤上存儲(chǔ)的數(shù)據(jù)可能都遠(yuǎn)遠(yuǎn)超過內(nèi)存大小了，所以這種方式根本就不可取。那有沒有辦法解決該問題呢？
我們做一點(diǎn)假設(shè)：假設(shè)我們寫磁盤的時(shí)候能保證順序?qū)懙耐瑫r(shí)，寫入的數(shù)據(jù)是有序的。比如，我們寫入了三條數(shù)據(jù)，這三條數(shù)據(jù)本身寫入的時(shí)候是排好序的，那么此時(shí)范圍查找時(shí)，我們只要定位到第一條數(shù)據(jù)，后面的數(shù)據(jù)是有序的，就可以很快進(jìn)行按序讀取了。如果假設(shè)條件成立的話，那排序、范圍查找這個(gè)問題就從根本上得到簡(jiǎn)化了。我們也就不用這么大費(fèi)周折了。我們先基于這個(gè)簡(jiǎn)單假設(shè)來看一下，在假設(shè)條件成立的情況下，我們還需要解決哪些問題呢？
在這種模式下，我們?cè)L問每條記錄同時(shí)還是需要保留之前的結(jié)論：每條數(shù)據(jù)都維護(hù)一個(gè)索引項(xiàng)：offset、size。
我們要存儲(chǔ)的是千萬級(jí)量級(jí)的數(shù)據(jù)，每一條記錄都需要一個(gè)索引項(xiàng)，那么千萬條的記錄就需要維護(hù)千萬條索引項(xiàng)。問題就接著產(chǎn)生了，這千萬條的索引項(xiàng)怎么組織？選哪種數(shù)據(jù)結(jié)構(gòu)組織? 存哪里？...
針對(duì)千萬條索引項(xiàng)這個(gè)問題，我們來看看這個(gè)問題有沒有解。直觀的想法可能就分為兩大類：
能否減少索引項(xiàng)的個(gè)數(shù)？索引項(xiàng)個(gè)數(shù)減少，自然問題就好解決了
不能減少索引項(xiàng)個(gè)數(shù)的情況下，是否可以找到合理的數(shù)據(jù)結(jié)構(gòu)來組織。這兒的“合理”可以理解成：空間壓縮、優(yōu)化等等。
我們先從按照第一個(gè)思路來看看吧！
Q:為什么會(huì)產(chǎn)生千萬條索引項(xiàng)呢？
W:因?yàn)槊恳粭l記錄都需要維護(hù)一個(gè)索引項(xiàng)，我們需要保存千萬條記錄，所以就得存儲(chǔ)千萬條索引項(xiàng)。
Q:為什么每一條記錄需要維護(hù)一個(gè)索引項(xiàng)呢？
W:因?yàn)槊恳粭l記錄都是從用戶請(qǐng)求傳遞進(jìn)來的，每條記錄在按照行格式扁平化存儲(chǔ)時(shí)，長(zhǎng)度是不固定的，所以需要每一條記錄維護(hù)一個(gè)索引項(xiàng)。
到這兒我們知道了問題的核心原因了。
到這兒我們將上面層層推導(dǎo)的內(nèi)容用一張圖來總結(jié)一下：
3.4 索引矛盾點(diǎn)
索引核心矛盾點(diǎn): 根據(jù)前面的分析，每條記錄是變長(zhǎng)的，所以需要每條記錄都維護(hù)一個(gè)索引項(xiàng)。變長(zhǎng)、變長(zhǎng)、變長(zhǎng)，我們能從變長(zhǎng)這個(gè)維度切入做一些改進(jìn)或者優(yōu)化嗎？既然每條記錄的長(zhǎng)度我們無法控制，那是否可以將磁盤轉(zhuǎn)化一下呢？
我們?nèi)绻麑⒋疟P劃分成一段一段的固定大小的連續(xù)塊，對(duì)于每一塊的話，我們記錄一個(gè)塊編號(hào) no 來區(qū)分不同的塊，假設(shè)我們的塊大小是 100 個(gè)字節(jié)，那么第 0 塊對(duì)應(yīng)的范圍是 0~99，第 1 塊對(duì)應(yīng)的是 100~199，依次類推。做了這樣的改變后會(huì)發(fā)生什么呢？我們?cè)敿?xì)分析一下。
將磁盤劃分成一個(gè)一個(gè)的固定大小連續(xù)塊后，每個(gè)塊內(nèi)仍然保留原先過程中的兩大特性：數(shù)據(jù)有序并且順序?qū)?/strong>。大致的結(jié)果如下圖所以：
這樣改造以后，關(guān)鍵我們看看怎么保證讀寫呢？
我們先假設(shè)我們的塊空間足夠大，這樣的話就能避免出現(xiàn)一個(gè)塊存不下一條記錄的問題。
正常情況下，我們的一個(gè)塊會(huì)保存多條記錄，并且塊內(nèi)的記錄是有序存儲(chǔ)的。我們?cè)谧x取一條記錄的時(shí)候，一條記錄肯定是位于其中一塊上，首先我們得解決這個(gè)定位問題。當(dāng)定位到具體的塊后，將當(dāng)前塊的數(shù)據(jù)從磁盤加載到內(nèi)存中，塊內(nèi)部的數(shù)據(jù)是有序存儲(chǔ)的，那自然就可以通過二分的方式來找到我們的具體數(shù)據(jù)對(duì)應(yīng)的索引項(xiàng)了。最后再根據(jù)索引項(xiàng)來讀取數(shù)據(jù)即可。同理寫的過程雖然對(duì)外來看是對(duì)單條記錄進(jìn)行寫，但內(nèi)部是按照塊作為單位來寫磁盤。
那問題就轉(zhuǎn)化成了如何確定一條記錄保存在哪一塊上了？
針對(duì)這個(gè)問題，我們就需要確定一塊上具體存儲(chǔ)的多條記錄的具體范圍。例如第 0 塊保存的是 id 從 0~10 的記錄；第 1 塊保存的是 id 從 11~23 的記錄。等等
這樣的話，當(dāng)查詢 id 為 7 的記錄時(shí)，我們就很快可以知道該條記錄存儲(chǔ)在第 0 塊上，然后再從第 0 塊內(nèi)部查找具體 id 為 7 的記錄的索引項(xiàng)，最后再讀取數(shù)據(jù)。
怎么確定呢？自然就需要在原先只保存一個(gè)塊編號(hào) no 的基礎(chǔ)上，再多保存兩個(gè)信息：該塊保存的記錄最小值 min、該塊保存的記錄的最大值 max。
每一塊都對(duì)應(yīng)這樣一個(gè)三元組 block->(no,min,max)。
這個(gè)三元組表達(dá)的含義是：第 no 塊保存的記錄范圍是 min~max
我們仔細(xì)再回想一下，其實(shí)這個(gè)三元組還是有改進(jìn)空間的。因?yàn)槲覀儗懭氲臅r(shí)候，每個(gè)塊都是順序?qū)懙牟⑶覊K內(nèi)數(shù)據(jù)是有序的，塊間也是有序的。那也就是說：對(duì)于第 i 塊而言，第 i 塊存儲(chǔ)的記錄范圍就是第 i 塊的最小值拼接上第 i+1 塊的最小值。其根本原因也就是存儲(chǔ)的時(shí)候塊間是有序的。那進(jìn)一步我們就可以將上述三元組簡(jiǎn)化成一個(gè)二元組了 block->(no,min)。同時(shí)附加保證每塊之間保存的數(shù)據(jù)是邏輯有序的。
前面啰里啰嗦說了一大堆，我們最后總結(jié)一下：
塊內(nèi)數(shù)據(jù)仍然按照有序、順序?qū)懘鎯?chǔ)：塊內(nèi)仍然對(duì)每條記錄保存兩個(gè)信息：該記錄寫到磁盤的哪個(gè)位置 offset、該條記錄占多長(zhǎng) size
塊間數(shù)據(jù)有序，每塊需要保存兩個(gè)信息：塊編號(hào) no、該塊保存的最小記錄值 min
在引入這個(gè)塊的概念后，我們看看當(dāng)執(zhí)行范圍查找、排序等操作時(shí)，大部分情況下可以減少 IO 的次數(shù)，因?yàn)橐淮巫x取的一塊數(shù)據(jù)，而一塊中的數(shù)據(jù)包含多條記錄。如果所涉及的數(shù)據(jù)在一塊內(nèi)的話，多條數(shù)據(jù)就只需要讀取一次磁盤。所以在這種場(chǎng)景下，性能也會(huì)有所改善。
整體大致的結(jié)構(gòu)如下圖所示：
同時(shí)，我們還有兩個(gè)遺留問題需要解決:
1. 塊的大小定多大呢？
2. 塊索引存不存？怎么存？
針對(duì)第一個(gè)問題:塊大小定多大？，我們可以辯證的來看。
如果塊大小越大，那么一塊能保存的數(shù)據(jù)就越多，因此同等數(shù)據(jù)量級(jí)的條件下我們需要的塊就越少，近而需要維護(hù)的塊索引也就越少。但讀寫每條記錄的時(shí)候額外讀寫的空間會(huì)越大(按照塊讀寫)，因此讀寫效率越低。
如果塊大小越小，那么一塊能保存的數(shù)據(jù)就越少，因此同等數(shù)據(jù)量級(jí)的條件下我們需要的塊就越多，近而需要維護(hù)的塊索引也就越多。但讀寫每條記錄的時(shí)候額外讀寫的空間會(huì)越小(按照塊讀寫)，因此讀寫效率越高。
到這兒總算看出來了，其實(shí)塊大小定多大就是一個(gè)折中問題。那我們?cè)趺磥磉x擇呢？
別忘了，我們的數(shù)據(jù)存儲(chǔ)在磁盤，同時(shí)我們的應(yīng)用時(shí)跑在操作系統(tǒng)上層，我們?cè)谶@兒就想怎么讓操作系統(tǒng)為我們的應(yīng)用服務(wù)的更好呢？簡(jiǎn)而言之就是更好的利用操作系統(tǒng)的特性，讓其發(fā)揮出最大的價(jià)值。我們每次讀寫數(shù)據(jù)都會(huì)涉及到磁盤操作，例如讀寫磁盤、刷盤等，而在數(shù)據(jù)寫到磁盤前，數(shù)據(jù)會(huì)先寫到內(nèi)存中，在操作系統(tǒng)中管理內(nèi)存時(shí)，有一個(gè)頁的概念。操作系統(tǒng)讀寫磁盤、刷盤時(shí)機(jī)都和管理內(nèi)存的頁有不可分割的關(guān)系。因此那我們這塊要不為了更好利用操作系統(tǒng)，就將操作系統(tǒng)頁做為基本單位來確定塊的大小，最簡(jiǎn)單也就是一塊大小等于一頁大小(默認(rèn) 4k)。更大也可以是 8k、16k、32k 等等。
其實(shí)到這兒，我們也就回想起來了，innodb 中默認(rèn)的頁大小就是 16k；而在 boltdb 中，默認(rèn)的頁大小就是操作系統(tǒng)的頁大小 4k。
既然選擇的操作系統(tǒng)頁作為塊大小基本單位，那我們也不引入一個(gè)新的概念塊了，我們也稱塊為頁唄。減少大家對(duì)新名詞的理解成本。
第一個(gè)問題，到這兒我們也就解答完了。接下來我們看第二個(gè)問題。
塊索引存不存？怎么存？
我們的答案是存，因?yàn)椴淮娴脑挘?dāng)我們的應(yīng)用重啟時(shí)，就需要重新建塊索引，當(dāng)存儲(chǔ)的數(shù)據(jù)量很大時(shí)，重建塊索引是相當(dāng)耗時(shí)的一件事情，在重建索引期間，可能會(huì)導(dǎo)致服務(wù)對(duì)外不可用。**所以我們需要存塊索引。**那具體怎么存儲(chǔ)呢？
第一種：最簡(jiǎn)單劃分獨(dú)立的塊來保存快索引
該種方式在 mysql 中也被稱為聚簇索引,索引和記錄數(shù)據(jù)存儲(chǔ)在一起，存儲(chǔ)在一個(gè)文件中。第二種：將快索引采用單獨(dú)的文件來保存
該種方式在 mysql 中也被稱為非聚簇索引,索引和記錄數(shù)據(jù)分開存儲(chǔ)，存儲(chǔ)在不同的文件中。
3.5 b 樹還是 b+樹
到此，我們的整體推導(dǎo)已經(jīng)差不多接近尾聲了，我們將上述推導(dǎo)做一個(gè)匯總，最終得到的結(jié)果如下圖所示。
上圖中每個(gè)虛線框表示一頁，其中每一頁都保存數(shù)據(jù)(數(shù)據(jù)項(xiàng)或者索引項(xiàng))，每一頁之間也可以有指針指向確保頁之間是邏輯有序的。其次每個(gè)頁內(nèi)部都包含多個(gè)數(shù)據(jù)項(xiàng)或者索引項(xiàng)，而且數(shù)據(jù)是有序存儲(chǔ)的。如果我們把其中的黑線去掉后，剩余的這種結(jié)構(gòu)是一種啥結(jié)構(gòu)呢？
答案是:多叉樹，其中每頁可以看做一個(gè)節(jié)點(diǎn)，該節(jié)點(diǎn)內(nèi)部有多項(xiàng)，同時(shí)一個(gè)節(jié)點(diǎn)可以多有個(gè)孩子節(jié)點(diǎn)
接下來我們?cè)賮砘叵雮€(gè)問題?，F(xiàn)在我們可以基于這樣的結(jié)構(gòu)進(jìn)行讀寫了。那我們來看看，當(dāng)我們讀取的時(shí)候，如果讀取的數(shù)據(jù)正好是其中某一頁保存的最小記錄，那這時(shí)候如果我們的最小記錄保存了數(shù)據(jù)的話，就可以直接返回了。而不用再往下遍歷了。如果只保存一個(gè)最小記錄關(guān)鍵字的話，那就還需要一直往下遍歷。那我們就來看看每頁中的索引項(xiàng)存或者不存該條記錄的原始數(shù)據(jù)會(huì)有哪些差異點(diǎn)呢？
根據(jù)上圖的分析，我們可以看到，如果對(duì)應(yīng)的頁索引項(xiàng)中保存了原始數(shù)據(jù)，則它對(duì)應(yīng)的就是b 樹的數(shù)據(jù)結(jié)構(gòu)；如果不存儲(chǔ)原始數(shù)據(jù)，則它對(duì)應(yīng)的就是b+樹的數(shù)據(jù)結(jié)構(gòu)。分析清楚了存和不存的區(qū)別，那我們到底選擇存還是不存呢？
答案是:不存，因?yàn)橥瑯哟笮〉囊豁?，如果頁索引?xiàng)存儲(chǔ)了額外的原始數(shù)據(jù)的話，必然一頁中存儲(chǔ)的頁索引個(gè)數(shù)就會(huì)減少。同時(shí)進(jìn)一步會(huì)導(dǎo)致存儲(chǔ)同等數(shù)據(jù)量級(jí)的情況下，存儲(chǔ)時(shí)的樹的高度會(huì)比不存時(shí)高太多。而樹的高度在我們這個(gè)場(chǎng)景里其實(shí)對(duì)應(yīng)的就是磁盤 IO 的次數(shù)。顯然我們要快速、高效，那就要盡可能減少不必要的磁盤 IO 次數(shù)。所以不存。近而，我們也就確定了我們選擇的數(shù)據(jù)結(jié)構(gòu)就是 b+樹了。
到此，我們就從最初的直觀思路出發(fā)，找到了在磁盤上容易維護(hù)的數(shù)據(jù)結(jié)構(gòu)：b+樹。
在我們的抽象和改進(jìn)中，引入了頁的概念，磁盤中按照頁的單位來組織數(shù)據(jù)，頁內(nèi)部保存的數(shù)據(jù)有序存儲(chǔ)，頁間數(shù)據(jù)也是有序存儲(chǔ)。同時(shí)在磁盤上的 b+樹中，非葉子節(jié)點(diǎn)保存頁索引信息。其中包括(頁編號(hào) no、該頁保存的數(shù)據(jù)最小記錄 min)；葉子節(jié)點(diǎn)保存具體的記錄數(shù)據(jù)。
既然磁盤上選擇了 b+樹存儲(chǔ)，那自然內(nèi)存中也就選擇 b+樹實(shí)現(xiàn)咯。我們來看看二者之間如何相互轉(zhuǎn)化。
內(nèi)存中 b+樹的節(jié)點(diǎn)對(duì)應(yīng)磁盤上的一頁。內(nèi)存中一個(gè)節(jié)點(diǎn)內(nèi)部的多項(xiàng)對(duì)應(yīng)磁盤上每一頁中保存每一個(gè)元素(每條記錄數(shù)據(jù) or 每個(gè)頁索引項(xiàng))。
這兒再強(qiáng)調(diào)下：我們選擇用 b+樹作為索引而不是 b 樹作為索引的核心點(diǎn)在于，在存儲(chǔ)同等數(shù)據(jù)量級(jí)的情況下，選擇用 b+樹做索引時(shí)，要比用 b 樹做索引。平均的磁盤 IO 次數(shù)要少。同時(shí)對(duì) b+樹而言，不同請(qǐng)求的時(shí)間復(fù)雜度都比較平均。因?yàn)槊織l記錄的數(shù)據(jù)都保存在葉子節(jié)點(diǎn)上。
3.6 總結(jié)
到此我們嘗試回答為什么選擇 b+樹作為存儲(chǔ)引擎索引結(jié)構(gòu)這個(gè)問題就回答完畢了。我們用一張圖來總結(jié)下：
最后我們看一下數(shù)據(jù)結(jié)構(gòu)的 b+樹長(zhǎng)啥樣，我們磁盤+內(nèi)存中的 b+樹又長(zhǎng)啥樣。
下圖是數(shù)據(jù)結(jié)構(gòu)中的 b+樹，此處我們就不再過多解釋其 b+樹的特性了。
下圖是磁盤+內(nèi)存中最后對(duì)應(yīng)的 b+樹示意圖。
最后，我們?cè)诮酉聛淼囊还?jié)內(nèi)容中嘗試通過回答第三個(gè)問題來我們來佐證一下我們選擇的這個(gè)方案。
4.反向論證
既然選擇了用 b+樹來存儲(chǔ)千萬級(jí)數(shù)據(jù)量級(jí)的索引結(jié)構(gòu)，那對(duì)于一個(gè)指定頁大小的存儲(chǔ)引擎，3 層或者 4 層的 b+樹能存儲(chǔ)多少條數(shù)據(jù)呢？通過這個(gè)問題，我們?cè)賮碜C明下，我們選擇的方案是否能解決我們當(dāng)初提到的存儲(chǔ)千萬級(jí)數(shù)據(jù)量級(jí)的數(shù)據(jù)這個(gè)問題。
4.1 3 層、4 層 b+樹(innodb 為例)各能存儲(chǔ)多少數(shù)據(jù)?
針對(duì)這個(gè)問題，我們?nèi)绾巫鲆粋€(gè)粗略的估算呢？
我們都知道 innodb 中，默認(rèn)的一頁大小是 16k，此處我們也就以 16k 來做近似的估算。
在估算前，我們需要事先假設(shè)兩個(gè)數(shù)據(jù):
假設(shè)非葉子節(jié)點(diǎn)中保存的頁索引項(xiàng)，每一項(xiàng)的大小占 16 個(gè)字節(jié)。對(duì)于 16k 的一頁而言，大約可以存儲(chǔ) 1000(16k/16)條索引項(xiàng)。
假設(shè)葉子節(jié)點(diǎn)中保存的每條記錄數(shù)據(jù)的平均大小為 160 個(gè)字節(jié)。對(duì)于 16k 的一頁而言，大約可以存儲(chǔ) 100(16k/160)條記錄。
綜上：
對(duì)于 3 層的 b+樹而言，其所能存儲(chǔ)的數(shù)據(jù)量級(jí)：1000 *1000 * 100，大概 10^8 條
對(duì)于 4 層的 b+樹而言，其所能存儲(chǔ)的數(shù)據(jù)量級(jí)：1000 * 1000 * 1000 * 100，大概 10^11 條
也就是說，一個(gè) 3 層的 b+樹，在此種場(chǎng)景下，大約可以存儲(chǔ)的數(shù)據(jù)量級(jí)就在千萬級(jí)。因此該解決方案是可以解決我們最初提出來的問題的。下圖是一個(gè)簡(jiǎn)單的總結(jié)。
4.2 總結(jié)
到此，我們也就回答完了三個(gè)問題。并通過回答這三個(gè)問題，探討了面對(duì)讀多寫少場(chǎng)景時(shí)選擇的 b+樹存儲(chǔ)引擎背后的一些選型過程。值得說明的是本文純屬個(gè)人學(xué)習(xí)過程中的一點(diǎn)思考和琢磨。有理解或表達(dá)不正確之處還請(qǐng)各位指正。
轉(zhuǎn)自：為什么磁盤存儲(chǔ)引擎用 b+樹來作為索引結(jié)構(gòu)？ (qq.com)
本文使用 文章同步助手 同步
