從數(shù)據(jù)結(jié)構(gòu)角度
1、B+樹索引
2、hash索引
3、FULLTEXT索引（InnoDB引擎5.7以后支持）
4、R-Tree索引（用于對GIS數(shù)據(jù)類型創(chuàng)建SPATIAL索引）
問題：這些索引的區(qū)別跟用途在哪？B+樹相比hash的優(yōu)點在哪？

從物理存儲角度
1、聚簇索引（clustered index）
2、非聚簇索引（non-clustered index）
問題：實現(xiàn)方式有什么差異？

從邏輯角度

1. 普通索引index :加速查找
2. 唯一索引
   主鍵索引：primary key ：加速查找+約束（不為空且唯一）
   唯一索引：unique：加速查找+約束 （唯一）
3. 聯(lián)合索引
   -primary key(id,name):聯(lián)合主鍵索引
   -unique(id,name):聯(lián)合唯一索引
   -index(id,name):聯(lián)合普通索引
4. 全文索引fulltext :用于搜索很長一篇文章的時候，效果最好。
5. 空間索引spatial :了解就好，幾乎不用
   問題：多列索引有什么命中規(guī)則？這幾種索引對加鎖有什么影響？

在《數(shù)據(jù)庫原理》一書中是這么解釋聚簇索引和非聚簇索引的區(qū)別的：聚簇索引的葉子節(jié)點就是數(shù)據(jù)節(jié)點，而非聚簇索引的葉子節(jié)點仍然是索引節(jié)點，只不過有指向?qū)?yīng)數(shù)據(jù)塊的指針。

聚簇索引

聚簇索引(innoDB的主鍵索引)：表數(shù)據(jù)按照索引的順序來存儲的，也就是說索引項的順序與表中記錄的物理順序一致。對于聚簇索引，葉子結(jié)點即存儲了真實的數(shù)據(jù)行，不再有另外單獨的數(shù)據(jù)頁。 在一張表上最多只能創(chuàng)建一個聚簇索引（不包括二級索引，二級索引可以有多個），因為真實數(shù)據(jù)的物理順序只能有一種。
"聚簇"指實際的數(shù)據(jù)行和相關(guān)的鍵值都保存在一起。
聚簇索引的二級索引(innoDB的其他索引)：葉子節(jié)點不會保存引用的行的物理位置,而是保存了行的主鍵值

注意：數(shù)據(jù)的物理存放順序與索引順序是一致的，即：只要索引是相鄰的，那么對應(yīng)的數(shù)據(jù)一定也是相鄰地存放在磁盤上的，如果主鍵不是自增id，那么可以想象，它會干些什么，不斷地調(diào)整數(shù)據(jù)的物理地址、分頁，當(dāng)然也有其他一些措施來減少這些操作，但卻無法徹底避免。但，如果是自增的，那就簡單了，它只需要一頁一頁地寫，索引結(jié)構(gòu)相對緊湊，磁盤碎片少，效率也高。

非聚簇索引

非聚簇索引（MyISAM的所有索引）：表數(shù)據(jù)存儲順序與索引順序無關(guān)。對于非聚簇索引，葉結(jié)點包含索引字段值及指向數(shù)據(jù)頁數(shù)據(jù)行的邏輯指針，其行數(shù)量與數(shù)據(jù)表行數(shù)據(jù)量一致。
MyISAM的B+Tree的葉子節(jié)點上的data，并不是數(shù)據(jù)本身，而是數(shù)據(jù)存放的地址。主索引和輔助索引沒啥區(qū)別，只是主索引中的key一定得是唯一的

因此，MYSQL中不同的數(shù)據(jù)存儲引擎對聚簇索引的支持不同就很好解釋了。下面，我們可以看一下MYSQL中MYISAM和INNODB兩種引擎的索引結(jié)構(gòu)。
如原始數(shù)據(jù)為：

MyISAM引擎的數(shù)據(jù)存儲方式如圖：

image.png

MYISAM是按列值與行號來組織索引的。它的葉子節(jié)點中保存的實際上是指向存放數(shù)據(jù)的物理塊的指針。從MYISAM存儲的物理文件我們能看出，MYISAM引擎的索引文件（.MYI）和數(shù)據(jù)文件(.MYD)是相互獨立的。

而InnoDB按聚簇索引的形式存儲數(shù)據(jù)，所以它的數(shù)據(jù)布局有著很大的不同。它存儲數(shù)據(jù)的結(jié)構(gòu)大致如下：

image.png

