清空認知巢寡,然后重新理解MySQL索引結(jié)構(gòu)

前言

Hello我又來了,快年底了椰苟,作為一個有抱負的碼農(nóng)抑月,我想給自己攢一個年終總結(jié)。自上上篇寫了手動搭建Redis集群和MySQL主從同步(非Docker)和上篇寫了動手實現(xiàn)MySQL讀寫分離and故障轉(zhuǎn)移之后舆蝴,索性這次把數(shù)據(jù)庫中最核心的也是最難搞懂的內(nèi)容谦絮,也就是索引,分享給大家洁仗。這篇博客我會談談對于索引結(jié)構(gòu)我自己的看法层皱,以及分享如何從零開始一層一層向上最終理解索引結(jié)構(gòu)。

從一個簡單的表開始

create table user(
    id int primary key,
    age int,
    height int,
    weight int,
    name varchar(32)
)engine = innoDb;

相信只要入門數(shù)據(jù)庫的同學都可以理解這個語句京痢,我們也將從這個最簡單的表開始奶甘,一步步地理解MySQL的索引結(jié)構(gòu)。

首先祭椰,我們往這個表中插入一些數(shù)據(jù)臭家。

INSERT INTO user(id,age,height,weight,name)VALUES(2,1,2,7,'小吉');
INSERT INTO user(id,age,height,weight,name)VALUES(5,2,1,8,'小尼');
INSERT INTO user(id,age,height,weight,name)VALUES(1,4,3,1,'小泰');
INSERT INTO user(id,age,height,weight,name)VALUES(4,1,5,2,'小美');
INSERT INTO user(id,age,height,weight,name)VALUES(3,5,6,7,'小蔡');

我們來查一下,看看這些數(shù)據(jù)是否已經(jīng)放入表中蹄殃。

select * from user;
最初的表

可以看到,數(shù)據(jù)已經(jīng)完整地放到了我們創(chuàng)建的user表中。

但是不知道大家發(fā)現(xiàn)了什么沒有式廷,好像發(fā)生了一件非常詭異的事情,我們插入的數(shù)據(jù)好像亂序了...

MySQL好像悄悄的給我們按照id排了個序蠕趁。

為什么會出現(xiàn)MySQL在我們沒有顯式排序的情況下,默默幫我們排了序呢倔韭?它是在什么時候進行排序的?

頁的引入

不知道大家畢業(yè)多長時間了醇疼,作為一個剛學完操作系統(tǒng)不久的學渣,頁的概念依舊在腦中還沒有變涼乙濒。其實MySQL中也有類似頁的邏輯存儲單位么库,聽我慢慢道來。

在操作系統(tǒng)的概念中忱反,當我們往磁盤中取數(shù)據(jù),假設要取出的數(shù)據(jù)的大小是1KB米者,但是操作系統(tǒng)并不會只取出這1kb的數(shù)據(jù)随橘,而是會取出4KB的數(shù)據(jù),因為操作系統(tǒng)的一個頁表項的大小是4KB萝嘁。那為什么我們只需要1KB的數(shù)據(jù),但是操作系統(tǒng)要取出4KB的數(shù)據(jù)呢咱枉?這就涉及到一個程序局部性的概念,具體的概念我背不清了亿乳,大概就是“一個程序在訪問了一條數(shù)據(jù)之后障陶,在之后會有極大的可能再次訪問這條數(shù)據(jù)和訪問這條數(shù)據(jù)的相鄰數(shù)據(jù)”,所以索性直接加載4KB的數(shù)據(jù)到內(nèi)存中媳维,下次要訪問這一頁的數(shù)據(jù)時,直接從內(nèi)存中找州丹,可以減少磁盤IO次數(shù),我們知道所计,磁盤IO是影響程序性能主要的因素,因為磁盤IO和內(nèi)存IO的速度是不可同日而語的。

或許看完上面那一大段描述夷都,還是有些抽象,所以我們索性回到數(shù)據(jù)庫層面中荣瑟,重新理解頁的概念劫谅。

拋開所有東西不談荞驴,假設還是我們剛才插入的那些數(shù)據(jù),我們現(xiàn)在要找id = 5的數(shù)據(jù)鲫骗,依照最原始的方式,我們一定會想到的就是——遍歷术吝,沒錯,這也是我們剛開始學計算機的時候最常用的尋找數(shù)據(jù)的方式纪岁。那么我們就來看看漩氨,以遍歷的方式款青,我們找到id=5的數(shù)據(jù),需要經(jīng)歷幾次磁盤IO康震。

首先,我們得先從id=1的數(shù)據(jù)開始讀起橘忱,然后判斷是否是我們需要的數(shù)據(jù),如果不是潘拱,就再取id=2的數(shù)據(jù)泽铛,再進行判斷,循環(huán)往復弛随。毋庸置疑,在MySQL幫我們排好序之后愕够,我們需要經(jīng)歷五次磁盤IO,才能將5號數(shù)據(jù)找到并讀出來遂跟。

