摩西摩西淋淀，這是花生的第一篇博客——20200830

1弟头、B+樹

B+樹的特點(diǎn)：

（1）適用于磁盤IO的多路平衡查找樹阁危。由于磁盤IO的速度很慢，需要一種能夠有效減少IO次數(shù)的數(shù)據(jù)結(jié)構(gòu)來組織磁盤中的數(shù)據(jù)状飞。B+樹就是這樣一種數(shù)據(jù)結(jié)構(gòu)毫胜。相比于二叉平衡查找樹，B+樹增加了子樹的數(shù)量來降低整個樹的高度昔瞧，而每個節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)量由磁盤的最小分區(qū)單位——磁盤頁（InnoDB為16K）來決定指蚁。一個磁盤頁即為B+樹的一個節(jié)點(diǎn)，節(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)量由磁盤頁的大小決定自晰，并且規(guī)定了每個磁盤頁的利用率不得低于50%凝化，否則就需要進(jìn)行合并。如果超過了磁盤頁的容量酬荞，則發(fā)生分裂搓劫。

（2）B+樹是一種平衡查找樹瞧哟。也即B+樹本身帶有一定的有序性。B+樹中枪向，所有的數(shù)據(jù)都存放在同一層的葉子節(jié)點(diǎn)上勤揩，體現(xiàn)了B+樹的高度平衡性，并且每個葉子節(jié)點(diǎn)之間通過雙向鏈表連接秘蛔，也即陨亡，B+樹索引的所有數(shù)據(jù)項(xiàng)都按照大小順序在B+樹的葉子節(jié)點(diǎn)上形成了雙向鏈表結(jié)構(gòu)。因此B+樹非常適合于順序遍歷和范圍查找深员。

（3）不同于B樹的是负蠕，B+樹將索引的全部的數(shù)據(jù)項(xiàng)都存放在處于同一高度的葉子節(jié)點(diǎn)，而非頁節(jié)點(diǎn)只有索引列倦畅，也即只有葉子節(jié)點(diǎn)代表了所有的數(shù)據(jù)項(xiàng)遮糖。而B樹的每個節(jié)點(diǎn)的關(guān)鍵字都代表了一個數(shù)據(jù)項(xiàng)，也即整個樹的節(jié)點(diǎn)的所有關(guān)鍵字代表了全部的數(shù)據(jù)項(xiàng)叠赐。因此欲账，B樹的每個節(jié)點(diǎn)不僅要存放關(guān)鍵字以及子節(jié)點(diǎn)的指針，還要存放指向數(shù)據(jù)項(xiàng)的指針芭概，因此每個磁盤頁（即每個節(jié)點(diǎn)）所能存放的關(guān)鍵字?jǐn)?shù)量要小于B+樹赛不，因此B+樹的階數(shù)是要高于B樹的，因而深度更小谈山。

2俄删、B+樹索引

索引組織表

在InnoDB存儲引擎中，表都是根據(jù)主鍵順序組織存放的奏路，這種存儲方式的表稱為索引組織表畴椰。在InnoDB存儲引擎表中，每張表都有一個主鍵鸽粉，如果在創(chuàng)建表時如果沒有顯式定義主鍵斜脂，則InnoDB會按如下方式選擇或創(chuàng)建主鍵：

（1）如果表中有非空的唯一索引（Unique Not Null），則定義的第一個非空唯一索引列即為主鍵

（2）否則触机，InnoDB存儲引擎會自動創(chuàng)建一個6字節(jié)大小的指針

可以通過"_rowid"字段來select表中的主鍵

創(chuàng)建一張表：

插入幾條數(shù)據(jù)：

查詢主鍵帚戳，主鍵為第一個定義的非空唯一索引d

不過_rowid只能查看單個列為主鍵的情況，多列主鍵或者InnoDB自生成的主鍵是看不了的
刪掉再重建一張表：

插入幾條數(shù)據(jù)：

查看_rowid儡首，失斊巍：

給表增加主鍵，主鍵包含a和b兩列：

查看_rowid蔬胯，失敹怨：

但是如果主鍵只有一列：

那么查詢_rowid，成功：

（可以看到，當(dāng)在表創(chuàng)建之后添加主鍵产场，那么被設(shè)置為主鍵的列如果沒有設(shè)置為NOT NULL鹅髓，那么在創(chuàng)建主鍵之后會被自動修改為NOT NULL）

聚集索引

