MYSQL實(shí)戰(zhàn)優(yōu)化——索引介紹

初步了解索引

之前我們介紹過,數(shù)據(jù)頁在磁盤文件中的物理存儲結(jié)構(gòu)胡岔,數(shù)據(jù)頁之間是組成雙向鏈表的椿息,然后數(shù)據(jù)頁內(nèi)部的數(shù)據(jù)行是組成單向鏈表的歹袁,而且數(shù)據(jù)行是根據(jù)主鍵從小到大排序的。然后每個數(shù)據(jù)頁里都會有一個頁目錄寝优,里面根據(jù)數(shù)據(jù)行的主鍵存放了一個目錄条舔,同時數(shù)據(jù)行是被分散存儲到不同的槽位里去的,所以實(shí)際上每個數(shù)據(jù)頁的目錄里乏矾,就是這個頁里每個主鍵跟所在槽位的映射關(guān)系孟抗,如下圖所示:


index1.jpg

假設(shè)你要根據(jù)主鍵查找一條數(shù)據(jù),而且假設(shè)數(shù)據(jù)庫里那個表沒幾條數(shù)據(jù)钻心,那個表總共就一個數(shù)據(jù)頁凄硼,那么就太簡單了,首先就會先找到數(shù)據(jù)頁的頁目錄里根據(jù)主鍵進(jìn)行二分查找扔役。然后通過二分查找在目錄里迅速定位到主鍵對應(yīng)的數(shù)據(jù)是在哪個槽位里帆喇,然后到那個槽位里去遍歷每一行數(shù)據(jù),就能快速找到那個主鍵對應(yīng)的數(shù)據(jù)了亿胸。

但是假設(shè)你要根據(jù)非主鍵的其它字段查找數(shù)據(jù)呢坯钦?
那就尷尬了,此時你是沒辦法使用主鍵的那種頁目錄來二分查找的侈玄,只能進(jìn)入到數(shù)據(jù)頁里婉刀,根據(jù)單向鏈表依次遍歷查找數(shù)據(jù)了,這就性能很差了序仙。那么現(xiàn)在假如我們有很多數(shù)據(jù)呢突颊?比如成百上千個數(shù)據(jù)頁?這就沒有什么好的辦法,只能根據(jù)數(shù)據(jù)頁鏈表一個數(shù)據(jù)頁一個數(shù)據(jù)頁的去查找律秃,就是我們常說的全表掃描爬橡。

頁分裂

大家都知道,正常情況下我們在一個表里插入一些數(shù)據(jù)后棒动,他們都會進(jìn)入到一個數(shù)據(jù)頁里糙申,在數(shù)據(jù)頁內(nèi)部,它們會組成一個單項(xiàng)鏈表船惨,這個數(shù)據(jù)頁內(nèi)部的單向鏈表大致如下所示:


index2.jpg

在上述圖中柜裸,里面就是一行一行的數(shù)據(jù),剛開始第一行是個起始行粱锐,它的類型是2疙挺,就是最小的一行,然后它有一個指針指向了下一行數(shù)據(jù)怜浅,每一行數(shù)據(jù)都有自己每個字段的值铐然,然后每一行通過一個指針指向下一行數(shù)據(jù),普通的數(shù)據(jù)行的類型都是0海雪,最后一行類型為3锦爵,就是代表最大一行。

現(xiàn)在假設(shè)你不停的在表里插入數(shù)據(jù)奥裸,那么剛開始不停的在一個數(shù)據(jù)頁插入數(shù)據(jù),接著數(shù)據(jù)越來越多沪袭,此時就要再搞一個數(shù)據(jù)頁了湾宙。但是此時會遇到一個問題,之后會介紹索引機(jī)制冈绊,索引運(yùn)作的一個核心基礎(chǔ)就是要求你后一個數(shù)據(jù)頁的主鍵值都大于前面一個數(shù)據(jù)頁的主鍵值侠鳄,但是如果你的主鍵是自增的,那還可以保證這一點(diǎn)死宣,因?yàn)槟阈虏迦牒笠粋€數(shù)據(jù)頁的主鍵值一定都大于前面一個數(shù)據(jù)頁的主鍵值伟恶。但是,有時候你的主鍵并不是自動增長的毅该,所以可能會出現(xiàn)后一個數(shù)據(jù)頁的主鍵值里博秫,有的主鍵是小于前一個數(shù)據(jù)頁的主鍵值的。

