MySQL（二）——索引

索引

平衡二叉樹：左右節(jié)點(diǎn)的層級相差不大于1、左節(jié)點(diǎn)小于本節(jié)點(diǎn)死讹，本節(jié)點(diǎn)小于右節(jié)點(diǎn)墓猎，最多擁有兩個(gè)子節(jié)點(diǎn)

B樹：

枝節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量大于等于ceil(m/2)-1個(gè)且小于等于M-1個(gè)（注：ceil()是個(gè)朝正無窮方向取整的函數(shù) 如ceil(1.1)結(jié)果為2);
子節(jié)點(diǎn)數(shù)可以大于2工猜，每個(gè)節(jié)點(diǎn)包含的關(guān)鍵字多了乃秀，減少了層級顽频。

B+樹：

非葉子節(jié)點(diǎn)不存關(guān)鍵字?jǐn)?shù)據(jù)藤肢，所以每個(gè)非葉子節(jié)點(diǎn)存儲的關(guān)鍵字?jǐn)?shù)更多，樹的層級更少（磁盤每4k為一塊）
所有的關(guān)鍵字?jǐn)?shù)據(jù)地址都存在葉子節(jié)點(diǎn)上糯景，所以每次查找的次數(shù)都相同嘁圈，更穩(wěn)定。
葉子節(jié)點(diǎn)數(shù)據(jù)構(gòu)成了一個(gè)有序鏈表蟀淮，在查詢大小區(qū)間的數(shù)據(jù)時(shí)候更方便最住，緊密型更高
全節(jié)點(diǎn)遍歷更快，有利于全表掃描

如何定位記錄所在的頁

目錄項(xiàng)記錄頁怠惶，該頁中存放的數(shù)據(jù)只有（主鍵）索引的起始值和對應(yīng)子節(jié)點(diǎn)目錄（數(shù)據(jù)）頁的頁號信息
innodb采用了b+樹來做索引涨缚，所有的葉子節(jié)點(diǎn)是所有的用戶數(shù)據(jù)頁，也就是真正存數(shù)據(jù)的頁策治，而所有的非葉子節(jié)點(diǎn)都是目錄項(xiàng)記錄頁脓魏，當(dāng)數(shù)據(jù)量越來越大時(shí)，目錄項(xiàng)記錄頁也會越來越多通惫，此時(shí)需要一個(gè)更上層的節(jié)點(diǎn)來保存該層所有目錄項(xiàng)記錄頁的索引茂翔。最終頂層是一個(gè)根節(jié)點(diǎn)。如下圖：
當(dāng)進(jìn)行索引查詢的時(shí)候履腋，根據(jù)索引項(xiàng)珊燎，從根節(jié)點(diǎn)（單個(gè)目錄項(xiàng)記錄頁）通過二分法找到對應(yīng)的子節(jié)點(diǎn)的目錄項(xiàng)記錄頁，在再這個(gè)頁中再通過二分法找到下一個(gè)節(jié)點(diǎn)的目錄項(xiàng)記錄頁遵湖，直到找到葉子節(jié)點(diǎn)俐末，即數(shù)據(jù)頁，再通過二分法找到找到對應(yīng)的槽奄侠，再在槽里遍歷找到該數(shù)據(jù)。牛逼载矿！

聚簇索引（主鍵索引垄潮，葉子節(jié)點(diǎn)存放所有的數(shù)據(jù)）

存放目錄項(xiàng)記錄的頁分為不同的層次，在同一層次中的頁也是根據(jù)頁中目錄項(xiàng)記錄的主鍵大小順序排成一個(gè)雙向鏈表闷盔。存放用戶記錄的頁也是根據(jù)頁中用戶記錄的主鍵大小順序排成一個(gè)雙向鏈表弯洗。頁內(nèi)的記錄是按照主鍵的大小順序排成一個(gè)單向鏈表。
B+樹的葉子節(jié)點(diǎn)存儲的是完整的用戶記錄逢勾。

所謂完整的用戶記錄牡整，就是指這個(gè)記錄中存儲了所有列的值（包括隱藏列）。

