1.索引數據結構紅黑樹曲伊，Hash,B+樹詳解
索引的本質
描述:索引是幫助Mysql高效獲取數據的排好序的數據結構
索引數據結構分類
1.二叉樹
特點:左邊小右邊大于等于父節(jié)點
缺點：如果插入自增長索引，一直單邊增長锉走，對查詢沒有意義，如下圖
2.紅黑樹
特點：自動保持平衡
缺點:樓層太高拟烫，查詢次數過多弄企，維護復雜
3.Hash表
特點：對索引值進行hash運算戏挡，得到磁盤文件指針，查詢where index=1的等值預算的時候性能非常高
缺點：空間能力差左权，做范圍查詢where index>1的時候不好做索引
4.B-Tree
葉節(jié)點具有相同的深度皮胡，葉節(jié)點的指針為空
所有索引元素不重復
節(jié)點中的數據索引從左到右遞增排列
對比:比紅黑樹樓層低，查詢效率高
缺點：每個索引對應一個值赏迟，導致索引占用空間太大
B+Tree(MySql底層采用B+Tree數據結構)
特點：非葉子節(jié)點不存儲data屡贺，只存儲索引(冗余)，可以放更多的索引
葉子節(jié)點包含所有索引字段
葉子節(jié)點用指針連接锌杀，提高區(qū)間訪問的性能
2.索引是怎么支撐千萬級表的快速查找
一個索引(8B)加上一個指針(6B),mysql允許最大值為16kb,16kb/(6B+8B)=1170個分叉甩栈，所以最后結果為1170*1170*16=21902400兩千多萬
3.面試常問B+樹索引面試題解析
Mysql存儲引擎：
1.MyISAM(非聚集索引)
文件：.frm 存儲數據結構 .MYD存儲數據記錄.MYI存儲索引
查詢方式:根據索引查找內存空間指針，再根據空間指針再MYD文件查找記錄
2.InnerDB（聚集索引）
文件：.frm 存儲數據結構 .idb數據和索引存在一起
查詢方式:根據索引直接查找數據
提問：聚集索引和非聚集索引區(qū)別
答:非聚集索引是通過空間指正查找MYD文件查詢到的數據糕再，聚集索引是因為索引和數據存儲在一起量没，每一條記錄前面都有個索引，可以直接通過索引取數據
提問：為什么InnoDB表必須有主鍵亿鲜，并且推薦使用整型的自增主鍵允蜈？
答：InnoDB就是這樣設計的冤吨，通過主鍵索引構建B+Tree；整形比較大小比字符串比較大小更快更高效饶套，例如比較1<2比a>b更高效漩蟆，字符串比較還要轉換asci,自增是不用打破原來的B+Tree，直接再后面加數據妓蛮，如果不是怠李，可能需要重新元素分裂平衡
提問：為什么非主鍵索引結構葉子節(jié)點存儲的是主鍵值？
答：一致性和節(jié)省存儲空間蛤克，所有的非主鍵索引最后定位到的是主鍵索引捺癞，然后再通過主鍵索引查找數據，換而言之构挤，就是差了兩次樹髓介，非主鍵索引定位到主鍵索引，這樣節(jié)省了存儲空間筋现，如果建了多個非主鍵索引唐础，我就要保存多個記錄，如果非主鍵索引做了修改矾飞，主鍵索引沒有一膨，這樣就導致了數據不一致，但是如果非主鍵索引最后定位到主鍵索引洒沦，通過主鍵索引查找數據豹绪，這樣就保持了一致性
4.聯合索引底層數據結構又是怎樣的
和主鍵索引類似，不過是有多個字段組成