所以此時就會出現(xiàn)一個過程眶掌,叫做頁分裂挡育,就是萬一你的主鍵值都是你自己設(shè)置的,那么在增加一個新的數(shù)據(jù)頁的時候朴爬,實(shí)際上會把前一個數(shù)據(jù)頁里主鍵值較大的即寒,挪動到新的數(shù)據(jù)頁里來,然后把你新插入的主鍵值較小的數(shù)據(jù)挪動到上一個數(shù)據(jù)頁里去,保證新數(shù)據(jù)頁里的主鍵值一定都比上一個數(shù)據(jù)頁里的主鍵值大母赵。

主鍵索引

假設(shè)我們有很多個數(shù)據(jù)頁逸爵,然后我們想要根據(jù)主鍵來查詢數(shù)據(jù),那么直接查詢的話也是不行的凹嘲,因?yàn)槲覀円膊恢乐麈I到底是在哪里师倔。比如說你要查找id=4的數(shù)據(jù),你怎么知道在哪個數(shù)據(jù)頁里施绎?沒有任何證據(jù)可以告訴你它到底是在哪個數(shù)據(jù)頁里溯革。所以如果是這個樣子的話,也就只能全表掃描了谷醉,這肯定是不能接受的致稀。

所以此時就需要針對主鍵設(shè)計一個索引了,針對主鍵的索引實(shí)際上就是主鍵目錄俱尼,就是把每個數(shù)據(jù)頁的頁號抖单,還有數(shù)據(jù)頁里最小的主鍵值放在一起,組成一個索引的目錄遇八。如下圖所示:

index3.jpg

現(xiàn)在我們有了上圖的主鍵目錄就方便了矛绘,直接就可以到主鍵目錄里去搜索,比如你要找id=3的數(shù)據(jù)刃永,此時就會跟每個數(shù)據(jù)頁的最小主鍵來比货矮,首先id=3大于了數(shù)據(jù)頁1里的最小主鍵值1,接著小于了數(shù)據(jù)頁2里的最小主鍵值4斯够。所以既然如此囚玫,你直接就可以定位到id=3的數(shù)據(jù)一定是在數(shù)據(jù)頁1里面。

如果你有很多的數(shù)據(jù)頁读规,在主鍵目錄里就會有很多的數(shù)據(jù)頁和最小主鍵值抓督,此時你完全可以根據(jù)二分查找的方式來找你要找的id到底在哪個數(shù)據(jù)頁里。所以這個效率是非常之高的束亏,而類似上圖的主鍵目錄铃在,就可以認(rèn)為是主鍵索引。

B+實(shí)現(xiàn)索引的頁存儲物理結(jié)構(gòu)

上面我們說了主鍵索引的目錄結(jié)構(gòu)和查找方法碍遍,但是其實(shí)是有問題的定铜,如果你的表里的數(shù)據(jù)很多,比如有幾千萬雀久,甚至單表幾億條數(shù)據(jù)都是有可能的宿稀,所以此時有大量的數(shù)據(jù)頁,然后主鍵目錄里存儲大量的數(shù)據(jù)頁頁號和最小主鍵值赖捌,這怎么辦呢祝沸?所以在考慮這個問題的時候矮烹,實(shí)際上是采取了一種把索引數(shù)據(jù)存儲在數(shù)據(jù)頁里的方式來做的。