我們把具有這兩種特性的B+樹稱為聚簇索引溺拱，所有完整的用戶記錄都存放在這個(gè)聚簇索引的葉子節(jié)點(diǎn)處逃贝。這種聚簇索引并不需要我們在MySQL語句中顯式的使用INDEX語句去創(chuàng)建（后邊會介紹索引相關(guān)的語句）谣辞，InnoDB存儲引擎會自動的為我們創(chuàng)建聚簇索引。另外有趣的一點(diǎn)是沐扳，在InnoDB存儲引擎中泥从，聚簇索引就是數(shù)據(jù)的存儲方式（所有的用戶記錄都存儲在了葉子節(jié)點(diǎn)），也就是所謂的索引即數(shù)據(jù)沪摄，數(shù)據(jù)即索引躯嫉。

二級索引（非聚簇索引也叫輔助索引）

使用其他列字段的大小作為排序依據(jù)（作為索引）
葉子節(jié)點(diǎn)存儲的不是完整的用戶記錄，而是索引列+主鍵
目錄頁記錄的不是主鍵+頁號杨拐，而是索引列+主鍵+頁號
查找到用戶記錄后祈餐，根據(jù)查找到的主鍵再去聚簇索引中查找一遍完整的用戶記錄也就是回表，需要2棵b+樹

聯(lián)合索引

如果根據(jù)c2和c3來建索引哄陶，則按照c2和c3的大小進(jìn)行排序

先把各記錄的頁按照c2進(jìn)行排序
如果c2相同則根據(jù)c3排序
葉子節(jié)點(diǎn)由c2帆阳、c3、主鍵組成
如果要查詢的數(shù)據(jù)剛好都在索引列里面奕筐，則不會回表舱痘，直接從二級索引的葉子節(jié)點(diǎn)中取數(shù)據(jù)。
如果是ab聯(lián)合索引离赫，查詢條件中b在前芭逝，a在后，那mysql會通過查詢優(yōu)化器進(jìn)行優(yōu)化渊胸，先用a來搜索旬盯。但是如果只用b來進(jìn)行查詢，則不會走索引翎猛，因?yàn)闆]辦法通過b的大小來二分查找胖翰。

注意事項(xiàng)

每當(dāng)為某個(gè)表創(chuàng)建一個(gè)B+樹索引（聚簇索引不是人為創(chuàng)建的，默認(rèn)就有）的時(shí)候切厘，都會為這個(gè)索引創(chuàng)建一個(gè)根節(jié)點(diǎn)頁面萨咳。最開始表中沒有數(shù)據(jù)的時(shí)候，每個(gè)B+樹索引對應(yīng)的根節(jié)點(diǎn)中既沒有用戶記錄疫稿，也沒有目錄項(xiàng)記錄培他。
隨后向表中插入用戶記錄時(shí)，先把用戶記錄存儲到這個(gè)根節(jié)點(diǎn)中遗座。
當(dāng)根節(jié)點(diǎn)中的可用空間用完時(shí)繼續(xù)插入記錄舀凛，此時(shí)會將根節(jié)點(diǎn)中的所有記錄復(fù)制到一個(gè)新分配的頁，比如頁a中途蒋，然后對這個(gè)新頁進(jìn)行頁分裂的操作猛遍，得到另一個(gè)新頁，比如頁b。這時(shí)新插入的記錄根據(jù)鍵值（也就是聚簇索引中的主鍵值懊烤，二級索引中對應(yīng)的索引列的值）的大小就會被分配到頁a或者頁b中梯醒，而根節(jié)點(diǎn)便升級為存儲目錄項(xiàng)記錄的頁。
一個(gè)B+樹索引的根節(jié)點(diǎn)自誕生之日起奸晴，便不會再移動冤馏。這樣只要我們對某個(gè)表建立一個(gè)索引，那么它的根節(jié)點(diǎn)的頁號便會被記錄到某個(gè)地方寄啼，然后凡是InnoDB存儲引擎需要用到這個(gè)索引的時(shí)候逮光，都會從那個(gè)固定的地方取出根節(jié)點(diǎn)的頁號，從而來訪問這個(gè)索引

MyISAM中的索引方案

MyISAM的索引方案雖然也使用樹形結(jié)構(gòu)墩划，但是卻將索引和數(shù)據(jù)分開存儲：

