B+樹被廣泛應用于MySQL數(shù)據(jù)庫的索引實現(xiàn)，不過并未展開細說，但是呢B+樹是一種重要的數(shù)據(jù)結構，常年出現(xiàn)在各種面試題中，這次就來一起學習下和B+樹相關的MySQL索引底層實現(xiàn)的內容。

面試官：簡單講講MySQL數(shù)據(jù)庫的索引實現(xiàn)，以及為什么這么實現(xiàn)？

這個面試題出現(xiàn)的頻率非常之高，從我自己和朋友們參加的大小廠面試都有被問過這個問題，大部分人可能看過一些網(wǎng)上的博客能說出個一二三，如果面試官沒有細問還真能混過去，但是對于細節(jié)沒能真正理解的非常透徹。

所以今天堂主檸檬就來寫寫這個話題，讓你知其然也知其所以然。寫作目標是無論你是否學過數(shù)據(jù)結構，看完都能徹底搞懂這個問題，花5分鐘來跟著學一遍看看我有沒有做到吧。

首先需要明白，數(shù)據(jù)庫索引是在存儲引擎層實現(xiàn)，常見的存儲引擎有 2 種。

InnoDB 存儲引擎：

innoDB存儲引擎支持事務，其設計目標是面向在線事務處理的應用，行鎖設計、支持外鍵，默認度操作不會產生鎖，從MySLQ 5.5.7版本開始，InnoDB存儲引擎作為默認的存儲引擎存在于MySLQ中。

MyISAM 存儲引擎：

MyISAM存儲引擎不支持事務，表鎖設計，支持全文索引，主要面向離線事務處理的數(shù)據(jù)庫應用，在InnoDB引擎成為默認引擎之前，MyISAM存儲引擎一直霸占著默認存儲引擎的位置，直到他被InnoDB取代，這是個悲傷的故事。

存儲引擎不同，索引實現(xiàn)方式也不盡相同，因此，我們先約定本文講的索引都是InnoDB存儲引擎實現(xiàn)的B+樹索引。

MySQL架構

索引由存儲引擎實現(xiàn)，那存儲引擎到底是個什么東西呢？

從我們平常使用的的角度來看，對MySQL的直觀感受是命令行的各種指令，或是一個數(shù)據(jù)庫管理工具比如SQLyog的界面點擊操作，堂主檸檬在剛接觸MySQL時就是用的SQLyon圖形界面操作，就是下面這個小海豚。

MySQL可能是世界上最流行的開源數(shù)據(jù)庫引擎，但使用基于文本的工具和配置文件管理起來可能很困難。SQLyog提供了一個完整的圖形界面，即使對于初學者來說，使用MySQL的強大功能也很簡單，SQLyog直觀的圖形用戶界面使您可以輕松管理MySQL數(shù)據(jù)庫的各個方面。

不管是使用圖形界面還是命令行，我們接觸到的都只是客戶端，MySQL作為一個軟件系統(tǒng)的架構，存儲引擎在MySQL服務端系統(tǒng)架構的什么位置呢？

總的來說，MySLQ系統(tǒng)架構分為 ?3 層，直接上圖，看下MySQL的架構劃分。

• 第一層：連接管理層。MySLQ是典型的CS模型軟件，所謂CS就是客戶端/服務端的意思，作為一個靠網(wǎng)絡連接的服務，必不可少的要有連接管理層，用于管理和維護MySQL服務端和客戶端之間的連接、鑒權等等。
• 第二層：這一層是MySQL的核心服務功能層，包括了查詢緩存、解析器、優(yōu)化器等所有跨存儲引擎的功能都在這一層實現(xiàn)，屏蔽掉存儲引擎間的差別，對上層也就是連接管理層提供統(tǒng)一的接口。
• 第三層：存儲引擎層就在這一層實現(xiàn)，負責MySQL中數(shù)據(jù)的存儲和提取，這其中有我們今天的主角InnoDB存儲引擎和它實現(xiàn)的B+樹索引。