聚集索引并不是一種特殊的索引結(jié)構(gòu)，它正是基于B+樹結(jié)構(gòu)京景，將整張表按照主鍵作為索引列組織成一棵B+樹窿冯，整張表的行數(shù)據(jù)都順序存放在索引的葉子節(jié)點(diǎn)，每個數(shù)據(jù)頁通過雙向鏈表進(jìn)行連接确徙。此時整張表就成為了B+樹索引的一部分醒串，葉子節(jié)點(diǎn)包含了所有行數(shù)據(jù)，而飛葉節(jié)點(diǎn)則只包含索引主鍵列米愿∠梅铮可以說鼻吮，聚集索引是一種索引組織表的實(shí)現(xiàn)形式育苟。

因?yàn)榫奂饕龑?shí)際上就是一張表，表的行數(shù)據(jù)只能組織成一棵B+樹來進(jìn)行排序椎木，因此一張表只能擁有一個聚集索引

輔助索引

輔助索引也稱為非聚集索引违柏、二級索引。一張表只能有一個聚集索引香椎，但可以有多個輔助索引漱竖，它也是一種B+樹的結(jié)構(gòu)，但與聚集索引不同的是畜伐，它的葉子節(jié)點(diǎn)并沒有存放行記錄信息馍惹，除了索引鍵值之外，還包含了一個指向?qū)?yīng)行記錄的書簽玛界，也就是主鍵万矾。輔助索引通過葉子節(jié)點(diǎn)的聚集索引鍵（也即主鍵），然后據(jù)此去聚集索引中查找對應(yīng)的行記錄慎框。因此良狈，通過輔助索引查找行記錄，需要兩次B+索引查找笨枯。

輔助索引的葉子節(jié)點(diǎn)保存的是行的主鍵值而非行的物理地址薪丁，其目的 就在于當(dāng)出現(xiàn)行移動或者數(shù)據(jù)頁分裂時行記錄的物理地址發(fā)生了改變，輔助索引的葉子節(jié)點(diǎn)則不需要進(jìn)行任何的變動馅精，減少輔助索引的維護(hù)严嗜。輔助索引中的主鍵值就相當(dāng)于一個句柄。

3洲敢、B+樹索引的使用

聯(lián)合索引

聯(lián)合索引指對表上的多個列進(jìn)行索引漫玄。本質(zhì)上，聯(lián)合索引也是一棵B+樹沦疾，跟單列的輔助索引別無二致称近，只是在節(jié)點(diǎn)的鍵值的大小排序上第队，根據(jù)的是聯(lián)合索引列的字典順序來比較。

在使用聯(lián)合索引時必須符合最左前綴匹配原則刨秆，也即按照索引的最左列開始查找凳谦，否則無法使用聯(lián)合索引進(jìn)行查找。

覆蓋索引

覆蓋索引衡未，或稱為索引覆蓋尸执，即從輔助索引中即可得到查詢的記錄，而無需查詢聚集索引缓醋。使用覆蓋索引的好處就是如失，輔助索引不包括整行記錄的信息，因此大小要遠(yuǎn)小于聚集索引送粱，可以減少IO操作褪贵，并且通過索引覆蓋而無需回表進(jìn)行二次查詢，提高查詢性能抗俄。

我們說脆丁，如果一個索引包含所有需要查詢的字段的值，那么就稱之為覆蓋索引动雹。覆蓋索引針對的都是輔助索引槽卫，因?yàn)榫奂饕隙ㄊ前怂行枰樵兊淖侄蔚模驗(yàn)榫奂饕怂械男袛?shù)據(jù)信息啊胰蝠。

4歼培、索引實(shí)踐

創(chuàng)建一張表tb_test，a為主鍵：

插入數(shù)據(jù)茸塞，共16行躲庄，都大于0。_rowid表示主鍵翔横，InnoDB表肯定會有一個主鍵：

創(chuàng)建b和c的聯(lián)合索引：

或者刪掉該索引读跷，換一種語法：

查看tb_test的索引列，其中a為主鍵索引禾唁，b和c為聯(lián)合索引(idx_b_c)效览，且b在第一位(Seq_in_index:1)，c在第二位(Seq_in_index:2)：

使用explain得到執(zhí)行計(jì)劃荡短，查詢b and c時使用了idx_b_c這個聯(lián)合索引：

可以看到丐枉，雖然select *選擇了所有列（a、b掘托、c三列）瘦锹，而聯(lián)合索引(b, c)只包含了b和c兩列，但是依然選擇了輔助索引，這是因?yàn)榇藭r的輔助索引是覆蓋索引弯院，聯(lián)合索引idx_b_c在葉子節(jié)點(diǎn)上包含了主鍵a辱士，因此此索引包含了要查詢的所有字段，實(shí)現(xiàn)了索引覆蓋查詢听绳。Extra: Using index即表示使用了覆蓋索引

