MySQL 數(shù)據(jù)庫(kù)專(zhuān)題放送~

前言

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

目錄

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

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

我們先看一個(gè)問(wèn)題：

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

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

那么怎樣在I/O 塊大小 的限制下快速利用二分查找找到目標(biāo)值呢？我們得引入新的數(shù)據(jù)結(jié)構(gòu)，B+樹(shù)正好可以解決上述I/O塊大小的限制，解決限制不是說(shuō)增大了限制范圍，而是我們?cè)诖讼拗粕细淖兞藬?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，即在同等限制條件下，快速檢索到目標(biāo)數(shù)據(jù)，如下是B+樹(shù)的原理講解：

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

1.1 B+ 樹(shù)

B+樹(shù)圖示

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

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

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

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

2.索引的分類(lèi)？

2.1 聚簇索引 & 非聚簇索引

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

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

聚簇索引與非聚簇索引

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

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

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

1.當(dāng)你需要取出一定范圍內(nèi)的數(shù)據(jù)時(shí)
，用聚簇索引也比用非聚簇索引好。
2.當(dāng)通過(guò)聚簇索引查找目標(biāo)數(shù)據(jù)時(shí)理論上比非聚簇索引要快，因?yàn)榉蔷鄞厮饕ㄎ坏綄?duì)應(yīng)主鍵時(shí)還要多一次目標(biāo)記錄尋址,即多一次I/O。

聚簇索引的缺點(diǎn)

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

唯一索引

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

覆蓋索引

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

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

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

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