Mysql索引的B+樹的??流程如下圖所示：

1.B+索引樹是如何??的

1.1 ?索引時(shí)的數(shù)據(jù)查詢

數(shù)據(jù)?是Mysql中數(shù)據(jù)管理的最?單元，既然我們要研究索引是如何?效查詢數(shù)據(jù)的破加，?先我們肯定要搞清楚數(shù)據(jù)是如何存放的腹备，數(shù)據(jù)?的結(jié)構(gòu)通過上篇?章我們了解到?概是這樣的：

?數(shù)據(jù)表中的每?數(shù)據(jù)就存放在數(shù)據(jù)區(qū)中瘩将，數(shù)據(jù)區(qū)中每?數(shù)據(jù)以單向鏈表的?式至会，通過指針連接起來，如下圖所示：

同時(shí)每個(gè)數(shù)據(jù)?之間再通過雙向鏈表的?式組織連接起來阶牍，如下圖所示：

（1）?索引時(shí)的數(shù)據(jù)查詢

通過以上對(duì)數(shù)據(jù)?以及數(shù)據(jù)?內(nèi)部數(shù)據(jù)結(jié)構(gòu)初步的分析恳啥，現(xiàn)在我們就可以看下偏灿，如果說要查詢某張表的某?數(shù)據(jù)會(huì)經(jīng)過什么樣的流程。

數(shù)據(jù)??開始當(dāng)然是存放在磁盤中的角寸，?張表對(duì)?般會(huì)應(yīng)著多個(gè)數(shù)據(jù)?菩混，查詢數(shù)據(jù)時(shí)從磁盤中依次加載數(shù)據(jù)?到InnoDB的緩沖池中，然后對(duì)緩沖池中緩存?的每?數(shù)據(jù)扁藕，通過數(shù)據(jù)?的單向鏈表?個(gè)?個(gè)去遍歷查找沮峡，如果沒有找到，那么就會(huì)順著數(shù)據(jù)?的雙向鏈表數(shù)據(jù)結(jié)構(gòu)亿柑，依次遍歷加載磁盤中的其他數(shù)據(jù)?到緩沖池中遍歷查詢邢疙。

?家可以看到，像上?這樣的查詢?式就有點(diǎn)傻了，因?yàn)槿绻『媚阋榈臄?shù)據(jù)?在這張表最后?個(gè)數(shù)據(jù)?的最后??疟游，那豈不是所有的數(shù)據(jù)?都要被掃描?遍呼畸，然后每個(gè)數(shù)據(jù)?中也是遍歷鏈表，整體 的效果就是以O(shè)(n)的時(shí)間復(fù)雜度在遍歷鏈表了,這樣查詢的性能肯定是不?的颁虐。

（2）優(yōu)化數(shù)據(jù)?內(nèi)查詢效率-槽位

我們先把?光轉(zhuǎn)移到單個(gè)數(shù)據(jù)?內(nèi)的數(shù)據(jù)查詢蛮原，假如說我們現(xiàn)在已經(jīng)鎖定數(shù)據(jù)就在某個(gè)數(shù)據(jù)?中了，但是我們?cè)撛鯓涌焖俚膹倪@個(gè)數(shù)據(jù)?中找到我們想要的那?數(shù)據(jù)呢另绩？

通過之前的分析我們可以知道儒陨，最傻的?種?式就是遍歷數(shù)據(jù)?中的單向鏈表查詢，?個(gè)節(jié)點(diǎn)?個(gè)節(jié)點(diǎn)去掃描笋籽，相對(duì)應(yīng)的查詢效率是?眼可?的低蹦漠。但是如果說可以像翻書?樣，根據(jù)?錄來減?我們查 詢的范圍车海，相對(duì)應(yīng)的查詢效率不就上來了嗎笛园，根據(jù)這種想法，InnoDB存儲(chǔ)引擎設(shè)計(jì)了槽位這種?式來組織數(shù)據(jù)?中的多個(gè)數(shù)據(jù)?侍芝，槽位信息存放在數(shù)據(jù)?中的數(shù)據(jù)??錄中研铆。

槽位簡(jiǎn)單來說就是將數(shù)據(jù)?中的多個(gè)數(shù)據(jù)?分組劃分，每個(gè)數(shù)據(jù)?組都找這個(gè)組中的主鍵值最?的那個(gè)數(shù)據(jù)?的地址作為槽位的信息竭贩，這樣數(shù)據(jù)??錄中的?個(gè)個(gè)槽位不就是像是?個(gè)個(gè)?錄了嗎蚜印，標(biāo)記好了多個(gè)數(shù)據(jù)?分組的位置信息，如下圖所示：

