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

Hash索引

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

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

B-Tree能加快數(shù)據(jù)的訪問速度，因?yàn)榇鎯?chǔ)引擎不再需要進(jìn)行全表掃描來獲取數(shù)據(jù)，數(shù)據(jù)分布在各個(gè)節(jié)點(diǎn)之中。

B+Tree索引

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

B+tree性質(zhì)：

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

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

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

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

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