將表中的記錄按照記錄的插入順序單獨(dú)存儲在一個(gè)文件中涕刚，稱之為數(shù)據(jù)文件。這個(gè)文件并不劃分為若干個(gè)數(shù)據(jù)頁乙帮，有多少記錄就往這個(gè)文件中塞多少記錄就成了杜漠。我們可以通過行號而快速訪問到一條記錄。MyISAM 記錄也需要記錄頭信息來存儲一些額外數(shù)據(jù)察净，我們以index_demo表為例驾茴，看一下這個(gè)表中的記錄使用MyISAM作為存儲引擎在存儲空間中的表示：
由于在插入數(shù)據(jù)的時(shí)候并沒有刻意按照主鍵大小排序，所以我們并不能在這些數(shù)據(jù)上使用二分法進(jìn)行查找氢卡。
使用MyISAM存儲引擎的表會把索引信息另外存儲到一個(gè)稱為索引文件的另一個(gè)文件中锈至。MyISAM會單獨(dú)為表的主鍵創(chuàng)建一個(gè)索引，只不過在索引的葉子節(jié)點(diǎn)中存儲的不是完整的用戶記錄译秦，而是主鍵值 + 行號的組合峡捡。也就是先通過索引找到對應(yīng)的行號，再通過行號去找對應(yīng)的記錄筑悴！

CREATE TALBE 表名 (
    各種列的信息 ··· , 
    [KEY|INDEX] 索引名 (需要被索引的單個(gè)列或多個(gè)列)
)
ALTER TABLE 表名 ADD [INDEX|KEY] 索引名 (需要被索引的單個(gè)列或多個(gè)列);
ALTER TABLE 表名 DROP [INDEX|KEY] 索引名;

索引的代價(jià)

空間上的代價(jià)

這個(gè)是顯而易見的们拙，每建立一個(gè)索引都要為它建立一棵B+樹，每一棵B+樹的每一個(gè)節(jié)點(diǎn)都是一個(gè)數(shù)據(jù)頁阁吝，一個(gè)頁默認(rèn)會占用16KB的存儲空間砚婆，一棵很大的B+樹由許多數(shù)據(jù)頁組成，那可是很大的一片存儲空間呢突勇。
時(shí)間上的代價(jià)

每次對表中的數(shù)據(jù)進(jìn)行增装盯、刪、改操作時(shí)与境，都需要去修改各個(gè)B+樹索引。而且我們講過猖吴，B+樹每層節(jié)點(diǎn)都是按照索引列的值從小到大的順序排序而組成了雙向鏈表摔刁。不論是葉子節(jié)點(diǎn)中的記錄，還是內(nèi)節(jié)點(diǎn)中的記錄（也就是不論是用戶記錄還是目錄項(xiàng)記錄）都是按照索引列的值從小到大的順序而形成了一個(gè)單向鏈表海蔽。而增共屈、刪绑谣、改操作可能會對節(jié)點(diǎn)和記錄的排序造成破壞，所以存儲引擎需要額外的時(shí)間進(jìn)行一些記錄移位拗引，頁面分裂借宵、頁面回收啥的操作來維護(hù)好節(jié)點(diǎn)和記錄的排序。如果我們建了許多索引矾削，每個(gè)索引對應(yīng)的B+樹都要進(jìn)行相關(guān)的維護(hù)操作壤玫，這還能不給性能拖后腿么？

匹配左邊的列

最好不要跨過中間索引查詢前后索引哼凯，這樣只會用到最左側(cè)的連續(xù)索引欲间。

匹配列前綴

字符串排序，根據(jù)第一個(gè)字符的大小排序断部，如果相同則根據(jù)第二個(gè)猎贴，依次類推。
最好使用a = 'test%' 而不是a = '%test' 或者 a= '%test%'
如果對多個(gè)列同時(shí)進(jìn)行范圍查找的話蝴光，只有對索引最左邊的那個(gè)列進(jìn)行范圍查找的時(shí)候才能用到B+樹索引她渴，因?yàn)榈谝粋€(gè)列查出來的是范圍，只有在第一列相同的情況下蔑祟，第二列才做了排序趁耗，所以用不到這個(gè)索引。
如果最左邊的列是精確做瞪，第二列是范圍对粪，是可以用到索引，如果再有第三列是范圍装蓬，則只能遍歷了

排序

