我們在學習MySQL的時候經常會聽到索引這個詞，大概也知道這是什么，但是深究下去又說不出什么道道來，下面將會比較全面的介紹一下關于索引！
索引是什么？
這里用百度百科的一句話來說，在關系資料庫中，索引是一種單獨的、物理的對資料庫表中一列或多列的值進行排序的一種存盤結構，它是某個表中一列或若干列值的集合和相應的指向表中物理標識這些值的資料頁的邏輯指標清單，
簡單來說，索引就是我們一本書的目錄，通過目錄我們才能更快在一本書中查找到我們所要看的內容，同樣的，通過索引我們才能在資料庫中查找到我們的資料！
沒使用索引的MySQL
我們知道索引可以加快我們的查找，所以這里通過沒有使用索引的查找可以更加地讓我們認識到使用索引的好處，
我們的MySQL基本的頁存盤結構是頁，也就是我們的資料記錄都在頁里面，
當我們插入一條記錄的時候就會存盤在我們的資料頁中的存放行記錄的位置，并在我們的Page Directory頁目錄那里生成主鍵的資訊，我們的資料頁中記錄又可以組成一個單鏈表，每插入一條資料就會在尾節點那里添加上，
當我們通過主鍵查找某條記錄的時候可以在頁目錄中使用二分法快速定位到對應的槽，然后再遍歷該槽對應分組中的記錄即可快速找到指定的記錄，如果不是主鍵的話，那么只能遍歷單鏈表中的每條記錄對比查找，
所以，如果不用索引優化的話，那么在進行一條查找的sql的話，默認的流程是這樣子的：
- 定位到記錄所在的頁（需要遍歷雙向鏈表，找到所在的頁）
- 從所在的頁內中查找相應的記錄（是不是根據主鍵查詢，不是只能遍歷所在頁的單鏈表了）
如果在資料量特別大的時候，又是極端情況，遍歷雙向鏈表和單鏈表，速度就會顯得非常慢！
B-Tree索引與B+Tree索引
B-Tree索引結構
當人們開始談論索引的時候，如果沒有特別指明型別的話，那么多半說的就是B-Tree（B樹）所以，它使用的是B-Tree資料結構來存盤資料，大多數的MySQL引擎都支持這種索引（但實際上很多存盤引擎使用的是B+Tree，這個我們稍后再談到），我們這里通過B-Tree索引結構就可以極大的優化了上面的查找，
從圖中我們可以很明顯的感受到，使用索引后，就不需要再遍歷雙向鏈表那樣去查找頁，而是通過目錄就可以很快的定位到我們的實際的頁，如查找id為1的資料
- 首先小于4，可以確定在p1下，指向磁盤頁2
- 在磁盤頁里面，小于2，指向p1，然后查找到
而且，我們也可以根據圖總結出B-Tree的特點：
- 所有鍵值資料分布在整棵樹各個節點中
- 我們的查找有可能在非節點結束，比如上圖中，我們要找id為4的資料的話，在根節點就可以查找到
- 所有葉子節點都在同一層，并且以升序排列
B+Tree索引結構
B+Tree索引是依據B-Tree索引基礎上的一次優化，具體變化如下：
-
B+Tree 非葉子節點不存放資料
-
葉子節點存盤關鍵字和資料，非葉子節點的關鍵字也會沉到葉子節點，并且排序
-
葉子節點兩兩指標相互連接，形成一個雙向環形鏈表（符合磁盤的預讀特性），順序查詢性能更高（區間查找更加方便）
我們的B+Tree的優化到底有什么好處呢？
首先是我們的資料只放在了葉子節點上面，這個唯一的好處就是我們的非葉子節點可以存放更多的關鍵字了，整體就可以存放更多的資料，因為我們MySQL查詢程序是按頁加載資料的，每加載一頁就是一次IO操作，我們根磁盤頁存放的資料越少，關鍵字越多，那么整體的資料量就可以說是越多，
還有一個好處就是，在葉子節點形成雙向環形鏈表，這樣子如果要進行區間查詢的話，只需要順著葉子節點的指標向下查詢就行，而如果是B-Tree的話，就需要回傳上一級節點然后再讀取磁盤頁進行查找，節省了不少時間！
為什么不采用別的樹結構？
為什么要采用B-Tree的結構，甚至是B+Tree的結構呢？
其實還是跟我們的磁盤讀取的原因有關，上面我們說到了，MySQL查詢程序是按頁加載資料的，而我們的作業系統一般將記憶體和磁盤分割成固定大小的塊，每一塊稱為一頁，記憶體與磁盤以頁為單位交換資料，我們的記憶體每次讀取的就是MySQL分割成的一個頁大小，也就是一個索引點，圖中的一個磁盤頁，
采用普通二叉樹？不！
如果采用普通的二叉樹的話，我們要考慮到一種情況，那就是在極端的情況下，一棵樹是會退化成鏈表的，那么樹的優點就沒有了， 這與我們原來用雙向鏈表有何異同？
采用紅黑樹？不！
那么可能有人說了，如果采用紅黑樹，樹保持平衡不就行了嗎？確實，紅黑樹等平衡樹也可以用來實作索引，但是與我們的B-Tree/B+Tree來說性能要差很多，
我們上面說到了記憶體每一次I/O都是載入一個索引節點，也就是一個磁盤頁，如果資料不在同一個磁盤塊上，那么通常需要移動制動手臂進行尋道，而制動手臂因為其物理結構導致了移動效率低下，從而增加磁盤資料讀取時間，B-Tree/B+Tree相對于紅黑樹有更低的樹高，進行尋道的次數與樹高成正比，在同一個磁盤塊上進行訪問只需要很短的磁盤旋轉時間，所以 B-Tree/B+Tree 樹更適合磁盤資料的讀取，
而且為了減少磁盤 I/O 操作，磁盤往往不是嚴格按需讀取，而是每次都會預讀，預讀程序中，磁盤進行順序讀取，順序讀取不需要進行磁盤尋道，并且只需要很短的磁盤旋轉時間，速度會非常快，并且可以利用預讀特性，相鄰的節點也能夠被預先載入，
哈希索引
MySQL除了B+樹之外，還有一種常見的是就是哈希索引，
哈希索引就是采用一定的哈希演算法，把鍵值換算成新的哈希值，檢索時不需要類似B+樹那樣從根節點到葉子節點逐級查找，只需一次哈希演算法即可立刻定位到相應的位置，速度非常快，
本質上就是把鍵值換算成新的哈希值，根據這個哈希值來定位，
使用哈希索引最大的好處就是速度特別快，我們只需要一次定位就可以找到我們要的資料，時間復雜度為O(1)，但是我們的InnoDB（MySQL默認存盤引擎）默認使用的卻是B+樹索引，這也是因為哈希索引有一定的缺點：
- 無法用于排序和分組
- 只支持精確查找，無法用于部分查找和范圍查找
- 在有大量重復鍵值情況下，哈希索引的效率也是極低的---->哈希碰撞問題，
- 不支持最左匹配原則
可是如果一個索引值被頻繁使用的話，我們的InnoDB會再B+Tree索引之上再創建一個哈希索引，用來方便快速查找，這個功能叫做“自適應哈希索引”，
聚簇索引與輔助索引
MySQL資料庫中innodb存盤引擎，B+樹索引可以分為聚簇索引（也稱聚集索引，clustered index）和輔助索引（有時也稱非聚簇索引或二級索引，secondary index，non-clustered index），這兩種索引內部都是B+樹，聚集索引的葉子節點存放著一整行的資料，
Innodb中的主鍵索引是一種聚簇索引，非聚簇索引都是輔助索引，像復合索引、前綴索引、唯一索引，
聚簇索引
聚簇索引就是按照每張表的主鍵構造一顆B+樹，同時葉子節點中存放的就是整張表的行記錄資料，也將聚集索引的葉子節點稱為資料頁，這個特性決定了索引組織表中資料也是索引的一部分，每張表只能擁有一個聚簇索引，
Innodb通過主鍵聚集資料，如果沒有定義主鍵，innodb會選擇非空的唯一索引代替，如果沒有這樣的索引，innodb會隱式的定義一個主鍵來作為聚簇索引，
使用聚簇索引的優點：
- 資料訪問更快，因為聚簇索引將索引和資料保存在同一個B+樹中，因此從聚簇索引中獲取資料比非聚簇索引更快
- 聚簇索引對于主鍵的排序查找和范圍查找速度非常快
缺點：
- 插入速度嚴重依賴于插入順序，按照主鍵的順序插入是最快的方式，否則將會出現頁分裂，嚴重影響性能，因此，對于InnoDB表，我們一般都會定義一個自增的ID列為主鍵
- 更新主鍵的代價很高，因為將會導致被更新的行移動，因此，對于InnoDB表，我們一般定義主鍵為不可更新，
- 二級索引（輔助）訪問需要兩次索引查找，第一次找到主鍵值，第二次根據主鍵值找到行資料，
Innodb中聚簇索引示意圖：
InnoDB要求表必須有主鍵（MyISAM可以沒有），如果沒有顯式指定，則MySQL系統會自動選擇一個可以唯一標識資料記錄的列作為主鍵，如果不存在這種列，則MySQL自動為InnoDB表生成一個隱含欄位作為主鍵，這個欄位長度為6個位元組，型別為長整形，
輔助索引
在聚簇索引之上創建的索引稱之為輔助索引，輔助索引訪問資料總是需要二次查找，輔助索引葉子節點存盤的不再是行的物理位置，而是主鍵值，通過輔助索引首先找到的是主鍵值，再通過主鍵值找到資料行的資料頁，再通過資料頁中的Page Directory（頁目錄）找到資料行，
Innodb輔助索引的葉子節點并不包含行記錄的全部資料，葉子節點除了包含鍵值外，還包含了相應行資料的聚簇索引鍵，輔助索引的存在不影響資料在聚簇索引中的組織，所以一張表可以有多個輔助索引，在innodb中有時也稱輔助索引為二級索引，
Innodb中輔助索引示意圖：
通過對比我們就可以知道為什么我們對主鍵會有要求：
1、為什么不建議使用過長的欄位作為主鍵，因為所有輔助索引都參考主索引，過長的主索引會令輔助索引變得過大，
2、為什么用非單調的欄位作為主鍵在InnoDB中不是個好主意，因為InnoDB資料檔案本身是一顆B+Tree，非單調的主鍵會造成在插入新記錄時資料檔案為了維持B+Tree的特性而頻繁的分裂調整，十分低效，而使用自增欄位作為主鍵則是一個很好的選擇，
當然，如果我們通過索引優化，將輔助索引優化成覆寫索引，那么輔助索引也包含所有需要查詢的欄位的值，也就是我們的索引就是我們要的值，無需再訪問主索引了，這里，涉及到索引的優化不過多介紹！
MyISAM實作對比
上面我介紹了在InnoDB存盤引擎下的聚簇索引與輔助索引的實作，因為如果沒有說明具體的資料庫和存盤引擎，默認指的是MySQL中的InnoDB存盤引擎，但是我們MySQL還支持MyISAM存盤引擎，它也是支持聚簇索引與輔助索引的，
但是該引擎下的實作卻有些不同，我們的聚簇索引和輔助索引沒有什么區別，他們的葉子節點都不存放資料，而是存放資料記錄的地址，唯一的區別就是聚簇索引要求key是唯一的，而輔助索引的key可以重復，
所以如果嚴格的按照聚簇索引葉子節點存放資料來定義的話，MyISAM的索引都只能算是非聚簇索引！聚簇索引，或者嚴格說主鍵索引示意圖：
輔助索引示意圖：
為了更形象說明這兩種存盤引擎下兩種索引的區別，我們假想一個表如下圖存盤了4行資料，其中Id作為主索引，Name作為輔助索引，圖示清晰的顯示了聚簇索引和非聚簇索引的差異，
索引優點及使用
我們通過結構對比了使用索引的好處，總結下來的話就是：
- 大大減少了服務器需要掃描的資料行數
- 幫助服務器避免進行排序和分組，以及避免創建臨時表（B+Tree 索引是有序的，可以用于 ORDER BY 和 GROUP BY 操作，臨時表主要是在排序和分組程序中創建，不需要排序和分組，也就不需要創建臨時表）
- 將隨機 I/O 變為順序 I/O（B+Tree 索引是有序的，會將相鄰的資料都存盤在一起）
但是我們要知道，索引并不是最好的解決方案，總的來說，只有當索引幫助存盤引擎快速找到記錄帶來的好處大于其帶來的額外作業時，索引才是有效的，
- 對于非常小的表、大部分情況下簡單的全表掃描比建立索引更高效；
- 對于中到大型的表，索引就非常有效；
- 但是對于特大型的表，建立和維護索引的代價將會隨之增長，這種情況下，需要用到一種技術可以直接區分出需要查詢的一組資料，而不是一條記錄一條記錄地匹配，例如可以使用磁區技術（具體可以查看高性能MySQL第七章），
總結
這里僅僅是介紹了索引結構原理等，關于索引還有很多，如全文索引，空間索引等，以及索引的優化之類，這更多是我們要去學習的，
參考資料
高性能MySQL（第三版）
MySQL存盤結構
資料庫兩個神器索引和鎖(修訂版)
CS-Nodes聚簇索引與非聚簇索引
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/98204.html
標籤：Java