那么我們再來看看引入頁的概念之后,我們是如何讀數(shù)據(jù)的哄尔。

在引入頁的概念之后,MySQL會將多條數(shù)據(jù)存在一個叫“頁”的數(shù)據(jù)結(jié)構(gòu)中媒峡,當MySQL讀取id=1的數(shù)據(jù)時,會將id=1數(shù)據(jù)所在的頁整頁讀到內(nèi)存中,然后在內(nèi)存中進行遍歷判斷氯檐,由于內(nèi)存的IO速度比磁盤高很多,所以相對于磁盤IO,幾乎可以忽略不計拆挥,那么我們來看看這樣讀取數(shù)據(jù)我們需要經(jīng)歷幾次磁盤IO(假設每一頁可以存4條數(shù)據(jù))。那么我們第一次會讀取id=1的數(shù)據(jù)汉矿,并且將id=1到id=4的數(shù)據(jù)全部讀到內(nèi)存中流强,這是第一次磁盤IO,第二次將讀取id=5的數(shù)據(jù)到內(nèi)存中柴淘,這是第二次磁盤IO敛熬。所以我們只需要經(jīng)歷2次磁盤IO就可以找到id=5的這條數(shù)據(jù)夕吻。

但其實,在MySQL的InnoDb引擎中庸诱,頁的大小是16KB,是操作系統(tǒng)的4倍,而int類型的數(shù)據(jù)是4個字節(jié)形导,其它類型的數(shù)據(jù)的字節(jié)數(shù)通常也在4000字節(jié)以內(nèi),所以一頁是可以存放很多很多條數(shù)據(jù)的淋叶,而MySQL的數(shù)據(jù)正是以頁為基本單位組合而成的阎曹。

最初的頁結(jié)構(gòu)

上圖就是我們目前為止所理解的頁的結(jié)構(gòu),他包含我們的多條數(shù)據(jù)煞檩,另外处嫌,MySQL的數(shù)據(jù)以頁組成,那么它有指向下一頁的指針和指向上一頁的指針斟湃。

那么說到這里赚楚,其實可以回答第一個問題了敛摘,MySQL實際上就是在我們插入數(shù)據(jù)的時候,就幫我們在頁中排好了序晌端,至于為什么要排序演痒,這里先賣個關子曾撤,接著往下看。

排序?qū)π阅艿挠绊?/h2>

上文中我們提了一個問題属瓣,為什么數(shù)據(jù)庫在插入數(shù)據(jù)時要對其進行排序呢?我們按正常順序插入數(shù)據(jù)不是頁挺好的嗎选泻?

這就要涉及到一個數(shù)據(jù)庫查詢流程的問題了短曾,無論如何儒鹿,我們是絕對不會去平白無故地在插入數(shù)據(jù)時增加一個操作來讓流程復雜化的,所以插入數(shù)據(jù)時排序一定有其目的株搔,就是優(yōu)化查詢的效率

而我們不難看出,頁內(nèi)部存放數(shù)據(jù)的模塊,實質(zhì)上就是一個鏈表的結(jié)構(gòu)妓湘,鏈表的特點也就是增刪快坷随,查詢慢译暂,所以優(yōu)化查詢的效率是必須的劫乱。

  • 基于單頁模式存儲的查詢流程

    還是基于我們第一節(jié)中的那張頁圖來談舰绘,我們插入了五條數(shù)據(jù)驳概,id分別是從1-5流济,那么假設我要找一個表中不存在的id并扇,假設id=-1出刷,那么現(xiàn)在的查詢流程就是:

    將id=1的這一整頁數(shù)據(jù)取出璧疗,進行逐個比對,那么當我們找到id=1的這條數(shù)據(jù)時馁龟,發(fā)現(xiàn)這個id大于我們所需要找的哪個id崩侠,由于數(shù)據(jù)庫在插入數(shù)據(jù)時,已經(jīng)進行過排序了坷檩,那么在id=1的數(shù)據(jù)后面却音,都是id>1的數(shù)據(jù),所以我們就不需要再繼續(xù)往下尋找了矢炼。

    如果在插入時沒有進行排序盏求,那毋庸置疑,我們需要再繼續(xù)往下進行尋找雾叭,逐條查找直到到結(jié)尾也沒有找到這條數(shù)據(jù)料身,才能返回不存在這條數(shù)據(jù)。

當然胰锌,這只是排序優(yōu)化的冰山一角骗绕,接著往下看。

上述頁模式可能帶來的問題

說完了排序资昧,下面就來分析一下我們在第一節(jié)中的那幅圖酬土,對于大數(shù)據(jù)量下有什么弊端,或者換一個說法格带,我們可以怎么對這個模式進行優(yōu)化撤缴。

