索引的本質
1.1 索引的定義
在關系資料庫中，索引是一種單獨的、實體的對資料庫表中一列或多列的值進行排序的一種存儲結構，它是某個表中一列或若幹列值的集合和相應的指向表中實體辨別這些值的資料頁的邏輯指針清單，
索引是為了加速對表中資料行的檢索而建立的一種分散的存儲結構。索引是幫助MySQL高效擷取資料的排好序的資料結構。
一張表的資料在磁盤上面是随機分布的，不一定資料絕對的是相鄰的，如果要從磁盤上拿取一行記錄，需要與磁盤做IO互動,互動越多，越消耗性能。(索引也是存儲在磁盤上的)
索引是一種資料結構，資料結構有：二叉樹（二叉查找樹Binary Search Tree）、紅黑樹（Red Black Tree）、Hash表、B-Tree、B+Tree
索引是幫助MySQL高效擷取資料的排好序的資料結構。
1.2 索引的資料結構
1.2.1 二叉樹資料結構
如圖所示：我們建了一張表，如果采用二叉樹資料結構
此時如果進行查詢：select * from user where col2=89 ;
弊端：如果索引字段一直都是一種規律增加，樹的高度會很高，而且查詢效率依然很低，這種情況下，幾乎變成了線性查找。用二叉樹建索引，對于單邊增長的索引基本沒有提升效率性能的作用，是以mysql沒有選擇用二叉樹。如圖
1.2.2.紅黑樹 （二叉平衡樹）
此時紅黑樹就應運而生，可解決此問題，紅黑樹不僅具有二叉樹的特性，還有自己的附加屬性，即使是單邊增長，也會自動去調整進行優化，如果資料量很大的情況下，樹的根節點到葉子節點會非常高，不可控（查找的次數跟高度緊密相關的）；
簡單了解如圖：
旋轉重新組成合理的樹狀結構，這樣樹的高度降低，查找的效率提高！例如主鍵：
在大資料量的情況下，紅黑樹依然會有性能問題，例如百萬或者更多級别的資料，紅黑樹的高度依然會特别高，因為基本的特性就是二分查找。此時B-Tree就出現了，在縱向高度無法突破的情況下，隻能考慮橫向擴充，可考慮橫向放的索引資料增加，讓一個節點存放更多的索引元素，同時可以分更多的叉出來。在磁盤上配置設定更大一塊磁盤空間，一個大的節點裡面可以放更多索引元素
1.2.3.B-Tree
B-Tree : 葉節點具有相同的深度 ，所有索引元素不重複，葉節點的指針為空，節點中的資料索引從左到右遞增排列。
MySQL的索引底層用的 B+Tree ,是對B-Tree的一個改造，實際上是一個多叉平衡樹。
1.2.4.B+Tree
B+Tree : 非葉子節點不存儲data（有可能是此索引所在磁盤檔案位址指針，也可能是此索引所在行的其他列的所有資料資訊，跟存儲引擎有關），隻存儲索引，可以放更多的索引； 同時葉子節點維護了順序通路指針（mysql優化為了雙向指針），提高區間通路的性能。（所有的索引元素都是存儲在葉子節點裡面，如下圖示）
1.會從葉子節點裡面取很多相同的數作為備援索引，用于建構B+Three。所有的資料都存儲在葉子節點上
2.實體層面都稱之為在資料頁上面，每一個節點從左到右是排好序的（B-Three也具備），不論是節點内還是節點之間都是從左到右依次遞增；
3.B+Three相鄰葉子節點之間有一塊空間維護了指針，指向前後的節點，B-Three沒有
4.B-Three因為data元素在每個節點都有存儲，導緻在節點大小一樣的情況下，所存儲的索引将會變少，意味着樹的高度會增加，是以選擇了B+Three
5.範圍查找的情況下，B+Three有指針，直接找到節點拿到資料結果集，B-Three 節點上沒有維護雙向指針，沒法指向下一個節點，找到一組資料後，隻能再次從根節點load記憶體中再去查找直到得到結果。
相關的索引資料隻存儲在葉子節點裡面，這樣做可以讓非葉子節點能存儲更多的索引，但也并不是說每一個節點索引可以無限存儲，因為最後都是會放到記憶體裡面去進行運算查找，需要考慮記憶體及成本。
目前MySQL的每個節點配置設定的空間可以通過指令檢視：
SHOW GLOBAL STATUS LIKE 'INNODB_page_size';
磁盤上每個節點配置設定了16384個位元組，也就是16KB的空間。
将節點load進記憶體，就是一次磁盤IO， 那麼存儲索引的時候，一個節點最多能存儲 16k/14B=1170個索引(bigint類型 8位元組+下一個檔案位址6位元組/指針)；葉子節點由于存儲了索引及相關的資料，葉子節點 假設每組大小為1KB則一個葉子節點可存16個資料；如圖所示 ，B+Tree高度為3的時候，理論上所能存儲的資料量則為：1170*1170*16=21902400 兩千萬的資料量。也就是千萬級别的資料量情況下，樹的高度隻有3，效率很高，最多三次磁盤IO就能找到。（MySQL根節點常駐記憶體，高版本，有可能是把所有的非葉子節點都放在記憶體中的）
B+Tree 葉子節點維護有指針，右邊元素的索引值都是大于左邊的，是以當出現範圍查找的時候，隻需要找到對應的索引即可找到想要的結果集。順着指針依次将後面所有的元素放到結果集裡面，如果沒有這個指針，則會每次都要再從根節點開始去找對應的索引找資料。
1.2.4.Hash
Hash：MySQL目前支援BTREE 和 HASH 兩種索引方法，也就是兩種索引存儲資料結構，用Hash雜湊演算法，key為索引值，value為存儲資料的磁盤檔案位址，同hash算出來的值進行映射，這樣進行單條資料查找的時候會非常快，但是一般資料庫用的很少，雖然在進行單一資料查找很快，但是hash無法支撐範圍查找，範圍查找的時候性能會非常低，所支援的場景單一。
1.對索引的key進行一次hash計算就可以定位出資料存儲的位置，一般經過一次磁盤IO
2.僅能滿足 “=”，“IN” 不支援範圍查詢，如果用不到此索引，就會全表掃描，B+Three支援（葉子節點有雙向指針）
3.hash沖突問題
1.3索引的存儲引擎
1.3.1MyISAM的索引檔案和資料檔案是分離的（非聚集）
不同的存儲引擎（引擎是用于形容資料庫表的），底層用B+Tree存儲的時候，存儲檔案還有一點點差別
SHOW VARIABLES like '%char%'
磁盤上檔案存儲的時候，一張表至少三個檔案，*_myisam.frm 表結構檔案，*_myisam.MYD 表資料行檔案，*_myisam.MYI 存儲表資料的索引（B+Tree結構）。如果是這種類型的存儲引擎，命中索引的時候先去 MYI檔案中定位到這個索引，找到這個檔案中存儲的對應的磁盤檔案指針，此時（葉子節點的data存儲的是這個索引所對應的資料所在磁盤的所在行的檔案指針），再去MYD檔案中找到對應的資料，放到記憶體中去。
1.3.2InnoDB的索引實作（聚集：葉子節點包含了完整的資料記錄）
一張使用InnoDB存儲引擎的表，對應的檔案有兩個*_innodb_lock_frm （表結構檔案）、*_innodb_lock_ibd（存儲了索引+資料），（葉子節點裡面的data 存儲的是相應的行資料），比MyISAM少了一次磁盤IO。
為什麼InnoDB必須有主鍵，且推薦使用整型自增主鍵？
表資料本身就是按B+Tree組織的一個索引結構檔案， 聚集索引-葉子節點包含了完整的資料記錄
1.如果不設定主鍵依然可以建表存儲，但是底層會自動識别一個字段或者單獨建立一個字段作為主鍵。 如果沒有選到，會建一個隐藏列，幫你進行維護，幫你組織整張表的資料
2.非主鍵索引，data存儲的不是具體的行資料，而是主鍵索引
3.用整型是因為查找索引的時候會經過很多的比較運算操作，這種情況下其他類型效率不會很高，比如用UUID的時候，字元串進行比較，需要逐位對比，如果英文跟數字又需要轉位ASCII碼來比較大小，影響效率。
4.如果非自增主鍵，就會存在後續新增的資料可能在之前的節點的中間，由于data存儲的行資料，一個節點16KB大小，如果本來這個葉子節點已經這麼大了，現在又要新增一個主鍵索引和資料，之前的葉子節點就需要做一個資料頁分裂操作，才能将新增的資料加進去，影響性能。用自增，則可以保證每次新增的資料都是在後面，不會遇到資料頁分裂的情況。
為什麼非主鍵索引結構葉子節點存儲的是主鍵值？（一緻性和節省存儲空間）
MyISAM 非主鍵索引和主鍵索引沒差別都是存儲的檔案位址值；
InnoDB隻有一個聚集索引（主鍵），如果建有非主鍵索引（二級索引），葉子節點data資料存儲的為主鍵值，可節約存儲空間（不可能有多少索引，放多少份資料，會浪費空間），每加一個索引，在索引檔案中就會加一個樹結構存放索引資料。如果用二級索引去查詢資料，會先根據二級索引找到對應主鍵，再到聚簇索引中去尋找資料，這就是回表操作。
1.3.3聯合索引的底層存儲結構
常用的聯合索引的底層存儲結構（複合索引：多個字段共同組織成一個索引）：
索引是排好序的資料結構
一般一張表不建議建很多單值索引，盡量用兩到三個聯合索引來解決，底層也是排好序的資料結構。底層依然是B+Three
索引最左原理
聯合主鍵
如果第一個字段就已經能區分大小，就不會再看後面的字段了（如果是字元串會轉ACSS碼去對比），比如Bill 和 HanMeimel這兩個索引值就是如此排的。
如果第一個字段都相等，接下來就看第二個字段，如果前面兩個字段都相等，就看第三個字段，聯合主鍵索引不可能存在三個字段都相等的情況，（如果是輔助索引可能相同，但是存放的data主鍵是不同的，那麼就根據主鍵再去區分）
如果資料放滿，需要提升某個索引，都是提升的最小的那個節點上去作為備援索引，來建構這個樹。
EXPLAIN SELECT * FROM test_hello WHERE name='liuyan' and age=18 AND position='大鵬家'; EXPLAIN SELECT * FROM test_hello WHERE age=18 AND position='大鵬家'; # 不會走索引
EXPLAIN SELECT * FROM test_hello WHERE position='大鵬家'; # 不會走索引
跳過了 `name` 就不能走索引，必須要先用 `name`字段 才能走這個聯合索引，因為是排好序的，比如第二條資料，跳過name 直接走age, 在 第一個葉子節點裡面age是排好了的，但是在整張表裡面，并不是排好序的，就不符合索引的原理（排好序原理），因為現在不是排好序，意味着需要全表掃描才能找到所有age=18的元素！