正文
面試官：簡單講講MySQL資料庫的索引實現，以及為什麼這麼實現？
這個面試題出現的頻率非常之高，從我自己和朋友們參加的大小廠面試都有被問過這個問題，大部分人可能看過一些網上的部落格能說出個一二三，如果面試官沒有細問還真能混過去，但是對於細節沒能真正理解的非常透徹。
所以今天堂主檸檬就來寫寫這個話題，讓你知其然也知其所以然。寫作目標是無論你是否學過資料結構，看完都能徹底搞懂這個問題，花5分鐘來跟著學一遍看看我有沒有做到吧。
首先需要明白，
資料庫索引是在儲存引擎層實現
，常見的儲存引擎有 2 種。
InnoDB 儲存引擎：
innoDB儲存引擎支援事務，其設計目標是面向線上事務處理的應用，行鎖設計、支援外來鍵，預設度操作不會產生鎖，從MySLQ 5。5。7版本開始，InnoDB儲存引擎作為
預設的儲存引擎
存在於MySLQ中。
MyISAM 儲存引擎：
MyISAM儲存引擎不支援事務，表鎖設計，支援全文索引，主要面向離線事務處理的資料庫應用，在InnoDB引擎成為預設引擎之前，MyISAM儲存引擎一直霸佔著預設儲存引擎的位置，直到他被InnoDB取代，這是個悲傷的故事。
儲存引擎不同，索引實現方式也不盡相同，因此，我們先約定本文講的索引都是InnoDB儲存引擎實現的B+樹索引
。
MySQL架構
索引由儲存引擎實現，
那儲存引擎到底是個什麼東西呢？
從我們平常使用的的角度來看，對MySQL的直觀感受是命令列的各種指令，或是一個數據庫管理工具比如SQLyog的介面點選操作，堂主檸檬在剛接觸MySQL時就是用的SQLyon圖形介面操作，就是下面這個小海豚。
MySQL可能是世界上最流行的開源資料庫引擎，但使用基於文字的工具和配置檔案管理起來可能很困難。SQLyog提供了一個完整的圖形介面，即使對於初學者來說，使用MySQL的強大功能也很簡單，SQLyog直觀的圖形使用者介面使您可以輕鬆管理MySQL資料庫的各個方面。
不管是使用圖形介面還是命令列，我們接觸到的都只是客戶端，MySQL作為一個軟體系統的架構，
儲存引擎在MySQL服務端系統架構的什麼位置呢？
總的來說，MySLQ系統架構分為 3 層，直接上圖，看下MySQL的架構劃分。
第一層：連線管理層。MySLQ是典型的CS模型軟體，所謂CS就是客戶端/服務端的意思，作為一個靠網路連線的服務，必不可少的要有連線管理層，用於管理和維護MySQL服務端和客戶端之間的連線、鑑權等等。
第二層：這一層是MySQL的核心服務功能層，包括了查詢快取、解析器、最佳化器等所有跨儲存引擎的功能都在這一層實現，遮蔽掉儲存引擎間的差別，對上層也就是連線管理層提供統一的介面。
第三層：儲存引擎層就在這一層實現，負責MySQL中資料的儲存和提取，這其中有我們今天的主角InnoDB儲存引擎和它實現的B+樹索引。
如何指定儲存引擎型別
既然要研究innoDB的索引，那我們首先來建立一個使用innoDB儲存引擎的表。
MySQL目前支援的儲存引擎種類非常豐富，可以在連線MySQL客戶端，進入到命令列模式下，輸入如下命令檢視當前版本MySQL提供的所有儲存引擎。
show engines；
儲存形式
InnoDB儲存引擎用B+樹實現索引
，說到B+樹不得不提到他的兄弟B樹，這兩者的區別比較微妙，但查詢磁碟儲存資料的效能上卻相差很大，要知道為何MySQL InnoDB 選擇B+樹而不選擇B樹做索引，我們先來假設分別用這兩種資料結構實現索引對比一下。
B樹索引
拿來一本資料結構的教材，我們翻開B樹的定義。一棵M階的b樹是這麼定義的：
定義任意非葉子結點最多隻有M個兒子，且M>2；
根結點的兒子數為［2， M］；
除根結點以外的非葉子結點的兒子數為［M/2， M］，向上取整；
非葉子結點的關鍵字個數=兒子數-1；
所有葉子結點位於同一層；
k個關鍵字把節點拆成k+1段，分別指向k+1個兒子，同時滿足查詢樹的大小關係。
看完你大概有點懵，不過沒關係，我們現是要對比它和B+樹在資料庫索引上的使用，不是要去手寫一個數據庫索引，只要抓住它主要的特點便於理解幫助我們理解索引原理即可，
這裡抓住B樹最主要的兩個特點：
非葉子節點只存放「索引」和指向子節點的「指標」。
葉子節點存放「索引」和「資料」，且葉子節點之間沒有關聯。
便於理解，假如在資料庫中使用B樹來做索引結構，我試著畫出這個B樹的索引結構圖，如下：
B+樹索引
看完了B樹索引實現，現在我們來用B+樹實現索引看看，一樣的隨便開啟一本資料結構教材找到B+樹的定義，一顆M階的B+樹：
有n棵子樹的非葉子結點中含有n個關鍵字（b樹是n-1個），這些關鍵字不儲存資料，只用來索引，所有資料都儲存在葉子節點（b樹是每個關鍵字都儲存資料）。
所有的葉子結點中包含了全部關鍵字的資訊，及指向含這些關鍵字記錄的指標，且葉子結點本身依關鍵字的大小自小而大順序連結。
所有的非葉子結點可以看成是索引部分，結點中僅含其子樹中的最大（或最小）關鍵字。
通常在b+樹上有兩個頭指標，一個指向根結點，一個指向關鍵字最小的葉子結點。
同一個數字會在不同節點中重複出現，根節點的最大元素就是b+樹的最大元素。
如果以前沒接觸過資料結構相關概念，看完估計還是不大明白，沒關係，那不是本文的重點，我們不去深究細枝末節。
我來幫你總結下，B+樹和B樹有很多相同的特點，但也有一些不同讓B+樹在查詢磁碟儲存的資料時有更好的效能（為什麼？我們稍後講），最大的不同是下面兩個
：
「資料」只存放葉子節點上面的，非葉子節點存放「索引」和「指標」。
葉子節點按大小順序透過雙向連結串列連線起來，可以像遍歷連結串列一樣遍歷整棵B+樹。
innoDB的選擇
innoDB的索引選擇用B+樹來實現，B樹和B+樹非常相似，
為什麼用B+樹不用B樹做索引呢
？這就要從資料庫的儲存方式說起。
效能瓶頸
innoDB索引以B+樹形式組織儲存，
我們首先要明白B+樹的每個節點不是儲存在記憶體而是放在屬於外部儲存的「磁碟頁」中
。
為什麼呢？因為記憶體快是快，但是它貴啊！而且很多資料不是熱點資料，十天半個月都用不上，完全沒必要都放在記憶體裡面，想想看如果淘寶會把那種萬億級別的交易訂單資料如果都存在記憶體中嗎，馬爸爸雖然有錢也不至於這麼奢侈。
重點關注下這裡所說的磁碟頁，的大小每個系統可能不一樣，就堂主所用的這個Centos Linux系統來說，透過下面的命令檢視磁碟頁大小為
4096B
也就是
4KB
［lemon/test］$ getconf PAGE_SIZE4096
這些磁碟資料頁
如果是B+樹的葉子節點
，那就儲存著關鍵字和資料（就是我們用
INSERT
語句塞進資料庫的那些資料）。
如果是非葉子節點
那就儲存著關鍵字和指標（指向子節點的指標），從上圖B+樹實現的索引示意圖也可以看到這兩種儲存形式的差別。
記憶體VS外存
當我們在MySQL InnoDB中執行
select
查詢語句，這個查詢資料的過程是這樣的
：
沿著B+樹索引來查詢一個給定關鍵字（或者範圍關鍵字）的所在的資料行。
找到資料行所在的磁碟頁，把這個磁碟頁載入到記憶體中。
在記憶體中進行查詢（比如二分查詢），最終得到目標資料行內容。
我們知道磁碟是外部儲存裝置，那MySQL資料庫查詢的時候將磁碟中資料讀入記憶體這個過程是非常緩慢的，對於機械硬碟具體來說，從磁碟載入資料需要經過尋道、旋轉以及傳輸的這些過程，
時間花費至少是幾十毫秒，作為對比，DDR4記憶體定址時間僅為6ns左右
。
機械硬碟
記憶體讀取速度是磁碟讀取速度的100萬倍
！雖然現在固態硬碟的速度提升了很多，但和記憶體比起來還是有很大的差距，
所以要儘量減少資料庫對磁碟資料頁的隨機IO操作
。
由於磁碟讀寫耗時的原因，在高併發系統中關係型資料庫MySQL會成為系統性能瓶頸。
在高併發服務中幾十毫秒的的耗時太久了，假設10ms處理一個請求，那1秒處理100個
QPS=100
對比秒殺這一類的場景這個吞吐量完全是不夠用的，
這也是現在像Redis這樣的快取記憶體資料庫會站在前面，為MySQL擋一刀的原因
，因為Redis都是記憶體操作，速度非常快！
Why B+樹？
為了更方便的說明B樹和B+樹兩種儲存結構的差異，我們來對比下兩種樹實現的索引上讀取資料的過程，i再來回答innoDB 引擎為什麼選B+樹。
為方便對比，假設我們在B和B+樹中我們都要「查詢
1 之間」的所有資料行。
B樹索引
先來看下如果索引用B樹來實現，查詢資料的流程圖：
在不考慮任何最佳化的前提下，
圖中綠色虛線是在B樹索引上查詢資料的遍歷軌跡
，來拆解一下：
從索引樹根節點開始，載入磁碟頁 page1 找到第一個節點
key=1
資料行（1，小林）不符合。
繼續透過指標找到磁碟頁面page2，載入磁碟頁page2到記憶體，
key=2
符合，讀取資料行
（2， 石頭）
重新載入磁碟頁 page1 找到第二個節點
key=3
符合，讀取資料行（3，軒轅）。
繼續透過指標載入磁碟頁 page4 到記憶體，key=4 符合，讀取資料行（4，小北）。
重新載入磁碟頁 page1 找到第三個節點 key=5 符合，讀取資料行（5，why神）。
數一數上面的5個步驟有幾個「載入磁碟頁」字眼，5個，還記得上面我們說的：**載入磁碟資料非常費時！**這種隨機大量的磁碟IO造成了B樹索引的的效能瓶頸，使其與innoDB索引無緣。
B+樹索引
再來看下現在innoDB的用B+樹的實現方案吧，同樣的查詢條件，還是畫出資料查詢的遍歷軌跡：
在不考慮任何最佳化的前提下，
圖中綠色虛線是在innoDB B+樹索引上查詢資料的遍歷軌跡
，同樣來拆解一下：
從索引樹根節點開始，載入磁碟頁 page1 找到第一個節點
key=1
不符合，繼續往下搜尋。
透過指標找到磁碟頁page2， 載入磁碟頁page2 到記憶體，其中存放了key=1、2的資料行，讀取符合條件資料行。
由於葉子節點間組成雙向連結串列，直接順著page2 載入磁碟頁page3 、 載入磁碟頁page4，讀取其中符合條件的資料行。
這其中涉及了4次載入磁碟頁的操作，看起來只是比上面的B樹少了一次，但這是在我的簡單例子，為了便於理解資料量比較少。
實際應用中B+確實能夠減少大量的磁碟IO，從而大大提高查詢效能，而且由於B+樹根節點的資料已經是排序好的雙向連結串列，我們可以像連結串列一樣遍歷所有資料，非常適合範圍查詢和排序操作！
再談B樹
B樹索引並非一無是處
。雖然我們前面詳細對比了在innoDB中使用B+樹索引的優勢，但不要以為B樹就一無是處了，一種資料結構被設計出來肯定是有使用場景的需求，不然誰也不會閒著沒事折騰出一個東西，你說對吧。
事實上B樹也被用於實現資料庫索引，只不過不是在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是一種文件型的非關係型資料庫，被劃分為NoSql資料庫，使用類似JSON的語法儲存文件，熟悉Redis的同學應該很容易理解NoSQL的含義。
因為關係型資料庫比如 MySQL 經常需要執行遍歷和範圍查詢的操作，B+樹的特點正是迎合了這樣的需求。
但是在MongoDB這樣的NoSLQ資料庫中，在資料表的設計層面就決定了不會有太多的遍歷和範圍查詢，基本就是一個鍵對應一個值的單一查詢
。
在MongoDB上的查詢如果用B+樹來實現索引的話，由於非葉子節點不存放資料，每次查詢必須搜尋到B+樹的葉子節點才能獲取到資料，時間複雜度是固定的樹的高度
log n
；
而如果用B樹實現索引，由於每個節點都可以存放資料，
幸運的話有可能不必找到葉子節點就能取得資料
，複雜度更低，再來看下B樹實現的索引，如果換作是 MongoDB 你仔細品。
雖然沒有MySQL的使用普及程度那麼高，用B樹實現索引的MongoDB很多大公司也都有使用。
使用客戶
脫離業務場景談具體實現都是耍流氓
。正是由於關係型資料庫和非關係型資料庫應用場景的不同，工程實現上最終會在損失和收益中找到平衡點，使得B樹和B+樹在不同資料庫上有各自的用武之地。
所以下次面試和麵試官誇MySQL B+樹索引好處的時候，注意別把 B 樹噴的太慘，以防面試官來個回馬槍，
讓你說說為啥MongoDB還要用B樹來實現索引
？這時候雖然你心裡笑開了花，還是要假裝再思考下，愣著幹嘛，接著繼續吹B樹啊。
可以看到上圖中有包含MyISAM 和 InnoDB 這兩種常見引擎，關於這些儲存引擎的詳細介紹，可以參考MySQL的官方文件，我放上鍊接：
https：//dev。mysql。com/doc/refman/8。0/en/storage-engines。html
好了，現在來建立資料表並指定innoDB儲存引擎。
舉個栗子：建立表一張大佬資料表
BigOld
，表中第一個欄位是大佬
id
標識，第二個欄位是大佬名字
name
，並指定資料庫使用的儲存引擎型別
ENGINE=InnoDB
，下面這條建表語句建立並指定了一個使用 InnoDB 儲存引擎的資料庫表。
CREATE TABLE BigOld （ id INT， name CHAR （32）， PRIMARY KEY （id）） ENGINE=InnoDB；
當然，如果你一開始建立的表使用的不是InnoDB引擎，那也沒關係，
還可以再建立表之後修改表的儲存引擎
，像下面的這樣操作。
alert table BigOld engine = InnoDB
索引
好了，經過前面的操作，終於我們有了一個innoDB的資料表，現在我們可以來講講innoDB儲存引擎的索引，索引的作用當然是為了快速的存取MySQL資料庫的資料。
舉個栗子，如果把MySQL比作一個大型圖書館，其中的資料比作圖書館裡的書
。
圖書館 unsplash。com
你去圖書館找書，圖書館那麼大我們不可能一頭扎進去，一層層、一個個書架去找想要的書，這時候我們會在圖書管理系統中透過圖書編號（索引）查詢到圖書所在的樓層，到了指定的樓層在透過書架上的提示找到對應區域，最終在某個書架找到想要的書，這個圖書編號就起到索引的作用，幫助我們快速找到圖書（資料）。
感謝各位的閱讀，文章的目的是分享對知識的理解，技術類文章我都會反覆求證以求最大程度保證準確性，若文中出現明顯紕漏也歡迎指出，我們一起在探討中學習。
炒股開戶享福利，入金抽188元紅包，100%中獎！
開啟App看更多精彩內容