也就是說罩锐,你的表的實(shí)際數(shù)據(jù)是存放在數(shù)據(jù)頁里的奉狈,然后你的表的索引也是存放在頁里的,此時索引放在頁里之后涩惑,就會有索引頁仁期,假設(shè)你有很多的數(shù)據(jù)頁,那么此時你就可以有很多的索引頁竭恬。但是現(xiàn)在又會存在一個問題了跛蛋,你現(xiàn)在有很多索引頁,但是此時你需要知道你應(yīng)該到哪個索引頁里去找你的主鍵數(shù)據(jù)痊硕,是索引頁20赊级?還是索引頁28?這也是個大問題岔绸。于是接下來我們又可以把索引頁多加一個層級出來理逊,在更高的索引層級里,保存了每個索引頁和索引頁里的最小主鍵值盒揉,如下圖所示:


index4.jpg

假設(shè)我們要查詢id=46的數(shù)據(jù)晋被,直接先到最頂層的索引頁35里去找,直接通過二分查找可以定位到下一步應(yīng)該到索引頁20里去找刚盈,接下來到索引頁20里通過二分查找定位羡洛,也很快可以定位到數(shù)據(jù)應(yīng)該在數(shù)據(jù)頁2里,這樣就可以找到id=46的那行數(shù)據(jù)了藕漱。那么現(xiàn)在問題再次來了翘县,假如你最頂層的那個索引頁里存放的下層索引頁的頁號也太多了,怎么辦呢谴分?此時可以再次分裂,再加一層索引頁镀脂,比如下圖那樣:

index5.jpg

現(xiàn)在搞的是不是有點(diǎn)像一棵樹了牺蹄?沒錯,這就是一顆B+樹薄翅,屬于數(shù)據(jù)結(jié)構(gòu)里的一種樹形數(shù)據(jù)結(jié)構(gòu)沙兰,所以一直說MySQL的索引是用B+樹來組成的。

B+實(shí)現(xiàn)索引的頁存儲物理結(jié)構(gòu)

我們上面講了如何基于索引數(shù)據(jù)結(jié)構(gòu)去查找主鍵的過程翘魄,那么大家有沒有發(fā)現(xiàn)一件事情鼎天,就是最下層的索引頁,都是會有指針引用數(shù)據(jù)頁的暑竟,所以實(shí)際上索引頁跟數(shù)據(jù)頁之間是有指針連接起來的斋射。另外,索引頁自己內(nèi)部,對于一個層級內(nèi)的索引頁罗岖,互相之間都是基于指針組成雙向鏈表的涧至。如下圖:


index6.jpg

在上圖這個B+樹里,最底層的一層就是數(shù)據(jù)頁桑包,數(shù)據(jù)頁也就是B+樹里的葉子節(jié)點(diǎn)南蓬。所以:

如果一顆大的B+樹索引數(shù)據(jù)結(jié)構(gòu)里,葉子節(jié)點(diǎn)就是數(shù)據(jù)頁自己本身哑了,那么此時我們就可以稱這顆B+樹索引為聚簇索引赘方。

其實(shí)在innodb存儲引擎里,你在對數(shù)據(jù)增刪改的時候,就是直接把你的數(shù)據(jù)頁放在聚簇索引里的看成,數(shù)據(jù)就在聚簇索引里停做。如果你的數(shù)據(jù)頁開始進(jìn)行頁分裂了,它此時會調(diào)整各個數(shù)據(jù)頁內(nèi)部的行數(shù)據(jù)泳梆,保證數(shù)據(jù)頁內(nèi)的主鍵值都是有順序的,下一個數(shù)據(jù)頁的所有主鍵值大于上一個數(shù)據(jù)頁的所有主鍵值榜掌。

同時在分裂的時候优妙,會維護(hù)你的上層索引數(shù)據(jù)結(jié)構(gòu),在上層索引頁里維護(hù)你的索引條目憎账,不同的數(shù)據(jù)頁號和最小主鍵值套硼。另外,這個聚簇索引默認(rèn)是按照主鍵來組織的胞皱,所有在增刪改數(shù)據(jù)的時候邪意,一方面會更新數(shù)據(jù)頁,一方面會給你字段維護(hù)B+樹結(jié)構(gòu)的聚簇索引反砌。其實(shí)聚簇索引就是innodb存儲引擎默認(rèn)給我們創(chuàng)建的一套基于主鍵的索引結(jié)構(gòu)雾鬼,而且我們表里的數(shù)據(jù)就是直接放在聚簇索引里的,作為葉子節(jié)點(diǎn)的數(shù)據(jù)頁宴树。

