索引的總共有四種類型：BTree索引仍侥，HASH索引，F(xiàn)ullText索引和RTree索引
不同的存儲(chǔ)引擎使用是不同實(shí)現(xiàn)原理實(shí)現(xiàn)索引
目錄結(jié)構(gòu)
1鸳君、BTree索引
????（1）BTree簡(jiǎn)要介紹
????（2）B+Tree簡(jiǎn)要介紹
????（3）B+Tree實(shí)現(xiàn)索引
2农渊、HASH索引
3、FullText索引
4或颊、RTree索引
1砸紊、BTree索引（B+Tree索引）
（1）BTree簡(jiǎn)要介紹
BTree索引就是以BTree結(jié)構(gòu)實(shí)現(xiàn)的索引。
使用BTree結(jié)構(gòu)實(shí)現(xiàn)索引基本是每個(gè)數(shù)據(jù)庫(kù)索引結(jié)構(gòu)的首選囱挑，
（為什么都選擇使用BTree結(jié)構(gòu)而不是其他什么樹醉顽，如紅黑樹之類的，參照文章MySQL索引詳解（四）BTree為什么更適合做索引結(jié)構(gòu)）
MySQL中除了Archive引存儲(chǔ)引擎外平挑，其他所有的存儲(chǔ)引擎都支持BTree索引游添。
BTree也叫平衡多路查找樹，與二叉樹的區(qū)別是BTree的節(jié)點(diǎn)可以有多個(gè)子節(jié)點(diǎn)（可多于兩個(gè)）通熄。
BTree結(jié)構(gòu)中每個(gè)節(jié)點(diǎn)都有指針唆涝，key，value三個(gè)元素唇辨，如上圖空白框表示指針廊酣，15表示為key，data為value赏枚。
（2）B+Tree簡(jiǎn)要介紹
B+Tree結(jié)構(gòu)如下圖：
有圖可知亡驰，B+Tree與BTree的不同在于晓猛，B+Tree只有葉子節(jié)點(diǎn)存儲(chǔ)value，非葉子節(jié)點(diǎn)只有指針和key
一般在數(shù)據(jù)庫(kù)文件系統(tǒng)中凡辱，為了方便遍歷葉子節(jié)點(diǎn)戒职，對(duì)B+Tree做了小的改動(dòng)，在葉子節(jié)點(diǎn)上增加了順序訪問指針煞茫。改動(dòng)后的結(jié)構(gòu)圖如下：
（3）B+Tree實(shí)現(xiàn)索引
MySQL數(shù)據(jù)庫(kù)中帕涌，最常用的兩個(gè)存儲(chǔ)引擎MyISAM和InnoDB存儲(chǔ)引擎實(shí)現(xiàn)BTree索引都是使用B+Tree結(jié)構(gòu)實(shí)現(xiàn)的。但是兩個(gè)存儲(chǔ)引擎實(shí)現(xiàn)的思路也不完全相同续徽，下面分別介紹兩個(gè)存儲(chǔ)引擎各自的實(shí)現(xiàn)思路蚓曼。
MyISAM存儲(chǔ)引擎的實(shí)現(xiàn)
（1）主鍵索引實(shí)現(xiàn)的主要思想：
節(jié)點(diǎn)上的key是主鍵，然后將每行數(shù)據(jù)的地址信息存放在B+Tree的葉子節(jié)點(diǎn)的value中钦扭。結(jié)構(gòu)圖如下：
（2）非主鍵索引（普通索引或者唯一索引或組合索引）實(shí)現(xiàn)的主要思想：
節(jié)點(diǎn)上的key是索引行纫版，然后將每行數(shù)據(jù)的地址信息存放在B+Tree的葉子節(jié)點(diǎn)的value中。結(jié)構(gòu)圖如下（假設(shè)索引為col2）：
InnoDB存儲(chǔ)引擎的實(shí)現(xiàn)
（1）主鍵索引實(shí)現(xiàn)的主要思想：
節(jié)點(diǎn)上的key是主鍵客情，直接將每行數(shù)據(jù)的信息存放在B+Tree的葉子節(jié)點(diǎn)的value中其弊，結(jié)構(gòu)圖如下：
根據(jù)結(jié)構(gòu)可以看出，數(shù)據(jù)行本身存儲(chǔ)在B+Tree上膀斋，所有InnoDB要求每個(gè)表必須要有個(gè)主鍵梭伐，如果沒有添加，存儲(chǔ)引擎則會(huì)主動(dòng)默認(rèn)添加一個(gè)主鍵仰担。
這樣的存儲(chǔ)結(jié)構(gòu)被稱為“聚集索引”
聚集索引的優(yōu)點(diǎn)
可以索引覆蓋糊识，使效率更高
聚集索引的缺點(diǎn)
聚集索引的表在插入新行，或者主鍵被更新需要移動(dòng)的時(shí)候摔蓝，可能面臨頁分裂的問題
按照非主鍵索引查找赂苗，比較慢
主鍵id的長(zhǎng)度不能過長(zhǎng)限制
（2）非主鍵索引（普通索引或者唯一索引或組合索引）實(shí)現(xiàn)的主要思想：
節(jié)點(diǎn)上的key是索引列，每個(gè)葉子節(jié)點(diǎn)的value值存儲(chǔ)的是主鍵贮尉。結(jié)構(gòu)圖如下：
根據(jù)上面的結(jié)構(gòu)可以看出拌滋，如果按照非主鍵索引來查找數(shù)據(jù)，需要先在非主鍵索引結(jié)構(gòu)中查找到主鍵猜谚，然后再去主鍵索引結(jié)構(gòu)中再去拿出數(shù)據(jù)败砂。這個(gè)過程被稱為回表。
平時(shí)如果我們只需要取出主鍵id龄毡，就不要用select*去執(zhí)行吠卷。因?yàn)閟elect id from user where name = "s"和select * from user where name = "s"相比少一步回表操作。
2沦零、HASH索引
MySQL存儲(chǔ)引擎中只有memory存儲(chǔ)引擎執(zhí)行HASH索引祭隔。
HASH索引是通過設(shè)計(jì)抗碰撞HASH算法，將索引的信息存儲(chǔ)在HASH表中。
HASH索引優(yōu)點(diǎn)：
等值查詢速度比BTree要快疾渴，因?yàn)橹恍枰鲆淮蜨ASH運(yùn)算即可
HASH索引缺點(diǎn)：
只能進(jìn)行等值的查找千贯，不能進(jìn)行范圍查找
不能進(jìn)行模糊查找，只能對(duì)確定性的key值進(jìn)行查找
HASH算法的缺點(diǎn)搞坝，如果算法設(shè)計(jì)不夠精度搔谴，出現(xiàn)碰撞的情況，如果出現(xiàn)碰撞情況桩撮，就需要逐個(gè)遍歷整張表的每條數(shù)據(jù)
3敦第、FullText索引
FullText的底層也是使用BTree實(shí)現(xiàn)的，但是和普通的索引實(shí)現(xiàn)的原理是不同的店量。
僅MyISAM支持
FullText索引是將索引的列按照特定的算法芜果，將字段分割成幾部分（變成詞或詞組），然后對(duì)分割后的詞或詞組融师，進(jìn)行索引右钾。BTree中的節(jié)點(diǎn)存儲(chǔ)的信息如下：
FullText索引優(yōu)點(diǎn)：
對(duì)于較長(zhǎng)的字符串，查詢效率要比like %...%效率更高
FullText索引缺點(diǎn)：
創(chuàng)建FullText索引消耗的資源較大
4旱爆、RTree索引
RTree索引主要用來解決空間數(shù)據(jù)檢索問題
在MySQL5.0.16之前舀射，僅MyISAM支持，之后BDB怀伦，InnoDB等其他存儲(chǔ)引擎也支持
（1）脆烟、RTree結(jié)構(gòu)
RTree是BTree的多維版
RTree是Guttman在一片論文《R-trees: a dynamic index structure for spatial searching》中提出的為了解決空間查詢問題，而提出的房待。
RTree的結(jié)構(gòu)
RTree的結(jié)構(gòu)和BTree結(jié)構(gòu)類似浩淘，只不過上面存儲(chǔ)的信息不同，說清楚RTree上存儲(chǔ)的信息之前吴攒，先要介紹一下多維數(shù)據(jù)的查詢過程。
以二維數(shù)據(jù)為例砂蔽，RTree的目的就是要實(shí)現(xiàn)二維數(shù)據(jù)的的查找洼怔，如果要實(shí)現(xiàn)一個(gè)區(qū)域的查找，該如何實(shí)現(xiàn)呢左驾。假如有如下的區(qū)域：
在整個(gè)大的區(qū)域中有三個(gè)區(qū)域D1镣隶，D2，D3三個(gè)不規(guī)則區(qū)域诡右，通過MBR(Minimal Bounding Rectangle--最小邊界矩形)方法將不規(guī)則的區(qū)域框起來安岂，變成R8，R9和R10帆吻，稱R8是D1的MBR域那。其他的實(shí)線框同理（可以認(rèn)為都是一些不規(guī)則區(qū)域的MBR，不規(guī)則區(qū)域省略）猜煮。然后再將距離近的幾個(gè)區(qū)域劃分到一個(gè)大的區(qū)域內(nèi)次员，如上圖中的R3包括（R8,R9,R10）,同理R4（R9,R10,R12,R11）败许，R5(R14,R13)，R6(R15,R16)淑蔚，R7(R17,R18,R19)市殷。然后再對(duì)R3，R4刹衫，R5醋寝，R6，R7進(jìn)行區(qū)域劃分带迟。得到R1（R3音羞，R4，R5）邮旷，R2（R6黄选，R7），然后按這樣層級(jí)關(guān)系婶肩，構(gòu)建一個(gè)RTree办陷，如下如:
非葉子節(jié)點(diǎn)存儲(chǔ)信息：區(qū)域R的信息和指向葉子節(jié)點(diǎn)的指針
葉子節(jié)點(diǎn)存儲(chǔ)信息：區(qū)域R的信息和區(qū)域D的信息
通過這個(gè)結(jié)構(gòu)可以很快的查出某個(gè)區(qū)域，查找過程同BTree律歼。
詳細(xì)信息參照參考資料
參考資料
1民镜、《MySQL性能調(diào)優(yōu)與架構(gòu)設(shè)計(jì)》
2、http://www.reibang.com/p/eb5c9c05f2d4
3险毁、http://www.reibang.com/p/0371c9569736
4制圈、空間數(shù)據(jù)索引RTree完全解析
5、R-trees: a dynamic index structure for spatial searching