如何指定存儲引擎類型

既然要研究innoDB的索引，那我們首先來創(chuàng)建一個使用innoDB存儲引擎的表。

MySQL目前支持的存儲引擎種類非常豐富，可以在連接MySQL客戶端，進入到命令行模式下，輸入如下命令查看當前版本MySQL提供的所有存儲引擎。

show?engines;

可以看到上圖中有包含MyISAM 和 InnoDB 這兩種常見引擎，關于這些存儲引擎的詳細介紹，可以參考MySQL的官方文檔，我放上鏈接：

https://dev.mysql.com/doc/refman/8.0/en/storage-engines.html

好了，現(xiàn)在來創(chuàng)建數(shù)據(jù)表并指定innoDB存儲引擎。

舉個栗子：創(chuàng)建表一張大佬數(shù)據(jù)表 BigOld，表中第一個字段是大佬 id 標識，第二個字段是大佬名字 name，并指定數(shù)據(jù)庫使用的存儲引擎類型ENGINE=InnoDB ，下面這條建表語句創(chuàng)建并指定了一個使用 InnoDB 存儲引擎的數(shù)據(jù)庫表。

CREATE?TABLE?BigOld?(
????id?INT,
????name?CHAR?(32),?
????PRIMARY?KEY?(id))?ENGINE=InnoDB;

當然，如果你一開始創(chuàng)建的表使用的不是InnoDB引擎，那也沒關系，還可以再創(chuàng)建表之后修改表的存儲引擎，像下面的這樣操作。

alert?table?BigOld?engine?=?InnoDB

索引

好了，經(jīng)過前面的操作，終于我們有了一個innoDB的數(shù)據(jù)表，現(xiàn)在我們可以來講講innoDB存儲引擎的索引，索引的作用當然是為了快速的存取MySQL數(shù)據(jù)庫的數(shù)據(jù)。

舉個栗子，如果把MySQL比作一個大型圖書館，其中的數(shù)據(jù)比作圖書館里的書。

你去圖書館找書，圖書館那么大我們不可能一頭扎進去，一層層、一個個書架去找想要的書，這時候我們會在圖書管理系統(tǒng)中通過圖書編號（索引）查詢到圖書所在的樓層，到了指定的樓層在通過書架上的提示找到對應區(qū)域，最終在某個書架找到想要的書，這個圖書編號就起到索引的作用，幫助我們快速找到圖書（數(shù)據(jù)）。

存儲形式

InnoDB存儲引擎用B+樹實現(xiàn)索引，說到B+樹不得不提到他的兄弟B樹，這兩者的區(qū)別比較微妙，但查詢磁盤存儲數(shù)據(jù)的性能上卻相差很大，要知道為何MySQL InnoDB 選擇B+樹而不選擇B樹做索引，我們先來假設分別用這兩種數(shù)據(jù)結構實現(xiàn)索引對比一下。

B樹索引

拿來一本數(shù)據(jù)結構的教材，我們翻開B樹的定義。一棵M階的b樹是這么定義的：

1. 定義任意非葉子結點最多只有M個兒子，且M>2；
2. 根結點的兒子數(shù)為[2, M]；
3. 除根結點以外的非葉子結點的兒子數(shù)為[M/2, M]，向上取整；
4. 非葉子結點的關鍵字個數(shù)=兒子數(shù)-1；
5. 所有葉子結點位于同一層；
6. k個關鍵字把節(jié)點拆成k+1段，分別指向k+1個兒子，同時滿足查找樹的大小關系。

看完你大概有點懵，不過沒關系，我們現(xiàn)是要對比它和B+樹在數(shù)據(jù)庫索引上的使用，不是要去手寫一個數(shù)據(jù)庫索引，只要抓住它主要的特點便于理解幫助我們理解索引原理即可，這里抓住B樹最主要的兩個特點：