主鍵之外的字段索引原理

假設(shè)你要針對其它字段建立索引策菜,比如name、age之類的字段酒贬,這都是一樣的原理又憨,比如你插入數(shù)據(jù)的時候,一方面會把完整數(shù)據(jù)插入到聚簇索引的葉子節(jié)點(diǎn)的數(shù)據(jù)頁里去锭吨,同時維護(hù)好聚簇索引蠢莺,另一方面為其它字段建立索引,就是重新再建立一顆B+樹零如。

比如基于name字段建立了一個索引躏将,那么此時你插入數(shù)據(jù)的時候就會重新搞一顆B+樹锄弱,B+樹的葉子節(jié)點(diǎn)也是數(shù)據(jù)頁,但是這個數(shù)據(jù)頁里僅僅放主鍵字段和name字段耸携。至于排序規(guī)則之類的棵癣,跟之前說的一樣。也就是說夺衍,name字段的索引B+樹里狈谊,葉子節(jié)點(diǎn)的數(shù)據(jù)頁中的name值都是按大小排序的,就是下一個數(shù)據(jù)頁里的name字段值都是大于上一個數(shù)據(jù)頁里的name字段值沟沙,這個整體的排序規(guī)則都跟聚簇索引安照主鍵的排序規(guī)則是一樣的河劝。另外,name字段的B+樹建造也跟聚簇索引是一樣的矛紫,這里就不再重復(fù)介紹赎瞎。

假設(shè)你要根據(jù)name字段來搜索數(shù)據(jù),那搜索過程都一樣颊咬,就是從name字段的索引B+樹里的根節(jié)點(diǎn)開始找务甥,一層一層往下找,一直找到葉子節(jié)點(diǎn)的數(shù)據(jù)頁里喳篇,定位到name字段值對應(yīng)的主鍵值敞临。然后,此時針對select * from table where name='xxx'這樣的語句麸澜,先根據(jù)name字段值在name字段的索引B+樹里找挺尿,找到葉子節(jié)點(diǎn)也僅僅可以找到對應(yīng)的主鍵值,而找不到這行數(shù)據(jù)完整的所有字段炊邦。

所以此時還需要進(jìn)行\color{green}{回表}编矾,就是說還需要根據(jù)主鍵再到聚簇索引里從根節(jié)點(diǎn)開始,一路找到葉子節(jié)點(diǎn)的數(shù)據(jù)頁馁害,定位到主鍵對應(yīng)的完整數(shù)據(jù)行窄俏,此時才能把select *要的全部字段值都拿出來。所以一般把name字段這種普通字段的索引稱之為\color{green}{二級索引}碘菜,一級索引就是聚簇索引裆操,這就是普通字段的索引運(yùn)行原理。

其實(shí)我們也可以把多個字段聯(lián)合起來炉媒,建立聯(lián)合索引,比如name+age昆烁。這時候葉子節(jié)點(diǎn)的數(shù)據(jù)頁里放的是id+name+age吊骤,然后默認(rèn)按照name排序,name一樣就按照age排序静尼,不同數(shù)據(jù)頁之間的name+age值的排序也如此白粉。其它的就都跟二級索引是一樣的传泊,就不再重復(fù)。

不同索引B+樹的維護(hù)

首先鸭巴,剛開始一個表建好之后眷细,其實(shí)它就一個數(shù)據(jù)頁,這個數(shù)據(jù)頁就是屬于聚簇索引的一部分鹃祖,而且目前還是空的溪椎。此時如果你插入數(shù)據(jù),就是直接在這個數(shù)據(jù)頁里插入就可以了恬口,也沒必要給它弄什么索引頁校读。這個初始的數(shù)據(jù)頁其實(shí)就是一個\color{green}{根頁,}每個數(shù)據(jù)頁內(nèi)部默認(rèn)就有一個基于主鍵的頁目錄祖能,所以根據(jù)主鍵來搜索都是ok的歉秫,直接在唯一一個數(shù)據(jù)頁里根據(jù)頁目錄找就行了。

