說一說索引的底層實現？

Hash索引

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

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

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

B+Tree索引

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

B+tree性質：

n棵子tree的節點包含n個關鍵字，不用來保存數據而是保存數據的索引。

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

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

B+ 樹中，數據對象的插入和刪除僅在葉節點上進行。

B+樹有2個頭指針，一個是樹的根節點，一個是最小關鍵碼的葉節點。