索引是幫助數據庫高效獲取數據的數據結構
索引的數據結構
1.hash表
a.利用hash存儲的話需要將所有的數據文件添加到內存，比較耗費內存空間
b.hash表存儲的是無序數據，范圍查找的時候需要挨個進行遍歷，比較耗費時間。
2.二叉樹
二叉樹規定左子樹必須小于根節點，右子樹必須大于根節點，可能會導致右子樹變成一條鏈表，對提升查詢效率沒有幫助。
3.平衡樹(AVL樹)
AVL樹是一顆嚴格意義上的平衡樹，它要求最高子樹和最低子樹的高度之差不超過1，因此在進行元素插入的時候，會進行1到n次的旋轉，嚴重影響插入的效率。
4.紅黑樹
紅黑樹是基于AVL樹的一個升級，損失了部分查詢的性能，來提升插入的性能，在紅黑樹中，最高子樹不能超過最低子樹的2倍，在插入的時候，不需要進行N多次的旋轉操作，而且加入了變色的特性，來滿足插入和查詢性能的平衡。ps：二叉樹及其變種的其他樹都不能支撐索引的需求，原因是其插入數據的性能比較低，并且樹的深度無法控制，都會因為樹的深度過深而造成io的次數變多，影響讀取數據的效率。
5.B-Tree
B樹的特點：
1.所有鍵值分布在整顆樹上
2.搜索可能在非葉子節點上結束，在關鍵字全集內做一次查找，性能逼近二分查找
3.節點中的數據索引從左到右遞增排列
缺點：每個節點同時包含了key和data，而每個頁存儲空間是有限的，
如果data比較大的話會導致每個節點存儲的元素數量變小。
當存儲量變大時，會導致深度變大，增大磁盤io次數，進而影響查詢性能。
6.B+Tree
B+Tree是在B-Tree的基礎之上做的一種優化：
1.B+Tree的非葉子節點只存儲索引，不存儲data，使非葉子節點可以包含更多的節點，這樣有兩個好處，一是大大降低了樹的高度，二是將數據范圍變成多個區間，增加了檢索的效率。
2.葉子節點存儲所有的索引和data，而且所有的葉子節點相互連接，形成了一種鏈式結構，范圍查詢性能更高。ps：索引的從磁盤到內存的load過程中會產生磁盤I/O消耗，相對于內存讀取，I/O存取的消耗要高好幾個數量級，所以評價一個數據結構作為索引的優劣最重要的指標就是在查找過程中磁盤I/O操作次數。換句話說，索引的結構組織要盡量減少查找過程中磁盤I/O的存取次數。B+Tree這種數據結構利用了磁盤預讀原理，將每個節點的大小設為等于一個頁，每個節點只需要一次I/O就可以載入，并且節點中的數據和索引從左到右遞增排列，符合局部性原理，所以B+Tree擁有更好的性能。
InnoDB索引實現
聚簇索引
在InnoDB這種存儲引擎下，數據和索引是放在一起的.frm存放的是表結構.ibd存放表數據和索引
ps：innoDB存儲引擎默認情況下會把所有的數據文件放到表空間中，不會單獨為每一張表保存一份數據文件，如果需要將每一張表單獨使用文件保存，設置如下屬性：set gobal innodb_file_per_table=on
InnoDB--B+Tree
1.葉子節點直接存放索引和數據
2.InnoDB中至少有一個聚簇索引，一般會通過B+Tree對主鍵創建索引，如果沒有主鍵，會選擇唯一鍵，如果沒有唯一鍵，會自動生成一個6位rowid來作為主鍵
3.在非聚簇索引中，葉子節點上存儲的是該行數據的主鍵，然后通過聚簇索引找到對應的數據，也就是要走兩次B+Tree，叫做回表
MyISAM索引實現
非聚簇索引
在MyISAM這種存儲引擎下，數據和索引文件是單獨的文件.frm存放的是表結構.MYI存放索引.MYD存放表數據
MyISAM--B+Tree
1.葉子節點存放索引和對應數據的磁盤文件地址
2.MyISAM不存在回表的問題