之后表里的數(shù)據(jù)會越來越多养铸,此時你的數(shù)據(jù)頁滿了雁芙,那么就會高一個新的數(shù)據(jù)頁,然后把你根頁面里的數(shù)據(jù)都拷貝過去钞螟,同時再搞一個新的數(shù)據(jù)頁兔甘,根據(jù)你的主鍵值的大小進(jìn)行挪動,讓兩個新的數(shù)據(jù)頁根據(jù)主鍵值排序筛圆,第二個數(shù)據(jù)頁的主鍵值都大于第一個數(shù)據(jù)頁的主鍵值裂明。

那么此時那個根頁在哪兒呢?此時根頁就升級為了索引頁太援,這個根頁里放的是數(shù)據(jù)頁的頁號和它們里面最小的主鍵值闽晦。當(dāng)數(shù)據(jù)越來越多,索引條目也會越來越多提岔,一個索引頁已經(jīng)放不下了仙蛉,那就分裂成兩個索引頁,然后根頁繼續(xù)往上走一個層級碱蒙。以此類推荠瘪,就會有越來越多的索引頁生成,根頁就繼續(xù)往上走赛惩。這其實(shí)就是增刪改的時候哀墓,整個聚簇索引維護(hù)的一個過程,其它的二級索引也是類似的一個原理喷兼。

\color{green}{本文結(jié)束}

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末篮绰,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子季惯,更是在濱河造成了極大的恐慌吠各,老刑警劉巖臀突,帶你破解...
    沈念sama閱讀 222,729評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異贾漏,居然都是意外死亡候学,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評論 3 399
  • 文/潘曉璐 我一進(jìn)店門纵散,熙熙樓的掌柜王于貴愁眉苦臉地迎上來梳码,“玉大人,你說我怎么就攤上這事困食”呶蹋” “怎么了?”我有些...
    開封第一講書人閱讀 169,461評論 0 362
  • 文/不壞的土叔 我叫張陵硕盹,是天一觀的道長符匾。 經(jīng)常有香客問我,道長瘩例,這世上最難降的妖魔是什么啊胶? 我笑而不...
    開封第一講書人閱讀 60,135評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮垛贤,結(jié)果婚禮上焰坪,老公的妹妹穿的比我還像新娘。我一直安慰自己聘惦,他們只是感情好某饰,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,130評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著善绎,像睡著了一般黔漂。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上禀酱,一...
    開封第一講書人閱讀 52,736評論 1 312
  • 那天炬守,我揣著相機(jī)與錄音,去河邊找鬼剂跟。 笑死减途,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的曹洽。 我是一名探鬼主播鳍置,決...
    沈念sama閱讀 41,179評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼送淆!你這毒婦竟也來了墓捻?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,124評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎砖第,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體环凿,經(jīng)...
    沈念sama閱讀 46,657評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡梧兼,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,723評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了智听。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片羽杰。...
    茶點(diǎn)故事閱讀 40,872評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖到推,靈堂內(nèi)的尸體忽然破棺而出考赛,到底是詐尸還是另有隱情,我是刑警寧澤莉测,帶...
    沈念sama閱讀 36,533評論 5 351
  • 正文 年R本政府宣布颜骤,位于F島的核電站,受9級特大地震影響捣卤,放射性物質(zhì)發(fā)生泄漏忍抽。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,213評論 3 336
  • 文/蒙蒙 一董朝、第九天 我趴在偏房一處隱蔽的房頂上張望鸠项。 院中可真熱鬧,春花似錦子姜、人聲如沸祟绊。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽牧抽。三九已至,卻和暖如春扭弧,著一層夾襖步出監(jiān)牢的瞬間阎姥,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評論 1 274
  • 我被黑心中介騙來泰國打工鸽捻, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留呼巴,地道東北人。 一個月前我還...
    沈念sama閱讀 49,304評論 3 379
  • 正文 我出身青樓御蒲,卻偏偏與公主長得像衣赶,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子厚满,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,876評論 2 361