我們不難看出,在現(xiàn)階段我們了解的頁模式中叽唱,只有一個功能腹泌,就是在查詢某條數(shù)據(jù)的時候直接將一整頁的數(shù)據(jù)加載到內(nèi)存中,以減少硬盤IO次數(shù)尔觉,從而提高性能凉袱。但是,我們也可以看到侦铜,現(xiàn)在的頁模式內(nèi)部专甩,實際上是采用了鏈表的結(jié)構(gòu),前一條數(shù)據(jù)指向后一條數(shù)據(jù)钉稍,本質(zhì)上還是通過數(shù)據(jù)的逐條比較來取出特定的數(shù)據(jù)涤躲。那么假設,我們這一頁中有一百萬條數(shù)據(jù)贡未,我們要查的數(shù)據(jù)正好在最后一個种樱,那么我們是不是一定要從前往后找到這一條數(shù)據(jù)呢蒙袍?如果是這樣,我們需要查找的次數(shù)就達到了一百萬次嫩挤,即使是在內(nèi)存中查找害幅,這個效率也是不高的。那么有什么辦法來優(yōu)化這種情況下的查找效率呢岂昭?

頁目錄的引入

我們可以打個比方以现,我們在看書的時候,如果要找到某一節(jié)约啊,而這一節(jié)我們并不知道在哪一頁邑遏,我們是不是就要從前往后,一節(jié)一節(jié)地去尋找我們需要地內(nèi)容地頁碼呢恰矩?答案是否定的记盒,因為在書的前面,存在目錄外傅,它會告訴你這一節(jié)在哪一頁纪吮,例如,第一節(jié)在第1頁栏豺、第二節(jié)在第13頁彬碱。在數(shù)據(jù)庫的頁中豆胸,實際上也使用了這種目錄的結(jié)構(gòu)奥洼,這就是頁目錄

那么引入頁目錄之后晚胡,我們所理解的頁結(jié)構(gòu)灵奖,就變成了這樣:

加了頁目錄的頁結(jié)構(gòu)

分析一下這張圖,實際上頁目錄就像是我們在看書的時候書本的目錄一樣估盘,目錄項1就相當于第一節(jié)瓷患,目錄項2就相當于第二節(jié),而每一條數(shù)據(jù)就相當于書本的每一頁遣妥,這張圖就可以解釋成擅编,第一節(jié)從第一頁開始,第二節(jié)從第三頁開始箫踩,而實際上爱态,每個目錄項會存放自己這個目錄項當中最小的id,也就是說境钟,目錄項1中會存放1锦担,而目錄項2會存放3。

那么對比一下數(shù)據(jù)庫在沒有頁目錄時候的查找流程慨削,假設要查找id=3的數(shù)據(jù)洞渔,在沒有頁目錄的情況下套媚,需要查找id=1、id=2磁椒、id=3堤瘤,三次才能找到該數(shù)據(jù),而如果有頁目錄之后衷快,只需要先查看一下id=3存在于哪個目錄項下宙橱,然后直接通過目錄項進行數(shù)據(jù)的查找即可,如果在該目錄項下沒有找到這條數(shù)據(jù)蘸拔,那么就可以直接確定這條數(shù)據(jù)不存在师郑,這樣就大大提升了數(shù)據(jù)庫的查找效率,但是這種頁目錄的實現(xiàn)调窍,首先就需要基于數(shù)據(jù)是在已經(jīng)進行過排序的的場景下宝冕,才可以發(fā)揮其作用,所以看到這里邓萨,大家應該明白第二個問題了地梨,為什么數(shù)據(jù)庫在插入時會進行排序,這才是真正發(fā)揮排序的作用的地方缔恳。

頁的擴展

在上文中宝剖,我們基本上說明白了MySQL數(shù)據(jù)庫中頁的概念,以及它是如何基于頁來減少磁盤IO次數(shù)的歉甚,以及排序是如何優(yōu)化查詢的效率的万细。那么我們現(xiàn)在再來思考第三個問題:在開頭說頁的概念的時候,我們有說過纸泄,MySQL中每一頁的大小只有16KB赖钞,不會隨著數(shù)據(jù)的插入而自動擴容,所以這16KB不可能存下我們所有的數(shù)據(jù)聘裁,那么必定會有多個頁來存儲數(shù)據(jù)雪营,那么在多頁的情況下,MySQL中又是怎么組織這些頁的呢衡便?

針對這個問題献起,我們繼續(xù)來畫出我們現(xiàn)在所了解的多頁的結(jié)構(gòu)圖:

多頁結(jié)構(gòu)

可以看到,在數(shù)據(jù)不斷變多的情況下镣陕,MySQL會再去開辟新的頁來存放新的數(shù)據(jù)谴餐,而每個頁都有指向下一頁的指針和指向上一頁的指針,將所有頁組織起來(這里修改了一下數(shù)據(jù)茁彭,將每一列的數(shù)據(jù)都放到了數(shù)據(jù)區(qū)中总寒,其中第一個空格之前的代表id),第一頁中存放id為1-5的數(shù)據(jù)理肺,第二頁存放id為6-10的數(shù)據(jù)摄闸,第三頁存放id為11-15的數(shù)據(jù)善镰,需要注意的是在開辟新頁的時候,我們插入的數(shù)據(jù)不一定是放在新開辟的頁上年枕,而是要進行所有頁的數(shù)據(jù)比較炫欺,來決定這條插入的數(shù)據(jù)放在哪一頁上,而完成數(shù)據(jù)插入之后熏兄,最終的多頁結(jié)構(gòu)就會像上圖中畫的那樣品洛。

