說一說索引的底層實現(xiàn)？

Hash索引

基于哈希表實現(xiàn)，只有精確匹配索引所有列的查詢才有效，對于每一行數(shù)據(jù)，存儲引擎都會對所有的索引列計算一個哈希碼（hashcode），并且Hash索引將所有的哈希碼存儲在索引中，同時在索引表中保存指向每個數(shù)據(jù)行的指針。

B-Tree索引（MySQL使用B+Tree）

B-Tree能加快數(shù)據(jù)的訪問速度，因為存儲引擎不再需要進行全表掃描來獲取數(shù)據(jù)，數(shù)據(jù)分布在各個節(jié)點之中。

B+Tree索引

是B-Tree的改進版本，同時也是數(shù)據(jù)庫索引索引所采用的存儲結(jié)構(gòu)。數(shù)據(jù)都在葉子節(jié)點上，并且增加了順序訪問指針，每個葉子節(jié)點都指向相鄰的葉子節(jié)點的地址。相比B-Tree來說，進行范圍查找時只需要查找兩個節(jié)點，進行遍歷即可。而B-Tree需要獲取所有節(jié)點，相比之下B+Tree效率更高。

B+tree性質(zhì)：

n棵子tree的節(jié)點包含n個關(guān)鍵字，不用來保存數(shù)據(jù)而是保存數(shù)據(jù)的索引。

所有的葉子結(jié)點中包含了全部關(guān)鍵字的信息，及指向含這些關(guān)鍵字記錄的指針，且葉子結(jié)點本身依關(guān)鍵字的大小自小而大順序鏈接。

所有的非終端結(jié)點可以看成是索引部分，結(jié)點中僅含其子樹中的最大（或最小）關(guān)鍵字。

B+ 樹中，數(shù)據(jù)對象的插入和刪除僅在葉節(jié)點上進行。

B+樹有2個頭指針，一個是樹的根節(jié)點，一個是最小關(guān)鍵碼的葉節(jié)點。