MySQL 數(shù)據(jù)庫專題放送~

前言

數(shù)據(jù)庫索引本質(zhì)上是一種數(shù)據(jù)結(jié)構(gòu)(存儲結(jié)構(gòu)+算法)，目的是為了加快目標數(shù)據(jù)檢索的速度。

目錄

1.索引的本質(zhì)與原理？
2.索引的分類？
3.福利彩蛋

1.索引的本質(zhì)與原理

我們先看一個問題：

假設(shè)現(xiàn)在有100000條從0到10000且從大到小排列的整型數(shù)據(jù)，1條數(shù)據(jù)的大小假設(shè)(真的只是假設(shè))是1KB,操作系統(tǒng)的每次I/O數(shù)據(jù)塊(頁)大小是8KB。
如果現(xiàn)在我要查找其中 50001 這個數(shù)據(jù)值，有如下幾個方式：
1.最蠢的方式，遍歷，每次遍歷到一個值，就用這個值跟目標值做對比，如果不等于那么查找下一個。這樣的話那么每次I/O是8條數(shù)據(jù)，目標數(shù)據(jù)在50001/8 約6600多次I/O 才能找到目標數(shù)據(jù)。
2.二分查找，最好一次性將100000條數(shù)據(jù)全部讀到內(nèi)存，這樣查找也是很快的。

但是即使二分查找很快，但這些數(shù)據(jù)也不能單單通過一次I/O全部進入內(nèi)存，進行運算。

那么怎樣在I/O 塊大小 的限制下快速利用二分查找找到目標值呢？我們得引入新的數(shù)據(jù)結(jié)構(gòu)，B+樹正好可以解決上述I/O塊大小的限制，解決限制不是說增大了限制范圍，而是我們在此限制上改變了數(shù)據(jù)的存儲結(jié)構(gòu)，即在同等限制條件下，快速檢索到目標數(shù)據(jù)，如下是B+樹的原理講解：

注意，我們主要講解索引的原理，沒有必要過于糾結(jié)B+樹的各種操作，及代碼實現(xiàn)

1.1 B+ 樹

B+樹圖示

1.圖上藍色的塊為關(guān)鍵字，我們發(fā)現(xiàn)所有的關(guān)鍵字最終都會被包含在葉子節(jié)點當中。
  圖上的黃色區(qū)塊表示的是子樹的指針域，比如根節(jié)點下的P2指向的就是28-65之間的索引。
2.所有的葉子結(jié)點中包含了全部關(guān)鍵字的信息，及指向含有這些關(guān)鍵字記錄的指針，且葉子結(jié)點本身依關(guān)鍵字的大小自小而大
  的順序鏈接。 (而B 樹的葉子節(jié)點并沒有包括全部需要查找的信息)
3.所有的非終端結(jié)點可以看成是索引部分，結(jié)點中僅含有其子樹根結(jié)點中最大
 （或最小）關(guān)鍵字。 (而B 樹的非終節(jié)點也包含需要查找的有效信息)

現(xiàn)在我們來看下查找數(shù)據(jù) 60 的 查找過程，如下所示:

1.I/O第一次：讀入5、28、65 數(shù)據(jù)塊，在此同級別節(jié)點塊上，60在28到65之間(其實是二分查找)，那走P2指針指向的子樹。
2.I/O第二次：讀入28、35、56 數(shù)據(jù)塊，在此同級別節(jié)點塊上，60大于56，所以走P3指針指向的子樹(上圖中就是葉子節(jié)點)。
3.I/O第三次：讀入葉子節(jié)點，在這個葉子節(jié)點中，使用二分查找算法找到目標值60。

由上述查找過程所示統(tǒng)共需要三次I/O就能查到目標值，性能大大提升。

2.索引的分類？

2.1 聚簇索引 & 非聚簇索引

InnoDB 主鍵使用的是聚簇索引，MyISAM 不管是主鍵索引，還是二級索引使用的都是非聚簇索引。