這下有了數(shù)據(jù)??錄中的槽位信息留量，此時(shí)要查詢數(shù)據(jù)?中的某?數(shù)據(jù)不就很簡(jiǎn)單了，?如我們要查詢主鍵為4的那?數(shù)據(jù)哟冬，直接通過?分法以O(shè)(logn)的時(shí)間復(fù)雜度鎖定數(shù)據(jù)??錄中的槽位2楼熄，因?yàn)椴畚恢g都是緊密連接的，可以通過槽位2找到槽位1浩峡，從槽位1末尾開始可岂，對(duì)分組2中的數(shù)據(jù)開始遍歷，因?yàn)槊總€(gè)分組中的數(shù)據(jù)量都很少翰灾，此時(shí)在這么?的范圍內(nèi)簡(jiǎn)單遍歷下就可以快速找到主鍵為4的那?數(shù)據(jù)缕粹，時(shí)間復(fù)雜度從之前的O(n)降低到O(logn)效率還是挺可觀的。

但是如果你不是通過主鍵去查詢的纸淮，槽位此時(shí)就派不上?場(chǎng)平斩，你還得?個(gè)?個(gè)遍歷數(shù)據(jù)?中的單向鏈表去找到你想要的那?數(shù)據(jù)。

1.2 索引的前夕-?分裂

這?我們先來個(gè)?插曲咽块，簡(jiǎn)單了解下?分裂绘面，這塊內(nèi)容也是后?索引機(jī)制能夠正常運(yùn)?的基礎(chǔ)。

我們都知道?個(gè)數(shù)據(jù)?就是16KB??，當(dāng)?個(gè)數(shù)據(jù)?中的數(shù)據(jù)??夠多時(shí)就會(huì)重新創(chuàng)建?個(gè)數(shù)據(jù)?繼續(xù)寫數(shù)據(jù)?揭璃，如果說我們沒有?到索引還好晚凿，但是如果我們要在表中創(chuàng)建索引，那么對(duì)多個(gè)數(shù)據(jù)?中的數(shù)據(jù)就有約束了瘦馍。 如果新創(chuàng)建的數(shù)據(jù)?中的數(shù)據(jù)?的主鍵值歼秽，存在它上?個(gè)數(shù)據(jù)?的主鍵值還?的情況，這種情況是不被允許的情组，如下圖所示：

如果出現(xiàn)上圖的情況燥筷，多個(gè)數(shù)據(jù)?之間的主鍵就?序了，?索引機(jī)制的實(shí)現(xiàn)是要基于多個(gè)數(shù)據(jù)?主鍵的??是依次遞增的呻惕，所以此時(shí)就會(huì)出現(xiàn)?分裂的情況荆责。

其實(shí)?分裂?的也很明確，就是調(diào)整下不同數(shù)據(jù)?的數(shù)據(jù)順序亚脆，使得最終按順序創(chuàng)建的索?之間做院，后?個(gè)數(shù)據(jù)?中的每?個(gè)數(shù)據(jù)?的主鍵值都要?于上?個(gè)數(shù)據(jù)?，當(dāng)然?個(gè)數(shù)據(jù)?當(dāng)然是按照單向鏈表的?式依次遞增的濒持，?分裂流程如下圖所示：

我們可以看到?分裂主要就是調(diào)整了下數(shù)據(jù)?之間數(shù)據(jù)?的數(shù)據(jù)的順序键耕，使得多個(gè)數(shù)據(jù)?之間的主鍵值是按照順序來存放的，在這樣有序的數(shù)據(jù)中柑营，?效查詢才變得可能屈雄。

頻繁的出現(xiàn)?分裂情況，畢竟?分裂要涉及到數(shù)據(jù)的移動(dòng)官套，在性能上也是會(huì)有損耗的酒奶，這也警示我們減少?分裂的出現(xiàn)概率是?常有必要的，在設(shè)計(jì)表結(jié)構(gòu)時(shí)我們可以盡量使?主鍵?增?的?式奶赔，?不是?很難保證主鍵順序的?定義創(chuàng)建主鍵的?式惋嚎，使?主鍵?增??式，能??避免說數(shù)據(jù)?之間主鍵??出現(xiàn)順序錯(cuò)亂的問題站刑，減少?分裂發(fā)?的概率另伍。

1.3 從主鍵?錄到索引?

