初步了解索引

之前我們介紹過，數(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

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)行编矾，就是說還需要根據(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ù)的一個過程，其它的二級索引也是類似的一個原理喷兼。