多頁模式

在多頁模式下,MySQL終于可以完成多數(shù)據(jù)的存儲了摩桶,就是采用開辟新頁的方式桥状,將多條數(shù)據(jù)放在不同的頁中,然后同樣采用鏈表的數(shù)據(jù)結(jié)構(gòu)硝清,將每一頁連接起來辅斟。那么可以思考第四個問題:多頁情況下是否對查詢效率有影響呢?

  • 多頁模式對于查詢效率的影響

    針對這個問題芦拿,既然問出來了士飒,那么答案是肯定的,多頁會對查詢效率產(chǎn)生一定的影響蔗崎,影響主要就體現(xiàn)在酵幕,多頁其本質(zhì)也是一個鏈表結(jié)構(gòu),只要是鏈表結(jié)構(gòu)缓苛,查詢效率一定不會高芳撒。假設數(shù)據(jù)又非常多條,數(shù)據(jù)庫就會開辟非常多的新頁他嫡,而這些新頁就會像鏈表一樣連接在一起番官,當我們要在這么多頁中查詢某條數(shù)據(jù)時庐完,它還是會從頭節(jié)點遍歷到存在我們要查找的那條數(shù)據(jù)所存在的頁上钢属,我們好不容易通過頁目錄優(yōu)化了頁中數(shù)據(jù)的查詢效率,現(xiàn)在又出現(xiàn)了以頁為單位的鏈表门躯,這不是前功盡棄了嗎淆党?

  • 如何優(yōu)化多頁模式

    由于多頁模式會影響查詢的效率,那么肯定需要有一種方式來優(yōu)化多頁模式下的查詢讶凉。相信有同學已經(jīng)猜出來了染乌,既然我們可以用頁目錄來優(yōu)化頁內(nèi)的數(shù)據(jù)區(qū),那么我們也可以采取類似的方式來優(yōu)化這種多頁的情況懂讯。是的荷憋,頁內(nèi)數(shù)據(jù)區(qū)和多頁模式本質(zhì)上都是鏈表,那么的確可以采用相同的方式來對其進行優(yōu)化褐望,它就是目錄頁勒庄。

    所以我們對比頁內(nèi)數(shù)據(jù)區(qū)串前,來分析如何優(yōu)化多頁結(jié)構(gòu)。在單頁時实蔽,我們采用了頁目錄的目錄項來指向一行數(shù)據(jù)荡碾,這條數(shù)據(jù)就是存在于這個目錄項中的最小數(shù)據(jù),那么就可以通過頁目錄來查找所需數(shù)據(jù)局装。所以對于多頁結(jié)構(gòu)也可以采用這種方式坛吁,使用一個目錄項來指向某一頁,而這個目錄項存放的就是這一頁中存放的最小數(shù)據(jù)的索引值铐尚。和頁目錄不同的地方在于拨脉,這種目錄管理的級別是頁,而頁目錄管理的級別是行宣增。

    那么分析到這里女坑,我們多頁模式的結(jié)構(gòu)就會是下圖所示的這樣:

    形成B+樹

    存在一個目錄頁來管理頁目錄,目錄頁中的數(shù)據(jù)存放的就是指向的那一頁中最小的數(shù)據(jù)统舀。

    這里要注意的一點是:其實目錄頁的本質(zhì)也是頁匆骗,普通頁中存的數(shù)據(jù)是項目數(shù)據(jù),而目錄頁中存的數(shù)據(jù)是普通頁的地址誉简。

    假設我們要查找id=19的數(shù)據(jù)碉就,那么按照以前的查找方式,我們需要從第一頁開始查找闷串,發(fā)現(xiàn)不存在那么再到第二頁查找瓮钥,一直找到第四頁才能找到id=19的數(shù)據(jù),但是如果有了目錄頁烹吵,就可以使用id=19與目錄頁中存放的數(shù)據(jù)進行比較碉熄,發(fā)現(xiàn)19大于任何一條數(shù)據(jù),于是進入id=16指向的頁進行查找肋拔,直接然后再通過頁內(nèi)的頁目錄行級別的數(shù)據(jù)的查找锈津,很快就可以找到id為19的數(shù)據(jù)了。隨著數(shù)據(jù)越來越多凉蜂,這種結(jié)構(gòu)的效率相對于普通的多頁模式琼梆,優(yōu)勢也就越來越明顯。

    回歸正題窿吩,相信有對MySQL比較了解的同學已經(jīng)發(fā)現(xiàn)了茎杂,我們畫的最終的這幅圖,就是MySQL中的一種索引結(jié)構(gòu)——B+樹纫雁。

B+樹的引入

