本篇文章帶大家深入解析一下mysql中的索引，帶大家理解一下mysql索引原理，希望對大家有所幫助！
一、什么是索引
索引是幫助MySQL高效獲取數據的排好序的數據結構
前置知識：樹的高度越低查詢效率越高
二、索引數據結構
數據結構模擬網址：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
（一）二叉樹
問題：不能自平衡，極端情況出現傾斜，查詢效率和鏈表類似
（二）紅黑樹
紅黑樹對數據進行平衡，解決了單邊增長的問題；
問題：數據量大的不適合，數據量大的時候，樹的高度不可控，從根節點到葉子節點，需要多次遍歷查找，效率偏低。
（三）Hash
1、對索引的key進行一次hash計算就可以定位出數據存儲的位置
2、很多時候Hash索引要比B+ 樹索引更高效
3、僅能滿足 “=”，“IN”，不支持范圍查詢
4、hash沖突問題
（四）B-Tree
1、葉節點具有相同的深度，葉節點的指針為空；
2、所有索引元素不重復；
3、節點中的數據索引從左到右遞增排列；
（五）B+Tree(B-Tree變種)
1、非葉子節點不存儲data，只存儲索引(冗余)，可以放更多的索引
2、葉子節點包含所有索引字段
3、葉子節點用指針連接，提高區間訪問的性能
三、InnoDB一棵B+樹可以存放多少行數據？
這個問題的簡單回答是：約2千萬
在MySQL中我們的InnoDB頁的大小默認是16k，當然也可以通過參數設置：
SHOW GLOBAL STATUS LIKE "Innodb_page_size"
數據表中的數據都是存儲在頁中的，所以一個頁中能存儲多少行數據呢？假設一行數據的大小是1k，那么一個頁可以存放16行這樣的數據。
如果數據庫只按這樣的方式存儲，那么如何查找數據就成為一個問題
因為我們不知道要查找的數據存在哪個頁中，也不可能把所有的頁遍歷一遍，那樣太慢了。
所以人們想了一個辦法，用B+樹的方式組織這些數據。如圖所示：
InnoDB中主鍵索引B+樹是如何組織數據、查詢數據的，我們總結一下：
1、InnoDB存儲引擎的最小存儲單元是頁，頁可以用于存放數據也可以用于存放鍵值+指針，在B+樹中葉子節點存放數據，非葉子節點存放鍵值+指針。
2、索引組織表通過非葉子節點的二分查找法以及指針確定數據在哪個頁中，進而在去數據頁中查找到需要的數據；
那么回到我們開始的問題，通常一棵B+樹可以存放多少行數據？
這里我們先假設B+樹高為2，即存在一個根節點和若干個葉子節點，那么這棵B+樹的存放總記錄數為：根節點指針數*單個葉子節點記錄行數。
上文我們已經說明單個葉子節點（頁）中的記錄數=16K/1K=16。（這里假設一行記錄的數據大小為1k，實際上現在很多互聯網業務數據記錄大小通常就是1K左右）。
那么現在我們需要計算出非葉子節點能存放多少指針？
其實這也很好算，我們假設主鍵ID為bigint類型，長度為8字節，而指針大小在InnoDB源碼中設置為6字節，這樣一共14字節
我們一個頁中能存放多少這樣的單元，其實就代表有多少指針，即16384/14=1170。
那么可以算出一棵高度為2的B+樹，能存放1170*16=18720條這樣的數據記錄。
根據同樣的原理我們可以算出一個高度為3的B+樹可以存放：1170* 1170 *16=21902400條這樣的記錄。
所以在InnoDB中B+樹高度一般為1-3層，它就能滿足千萬級的數據存儲。
在查找數據時一次頁的查找代表一次IO，所以通過主鍵索引查詢通常只需要1-3次IO操作即可查找到數據。
四、為什么MySQL的索引要使用B+樹而不是其它樹形結構?比如B樹？
B樹
葉子節點具有相同的深度，葉子節點的指針為空
所有索引元素不重復
節點中的數據索引從左到右遞增排列
B+樹索引
非葉子節點不存儲data，只存儲索引(冗余)，可以放更多的索引
葉子節點包含所有索引字段
葉子節點用指針連接，提高區間訪問的性能
為什么data節點挪到葉子節點，一個節點可以存儲更多的索引
16^n=2000萬，n就是樹的高度，存儲同樣的數據，B+樹的高度遠小于B樹
因為B樹不管葉子節點還是非葉子節點，都會保存數據，這樣導致在非葉子節點中能保存的指針數量變少（有些資料也稱為扇出）
指針少的情況下要保存大量數據，只能增加樹的高度，導致IO操作變多，查詢性能變低；
五、存儲引擎索引實現
聚集索引的意思：葉子節點存放了索引和數據又叫聚簇索引。
非聚集索引又叫稀疏索引。主鍵索引就是一種聚簇索引！
（一）MyISAM索引文件和數據文件是分離的(非聚集)
MyISAM索引文件和數據文件是分離的(非聚集)，存儲引擎是作用于表的;
索引文件存放索引，數據文件存放數據，索引和數據不放在一起存
查詢：先查詢B+樹上的索引，再用查詢到的位置查詢數據文件
（一）InnoDB索引實現
表數據索引數據存放于.ibd文件中
1、表數據文件本身就是按B+Tree組織的一個索引結構文件
2、聚集索引-葉節點包含了完整的數據記錄
（1）主鍵索引：
（2）輔助索引（二級索引）
主鍵索引的葉子節點存儲了完整的數據行，而非主鍵索引的葉子節點存儲的則是主鍵索引值，通過非主鍵索引查詢數據時，會先查找到主鍵索引，然后再到主鍵索引上去查找對應的數據，這個過程叫做回表(下文中會再次提到)。
二級索引與聚簇索引有幾處不同：
- 按指定的索引列的值來進行排序
- 葉子節點存儲的不是完整的用戶記錄，而只是索引列+主鍵。
- 目錄項記錄中不是主鍵+頁號，變成了索引列+頁號。
- 在對二級索引進行查找數據時，需要根據主鍵值去聚簇索引中再查找一遍完整的用戶記錄，這個過程叫做回表
（3）聯合索引：
以多個列的大小為排序規則建立的B+樹稱為聯合索引，本質上也是一個二級索引。
3、為什么建議InnoDB表必須建主鍵，并且推薦使用整型的自增主鍵？
(1)主鍵是InnoDB用來構建B+樹的。如果沒有主鍵，會使用唯一的列作為索引，如果還是沒有，會建立隱藏列，作為索引列。
(2)如果不用整型的自增主鍵，用UUID作為主鍵會怎么樣？
UUID是字符串類型，查詢操作會有比較操作，整型比較操作快,整型主鍵比UUID省空間,UUID不是自增的
(3)HASH索引：值做hash運算，運算后的值和存儲位置一一映射
為什么不用Hash？
Hash對范圍查詢支持不好。某一列數據是無序的，B+樹在構建的時候可以讓數據有序。
4、為什么非主鍵索引結構葉子節點存儲的是主鍵值？(一致性和節省存儲空間)
六、B+樹索引總結
1、每個索引都對應一棵B+樹。用戶記錄都存儲在B+樹的葉子節點，所有目錄記錄都存儲在非葉子節點。
2、InnoDB存儲引擎會自動為主鍵（如果沒有它會自動幫我們添加）建立聚簇索引，聚簇索引的葉子節點包含完整的用戶記錄。
3、可以為指定的列建立二級索引，二級索引的葉子節點包含的用戶記錄由索引列 + 主鍵組成，所以如果想通過二級索引來查找完整的用戶記錄的話，需要通過回表操作，也就是在通過二級索引找到主鍵值之后再到聚簇索引中查找完整的用戶記錄。
4、B+樹中每層節點都是按照索引列值從小到大的順序排序而組成了雙向鏈表，而且每個頁內的記錄（不論是用戶記錄還是目錄項記錄）都是按照索引列的值從小到大的順序而形成了一個單鏈表。如果是聯合索引的話，則頁面和記錄先按照聯合索引前邊的列排序，如果該列值相同，再按照聯合索引后邊的列排序。
通過索引查找記錄是從B+樹的根節點開始，一層一層向下搜索。由于每個頁面都按照索引列的值建立了頁目錄，所以在這些頁面中的查找非常快。
七、Mysql索引會失效的幾種情況總結
查看博客：Mysql索引會失效的幾種情況總結https://blog.csdn.net/weixin_36586564/article/details/79641748
【相關推薦：mysql視頻教程】
