初步了解索引
之前我們介紹過,數(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)系孟抗,如下圖所示:
假設(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)部的單向鏈表大致如下所示:
在上述圖中柜裸,里面就是一行一行的數(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ù)頁里最小的主鍵值放在一起,組成一個索引的目錄遇八。如下圖所示:
現(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?這也是個大問題岔绸。于是接下來我們又可以把索引頁多加一個層級出來理逊,在更高的索引層級里,保存了每個索引頁和索引頁里的最小主鍵值盒揉,如下圖所示:
假設(shè)我們要查詢id=46的數(shù)據(jù)晋被,直接先到最頂層的索引頁35里去找,直接通過二分查找可以定位到下一步應(yīng)該到索引頁20里去找刚盈,接下來到索引頁20里通過二分查找定位羡洛,也很快可以定位到數(shù)據(jù)應(yīng)該在數(shù)據(jù)頁2里,這樣就可以找到id=46的那行數(shù)據(jù)了藕漱。那么現(xiàn)在問題再次來了翘县,假如你最頂層的那個索引頁里存放的下層索引頁的頁號也太多了,怎么辦呢谴分?此時可以再次分裂,再加一層索引頁镀脂,比如下圖那樣:
現(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)的索引頁罗岖,互相之間都是基于指針組成雙向鏈表的涧至。如下圖:
在上圖這個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)行编矾,就是說還需要根據(jù)主鍵再到聚簇索引里從根節(jié)點(diǎn)開始,一路找到葉子節(jié)點(diǎn)的數(shù)據(jù)頁馁害,定位到主鍵對應(yīng)的完整數(shù)據(jù)行窄俏,此時才能把select *要的全部字段值都拿出來。所以一般把name字段這種普通字段的索引稱之為
碘菜,一級索引就是聚簇索引裆操,這就是普通字段的索引運(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í)就是一個每個數(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ù)的一個過程,其它的二級索引也是類似的一個原理喷兼。