B+樹的特點我在《[從入門到入土]令人脫發(fā)的數(shù)據(jù)庫底層設計》已經(jīng)有詳細敘述過了煌往,在這里就不重復敘述了,如果有不了解的同學可以去看這篇博客轧邪。

我們接著往下聊刽脖,我們將我們畫的存在目錄頁的多頁模式圖宏觀化悼粮,可以形成下面的這張圖:

多頁宏觀化

這就是我們兜兜轉(zhuǎn)轉(zhuǎn)由簡到繁形成的一顆B+樹。和常規(guī)B+樹有些許不同曾棕,這是一棵MySQL意義上的B+樹扣猫,MySQL的一種索引結(jié)構(gòu),其中的每個節(jié)點就可以理解為是一個頁翘地,而葉子節(jié)點也就是數(shù)據(jù)頁申尤,除了葉子節(jié)點以外的節(jié)點就是目錄頁。這一點再圖中也可以看出來衙耕,非葉子節(jié)點只存放了索引昧穿,而只有葉子節(jié)點中存放了真實的數(shù)據(jù),這也是符合B+樹的特點的橙喘。

  • B+樹的優(yōu)勢

    1. 由于葉子節(jié)點上存放了所有的數(shù)據(jù)时鸵,并且有指針相連,每個葉子節(jié)點在邏輯上是相連的厅瞎,所以對于范圍查找比較友好饰潜。
    2. B+樹的所有數(shù)據(jù)都在葉子節(jié)點上,所以B+樹的查詢效率穩(wěn)定和簸,一般都是查詢3次彭雾。
    3. B+樹有利于數(shù)據(jù)庫的掃描。
    4. B+樹有利于磁盤的IO锁保,因為他的層高基本不會因為數(shù)據(jù)擴大而增高(三層樹結(jié)構(gòu)大概可以存放兩千萬數(shù)據(jù)量薯酝。

頁的完整結(jié)構(gòu)

說完了頁的概念和頁是如何一步一步地組合稱為B+樹的結(jié)構(gòu)之后,相信大家對于頁都有了一個比較清楚的認知爽柒,所以這里就要開始說說官方概念了吴菠,基于我們上文所說的,給出一個完整的頁結(jié)構(gòu)浩村,也算是對上文中自己理解頁結(jié)構(gòu)的一種補充做葵。

頁結(jié)構(gòu)

上圖為 Page 數(shù)據(jù)結(jié)構(gòu),F(xiàn)ile Header 字段用于記錄 Page 的頭信息穴亏,其中比較重要的是 FIL_PAGE_PREV 和 FIL_PAGE_NEXT 字段蜂挪,通過這兩個字段重挑,我們可以找到該頁的上一頁和下一頁嗓化,實際上所有頁通過兩個字段可以形成一條雙向鏈表。Page Header 字段用于記錄 Page 的狀態(tài)信息谬哀。接下來的 Infimum 和 Supremum 是兩個偽行記錄刺覆,Infimum(下確界)記錄比該頁中任何主鍵值都要小的值,Supremum (上確界)記錄比該頁中任何主鍵值都要大的值史煎,這個偽記錄分別構(gòu)成了頁中記錄的邊界谦屑。

User Records 中存放的是實際的數(shù)據(jù)行記錄驳糯,具體的行記錄結(jié)構(gòu)將在本文的第二節(jié)中詳細介紹。Free Space 中存放的是空閑空間氢橙,被刪除的行記錄會被記錄成空閑空間酝枢。Page Directory 記錄著與二叉查找相關的信息。File Trailer 存儲用于檢測數(shù)據(jù)完整性的校驗和等數(shù)據(jù)悍手。

來源:https://www.cnblogs.com/bdsir/p/8745553.html

B+樹頁結(jié)構(gòu)

基于B+樹聊聊MySQL的其它知識點

看到這里帘睦,我們已經(jīng)了解了MySQL從單條數(shù)據(jù)開始,到通過來減少磁盤IO次數(shù)坦康,并且在頁中實現(xiàn)了頁目錄來優(yōu)化頁中的查詢效率竣付,然后使用多頁模式來存儲大量的數(shù)據(jù),最終使用目錄頁來實現(xiàn)多頁模式的查詢效率并形成我們口中的索引結(jié)構(gòu)——B+樹滞欠。既然說到這里了古胆,那我們就來聊聊MySQL的其他知識點。

  • 聚簇索引和非聚簇索引

    關于聚簇索引和非聚簇索引在[從入門到入土]令人脫發(fā)的數(shù)據(jù)庫底層設計這篇文章中已經(jīng)有了詳細的介紹筛璧,這里簡單地說說逸绎,所謂聚簇索引,就是將索引和數(shù)據(jù)放到一起夭谤,找到索引也就找到了數(shù)據(jù)桶良,我們剛才看到的B+樹索引就是一種聚簇索引,而非聚簇索引就是將數(shù)據(jù)和索引分開沮翔,查找時需要先查找到索引陨帆,然后通過索引回表找到相應的數(shù)據(jù)。InnoDB有且只有一個聚簇索引采蚀,而MyISAM中都是非聚簇索引疲牵。

  • 聯(lián)合索引的最左前綴匹配原則

    在MySQL數(shù)據(jù)庫中不僅可以對某一列建立索引,還可以對多列建立一個聯(lián)合索引榆鼠,而聯(lián)合索引存在一個最左前綴匹配原則的概念纲爸,如果基于B+樹來理解這個最左前綴匹配原則,相對來說就會容易很很多了妆够。

    首先我們基于文首的這張表建立一個聯(lián)合索引:

    create index idx_obj on user(age asc,height asc,weight asc)
    

    我們已經(jīng)了解了索引的數(shù)據(jù)結(jié)構(gòu)是一顆B+樹识啦,也了解了B+樹優(yōu)化查詢效率的其中一個因素就是對數(shù)據(jù)進行了排序,那么我們在創(chuàng)建idx_obj這個索引的時候神妹,也就相當于創(chuàng)建了一顆B+樹索引颓哮,而這個索引就是依據(jù)聯(lián)合索引的成員來進行排序,這里是age,height,weight鸵荠∶崦看過我之前那篇博客的同學知道,InnoDB中只要有主鍵被定義,那么主鍵列被作為一個聚簇索引姨伤,而其它索引都將被作為非聚簇索引哨坪,所以自然而然的,這個索引就會是一個非聚簇索引乍楚。

    所以根據(jù)這些我們可以得出結(jié)論:

    1. idx_obj這個索引會根據(jù)age,height,weight進行排序
    2. idx_obj這個索引是一個非聚簇索引当编,查詢時需要回表

    根據(jù)這兩個結(jié)論,首先需要了解的就是徒溪,如何排序凌箕?

    單列排序很簡單,比大小嘛词渤,誰都會牵舱,但是多列排序時基于什么原則的呢(重點)?

    實際上在MySQL中缺虐,聯(lián)合索引的排序有這么一個原則芜壁,從左往右依次比較大小,就拿剛才建立的索引舉例子高氮,他會先去比較age的大小慧妄,如果age的大小相同,那么比較height的大小剪芍,如果height也無法比較大小塞淹, 那么就比較weight的大小,最終對這個索引進行排序罪裹。

    那么根據(jù)這個排序我們也可以畫出一個B+樹饱普,這里就不像上文畫的那么詳細了,簡化一下:

    數(shù)據(jù):

    多列索引數(shù)據(jù)

    B+樹:

    多列索引結(jié)構(gòu)

    注意:此時由于時非聚簇索引状共,所以葉子節(jié)點不在有數(shù)據(jù)套耕,而是存了一個主鍵索引,最終會通過主鍵索引來回表查詢數(shù)據(jù)峡继。

    B+樹的結(jié)構(gòu)有了冯袍,就可以通過這個來理解最左前綴匹配原則了。

    我們先寫一個查詢語句

    SELECT * FROM user WHERE age=1 and height = 2 and weight = 7
    

    毋庸置疑碾牌,這條語句一定會走idx_obj這個索引康愤。

    那么我們再看一個語句:

    SELECT * FROM user WHERE height=2 and weight = 7
    

    思考一下,這條SQL會走索引嗎舶吗?

    答案是否定的征冷,那么我們分析的方向就是,為什么這條語句不會走索引裤翩。

    上文中我們提到了一個多列的排序原則资盅,是從左到右進行比較然后排序的调榄,而我們的idx_obj這個索引從左到右依次是age,height,weight踊赠,所以當我們使用height和weight來作為查詢條件時呵扛,由于age的缺失,那么就無法從age來進行比較了筐带。看到這里可能有小伙伴會有疑問,那如果直接用height和weight來進行比較不可以嗎虐唠?顯然是不可以的贷痪,可以舉個例子,我們把缺失的這一列寫作一個問好帖鸦,那么這條語句的查詢條件就變成了?27芝薇,那么我們從這課B+樹的根節(jié)點開始,根節(jié)點上有127和365作儿,那么以height和weight來進行比較的話洛二,走的一定是127這一邊,但是如果缺失的列數(shù)字是大于3的呢攻锰?比如427晾嘶,527,627娶吞,那么如果走索引來查詢數(shù)據(jù)垒迂,將會丟失數(shù)據(jù),錯誤查詢妒蛇。所以這種情況下是絕對不會走索引進行查詢的机断。這就是最左前綴匹配原則的成因

    1.最左前綴匹配原則绣夺,MySQL會一直向右匹配直到遇到范圍查詢(>毫缆、<、between乐导、like)就停止匹配苦丁,比如 a=3 and b=4 and c>5 and d=6,如果建立(a,b,c,d)順序的索引,d是無法使用索引的物臂,如果建立(a,b,d,c)的索引則都可以使用到旺拉,a、b棵磷、d的順序可以任意調(diào)整蛾狗。
    2.=和in可以亂序,比如 a=1 and b=2 and c=3 建立(a,b,c)索引可以任意順序仪媒,MySQL的查詢優(yōu)化器會幫你優(yōu)化成索引可以識別的形式沉桌。

    根據(jù)我們了解的可以得出結(jié)論:

    只要無法進行排序比較大小的谢鹊,就無法走聯(lián)合索引

    可以再看幾個語句:

    SELECT * FROM user WHERE age=1 and height = 2
    

    這條語句是可以走idx_obj索引的留凭,因為它可以通過比較 (12?<365)佃扼。

    SELECT * FROM user WHERE age=1 and weight=7
    

    這條語句也是可以走ind_obj索引的,因為它也可以通過比較(1?7<365)蔼夜,走左子樹兼耀,但是實際上weight并沒有用到索引,因為根據(jù)最左匹配原則求冷,如果有兩頁的age都等于1瘤运,那么會去比較height,但是height在這里并不作為查詢條件匠题,所以MySQL會將這兩頁全都加載到內(nèi)存中進行最后的weight字段的比較拯坟,進行掃描查詢。

    SELECT * FROM user where age>1
    

    這條語句不會走索引韭山,但是可以走索引郁季。這句話是什么意思呢?這條SQL很特殊掠哥,由于其存在可以比較的索引巩踏,所以它走索引也可以查詢出結(jié)果,但是由于這種情況是范圍查詢并且是全字段查詢续搀,如果走索引塞琼,還需要進行回表,MySQL查詢優(yōu)化器就會認為走索引的效率比全表掃描還要低禁舷,所以MySQL會去優(yōu)化它彪杉,讓他直接進行全表掃描。

    SELECT * FROM user WEHRE age=1 and height>2 and weight=7
    

    這條語句是可以走索引的牵咙,因為它可以通過age進行比較派近,但是weight不會用到索引,因為height是范圍查找洁桌,與第二條語句類似渴丸,如果有兩頁的height都大于2,那么MySQL會將兩頁的數(shù)據(jù)都加載進內(nèi)存另凌,然后再來通過weight匹配正確的數(shù)據(jù)谱轨。

  • 為什么InnoDB只有一個聚簇索引,而不將所有索引都使用聚簇索引吠谢?

    因為聚簇索引是將索引和數(shù)據(jù)都存放在葉子節(jié)點中土童,如果所有的索引都用聚簇索引,則每一個索引都將保存一份數(shù)據(jù)工坊,會造成數(shù)據(jù)的冗余献汗,在數(shù)據(jù)量很大的情況下敢订,這種數(shù)據(jù)冗余是很消耗資源的。

補充兩個關于索引的點

這兩個點也是上次寫關于索引的博客時漏下的罢吃,這里補上楚午。

  1. 什么情況下會發(fā)生明明創(chuàng)建了索引,但是執(zhí)行的時候并沒有通過索引呢刃麸?
    科普時間——查詢優(yōu)化器 一條SQL語句的查詢醒叁,可以有不同的執(zhí)行方案司浪,至于最終選擇哪種方案泊业,需要通過優(yōu)化器進行選擇,選擇執(zhí)行成本最低的方案啊易。 在一條單表查詢語句真正執(zhí)行之前吁伺,MySQL的查詢優(yōu)化器會找出執(zhí)行該語句所有可能使用的方案,對比之后找出成本最低的方案租谈。這個成本最低的方案就是所謂的執(zhí)行計劃篮奄。 優(yōu)化過程大致如下: 1、根據(jù)搜索條件割去,找出所有可能使用的索引 2窟却、計算全表掃描的代價 3、計算使用不同索引執(zhí)行查詢的代價 4呻逆、對比各種執(zhí)行方案的代價夸赫,找出成本最低的那一個

    參考鏈接:https://juejin.im/post/5d23ef4ce51d45572c0600bc

    根據(jù)我們剛才的那張表的非聚簇索引咖城,這條語句就是由于查詢優(yōu)化器的作用茬腿,造成沒有走索引:

    SELECT * FROM user where age>1
    
  2. 在稀疏索引情況下通常需要通過葉子節(jié)點的指針回表查詢數(shù)據(jù),什么情況下不需要回表宜雀?
    科普時間——覆蓋索引 覆蓋索引(covering index)指一個查詢語句的執(zhí)行只用從索引中就能夠取得切平,不必從數(shù)據(jù)表中讀取。也可以稱之為實現(xiàn)了索引覆蓋辐董。 當一條查詢語句符合覆蓋索引條件時悴品,MySQL只需要通過索引就可以返回查詢所需要的數(shù)據(jù),這樣避免了查到索引后再返回表操作简烘,減少I/O提高效率苔严。 如,表covering_index_sample中有一個普通索引 idx_key1_key2(key1,key2)夸研。當我們通過SQL語句:select key2 from covering_index_sample where key1 = 'keytest';的時候邦蜜,就可以通過覆蓋索引查詢,無需回表亥至。
    參考鏈接:https://juejin.im/post/5d23ef4ce51d45572c0600bc

    例如:

    SELECT age FROM user where age = 1
    

    這句話就不需要進行回表查詢悼沈。

結(jié)語

本篇文章著重聊了一下關于MySQL的索引結(jié)構(gòu)贱迟,從零開始慢慢構(gòu)建了一個B+樹索引,并且根據(jù)這個過程談了B+樹是如何一步一步去優(yōu)化查詢效率的絮供。

簡單地歸納一下就是:

排序:優(yōu)化查詢的根本衣吠,插入時進行排序?qū)嶋H上就是為了優(yōu)化查詢的效率。

