一. 什么是索引？
索引的目的就是便于快速查找。一本書的索引就是目錄，可以讓我們快速定位到要查找的內(nèi)容；數(shù)據(jù)庫的數(shù)據(jù)是以記錄的方式存在的，所以索引的目的就是便于查找某一些記錄。
索引類型(常見的數(shù)據(jù)庫書籍中的關(guān)于索引類別的一些稱呼)：
??唯一索引：不允許其中任何兩行具有相同值的索引
????使用主鍵和候選鍵建立的索引就是唯一索引，因為主鍵和候選鍵都可以確定唯一一個元組，即一張表中不存在相同的主鍵和候選鍵。在MySQL中，當(dāng)你建立一個主鍵和候選鍵之后，MySQL會為它們分別建立索引。畢竟要想滿足唯一性，依然會在更新數(shù)據(jù)的時候檢驗是否已經(jīng)存在該主鍵或者候選鍵，而索引無疑是快速檢驗的標(biāo)配。
??主鍵索引：可以認(rèn)為是特殊的唯一索引，僅利用主鍵建立的索引
??單一索引：任何一個單一數(shù)據(jù)項建立的索引
????假如有下表【country，city，personNumber】，如果我們想查詢某個國家的人數(shù)，我們就應(yīng)當(dāng)以國家建立索引，這樣單一數(shù)據(jù)項建立的索引就是單一索引。
??復(fù)合索引：多個數(shù)據(jù)項建立的索引
????假如有下表【country，city，personNumber】，如果我們想查詢某個城市的人數(shù)，我們就應(yīng)當(dāng)以【country，city】建立索引，多個數(shù)據(jù)項建立索引的時候，我們應(yīng)當(dāng)指定其排序的先后順序，此處國家應(yīng)優(yōu)先排序，城市次之。
??聚簇索引：利用主鍵建立的索引，其物理存放順序與主鍵順序一致。因為數(shù)據(jù)只有一個物理存放順序，所以一個表只有一個聚簇索引。
????在MySQL中，選定主鍵之后將會自動為主鍵創(chuàng)建索引。該索引可以維護(hù)主鍵的唯一性。非葉子節(jié)點包含了主鍵值，而葉子節(jié)點則指向了一條完整的記錄
??非聚簇索引(二級索引，輔助索引)：除了聚簇索引之外，其余所有的索引都是非聚簇索引
????非聚簇索引為什么是二級索引呢？重點在于一個二字?？梢粤舷肴绻鸚HERE條件不是根據(jù)主鍵進(jìn)行索引，那么我們就需要基于該非主鍵建立的索引進(jìn)行檢索，這樣建立的索引葉子節(jié)點中包含了記錄的主鍵，再使用主鍵在聚簇索引中找尋到完整的記錄?？梢哉f進(jìn)行了兩次B+ Tree查找而不是一次
??覆蓋索引：一個索引包含(覆蓋)所要查詢的字段的值，注意覆蓋索引與具體的查詢有關(guān)
????假如有下表【country，city，personNumber】，如果我們想查詢某個城市的人數(shù)，覆蓋索引指的是可以將你想要查詢的列建立在一個索引中，如（國家，城市，人數(shù)）作為一個復(fù)合索引，此時查找某一個國家的所有城市利用索引就可以完成，實際上這也相當(dāng)于完成了聚簇索引的功能
二. 如何快速找到記錄
說到查找算法，最樸實的就是無序排列的遍歷了。在數(shù)據(jù)量較小的時候（PS：如果數(shù)據(jù)量較小我想數(shù)據(jù)庫也不會有這么快的發(fā)展），此方法也不失為一種好的方法，畢竟沒有相應(yīng)數(shù)據(jù)結(jié)構(gòu)的維護(hù)，插入更新數(shù)據(jù)的時候就可以再快一點。在學(xué)習(xí)算法的書籍中，數(shù)據(jù)結(jié)構(gòu)總也是扮演著重要的角色。無序排列的數(shù)據(jù)簡直就是一種佛系的數(shù)據(jù)結(jié)構(gòu)，不管不顧它就是那樣。一個好的算法基于一個合適的數(shù)據(jù)結(jié)構(gòu)的例子比比皆是，堆排序基于堆這種數(shù)據(jù)結(jié)構(gòu)；二叉搜索基于一棵構(gòu)建好的二叉搜索樹，哈希查找基于哈希表……所以數(shù)據(jù)庫中為了快速查找到需要的記錄也需要選擇合適的數(shù)據(jù)結(jié)構(gòu)。
三. 什么樣的數(shù)據(jù)結(jié)構(gòu)適合作為索引
下面就介紹幾種數(shù)據(jù)庫中快速查找記錄的數(shù)據(jù)結(jié)構(gòu)：
B+ Tree索引(MySQL，SQL Server，Oracle)
以上為一個3階的B+ Tree，其上的數(shù)字我們可以認(rèn)為使用ID建立起來的單一索引。如果需要使用如下SQL語句進(jìn)行查詢：
SELECT * FROM STUDENTS WHERE ID=1
?? 這個查詢語句只需要三次查找就可以找到ID為1的葉子節(jié)點，找到存放該條記錄（存放了ID為1的學(xué)生的所有屬性）的物理地址，進(jìn)而找到該條數(shù)據(jù)。
B+
Tree索引優(yōu)點
??①.全值匹配：指的是和索引中所有列進(jìn)行匹配。假設(shè)以(姓，名，出生日期)三個數(shù)據(jù)項建立復(fù)合索引，那么可以查找姓名為張三，出生日期在2000-12-12的人
??②.匹配最左前綴：假設(shè)以(姓，名，出生日期)三個數(shù)據(jù)項建立復(fù)合索引，可以查找所有姓張的人
??③.匹配列前綴：假設(shè)有姓為司徒，司馬的人，我們也可以查找第一列的前綴部分，如查找所有以司開頭的姓的人
??④.匹配范圍值：可以查找所有在李和張之間的姓的人，注意范圍查詢只在復(fù)合索引的優(yōu)先排序的第一列。（假設(shè)姓名按照拼音排序）
??⑤.精確匹配前面列并范圍匹配后一列：可以查找姓李并出生日期在2000-12-12之后的人或姓名為張三并出生日期在2000-12-12之后的人，注意范圍第一個范圍查詢后面的列無法再使用索引查詢
??⑥.只訪問索引的查詢：即查詢只需訪問索引，而無需訪問數(shù)據(jù)行。（此時應(yīng)想到索引中的覆蓋索引）
B+
Tree索引缺點
??①.如果不是按照索引的最左列開始查找，則無法使用索引。如無法查找名為龍的人，也無法查找在2000-12-12之后出生的人，當(dāng)然也無法查找姓中以龍結(jié)尾的人（注意為和含有的區(qū)別）
??②.不能跳過索引中的列：無法查找姓李并在2000-12-12之后出生的人
??③.如果查詢中包括某個列的范圍查詢，則其右邊所有列都無法使用索引優(yōu)化查詢
B Tree索引
哈希索引(MySQL，Oracle)
哈希索引優(yōu)點
??①.快速查詢：參與索引的字段只要進(jìn)行Hash運算之后就可以快速定位到該記錄，時間復(fù)雜度約為1
哈希索引缺點
??①.哈希索引只包含哈希值和行指針，所以不能用索引中的值來避免讀取行
??②.哈希索引數(shù)據(jù)并不是按照索引值順序存儲的，所以也就無法用于排序和范圍查詢
??③.哈希索引也不支持部分索引列查詢，因為哈希索引始終是使用索引列的全部數(shù)據(jù)進(jìn)行哈希計算的。
??④.哈希索引只支持等值比較查詢，如=，IN()，<=>操作
??⑤.如果哈希沖突較多，一些索引的維護(hù)操作的代價也會更高
參考資料
《高性能MySQL 第三版》Baron Schwartz / Peter Zaitsev / Vadim Tkachenko著