1. 非葉子節(jié)點只存放「索引」和指向子節(jié)點的「指針」。
2. 葉子節(jié)點存放「索引」和「數(shù)據(jù)」，且葉子節(jié)點之間沒有關聯(lián)。

便于理解，假如在數(shù)據(jù)庫中使用B樹來做索引結構，我試著畫出這個B樹的索引結構圖，如下：

B+樹索引

看完了B樹索引實現(xiàn)，現(xiàn)在我們來用B+樹實現(xiàn)索引看看，一樣的隨便打開一本數(shù)據(jù)結構教材找到B+樹的定義，一顆M階的B+樹：

1. 有n棵子樹的非葉子結點中含有n個關鍵字（b樹是n-1個），這些關鍵字不保存數(shù)據(jù)，只用來索引，所有數(shù)據(jù)都保存在葉子節(jié)點（b樹是每個關鍵字都保存數(shù)據(jù)）。
2. 所有的葉子結點中包含了全部關鍵字的信息，及指向含這些關鍵字記錄的指針，且葉子結點本身依關鍵字的大小自小而大順序鏈接。
3. 所有的非葉子結點可以看成是索引部分，結點中僅含其子樹中的最大（或最?。╆P鍵字。
4. 通常在b+樹上有兩個頭指針，一個指向根結點，一個指向關鍵字最小的葉子結點。
5. 同一個數(shù)字會在不同節(jié)點中重復出現(xiàn)，根節(jié)點的最大元素就是b+樹的最大元素。

如果以前沒接觸過數(shù)據(jù)結構相關概念，看完估計還是不大明白，沒關系，那不是本文的重點，我們不去深究細枝末節(jié)。

我來幫你總結下，B+樹和B樹有很多相同的特點，但也有一些不同讓B+樹在查詢磁盤存儲的數(shù)據(jù)時有更好的性能（為什么？我們稍后講），最大的不同是下面兩個：

1. 「數(shù)據(jù)」只存放葉子節(jié)點上面的，非葉子節(jié)點存放「索引」和「指針」。
2. 葉子節(jié)點按大小順序通過雙向鏈表連接起來，可以像遍歷鏈表一樣遍歷整棵B+樹。

innoDB的選擇

innoDB的索引選擇用B+樹來實現(xiàn)，B樹和B+樹非常相似，為什么用B+樹不用B樹做索引呢？這就要從數(shù)據(jù)庫的存儲方式說起。

性能瓶頸

innoDB索引以B+樹形式組織存儲，我們首先要明白B+樹的每個節(jié)點不是保存在內存而是放在屬于外部存儲的「磁盤頁」中。

為什么呢？因為內存快是快，但是它貴?。《液芏鄶?shù)據(jù)不是熱點數(shù)據(jù)，十天半個月都用不上，完全沒必要都放在內存里面，想想看如果淘寶會把那種萬億級別的交易訂單數(shù)據(jù)如果都存在內存中嗎，馬爸爸雖然有錢也不至于這么奢侈。

重點關注下這里所說的磁盤頁，的大小每個系統(tǒng)可能不一樣，就堂主所用的這個Centos Linux系統(tǒng)來說，通過下面的命令查看磁盤頁大小為 4096B 也就是 4KB

[lemon/test]$?getconf?PAGE_SIZE
4096

這些磁盤數(shù)據(jù)頁如果是B+樹的葉子節(jié)點，那就保存著關鍵字和數(shù)據(jù)（就是我們用 INSERT 語句塞進數(shù)據(jù)庫的那些數(shù)據(jù)）。

如果是非葉子節(jié)點那就保存著關鍵字和指針（指向子節(jié)點的指針），從上圖B+樹實現(xiàn)的索引示意圖也可以看到這兩種存儲形式的差別。

內存VS外存

當我們在MySQL InnoDB中執(zhí)行 select 查詢語句，這個查找數(shù)據(jù)的過程是這樣的：