頁:用于減少IO次數(shù)壤靶,還可以利用程序局部性原理缚俏,來稍微提高查詢效率。

頁目錄:用于規(guī)避鏈表的軟肋贮乳,避免在查詢時進行鏈表的掃描忧换。

多頁:數(shù)據(jù)量增加的情況下開辟新頁來保存數(shù)據(jù)。

目錄頁:“特殊的頁目錄”向拆,其中保存的數(shù)據(jù)是頁的地址亚茬。查詢時可以通過目錄頁快速定位到頁,避免多頁的掃描浓恳。

歡迎大家訪問我的個人博客:Object's Blog

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末刹缝,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子颈将,更是在濱河造成了極大的恐慌梢夯,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,729評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件晴圾,死亡現(xiàn)場離奇詭異颂砸,居然都是意外死亡,警方通過查閱死者的電腦和手機疑务,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評論 3 399
  • 文/潘曉璐 我一進店門沾凄,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人知允,你說我怎么就攤上這事撒蟀。” “怎么了温鸽?”我有些...
    開封第一講書人閱讀 169,461評論 0 362
  • 文/不壞的土叔 我叫張陵保屯,是天一觀的道長。 經(jīng)常有香客問我涤垫,道長姑尺,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,135評論 1 300
  • 正文 為了忘掉前任蝠猬,我火速辦了婚禮切蟋,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘榆芦。我一直安慰自己柄粹,他們只是感情好喘鸟,可當我...
    茶點故事閱讀 69,130評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著驻右,像睡著了一般什黑。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上堪夭,一...
    開封第一講書人閱讀 52,736評論 1 312
  • 那天愕把,我揣著相機與錄音,去河邊找鬼森爽。 笑死恨豁,一個胖子當著我的面吹牛,可吹牛的內(nèi)容都是我干的拗秘。 我是一名探鬼主播圣絮,決...
    沈念sama閱讀 41,179評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼祈惶,長吁一口氣:“原來是場噩夢啊……” “哼雕旨!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起捧请,我...
    開封第一講書人閱讀 40,124評論 0 277
  • 序言:老撾萬榮一對情侶失蹤凡涩,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后疹蛉,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體活箕,經(jīng)...
    沈念sama閱讀 46,657評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,723評論 3 342
  • 正文 我和宋清朗相戀三年可款,在試婚紗的時候發(fā)現(xiàn)自己被綠了育韩。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 40,872評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡闺鲸,死狀恐怖筋讨,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情摸恍,我是刑警寧澤悉罕,帶...
    沈念sama閱讀 36,533評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站立镶,受9級特大地震影響壁袄,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜媚媒,卻給世界環(huán)境...
    茶點故事閱讀 42,213評論 3 336
  • 文/蒙蒙 一嗜逻、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧缭召,春花似錦栈顷、人聲如沸令哟。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽屏富。三九已至,卻和暖如春蛙卤,著一層夾襖步出監(jiān)牢的瞬間狠半,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評論 1 274
  • 我被黑心中介騙來泰國打工颤难, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留神年,地道東北人。 一個月前我還...
    沈念sama閱讀 49,304評論 3 379
  • 正文 我出身青樓行嗤,卻偏偏與公主長得像已日,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子栅屏,可洞房花燭夜當晚...
    茶點故事閱讀 45,876評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 轉(zhuǎn)載:http://blog.codinglabs.org/articles/theory-of-mysql-in...
    qf1007閱讀 1,293評論 0 0
  • 索引 數(shù)據(jù)庫中的查詢操作非常普遍栈雳,索引就是提升查找速度的一種手段 索引的類型 從數(shù)據(jù)結(jié)構(gòu)角度分 1.B+索引:傳統(tǒng)...
    一凡呀閱讀 2,944評論 0 8
  • 為何要有索引护奈? 說白了,就是加速查詢哥纫。什么是索引霉旗? 索引在MySQL中也叫做“鍵”,是存儲引擎用于快速找到記錄的一...
    whenitsallover閱讀 635評論 0 0
  • 感謝耶殊陀尼看圖作詩蛀骇,好詩送貝 我跟在你的身后快樂地旅行 從搖搖擺擺的蹣跚學步 到昂首挺胸地大步流星 無憂無慮 跟...
    格乃閱讀 1,607評論 31 52
  • 最近似乎心情總是不好擅憔,沒有什么緣由鸵闪,這就讓我十分的琢磨不透了。呵雕欺,這越想還越不痛快岛马,這細雨綿綿于我這似乎也是遭了我...
    舞劍嘆閱讀 192評論 0 1