查詢??數(shù)據(jù)，在物理層?就是定位到哪?個(gè)數(shù)據(jù)?中的哪??數(shù)據(jù)绞旅。在數(shù)據(jù)?中定位數(shù)據(jù)的問題摆尝，在之前我們已經(jīng)通過槽位的?式、優(yōu)化了在單個(gè)數(shù)據(jù)?中查詢的效率因悲，現(xiàn)在我們要解決的是如何在?量的數(shù)據(jù)?中定位數(shù)據(jù)?的效率問題堕汞，這就是索引的?標(biāo)。

（1）主鍵?錄

InnoDB存儲(chǔ)引擎?開始是使?主鍵?錄的?式囤捻，將數(shù)據(jù)?號(hào)和數(shù)據(jù)?最?的主鍵值作為?條記錄臼朗，如下圖所示：

這樣的話邻寿，我們要查哪?條數(shù)據(jù)就不?掃描?個(gè)數(shù)據(jù)?內(nèi)的所有數(shù)據(jù)再掃描下?個(gè)了，直接通過id去主鍵?錄看?下视哑，通過?分查找定位到具體哪個(gè)數(shù)據(jù)?绣否，然后數(shù)據(jù)?內(nèi)部通過定位槽位，遍歷那個(gè)槽位對(duì)應(yīng)數(shù)據(jù)?分組找到具體的??數(shù)據(jù)挡毅。

（2）索引?

現(xiàn)在有?個(gè)問題就是蒜撮，每張表對(duì)應(yīng)的數(shù)據(jù)?都有很多，主鍵?錄就會(huì)有?量的數(shù)據(jù)跪呈、就有可能放不下段磨，這時(shí)InnoDB設(shè)計(jì)者們就想存放?錄數(shù)據(jù)也是數(shù)據(jù)啊，為什么不可以使?數(shù)據(jù)?來呢耗绿，就這樣主鍵?錄的信息就被移到數(shù)據(jù)?來了苹支，?這些數(shù)據(jù)?就被稱為索引?，如下圖所示：

從這?我們可以知道數(shù)據(jù)?肯定不是簡(jiǎn)單只存放數(shù)據(jù)表中的數(shù)據(jù)的误阻。好了债蜜，現(xiàn)在主鍵?錄由于容量有限，我們把主鍵?錄信息移動(dòng)到了數(shù)據(jù)?中形成了索引?究反，但同樣的問題不還是會(huì)出現(xiàn)嗎寻定，?個(gè)數(shù)據(jù)?的??也才16KB，索引?本身的容量也是有限的精耐，容量不夠了該怎么辦呢狼速？

為了解決索引?容量不夠的問題，索引?會(huì)重新創(chuàng)建和升級(jí)卦停，先把超出容量的數(shù)據(jù)放到?個(gè)新的索引?中向胡，然后再加?層索引?，如下圖所示：

由上圖我們可以看到惊完，新的?層索引?35它存放的就不是最?主鍵對(duì)應(yīng)的數(shù)據(jù)??錄了捷枯，?是最?主鍵對(duì)應(yīng)的索引??錄了，以此類推如果索引?35這?容量也不夠呢专执，那就繼續(xù)往上?層擴(kuò)展啊，最終效果看起來就像下??樣：

?家看出來了嗎郁油，由索引??層?層組成的結(jié)構(gòu)不就是我們經(jīng)常說的索引樹嗎本股，?這棵樹在mysql中稱之為B+索引樹。

樹這種數(shù)據(jù)結(jié)構(gòu)天然可以使??分法查詢桐腌，所以現(xiàn)在如果我們要查詢?條數(shù)據(jù)拄显，從樹的根節(jié)點(diǎn)開始通過?分法查找，以O(shè)(logn)的時(shí)間復(fù)雜度鎖定數(shù)據(jù)?案站，然后在數(shù)據(jù)?中同樣使??分法鎖定槽位躬审，在槽位中簡(jiǎn)單遍歷下不就找到數(shù)據(jù)了嗎，相?于沒有索引的場(chǎng)景，速度那可是相當(dāng)快了承边。

2.聚簇索引遭殉、普通索引和覆蓋索引

關(guān)于索引有?些常?的名詞我們需要加以區(qū)分。