order by后的列的順序也必須按照索引列的順序給出著拭，不然用不了索引。且排序方式必須一致牍帚，不能一個(gè)desc一個(gè)asc
如果包含了非同一個(gè)索引的列儡遮，也不能使用索引
不能使用別的函數(shù)，比如UPPER或者a*2=4 可以改成a=4/2

分組

如果是索引字段按順序進(jìn)行分組暗赶，天然就是排好序的鄙币，可以直接分組。

回表

根據(jù)索引查數(shù)據(jù)時(shí)蹂随，由于數(shù)據(jù)記錄再磁盤中的存儲是相連的十嘿，順序IO速度很快。而他們所對應(yīng)的主鍵往往是不連續(xù)的岳锁，所以用這些不連續(xù)的id值到聚簇索引中去查完整記錄時(shí)绩衷，大概率分布在不同的數(shù)據(jù)頁，就變成隨機(jī)IO了
需要回表的記錄越多，使用二級索引的性能就越低咳燕，甚至讓某些查詢寧愿使用全表掃描也不使用二級索引勿决。比方說name值在Asa～Barlow之間的用戶記錄數(shù)量占全部記錄數(shù)量90%以上，那么如果使用idx_name_birthday_phone_number索引的話招盲，有90%多的id值需要回表低缩，這不是吃力不討好么，還不如直接去掃描聚簇索引（也就是全表掃描）曹货∨胤保回表的記錄越少，性能提升就越高控乾，越傾向二級索引+回表

覆蓋索引

最好返回結(jié)果只查索引值

列的基數(shù)

在記錄行數(shù)一定的情況下么介，列的基數(shù)越大，該列中的值越分散蜕衡，列的基數(shù)越小壤短，該列中的值越集中。最好為那些列的基數(shù)大的列建立索引慨仿，為基數(shù)太小列的建立索引效果可能不好久脯。

索引列的類型盡量小

數(shù)據(jù)類型越小，在查詢時(shí)進(jìn)行的比較操作越快（這是CPU層次）
數(shù)據(jù)類型越小镰吆，索引占用的存儲空間就越少帘撰，在一個(gè)數(shù)據(jù)頁內(nèi)就可以放下更多的記錄，從而減少磁盤I/O帶來的性能損耗万皿，也就意味著可以把更多的數(shù)據(jù)頁緩存在內(nèi)存中摧找，從而加快讀寫效率。

索引字符串值的前綴

由于字符串長的話占用的空間會比較多牢硅，如果整個(gè)字符串做索引蹬耘，b+樹占用的空間會很大，做字符串比較也會占用更多的時(shí)間减余，所以可以用前綴幾個(gè)字符來做索引综苔，比如前10個(gè)字符進(jìn)行索引，則匹配的時(shí)候只查出前10個(gè)字符匹配上的數(shù)據(jù)位岔，然后再回表查完整數(shù)據(jù)如筛。減少比較時(shí)間，節(jié)約了空間抒抬。
索引列前綴的方式無法支持使用索引排序杨刨。

主鍵插入順序

插入時(shí)不要忽大忽小，不然會造成頁面分裂和記錄位移擦剑，會造成性能損耗妖胀。最好是自增主鍵可免。

總結(jié)：

B+樹索引適用于下邊這些情況：

全值匹配
匹配左邊的列
匹配范圍值
精確匹配某一列并范圍匹配另外一列
用于排序
用于分組

在使用索引時(shí)需要注意下邊這些事項(xiàng)：

只為用于搜索伶唯、排序或分組的列創(chuàng)建索引
為列的基數(shù)大的列創(chuàng)建索引
索引列的類型盡量小
可以只對字符串值的前綴建立索引
只有索引列在比較表達(dá)式中單獨(dú)出現(xiàn)才可以適用索引
為了盡可能少的讓聚簇索引發(fā)生頁面分裂和記錄移位的情況帚稠，建議讓主鍵擁有AUTO_INCREMENT屬性怎顾。
定位并刪除表中的重復(fù)和冗余索引
盡量使用覆蓋索引進(jìn)行查詢，避免回表帶來的性能損耗怕品。

區(qū)（extent）

