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