?先聚簇索引就是像我們上?看到的?棵樹?樣博助，它的葉?節(jié)點(diǎn)是?個(gè)個(gè)數(shù)據(jù)?险污，這些數(shù)據(jù)?中存放的都是數(shù)據(jù)表中每??的完整數(shù)據(jù)，所以說如果B+樹是以完整數(shù)據(jù)的數(shù)據(jù)?為葉?節(jié)點(diǎn)的富岳，我們把這個(gè)索引樹稱為聚簇索引蛔糯；如果?個(gè)索引的索引樹，葉?節(jié)點(diǎn)不是以數(shù)據(jù)?為葉?節(jié)點(diǎn)的窖式，就稱為?級(jí)索引或普通索引蚁飒。

聚簇索引和普通索引最?的區(qū)別就是，聚簇索引的葉?節(jié)點(diǎn)存放了數(shù)據(jù)?的完整數(shù)據(jù)萝喘，??級(jí)索引葉?節(jié)點(diǎn)只有數(shù)據(jù)的部分字段淮逻。

?覆蓋索引本身并不是?種索引，?是?種查詢數(shù)據(jù)的?式蜒灰，?如我們對(duì)表table中的字段name建?了索引弦蹂，然后我們執(zhí)?查詢?nèi)纾簊elect name from table where name like '張%'，此時(shí)直接從name字段對(duì)應(yīng)的B+樹種查詢到對(duì)應(yīng)的?批name值强窖，然后直接就返回就?了凸椿，也就是說我們想要的字段name它本來就在索引上，我們直接通過?分法?效的從樹上直接摘下來就?了翅溺，?這種查詢?式就稱為覆蓋索引脑漫。

當(dāng)然相?于覆蓋索引?式，如果查詢改為：select * from table where name like '張%'咙崎，這就不是覆蓋索引了优幸，因?yàn)榇藭r(shí)你不光要從索引樹上找到具體的name，還要利?id值回表查詢所有的字段褪猛。

3.索引的優(yōu)缺點(diǎn)分析

索引的優(yōu)點(diǎn)當(dāng)然就是?效查詢數(shù)據(jù)网杆，索引將遍歷鏈表的O(n)的查詢時(shí)間復(fù)雜度優(yōu)化為了O(logn)的時(shí)間復(fù)雜度。

但是索引的缺點(diǎn)也是很明顯的伊滋，?先在時(shí)間?度上碳却，它必須要求主鍵是要按順序增?的，?序的主鍵會(huì)帶來頻繁的?分裂笑旺，影響效率昼浦；對(duì)數(shù)據(jù)庫表的增刪改操作的同時(shí)也需要維護(hù)索引，這部分的維護(hù)也是?塊性能損耗點(diǎn)筒主；在空間?度上：索引相關(guān)的數(shù)據(jù)和實(shí)際數(shù)據(jù)?樣都是要占內(nèi)存空間的关噪。

所以索引雖然能夠提?查詢效率鸟蟹，但是同時(shí)也要承擔(dān)它給我們的系統(tǒng)帶來的性能損耗，從這點(diǎn)上來看索引并不是建的越多越好使兔。

4.三個(gè)維度設(shè)計(jì)好索引

下?我們從以下三個(gè)維度優(yōu)化下索引的設(shè)計(jì)

（1）?先我們從時(shí)間?度上

我們需要為了避免頻繁的?分裂建钥，需要盡可能使?主鍵?增?等?式，保證新增的數(shù)據(jù)?中的數(shù)據(jù)?的主鍵都是遞增火诸，避免不必要的?分裂帶來的性能損耗和拖慢查詢效率锦针。

另外選擇合適的字段作為索引字段也很重要，需要選擇基數(shù)較?的字段置蜀，也就是?個(gè)字段可能出現(xiàn)的值?較多奈搜，這樣我們?cè)贐+樹中查詢時(shí)，才能最?效的發(fā)揮出?分法查詢的威?盯荤，如果建?索引的字段基數(shù)?較?可能查詢時(shí)?分查找就會(huì)退化成時(shí)間復(fù)雜度為O(n)的線性查詢了馋吗。

（2）空間的?度上

因?yàn)樗饕龜?shù)據(jù)本身也是要占空間的，可以選擇字段?度較?的作為索引字段秋秤，這樣整棵B+樹不?于那么占空間宏粤。

但是如果?得要以?字段作為索引也不是不?，可以采?折中的以字段的前綴作為索引灼卢，這樣的索引也稱為前綴索引绍哎，但是這樣可能只能?在模糊查詢上了，?在group by和order by上就不太適合了鞋真。

（3）作?范圍上

當(dāng)然我們?cè)O(shè)計(jì)索引的?的崇堰，當(dāng)然是為了更好的?上索引，索引在設(shè)計(jì)時(shí)涩咖，盡可能讓where海诲、group by、order by這些語句都能?上索引檩互。