下圖形象說明了聚簇索引表(InnoDB)和非聚簇索引(MyISAM)的區(qū)別：

聚簇索引與非聚簇索引

1.對于非聚簇索引表來說（右圖），表數(shù)據(jù)和索引是分成兩部分存儲的，主鍵索引和二級索引存儲上沒有任何區(qū)別。使用的是B+樹作為索引的存儲結(jié)構(gòu)，所有的節(jié)點都是索引，葉子節(jié)點存儲的是索引+索引對應(yīng)的記錄的地址。

2.對于聚簇索引表來說（左圖），表數(shù)據(jù)是和主鍵一起存儲的，主鍵索引的葉結(jié)點存儲行數(shù)據(jù)(包含了主鍵值)，二級索引的葉結(jié)點存儲行的主鍵值。使用的是B+樹作為索引的存儲結(jié)構(gòu)，非葉子節(jié)點都是索引關(guān)鍵字，但非葉子節(jié)點中的關(guān)鍵字中不存儲對應(yīng)記錄的具體內(nèi)容或內(nèi)容地址。葉子節(jié)點上的數(shù)據(jù)是主鍵與具體記錄(數(shù)據(jù)內(nèi)容)。

聚簇索引的優(yōu)點

1.當你需要取出一定范圍內(nèi)的數(shù)據(jù)時
，用聚簇索引也比用非聚簇索引好。
2.當通過聚簇索引查找目標數(shù)據(jù)時理論上比非聚簇索引要快，因為非聚簇索引定位到對應(yīng)主鍵時還要多一次目標記錄尋址,即多一次I/O。

聚簇索引的缺點

1.插入速度嚴重依賴于插入順序，按照主鍵的順序插入是最快的方式，否則將會出現(xiàn)頁分裂，嚴重影響性能。因此，對于InnoDB表，我們一般都會定義一個自增的ID列為主鍵。
2.更新主鍵的代價很高，因為將會導(dǎo)致被更新的行移動。因此，對于InnoDB表，我們一般定義主鍵為不可更新。
3.二級索引訪問需要兩次索引查找，第一次找到主鍵值，第二次根據(jù)主鍵值找到行數(shù)據(jù)。
二級索引的葉節(jié)點存儲的是主鍵值，而不是行指針（非聚簇索引存儲的是指針或者說是地址），這是為了減少當出現(xiàn)行移動或數(shù)據(jù)頁分裂時二級索引的維護工作，但會讓二級索引占用更多的空間。
4.采用聚簇索引插入新值比采用非聚簇索引插入新值的速度要慢很多，因為插入要保證主鍵不能重復(fù)，判斷主鍵不能重復(fù)，采用的方式在不同的索引下面會有很大的性能差距，聚簇索引遍歷所有的葉子節(jié)點，非聚簇索引也判斷所有的葉子節(jié)點，但是聚簇索引的葉子節(jié)點除了帶有主鍵還有記錄值，記錄的大小往往比主鍵要大的多。這樣就會導(dǎo)致聚簇索引在判定新記錄攜帶的主鍵是否重復(fù)時進行昂貴的I/O代價。

唯一索引

主鍵就是唯一索引，但是唯一索引不一定是主鍵，唯一索引可以為空，但是空值只能有一個，主鍵不能為空。
普通唯一索引：單個字段上建立唯一索引，需要此字段所在的列上不能有重復(fù)的值，屬于二級索引。
復(fù)合唯一索引：多個字段上聯(lián)合建立唯一索引，屬于二級索引。

覆蓋索引

查找的目標數(shù)據(jù)， 包含在索引中，如建立idx_colum1_colum2.

select colum1 from table where colum1 = ? and colum2 > ?

通過查詢索引就能確定最終的數(shù)據(jù)，不用再利用葉子節(jié)點中存儲的主鍵值去查詢對應(yīng)的數(shù)據(jù)。
覆蓋索引的性能是極高的。

索引原理篇講述完，下一篇講解索引的優(yōu)化，以及 explain 工具的使用。