• 沿著B+樹索引來查找一個給定關鍵字（或者范圍關鍵字）的所在的數(shù)據(jù)行。

• 找到數(shù)據(jù)行所在的磁盤頁，把這個磁盤頁加載到內存中。

• 在內存中進行查找（比如二分查找），最終得到目標數(shù)據(jù)行內容。

我們知道磁盤是外部存儲設備，那MySQL數(shù)據(jù)庫查找的時候將磁盤中數(shù)據(jù)讀入內存這個過程是非常緩慢的，對于機械硬盤具體來說，從磁盤加載數(shù)據(jù)需要經(jīng)過尋道、旋轉以及傳輸?shù)倪@些過程，時間花費至少是幾十毫秒，作為對比，DDR4內存尋址時間僅為6ns左右。

內存讀取速度是磁盤讀取速度的100萬倍！雖然現(xiàn)在固態(tài)硬盤的速度提升了很多，但和內存比起來還是有很大的差距，所以要盡量減少數(shù)據(jù)庫對磁盤數(shù)據(jù)頁的隨機IO操作。

由于磁盤讀寫耗時的原因，在高并發(fā)系統(tǒng)中關系型數(shù)據(jù)庫MySQL會成為系統(tǒng)性能瓶頸。

在高并發(fā)服務中幾十毫秒的的耗時太久了，假設10ms處理一個請求，那1秒處理100個 QPS=100 對比秒殺這一類的場景這個吞吐量完全是不夠用的，這也是現(xiàn)在像Redis這樣的高速緩存數(shù)據(jù)庫會站在前面，為MySQL擋一刀的原因，因為Redis都是內存操作，速度非?？欤?/p>

Why B+樹？

為了更方便的說明B樹和B+樹兩種存儲結構的差異，我們來對比下兩種樹實現(xiàn)的索引上讀取數(shù)據(jù)的過程，i再來回答innoDB 引擎為什么選B+樹。

為方便對比，假設我們在B和B+樹中我們都要「查詢 1 < id < 6 之間」的所有數(shù)據(jù)行。

B樹索引

先來看下如果索引用B樹來實現(xiàn)，查找數(shù)據(jù)的流程圖：

在不考慮任何優(yōu)化的前提下，圖中綠色虛線是在B樹索引上查找數(shù)據(jù)的遍歷軌跡，來拆解一下：

1. 從索引樹根節(jié)點開始，加載磁盤頁 page1 找到第一個節(jié)點 key=1 數(shù)據(jù)行（1，小林）不符合。
2. 繼續(xù)通過指針找到磁盤頁面page2，加載磁盤頁page2到內存， key=2 符合，讀取數(shù)據(jù)行 （2, 石頭）
3. 重新加載磁盤頁 page1 找到第二個節(jié)點 key=3符合，讀取數(shù)據(jù)行（3，軒轅）。
4. 繼續(xù)通過指針加載磁盤頁 page4 到內存，key=4 符合，讀取數(shù)據(jù)行（4，小北）。
5. 重新加載磁盤頁 page1 找到第三個節(jié)點 key=5 符合，讀取數(shù)據(jù)行（5，why神）。

數(shù)一數(shù)上面的5個步驟有幾個「加載磁盤頁」字眼，5個，還記得上面我們說的：**加載磁盤數(shù)據(jù)非常費時！**這種隨機大量的磁盤IO造成了B樹索引的的性能瓶頸，使其與innoDB索引無緣。

B+樹索引

再來看下現(xiàn)在innoDB的用B+樹的實現(xiàn)方案吧，同樣的查詢條件，還是畫出數(shù)據(jù)查找的遍歷軌跡：

在不考慮任何優(yōu)化的前提下，圖中綠色虛線是在innoDB B+樹索引上查找數(shù)據(jù)的遍歷軌跡，同樣來拆解一下：

