小夥伴想精準查找自己想看的MySQL文章？喏 → MySQL江湖路 | 專欄目錄
面試一說起MySQL，我們總會提到B+Tree索引，你對B+Tree索引了解麼，它有哪些特性，優勢在哪裡，和B樹有什麼不同？
外行看熱鬧，内行看門道。對于這類熱門知識和問題，希望同學們都能做到心中有數。
好了，今天我們一起來複習複習MySQL索引的前世今生。一起聊聊索引的那些事兒。
目錄
- 一、什麼是索引？
- 二、索引的優缺點
-
- 1、優點
- 2、缺點
- 三、B+Tree索引的前世今生
-
- 1、二叉排序樹
- 2、AVL樹 (自平衡二叉查找樹)
- 3、B樹（Balanced Tree）多路平衡查找樹 多叉的
- 4、B+ Tree (B+樹是B樹的變體，也是一種多路搜尋樹)
- 四、為什麼MySQL索引選擇了 B+樹 而不是 B樹？
- 五、你應該知道的索引相關知識點
-
- 1、回表查詢
- 2、索引覆寫
- 3、最左字首原則
- 4、索引下推優化
一、什麼是索引？
在關系資料庫中，索引是一種單獨的、實體的對資料庫表中一列或多列的值進行排序的一種存儲結構，它是某個表中一列或若幹列值的集合和相應的指向表中實體辨別這些值的資料頁的邏輯指針清單。索引的作用相當于圖書的目錄，可以根據目錄中的頁碼快速找到所需的内容。
當表中有大量記錄時，若要對表進行查詢，第一種搜尋資訊方式是全表搜尋，是将所有記錄一一取出，和查詢條件進行一一對比，然後傳回滿足條件的記錄，這樣做會消耗大量資料庫系統時間，并造成大量磁盤I/O操作；第二種就是在表中建立索引，然後在索引中找到符合查詢條件的索引值，最後通過儲存在索引中的ROWID（相當于頁碼）快速找到表中對應的記錄。
MySQL5.5以後InnoDB儲引擎使用的索引資料結構主要用：
B+Tree
；本篇文章帶大家以B+Tree前世今生為主線來聊一聊；
Mark： B+Tree可以對<，<=，=，>，>=，BETWEEN，IN，以及不以通配符開始的LIKE使用索引。（MySQL5.5後）
這些事實或許會颠覆你的一些認知，比如在你讀過的其他文章或書中。以上這些都屬于“範圍查詢”，都是不走索引的！
沒錯，早先5.5以前優化器是不會選擇通過索引搜尋的，優化器認為這樣取出的行多與全表掃描的行，因為還要回表查一次嘛，可能會涉及I/O的行數更多，被優化器放棄。
經過算法（B+Tree）優化後，支援對部分範圍類型的掃描（得利與B+Tree資料結構的有序性）。該做法同時也違反了最左字首原則，導緻範圍查詢後的條件無法用到聯合索引，我們在後面詳細說明。
二、索引的優缺點
1、優點
- 索引大大減小了伺服器需要掃描的資料量
- 索引可以幫助伺服器避免排序和臨時表
- 索引可以将随機I/O變成順序I/O
2、缺點
- 雖然索引大大提高了查詢速度，同時卻會降低更新表的速度，如對表進行INSERT、UPDATE和DELETE。因為更新表時，MySQL不僅要儲存資料，還要儲存索引檔案。
- 建立索引會占用磁盤空間的索引檔案。一般情況這個問題不算嚴重，但如果你在一個大表上建立了多種組合索引，且伴随大量資料量插入，索引檔案大小也會快速膨脹。
- 如果某個資料列包含許多重複的内容，為它建立索引就沒有太大的實際效果。
- 對于非常小的表，大部分情況下簡單的全表掃描更高效；
是以應該隻為最經常查詢和最經常排序的資料列建立索引。（MySQL裡同一個資料表裡的索引總數限制為16個）
資料庫存在的意義之一就是是解決資料存儲和快速查找的。那麼資料庫的資料存在哪？沒錯，是磁盤，磁盤的優點是啥？便宜！缺點呢？相比記憶體通路速度慢。
那麼你知道MySQL索引主要使用的資料結構麼？
B+樹！你脫口而出。
那 B+樹 是什麼樣的資料結構？MySQL索引又是為什麼選擇了B+樹呢？
其實最終選用 B+樹 是經曆了漫長的演化：
二叉排序樹 → 二叉平衡樹 → B-Tree（B樹） → B+Tree（B+樹）
有小夥伴問我“B樹 跟 B-樹有什麼差別”？這裡普及一下，MySQL資料結構隻有B-Tree（B樹）和B+Tree（B+樹），多隻是讀法不同罷了，“B-Tree” 一般統稱為B樹，你叫他B-樹也行~~
還有小夥伴提到的紅黑樹，是程式設計語言中的存儲結構，不是MySQL的；如Java的HashMap就是用的連結清單加紅黑樹。
好了，今天就帶着大家一起看一下演化成 B+樹 的過程吧。
三、B+Tree索引的前世今生
1、二叉排序樹
了解B+樹之前，簡單說一下二叉排序樹，對于一個節點，它的左子樹的孩子節點值都要小于它本身，它的右子樹的孩子節點值都要大于它本身，如果所有節點都滿足這個條件，那麼它就是二叉排序樹。（此處可以串一下二分查找的知識點）
上圖是一顆二叉排序樹，你可以嘗試利用它的特點，體驗查找9的過程：
- 9比10小，去它的左子樹（節點3）查找
- 9比3大，去節點3的右子樹（節點4）查找
- 9比4大，去節點4的右子樹（節點9）查找
- 節點9與9相等，查找成功
一共比較了4次，那你有沒有想過上述結構的優化方式？
2、AVL樹 (自平衡二叉查找樹)
上圖是AVL樹，節點個數和值均和二叉排序樹一摸一樣
再來看一下查找9的過程：
- 9比4大，去它的右子樹查找
- 9比10小，去它的左子樹查找
- 節點9與9相等，查找成功
一共比較了3次，同樣的資料量比二叉排序樹少了一次，為什麼呢？因為AVL樹高度要比二叉排序樹小，高度越高意味着比較的次數越多；不要小看優化的這一次，假如是200w條資料，比較次數會明顯地不同。
你可以想象一下一棵 100 萬節點的平衡二叉樹，樹高 20。一次查詢可能需要通路 20 個資料塊。在機械硬碟時代，從磁盤随機讀一個資料塊需要 10 ms 左右的尋址時間。也就是說，對于一個 100 萬行的表，如果使用二叉樹來存儲，單獨通路一個行可能需要 20 個 10 ms 的時間，這個查詢可真夠慢的！
3、B樹（Balanced Tree）多路平衡查找樹 多叉的
B樹是一種多路自平衡搜尋樹，它類似普通的二叉樹，但是B書允許每個節點有更多的子節點。B樹示意圖如下：
值得注意的是，B樹的非葉子節點和葉子結點的data資料都是分開存儲的，那麼針對範圍查詢、排序等常用特性就很不友好了。
B樹的特點：
- 所有鍵值分布在整個樹中
- 任何關鍵字出現且隻出現在一個節點中
- 搜尋有可能在非葉子節點結束
- 在關鍵字全集内做一次查找，性能逼近二分查找算法
為了提升效率，要盡量減少磁盤I/O的次數。實際過程中，磁盤并不是每次嚴格按需讀取，而是每次都會預讀。
磁盤讀取完需要的資料後，會按順序再多讀一部分資料到記憶體中，這樣做的理論依據是計算機科學中注明的局部性原理：
- 由于磁盤順序讀取的效率很高(不需要尋址時間，隻需很少的旋轉時間)，是以對于具有局部性的程式來說，預讀可以提高I/O效率.預讀的長度一般為頁(page)的整倍數。
- MySQL(預設使用InnoDB引擎)，将記錄按照頁的方式進行管理，每頁大小預設為16K(可以修改)。
B-Tree借助計算機磁盤預讀機制:
每次建立節點的時候，都是申請一個頁的空間，是以每查找一個節點隻需要一次I/O;因為實際應用當中，節點深度會很少，是以查找效率很高.
那麼最終版的 B+樹 是如何做的呢？
4、B+ Tree (B+樹是B樹的變體，也是一種多路搜尋樹)
從圖中也可以看到，B+樹與B樹的不同在于：
- 所有關鍵字存儲在葉子節點，非葉子節點不存儲真正的data，進而可以快速定位到葉子結點。
- 為所有葉子節點增加了一個鍊指針，
意味着所有的值都是按順序存儲的，并且每一個葉子頁到根的距離相同，很适合查找範圍資料。說明支援範圍查詢和天然排序。
是以，B+Tree可以對<，<=，=，>，>=，BETWEEN，IN，以及不以通配符開始的LIKE使用索引。且如果用到了該索引，排序功能的消耗大大減少。
B+樹的優點：
比較的次數均衡，減少了I/O次數，提高了查找速度，查找也更穩定。
- B+樹的磁盤讀寫代價更低
- B+樹的查詢效率更加穩定
要知道的是，你每次建立表，系統會為你自動建立一個基于ID的聚集索引（上述B+樹），存儲全部資料；你每次增加索引，資料庫就會為你建立一個附加索引（上述B+樹），索引選取的字段個數就是每個節點存儲資料索引的個數，注意該索引并不存儲全部資料。
四、為什麼MySQL索引選擇了 B+樹 而不是 B樹？
- B+樹更适合外部存儲(一般指磁盤存儲),由于内節點(非葉子節點)不存儲data，是以一個節點可以存儲更多的内節點，每個節點能索引的範圍更大更精确。也就是說使用B+樹單次磁盤I/O的資訊量相比較B樹更大，I/O效率更高。
- mysql是關系型資料庫，經常會按照區間來通路某個索引列，B+樹的葉子節點間按順序建立了鍊指針，加強了區間通路性，是以B+樹對索引列上的區間範圍查詢很友好。而B樹每個節點的key和data在一起，無法進行區間查找。
五、你應該知道的索引相關知識點
1、回表查詢
比如你建立了name， age索引 name_age_index，查詢資料時使用了
select * from table where name ='陳哈哈' and age = 26; 複制
由于附加索引中隻有name 和 age，是以命中索引後，資料庫還必須回去聚集索引中查找其他資料，這就是回表，這也是你背的那條：少用select * 的原因。
2、索引覆寫
結合回表會更好了解，比如上述name_age_index索引，有查詢
select name， age from table where name ='陳哈哈' and age = 26; 複制
此時select的字段name，age在索引name_age_index中都能擷取到，是以不需要回表，滿足索引覆寫，直接傳回索引中的資料，效率高。是DBA同學優化時的首選優化方式。
3、最左字首原則
B+樹的節點存儲索引順序是從左向右存儲，在比對的時候自然也要滿足從左向右比對；通常我們在建立聯合索引的時候，也就是對多個字段建立索引，相信建立過索引的同學們會發現，無論是Oracle還是 MySQL 都會讓我們選擇索引的順序，比如我們想在a,b,c三個字段上建立一個聯合索引，我們可以選擇自己想要的優先級，a、b、c,或者是b、a、c 或者是c、a、b等順序。 為什麼資料庫會讓我們選擇字段的順序呢？不都是三個字段的聯合索引麼？這裡就引出了資料庫索引的最左字首原理。
在我們開發中經常會遇到明明這個字段建了聯合索引，但是SQL查詢該字段時卻不會使用索引的問題。比如索引abc_index:(a,b,c)是a,b,c三個字段的聯合索引，下列sql執行時都無法命中索引abc_index的；
select * from table where c = '1';
select * from table where b ='1' and c ='2'; 複制
以下三種情況卻會走索引:
select * from table where a = '1';
select * from table where a = '1' and b = '2';
select * from table where a = '1' and b = '2' and c='3'; 複制
從上面兩個例子大家是否闊以看出點眉目？
是的，索引abc_index:(a,b,c)，隻會在(a)、(a,b)、(a,b,c) 三種類型的查詢中使用。其實這裡說的有一點歧義，其實(a,c)也會走，但是隻走a字段索引，不會走c字段。
另外還有一個特殊情況說明下，下面這種類型的也隻會有 a與b 走索引，c不會走。
select * from table where a = '1' and b > '2' and c='3'; 複制
像上面這種類型的sql語句，在a、b走完索引後，c已經是無序了，是以c就沒法走索引，優化器會認為還不如全表掃描c字段來的快。
最左字首：顧名思義，就是最左優先，上例中我們建立了a_b_c多列索引,相當于建立了(a)單列索引，(a,b)組合索引以及(a,b,c)組合索引。
是以，在建立多列索引時，要根據業務需求，where子句中使用最頻繁的一列放在最左邊。
4、索引下推優化
還是索引name_age_index，有如下sql
select * from table where name like '陳%' and age > 26； 複制
該語句有兩種執行可能：
- 命中name_age_index聯合索引，查詢所有滿足name以"陳"開頭的資料， 然後回表查詢所有滿足的行。
- 命中name_age_index聯合索引，查詢所有滿足name以"陳"開頭的資料，然後順便篩出age>20的索引，再回表查詢全行資料。
顯然第2種方式回表查詢的行數較少，I/O次數也會減少，這就是索引下推。是以不是所有like都不會命中索引。
好了，多了就不說了，我勸你耗子尾汁，但推薦你關注我，因為我會讓你在快樂中學會很多東西！