第四章 索引
1. 索引概述
MySQL官方對(duì)索引的定義為：索引（Index）是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。
索引的本質(zhì)：索引是數(shù)據(jù)結(jié)構(gòu)着饥。你可以簡(jiǎn)單理解為“排好序的快速查找數(shù)據(jù)結(jié)構(gòu)”犀农，滿(mǎn)足特定查找算法。這些數(shù)據(jù)結(jié)構(gòu)以某種方式指向數(shù)據(jù)贱勃， 這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上實(shí)現(xiàn)高級(jí)查找算法井赌。
1.1 優(yōu)點(diǎn)
（1）提高數(shù)據(jù)檢索的效率谤逼，降低數(shù)據(jù)庫(kù)的IO成本贵扰，創(chuàng)建索引的主要原因。
（2）通過(guò)創(chuàng)建唯一索引流部，可以保證數(shù)據(jù)庫(kù)表中每一行數(shù)據(jù)的唯一性戚绕。
（3）在實(shí)現(xiàn)數(shù)據(jù)的參考完整性方面，可以加速表和表之間的連接枝冀。換句話(huà)說(shuō)舞丛，對(duì)于有依賴(lài)關(guān)系的子表和父表聯(lián)合查詢(xún)時(shí)耘子，可以提高查詢(xún)速度。
（4）在使用分組和排序子句進(jìn)行數(shù)據(jù)查詢(xún)時(shí)球切，可以顯著減少查詢(xún)中分組和排序的時(shí)間谷誓，降低了CPU的消耗。
1.2 缺點(diǎn)
（1）創(chuàng)建索引和維護(hù)索引要耗費(fèi)時(shí)間吨凑，并且隨著數(shù)據(jù)量的增加捍歪，所耗費(fèi)的時(shí)間也會(huì)增加。
（2）索引需要占磁盤(pán)空間鸵钝，除了數(shù)據(jù)表占數(shù)據(jù)空間之外糙臼，每一個(gè)索引還要占一定的物理空間存儲(chǔ)在磁盤(pán)上，如果有大量的索引恩商，索引文件就可能比數(shù)據(jù)文件更快達(dá)到最大文件尺寸变逃。
（3）雖然索引大大提高了查詢(xún)速度，同時(shí)卻會(huì)降低更新表的速度怠堪。當(dāng)對(duì)表中的數(shù)據(jù)進(jìn)行增加揽乱、刪除和修改的時(shí)候，索引也要?jiǎng)討B(tài)地維護(hù)粟矿，這樣就降低了數(shù)據(jù)的維護(hù)速度锤窑。
2. B+ 樹(shù)索引設(shè)計(jì)推演
2.1 無(wú)索引的查找
SELECT [列名列表] FROM 表名 WHERE 列名 = xxx;
在一個(gè)頁(yè)中的查找
假設(shè)目前表中的記錄比較少，所有的記錄都可以被存放在一個(gè)頁(yè)中嚷炉，在查找記錄的時(shí)候可以根據(jù)搜索條件的不同分為兩種情況：
- 以主鍵為搜索條件
可以在頁(yè)目錄中使用二分法快速定位到對(duì)應(yīng)的槽渊啰，然后再遍歷該槽對(duì)應(yīng)分組中的記錄即可快速找到指定的記錄。- 以其他列作為搜索條件
因?yàn)樵跀?shù)據(jù)頁(yè)中并沒(méi)有對(duì)非主鍵建立所謂的頁(yè)目錄申屹，所以我們無(wú)法通過(guò)二分法快速定位相應(yīng)的槽绘证。這種情況下只能從最小記錄開(kāi)始依次遍歷單鏈表中的每條記錄，然后對(duì)比每條記錄是不是符合搜索條件哗讥。很顯然嚷那，這種查找的效率是非常低的。
在很多頁(yè)中查找
大部分情況下我們表中存放的記錄都是非常多的杆煞，需要好多的數(shù)據(jù)頁(yè)來(lái)存儲(chǔ)這些記錄魏宽。在很多頁(yè)中查找記錄的話(huà)可以分為兩個(gè)步驟：
- 定位到記錄所在的頁(yè)。
- 從所在的頁(yè)內(nèi)查找相應(yīng)的記錄决乎。
總結(jié)：在沒(méi)有索引時(shí)队询，不論是根據(jù)主鍵列或者其他列的值進(jìn)行查找，只能
從第一個(gè)頁(yè)沿著雙向鏈表一直往下找构诚，在每一個(gè)頁(yè)中根據(jù)我們上面的查找方式去查找指定的記錄蚌斩。因?yàn)橐闅v所有的數(shù)據(jù)頁(yè)，所以這種方式顯然是超級(jí)耗時(shí)的范嘱。
2.2 設(shè)計(jì)索引
mysql> CREATE TABLE index_demo(
-> c1 INT,
-> c2 INT,
-> c3 CHAR(1),
-> PRIMARY KEY(c1)
-> ) ROW_FORMAT = Compact;
這個(gè)表使用Compact行格式來(lái)實(shí)際存儲(chǔ)記錄的送膳。這里簡(jiǎn)化index_demo表的行格式示意圖：
record_type：記錄頭信息的一項(xiàng)屬性员魏，表示記錄的類(lèi)型，0表示普通記錄叠聋、1表示目錄項(xiàng)記錄撕阎、2表示最小記錄、3表示最大記錄碌补。next_record：記錄頭信息的一項(xiàng)屬性闻书，表示下一條地址相對(duì)于本條記錄的地址偏移量，我們用箭頭來(lái)表明下一條記錄是誰(shuí)脑慧。各個(gè)列的值：這里只記錄在index_demo表中的三個(gè)列魄眉，分別是c1、c2和c3闷袒。其他信息：除了上述3種信息以外的所有信息坑律，包括其他隱藏列的值以及記錄的額外信息。
將記錄格式示意圖的其他信息項(xiàng)暫時(shí)去掉并把它豎起來(lái)的效果就是這樣：
把一些記錄放到頁(yè)里的示意圖就是：
2.2.1. 一個(gè)簡(jiǎn)單的索引設(shè)計(jì)方案
因?yàn)楦鱾€(gè)頁(yè)中的記錄并沒(méi)有規(guī)律囊骤，我所以不得不依次遍歷所有的數(shù)據(jù)頁(yè)晃择。所以如果我們
想快速的定位到需要查找的記錄在哪些數(shù)據(jù)頁(yè)中該咋辦？我們可以為快速定位記錄所在的數(shù)據(jù)頁(yè)而建立一個(gè)目錄也物，建這個(gè)目錄必須完成下邊這些事：
- 下一個(gè)數(shù)據(jù)頁(yè)中用戶(hù)記錄的主鍵值必須大于上一個(gè)頁(yè)中用戶(hù)記錄的主鍵值宫屠。
- 給所有的頁(yè)建立一個(gè)目錄項(xiàng)。
以
頁(yè)28為例滑蚯，它對(duì)應(yīng)目錄項(xiàng)2浪蹂，這個(gè)目錄項(xiàng)中包含著該頁(yè)的頁(yè)號(hào)28以及該頁(yè)中用戶(hù)記錄的最小主鍵值5。我們只需要把幾個(gè)目錄項(xiàng)在物理存儲(chǔ)器上連續(xù)存儲(chǔ)（比如：數(shù)組）告材，就可以實(shí)現(xiàn)根據(jù)主鍵值快速查找某條記錄的功能了坤次。比如：查找主鍵值為20的記錄，具體查找過(guò)程分兩步：
- 先根據(jù)
二分法快速確定出主鍵值為20的記錄在目錄項(xiàng)3中（因?yàn)?12 < 20 < 209 ）斥赋，它對(duì)應(yīng)的頁(yè)是頁(yè)9缰猴。- 再根據(jù)前邊說(shuō)的在頁(yè)中查找記錄的方式去
頁(yè)9中定位具體的記錄。
至此疤剑，針對(duì)數(shù)據(jù)頁(yè)做的簡(jiǎn)易目錄就搞定了滑绒。這個(gè)目錄有一個(gè)別名，稱(chēng)為索引隘膘。
2.2.2. 迭代1次：1個(gè)目錄項(xiàng)組成的頁(yè)
2.2.3. 迭代2次：多個(gè)目錄項(xiàng)組成的頁(yè)
2.2.4. 迭代3次：目錄項(xiàng)記錄頁(yè)的目錄頁(yè)
這個(gè)數(shù)據(jù)結(jié)構(gòu)疑故，它的名稱(chēng)是 B+樹(shù) 。
一個(gè)B+樹(shù)的節(jié)點(diǎn)其實(shí)可以分成好多層棘幸，規(guī)定最下邊的那層（第
0層）焰扳，用來(lái)存放用戶(hù)記錄，之后依次往上加误续。之前我們做了一個(gè)非常極端的假設(shè)：存放用戶(hù)記錄的頁(yè)最多存放3條記錄吨悍，存放目錄項(xiàng)記錄的頁(yè)最多存放4條記錄。其實(shí)真實(shí)環(huán)境中一個(gè)頁(yè)存放的記錄數(shù)量是非常大的蹋嵌，假設(shè)所有存放用戶(hù)記錄的葉子節(jié)點(diǎn)代表的數(shù)據(jù)頁(yè)可以存放100條用戶(hù)記錄育瓜，所有存放目錄項(xiàng)記錄的內(nèi)節(jié)點(diǎn)代表的數(shù)據(jù)頁(yè)可以存放1000條目錄項(xiàng)記錄，那么：
- 如果B+樹(shù)只有1層栽烂，也就是只有1個(gè)用于存放用戶(hù)記錄的節(jié)點(diǎn)躏仇，最多能存放
100條記錄。- 如果B+樹(shù)有2層腺办，最多能存放
1000×100=10,0000條記錄焰手。- 如果B+樹(shù)有3層，最多能存放
1000×1000×100=1,0000,0000條記錄怀喉。- 如果B+樹(shù)有4層书妻，最多能存放
1000×1000×1000×100=1000,0000,0000條記錄。相當(dāng)多的記錄９！６懵摹！
你的表里能存放100000000000條記錄嗎聊闯？所以一般情況下工猜，我們用到的B+樹(shù)都不會(huì)超過(guò)4層，那我們通過(guò)主鍵值去查找某條記錄最多只需要做4個(gè)頁(yè)面內(nèi)的查找（查找3個(gè)目錄項(xiàng)頁(yè)和一個(gè)用戶(hù)記錄頁(yè)）菱蔬，又因?yàn)樵诿總€(gè)頁(yè)面內(nèi)有所謂的Page Directory（頁(yè)目錄）篷帅，所以在頁(yè)面內(nèi)也可以通過(guò)二分法實(shí)現(xiàn)快速定位記錄。
3. 常見(jiàn)索引及其概念
索引按照物理實(shí)現(xiàn)方式拴泌，索引可以分為 2 種：
聚簇索引和非聚簇索引犹褒。
非聚集索引也稱(chēng)為二級(jí)索引或者輔助索引。
3.1 聚簇索引
特點(diǎn)：
- 使用記錄主鍵值的大小進(jìn)行記錄和頁(yè)的排序弛针，這包括三個(gè)方面的含義：
頁(yè)內(nèi)的記錄是按照主鍵的大小順序排成一個(gè)單向鏈表叠骑。- 各個(gè)存放
用戶(hù)記錄的頁(yè)也是根據(jù)頁(yè)中用戶(hù)記錄的主鍵大小順序排成一個(gè)雙向鏈表。- 存放
目錄項(xiàng)記錄的頁(yè)分為不同的層次削茁，在同一層次中的頁(yè)也是根據(jù)頁(yè)中目錄項(xiàng)記錄的主鍵大小順序排成一個(gè)雙向鏈表宙枷。
- B+樹(shù)的
葉子節(jié)點(diǎn)存儲(chǔ)的是完整的用戶(hù)記錄。
所謂完整的用戶(hù)記錄茧跋，就是指這個(gè)記錄中存儲(chǔ)了所有列的值（包括隱藏列）慰丛。
優(yōu)點(diǎn)：
數(shù)據(jù)訪(fǎng)問(wèn)更快，因?yàn)榫鄞厮饕龑⑺饕蛿?shù)據(jù)保存在同一個(gè)B+樹(shù)中瘾杭，因此從聚簇索引中獲取數(shù)據(jù)比非聚簇索引更快- 聚簇索引對(duì)于主鍵的
排序查找和范圍查找速度非匙绮。快- 按照聚簇索引排列順序，查詢(xún)顯示一定范圍數(shù)據(jù)的時(shí)候，由于數(shù)據(jù)都是緊密相連贤笆，數(shù)據(jù)庫(kù)不用從多個(gè)數(shù)據(jù)塊中提取數(shù)據(jù)蝇棉，所以
節(jié)省了大量的io操作。
缺點(diǎn)：
插入速度嚴(yán)重依賴(lài)于插入順序芥永，按照主鍵的順序插入是最快的方式篡殷，否則將會(huì)出現(xiàn)頁(yè)分裂，嚴(yán)重影響性能埋涧。因此板辽，對(duì)于InnoDB表，我們一般都會(huì)定義一個(gè)自增ID列為主鍵更新主鍵的代價(jià)很高棘催，因?yàn)閷?huì)導(dǎo)致被更新的行移動(dòng)劲弦。因此，對(duì)于InnoDB表醇坝，我們一般定義主鍵為不可更新二級(jí)索引訪(fǎng)問(wèn)需要兩次索引查找邑跪，第一次找到主鍵值，第二次根據(jù)主鍵值找到行數(shù)據(jù)
3.2 二級(jí)索引（輔助索引纲仍、非聚簇索引）
二級(jí)索引：以非主鍵列創(chuàng)建的索引呀袱。也會(huì)生成一棵B+樹(shù)，但此棵樹(shù)只存儲(chǔ)主鍵值郑叠，不存儲(chǔ)其他列數(shù)據(jù)夜赵，若需找到其他列數(shù)據(jù)，還需再到聚簇索引B+樹(shù)尋找一遍所需要的值乡革。
回表：再到聚簇索引B+樹(shù)尋找一遍所需要的值的過(guò)程就是回表寇僧。
3.3 聯(lián)合索引
同時(shí)以多個(gè)列的大小作為排序規(guī)則，也就是同時(shí)為多個(gè)列建立索引沸版，比方說(shuō)我們想讓B+樹(shù)按照
c2和c3列的大小進(jìn)行排序嘁傀，這個(gè)包含兩層含義：
- 先把各個(gè)記錄和頁(yè)按照c2列進(jìn)行排序。
- 在記錄的c2列相同的情況下视粮，采用c3列進(jìn)行排序
注意：聯(lián)合索引细办，本質(zhì)上也是一個(gè)二級(jí)索引。只不過(guò)是以多列的值先后排序的二級(jí)索引