每16kb為一頁，連續(xù)64個(gè)頁就是一個(gè)區(qū)巾遭，默認(rèn)占用1MB肉康，每256個(gè)區(qū)被劃分成一個(gè)組。
相鄰頁的物理位置可能離的很遠(yuǎn)灼舍，所以在進(jìn)行讀寫的時(shí)候是隨機(jī)IO吼和，速度并不快
為了使用順序IO，引入了區(qū)的概念骑素，連續(xù)的64個(gè)區(qū)炫乓，在表中數(shù)據(jù)量大的時(shí)候，為某個(gè)索引分配空間的時(shí)候就不再按照頁為單位了献丑，而是區(qū)末捣。甚至數(shù)據(jù)非常多的時(shí)候可以一次性分配多個(gè)連續(xù)的區(qū)。
葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)分別擁有各自的區(qū)创橄，這些區(qū)的集合就是一個(gè)段箩做，一個(gè)索引會有一個(gè)葉子節(jié)點(diǎn)段和一個(gè)非葉子節(jié)點(diǎn)段。
碎片區(qū)：由于直接分配一個(gè)區(qū)就是占用了1mb的內(nèi)存妥畏，對于小表會造成浪費(fèi)邦邦，所以提出了碎片區(qū)的概念，這個(gè)區(qū)中并不是所有的頁都是同一個(gè)段的醉蚁，可能是不同的段燃辖。碎片區(qū)直屬于表空間，不屬于任何一個(gè)段馍管。只有當(dāng)某個(gè)段已經(jīng)占用了32個(gè)碎片區(qū)頁面后郭赐，才會以完整的區(qū)為單位來分配存儲空間。

訪問方法

const：主鍵或唯一約束索引的等值匹配确沸，如果是多個(gè)列捌锭，則每一個(gè)列需要與常數(shù)進(jìn)行等值比較
ref：普通的二級索引，如果是key is null罗捎，不管是唯一二級索引還是普通二級索引观谦，都是ref形式，因?yàn)镹ULL值的數(shù)量不限制.如果最左邊的連續(xù)索引全都是等值比較,則還是ref,否則就不是了
ref_or_null：普通的等值比較或者key is null則成為ref_or_null
range：對二級索引進(jìn)行等值或者某個(gè)范圍的值
index：如果可以直接通過遍歷某個(gè)索引的子節(jié)點(diǎn)的記錄來比較查詢條件桨菜，且返回值包含在索引列中豁状，不需要回表捉偏。把這種遍歷二級索引記錄成為index
all：掃全表

索引合并：

`Intersection`

某個(gè)查詢可以使用多個(gè)二級索引，將從多個(gè)二級索引中查詢到的結(jié)果取交集泻红。MySQL在某些特定的情況下才可能會使用到Intersection索引合并：

情況一：二級索引列是等值匹配的情況夭禽，對于聯(lián)合索引來說，在聯(lián)合索引中的每個(gè)列都必須等值匹配谊路，不能出現(xiàn)只匹配部分列的情況讹躯。為什么？因?yàn)橹挥忻總€(gè)列全都等值匹配的情況下缠劝，才會對主鍵排序潮梯。只有在這種情況下根據(jù)二級索引查詢出的結(jié)果集是按照主鍵值排序的。
情況二：主鍵列可以是范圍匹配

why惨恭？Intersection索引合并會把從多個(gè)二級索引中查詢出的主鍵值求交集秉馏，如果從各個(gè)二級索引中查詢的到的結(jié)果集本身就是已經(jīng)按照主鍵排好序的，那么求交集的過程就很easy啦脱羡。

按照有序的主鍵值去回表取記錄有個(gè)專有名詞兒萝究，叫：Rowid Ordered Retrieval，簡稱ROR

Union合并

與Intersection索引合并類似锉罐，MySQL在某些特定的情況下才可能會使用到Union索引合并糊肤。其實(shí)就是union取并集，intersection取交集

情況一：二級索引列是等值匹配的情況氓鄙，對于聯(lián)合索引來說馆揉，在聯(lián)合索引中的每個(gè)列都必須等值匹配，不能出現(xiàn)只出現(xiàn)匹配部分列的情況抖拦。
情況二：主鍵列可以是范圍匹配
情況三：使用Intersection索引合并的搜索條件

Sort-Union合并

先按照二級索引記錄的主鍵值進(jìn)行排序升酣，之后按照Union索引合并方式執(zhí)行的方式稱之為Sort-Union索引合并，這種Sort-Union索引合并比單純的Union索引合并多了一步對二級索引記錄的主鍵值排序的過程态罪。