MySQL 高级 —— 索引实现的思考
引言
最近看了一個公開課，是有關MySQL對索引設計的思考。詳細講解了幾種索引實現的設計思考與利弊辨析，討論了為什么MySQL默認情況下會使用B樹索引，B+樹索引又對B樹做了哪些結構改進。
本片博客通過個人的學習理解和總結，由幾種簡單的索引數據結構，逐漸展開對B+樹索引的探究和思考。
一、常見的索引實現
索引是幫助MySQL 高效獲取數據的有序數據結構。它可以在幾十毫秒，最多幾百毫秒內快速定位數據在磁盤中的位置。它并非是MySQL中特有的概念，實際上很多地方都有索引思想，如 Java 中的 HashMap 其本身就可以理解為一種索引。
索引有以下幾種常見的可供實現的數據結構：
1.1?二叉樹實現下的索引
二叉樹可能是最容易被想到用作索引實現的一種方式，實際其他很多索引的實現都是二叉樹的變種。下圖是一個普通的二叉樹實現索引的基本方式：
如上圖，左側是表中記錄，右側是建立在 col2 上的索引，由根節點向下，每個節點的左子節點要小于自身，右節點要大于自身，以此來形成一種有序的結構。每個節點不僅存儲 col2 列上的值，同時還會指向其對應記錄的磁盤地址。如col2 = 89，其磁盤地址為 0x77。
由于表數據存儲于磁盤上，且表數據不可能全部加載到內存中供程序查詢，在沒有建立索引的情況下，如果想要找到 col2 = 89 這條記錄，就必須從表中的第一行記錄開始，執行6次磁盤IO 操作，而建立了 col2 列的索引后，col2 = 89 只需要從索引的根節點開始執行1次磁盤IO即可找到對應記錄，避免了全表掃描，從而極大地降低了磁盤IO，提高了性能。
1.2 普通二叉樹索引的弊端
還是以下圖為例，如果我們的索引建立在 col1 上，思考索引查找會有怎樣的問題？
根據表中的數據，col1 本身是呈現一種遞增的態勢，建立索引的過程也是從表中第一條數據開始，以此將列值放入二叉樹中，那么上圖中的數據就會組織成如下圖所示的二叉樹索引結構：
只有單右側的二叉樹，已經退化為一個鏈表，而鏈表對于查找操作來說是個非常糟糕的結構，完全無法提升搜索性能。
這是因為普通的二叉樹并沒有元素平衡分配規則，對樹的高度做有效的控制，才會出現這種情況。所以 MySQL并沒有采用這種簡單的二叉樹結構。
1.3 紅黑樹索引
紅黑樹對于了解 Java 8 HashMap 底層實現的開發者并不陌生。Java 中的 HashMap實現由 Java 7 “數組 + 鏈表”的組合變為了如今的“數組 + 紅黑樹”，鏈表變為紅黑樹，就是對查找性能的重大革新。
紅黑樹也是二叉樹的一種，確切的說應該是平衡二叉樹的一個子類。所謂平衡二叉樹，就是利用一定的平衡規則，將元素盡可能地分配到根節點的兩側，盡量彌補普通二叉樹在單邊增長情況下退化為鏈表的缺陷。
我們來看下實現了 Java 8 HashMap的紅黑樹會如何為 col1 建立索引。
首先，為紅黑樹添加col1 = 1：
然后，為紅黑索引樹添加 col1 = 2，從根節點開始，由于2 >= 1，繼續查找根節點右子樹，又由于右側無任何元素，直接插入：
繼續添加 col1 = 3，從根節點開始，3 >= 1，查找根節點右子樹，3 >= 2，繼續查找右子樹，右側無元素，插入元素，由于節點和父節點都是紅色，且節點本身是右子節點，父節點也是右子節點，根據紅黑樹的調整規則，旋轉以調整額外的紅色節點：
依據紅黑樹的插入規則，最后生成的索引結構為：
可以看到，經過紅黑樹的優化，一定程度上解決了二叉樹退化鏈表的問題。
雖然利用紅黑樹這種平衡的特性，但MySQL 依然沒有使用紅黑樹作為索引的實現。
這是因為，紅黑樹依然無法有效控制樹的高度。
當表中的數據多達上百萬、千萬的級別，對某個列建立索引，意味著需要有上百萬個索引值。這樣龐大的樹結構高度可能會達到20 ~ 30，即便是在內存中對樹節點進行檢索，依然可能需要搜索20 到 30 次才能夠找到對應的索引值。這就是MySQL 索引實現的又一個不得不重視的因素——樹的高度。
很遺憾，紅黑樹對樹的高度不可控，無法滿足 MySQL 對索引的要求。
1.4 B樹與B+樹
為了降低樹的高度，樹中節點必須橫向擴展以容納足夠的索引值。
B-Tree（B樹，也叫多叉平衡樹）具有以下一些重要特點：
結構簡圖如下所示：
B樹索引在使用的時候，會先把根節點整個加載到內存中，然后在根節點中隨機查找。
比如，我們需要查找 49 這個節點，那么先將根節點整個加載到內存，發現49在15和56之間，那么會將對應的節點整個加載到內存，再重復上述步驟，直到找到49。
以col1為例，構建B樹索引（假設樹最大高度為3）如下：
最大高度為4時，col1的B樹索引如下：
B樹會根據設定的最大深度（即樹高度）來調整每個節點所能容納的元素個數，因此，根據最大深度的不同，可能特定的B樹也會有不同的結構。
那每個節點最大容量是多少呢？
內存與磁盤的IO交互有一個數據量限制，一般是4KBytes。因此，MySQL為了將節點加載到內存的效率最大化，設置一個文件的默認“分頁大小”，它恰好是讀取量限制的4倍，即16K：
SHOW GLOBAL STATUS LIKE 'Innodb_page_size';Variable_name Value ---------------- ----- Innodb_page_size 16384實際上，MySQL并沒有安全遵照B樹來設計索引，而是采用了B樹的變種——B+樹。
B+樹的重要特性有如下這些：
我們需要關注MySQL的B+樹索引對 B樹的兩步優化。
第一點是將所有元素的數據部分移動到了葉子節點上，非葉子節點不存儲任何地址數據。
這是因為考慮到每個節點不能太大，MySQL對其限制為16K，因此，在大小限制的情況下，將數據的存儲空間讓出，那么每個節點就可以容納更多的“索引”，從而極大的提高了索引樹每個節點的數據容量。
以主鍵為 bigint 類型為例，我們計算一下B+樹的索引容量。
非葉子節點每個元素后面會有一個指向下一個節點的地址，MySQL底層設置該值大小為6Bytes，而bigint類型的大小是 8Bytes，因此非葉子節點中的每個索引元素占8 + 6 = 14 Bytes，根據前面的說明，每個節點大小為16KBytes，那么一個非葉子節點最多可以容納16 * 1024/14 = 1170個索引元素。
對于一個最大深度為3的B+樹，在深度為3 的葉子節點上，每個元素的數據大約1K（實際上大部分建立索引的元素遠不會有這么大），根據每個節點最大16K的限制條件，那么每個葉子節點最多可以容納16個索引元素，因此，這個B+樹的最大容量可以為1170*1170*16 ≈2000+萬，而實際上B+樹的存儲容量要比這個數字大很多。
B+樹的葉子節點包含全部索引元素，而其他非葉子節點中的索引元素是一種“冗余”元素，它們也是索引元素，但不具備存儲具體磁盤地址的功能，只作為構建B+樹的查找路徑的功能型存在。
第二點是所有葉子節點之間會使用雙向指針連接，而B樹本身所有葉子節點中的索引元素從左到右依次遞增，那么根據這樣的結構，如果有一個條件WHERE col >20，那么MySQL只需要定位一次索引元素的位置，就可以快速獲取該索引元素后面的全部索引元素，極大的降低了索引搜索的次數。
1.5 Hash索引
Hash算法會對目標參數進行散列，從而得到一串“隨機的”編碼。
MySQL同樣支持Hash索引，與樹型索引不同，Hash索引可以快速定位到具體的索引值，其性能是樹型索引遠遠趕不上的。
當我們通過 WHERE 子句查詢某個列值的時候，比如：WHERE col1 = 89，MySQL會首先分析該列是否有建立的索引，如果col1建立了一個Hash索引，那么MySQL會對89進行同樣的散列操作，獲得該記錄存儲的磁盤地址，然后直接取得數據。
但是為什么絕大多數情況下我們不會用到Hash索引呢？
這是因為通過Hash算法建立的索引對于范圍查詢，完全排不上用場。
所以，根據這樣的特性，如果確定某個列只會用到精確查找，那么可以考慮使用Hash索引來進一步提升性能，當然，這個秘密武器可能只有在極少的情況下才能派上用場了。
二、MySQL存儲引擎的B+樹索引
B-Tree對索引列是順序組織存儲的，所以很適合查找范圍數據。
2.1 InnoDB 索引實現
InnoDB 是以聚集的方式實現索引的。
InnoDB會將表數據以及索引都存儲在 .ibd 文件內，其內部結構如下圖示例：
InnoDB索引是一個典型的聚集索引，所謂聚集索引就是葉子節點中的索引不僅存儲了索引元素，同時也包含了索引值所在行的其他列值。而MyISAM的索引與數據是存儲在兩個文件中（數據存在.MYD，索引存在.MYI），因此索引元素只存儲了對應的數據地址，是非聚集型索引。由于聚集所有會存儲數據信息，所以查找效率要比非聚集索引高。
InnoDB必須為表添加一個主鍵列，這樣才能通過主鍵列將表數據組織成一個B+樹，這也是由于InnoDB聚集索引的存儲形式所決定的。如果開發者沒有給InnoDB表添加主鍵，MySQL會自動從表的第一列開始尋找適合作為主鍵的列，如果無法找到，那么就在后臺自動為表添加一個類似主鍵的rowid列，以維護B+樹結構。
InnoDB表建議使用整型作為主鍵，因為這種整型數據維護的B+樹，可以快速進行索引的比較并定位，如果使用類似UUID的字符串作為主鍵，那么不論是維護主鍵樹還是查找主鍵，都會一定程度上限制索引元素比較的速度，從而影響整體的性能。
那為什么又建議使用自增主鍵呢？這是因為B+樹的所有葉子節點中的所有元素要求必須從左到右依次遞增，為了維護這樣的結構，如果在主鍵中有非遞增的情況，就必須向中間插入索引元素保持遞增，這就可能會涉及到結構的旋轉、冗余節點的提升、樹結構的平衡等多項操作，嚴重影響B+索引樹創建的效率。
2.2 MyISAM索引實現
MyISAM索引文件和數據文件是分離的（非聚集）
總結
以上是生活随笔為你收集整理的MySQL 高级 —— 索引实现的思考的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python跨文件复制sheet_Pyt
- 下一篇： Android日志[进阶篇]三-Logc