1. 從索引樹根節(jié)點開始，加載磁盤頁 page1 找到第一個節(jié)點 key=1不符合，繼續(xù)往下搜索。
2. 通過指針找到磁盤頁page2, 加載磁盤頁page2 到內存，其中存放了key=1、2的數(shù)據(jù)行，讀取符合條件數(shù)據(jù)行。
3. 由于葉子節(jié)點間組成雙向鏈表，直接順著page2 加載磁盤頁page3 、 加載磁盤頁page4，讀取其中符合條件的數(shù)據(jù)行。

這其中涉及了4次加載磁盤頁的操作，看起來只是比上面的B樹少了一次，但這是在我的簡單例子，為了便于理解數(shù)據(jù)量比較少。

實際應用中B+確實能夠減少大量的磁盤IO，從而大大提高查詢性能，而且由于B+樹根節(jié)點的數(shù)據(jù)已經(jīng)是排序好的雙向鏈表，我們可以像鏈表一樣遍歷所有數(shù)據(jù)，非常適合范圍查找和排序操作！

再談B樹

B樹索引并非一無是處。雖然我們前面詳細對比了在innoDB中使用B+樹索引的優(yōu)勢，但不要以為B樹就一無是處了，一種數(shù)據(jù)結構被設計出來肯定是有使用場景的需求，不然誰也不會閑著沒事折騰出一個東西，你說對吧。

事實上B樹也被用于實現(xiàn)數(shù)據(jù)庫索引，只不過不是在MySQL上。在MongoDB的索引設計上就使用了B樹做索引，什么是MongoDB呢？我不做過多介紹，感興趣的可以下來了解一下，下面這段話來自MongoDB 英文Wiki

MongoDB is a cross-platform document-oriented database program. Classified as a NoSQL database program, MongoDB uses JSON-like documents with optional schemas. MongoDB is developed by MongoDB Inc. and licensed under the Server Side Public License (SSPL).

只需要知道它和MySQl不同，MongoDB是一種文檔型的非關系型數(shù)據(jù)庫，被劃分為NoSql數(shù)據(jù)庫，使用類似JSON的語法存儲文檔，熟悉Redis的同學應該很容易理解NoSQL的含義。

因為關系型數(shù)據(jù)庫比如 MySQL 經(jīng)常需要執(zhí)行遍歷和范圍查找的操作，B+樹的特點正是迎合了這樣的需求。但是在MongoDB這樣的NoSLQ數(shù)據(jù)庫中，在數(shù)據(jù)表的設計層面就決定了不會有太多的遍歷和范圍查找，基本就是一個鍵對應一個值的單一查詢。

在MongoDB上的查找如果用B+樹來實現(xiàn)索引的話，由于非葉子節(jié)點不存放數(shù)據(jù)，每次查詢必須搜索到B+樹的葉子節(jié)點才能獲取到數(shù)據(jù)，時間復雜度是固定的樹的高度 log n；

而如果用B樹實現(xiàn)索引，由于每個節(jié)點都可以存放數(shù)據(jù)，幸運的話有可能不必找到葉子節(jié)點就能取得數(shù)據(jù)，復雜度更低，再來看下B樹實現(xiàn)的索引，如果換作是 MongoDB 你仔細品。

雖然沒有MySQL的使用普及程度那么高，用B樹實現(xiàn)索引的MongoDB很多大公司也都有使用。

脫離業(yè)務場景談具體實現(xiàn)都是耍流氓。正是由于關系型數(shù)據(jù)庫和非關系型數(shù)據(jù)庫應用場景的不同，工程實現(xiàn)上最終會在損失和收益中找到平衡點，使得B樹和B+樹在不同數(shù)據(jù)庫上有各自的用武之地。

所以下次面試和面試官夸MySQL B+樹索引好處的時候，注意別把 B 樹噴的太慘，以防面試官來個回馬槍，讓你說說為啥MongoDB還要用B樹來實現(xiàn)索引？這時候雖然你心里笑開了花，還是要假裝再思考下，愣著干嘛，接著繼續(xù)吹B樹啊。