注：聚簇索引中的每個葉子節(jié)點包含主鍵值、事務(wù)ID、回滾指針(rollback pointer用于事務(wù)和MVCC）和余下的列(如col2)。
INNODB的二級索引與主鍵索引有很大的不同。InnoDB的二級索引的葉子包含主鍵值，而不是行指針(row pointers)，這減小了移動數(shù)據(jù)或者數(shù)據(jù)頁面分裂時維護二級索引的開銷，因為InnoDB不需要更新索引的行指針。其結(jié)構(gòu)大致如下：

image.png

INNODB和MYISAM的主鍵索引與二級索引的對比：

image.png

InnoDB的的二級索引的葉子節(jié)點存放的是KEY字段加主鍵值。因此，通過二級索引查詢首先查到是主鍵值，然后InnoDB再根據(jù)查到的主鍵值通過主鍵索引找到相應(yīng)的數(shù)據(jù)塊。而MyISAM的二級索引葉子節(jié)點存放的還是列值與行號的組合，葉子節(jié)點中保存的是數(shù)據(jù)的物理地址。所以可以看出MYISAM的主鍵索引和二級索引沒有任何區(qū)別，主鍵索引僅僅只是一個叫做PRIMARY的唯一、非空的索引，且MYISAM引擎中可以不設(shè)主鍵。
為了更形象說明這兩種索引的區(qū)別，我們假想一個表如下圖存儲了4行數(shù)據(jù)。其中Id作為主索引，Name作為輔助索引。圖示清晰的顯示了聚簇索引和非聚簇索引的差異。

對于聚簇索引存儲來說，行數(shù)據(jù)和主鍵B+樹存儲在一起，輔助鍵B+樹只存儲輔助鍵和主鍵，主鍵和非主鍵B+樹幾乎是兩種類型的樹。對于非聚簇索引存儲來說，主鍵B+樹在葉子節(jié)點存儲指向真正數(shù)據(jù)行的指針，而非主鍵。

InnoDB使用的是聚簇索引，將主鍵組織到一棵B+樹中，而行數(shù)據(jù)就儲存在葉子節(jié)點上，若使用"where id = 14"這樣的條件查找主鍵，則按照B+樹的檢索算法即可查找到對應(yīng)的葉節(jié)點，之后獲得行數(shù)據(jù)。若對Name列進行條件搜索，則需要兩個步驟：第一步在輔助索引B+樹中檢索Name，到達其葉子節(jié)點獲取對應(yīng)的主鍵。第二步使用主鍵在主索引B+樹種再執(zhí)行一次B+樹檢索操作，最終到達葉子節(jié)點即可獲取整行數(shù)據(jù)。

MyISM使用的是非聚簇索引，非聚簇索引的兩棵B+樹看上去沒什么不同，節(jié)點的結(jié)構(gòu)完全一致只是存儲的內(nèi)容不同而已，主鍵索引B+樹的節(jié)點存儲了主鍵，輔助鍵索引B+樹存儲了輔助鍵。表數(shù)據(jù)存儲在獨立的地方，這兩顆B+樹的葉子節(jié)點都使用一個地址指向真正的表數(shù)據(jù)，對于表數(shù)據(jù)來說，這兩個鍵沒有任何差別。由于索引樹是獨立的，通過輔助鍵檢索無需訪問主鍵的索引樹。

為了更形象說明這兩種索引的區(qū)別，我們假想一個表如下圖存儲了4行數(shù)據(jù)。其中Id作為主索引，Name作為輔助索引。圖示清晰的顯示了聚簇索引和非聚簇索引的差異。

image.png

我們重點關(guān)注聚簇索引，看上去聚簇索引的效率明顯要低于非聚簇索引，因為每次使用輔助索引檢索都要經(jīng)過兩次B+樹查找，這不是多此一舉嗎？聚簇索引的優(yōu)勢在哪？

1 由于行數(shù)據(jù)和葉子節(jié)點存儲在一起，這樣主鍵和行數(shù)據(jù)是一起被載入內(nèi)存的，找到葉子節(jié)點就可以立刻將行數(shù)據(jù)返回了，如果按照主鍵Id來組織數(shù)據(jù)，獲得數(shù)據(jù)更快。

2 輔助索引使用主鍵作為"指針" 而不是使用地址值作為指針的好處是，減少了當(dāng)出現(xiàn)行移動或者數(shù)據(jù)頁分裂時輔助索引的維護工作，使用主鍵值當(dāng)作指針會讓輔助索引占用更多的空間，換來的好處是InnoDB在移動行時無須更新輔助索引中的這個"指針"。也就是說行的位置（實現(xiàn)中通過16K的Page來定位，后面會涉及）會隨著數(shù)據(jù)庫里數(shù)據(jù)的修改而發(fā)生變化（前面的B+樹節(jié)點分裂以及Page的分裂），使用聚簇索引就可以保證不管這個主鍵B+樹的節(jié)點如何變化，輔助索引樹都不受影響。

轉(zhuǎn)自：http://wangxinchun.iteye.com/blog/2373650