我們都知道颂碘，要命中聯(lián)合索引需要滿足最左前綴匹配∫握酰可是头岔，如果此時只查詢c，看看是否會命中idx_b_c聯(lián)合索引：

可以看到鼠证，MySQL依然選擇了idx_b_c聯(lián)合索引峡竣，因?yàn)榇藭r的idx_b_c是一個覆蓋索引，從Extra:Using index也可以看出量九。由于輔助索引沒有包含行的全部信息适掰，因此比聚集索引要小。比起掃描聚集索引娩鹉，優(yōu)化器會更傾向于選擇更小的可以減少IO操作的輔助索引攻谁。并且，即使查詢的數(shù)據(jù)量占到全表數(shù)據(jù)量的很大比例弯予，也依然堅(jiān)定不移的選擇輔助索引：

但是，當(dāng)新增一列d

再進(jìn)行b和c的聯(lián)合查詢个曙，會發(fā)現(xiàn)Extra沒有Using index锈嫩，也即不是覆蓋索引了。但是存儲引擎依然選擇了idx_b_c聯(lián)合索引垦搬，這是因?yàn)閮?yōu)化器進(jìn)行了優(yōu)化選擇呼寸。當(dāng)查詢的字段（select *）不能進(jìn)行索引覆蓋時，但是索引覆蓋了where查詢的條件（idx_b_c覆蓋where b = 2 and c = 3）猴贰，并且當(dāng)訪問的數(shù)據(jù)量很少時（不超過表數(shù)據(jù)的20%）優(yōu)化器才會依然選擇輔助索引对雪，但是需要進(jìn)行聚集索引的二次查找。

所以米绕，當(dāng)where條件查詢的數(shù)據(jù)量超過全表數(shù)據(jù)一定比例時瑟捣，優(yōu)化器便不會選擇輔助索引了：

并且，如果不是覆蓋索引栅干，并且索引沒有覆蓋查詢的條件迈套，則不會命中輔助索引，比如查詢條件并不滿足最左前綴匹配：

同時碱鳞，覆蓋索引也非常適合于統(tǒng)計(jì)查詢桑李，當(dāng)進(jìn)行COUNT(*)統(tǒng)計(jì)時，通過輔助索引即可得到統(tǒng)計(jì)信息，因此此時是一個覆蓋索引贵白，InnoDB存儲引擎不會選擇通過查詢聚集索引來進(jìn)行統(tǒng)計(jì)率拒，而是優(yōu)先采用輔助索引，因?yàn)檩o助索引的大小遠(yuǎn)小于聚集索引禁荒，可以減少IO操作俏橘。

另外，同理可得圈浇，此時有a寥掐、b、c磷蜀、d四個字段召耘，如果查詢b和c字段，但是查詢條件只有c褐隆，雖然不滿足最左前綴匹配污它，但是因?yàn)閕dx_b_c為覆蓋索引，因此依然可以命中索引：

但是庶弃，如果此時查詢?nèi)孔侄紊辣幔捎趇dx_b_c此時不是覆蓋索引了，所以不滿足最左前綴匹配的情況下歇攻，是不會命中聯(lián)合索引的：

但是固惯，之前提到過，覆蓋索引非常適用于統(tǒng)計(jì)查詢缴守。在統(tǒng)計(jì)查詢的情況下葬毫，如果只依靠輔助索引即可進(jìn)行統(tǒng)計(jì)，那么此時輔助索引即為覆蓋索引屡穗，那么優(yōu)化器依然會選擇輔助索引：

可以看到贴捡，當(dāng)統(tǒng)計(jì)count(*)時，依靠輔助索引idx_b_c葉子節(jié)點(diǎn)的主鍵即可進(jìn)行統(tǒng)計(jì)村砂，因此此時的idx_b_c是一個覆蓋索引烂斋。

但是如果統(tǒng)計(jì)的是d字段：

此時就不能通過idx_b_c進(jìn)行統(tǒng)計(jì)了，因?yàn)閐可能為空础废，也即此時的idx_b_c不是覆蓋索引了（從Extra沒有Using index也可以看出來）汛骂，也就不會命中輔助索引。

最后一點(diǎn)色迂，雖然查詢條件需要滿足最左前綴匹配香缺，但并不是嚴(yán)格要求查詢的字段順序跟聯(lián)合索引列的完全順序一致。對于輔助索引 idx_b_c歇僧，查詢時的字段b和c的先后順序并不用固定：