萬盛學電腦網

 萬盛學電腦網 >> 數據庫 >> mysql教程 >> MySQL數據庫InnoDB索引原理詳解實踐教程【圖】

MySQL數據庫InnoDB索引原理詳解實踐教程【圖】

這篇文章是我在學習過程總結完成的,主要介紹Mysql的InnoDB索引相關知識,InnoDB索引原理及深入講解,從各種樹到索引原理到存儲的細節,為了方便理解,少量涉及MyISAM作為對比。

InnoDB是Mysql的默認存儲引擎(Mysql5.5.5之前是MyISAM,文檔)。本著高效學習的目的,本篇以介紹InnoDB為主,少量涉及MyISAM作為對比。

這篇文章是我在學習過程中總結完成的,內容主要來自書本和博客(參考文獻會給出),過程中加入了一些自己的理解,描述不准確的地方煩請指出。

1 各種樹形結構

本來不打算從二叉搜索樹開始,因為網上已經有太多相關文章,但是考慮到清晰的圖示對理解問題有很大幫助,也為了保證文章完整性,最後還是加上了這部分。

先看看幾種樹形結構:

1 搜索二叉樹:每個節點有兩個子節點,數據量的增大必然導致高度的快速增加,顯然這個不適合作為大量數據存儲的基礎結構。

2 B樹:一棵m階B樹是一棵平衡的m路搜索樹。最重要的性質是每個非根節點所包含的關鍵字個數 j 滿足:┌m/2┐ – 1 <= j <= m – 1;一個節點的子節點數量會比關鍵字個數多1,這樣關鍵字就變成了子節點的分割標志。一般會在圖示中把關鍵字畫到子節點中間,非常形象,也容易和後面的B+樹區分。由於數據同時存在於葉子節點和非葉子結點中,無法簡單完成按順序遍歷B樹中的關鍵字,必須用中序遍歷的方法。

3 B+樹:一棵m階B樹是一棵平衡的m路搜索樹。最重要的性質是每個非根節點所包含的關鍵字個數 j 滿足:┌m/2┐ – 1 <= j <= m;子樹的個數最多可以與關鍵字一樣多。非葉節點存儲的是子樹裡最小的關鍵字。同時數據節點只存在於葉子節點中,且葉子節點間增加了橫向的指針,這樣順序遍歷所有數據將變得非常容易。

4 B*樹:一棵m階B樹是一棵平衡的m路搜索樹。最重要的兩個性質是1每個非根節點所包含的關鍵字個數 j 滿足:┌m2/3┐ – 1 <= j <= m;2非葉節點間添加了橫向指針。

MySQL數據庫InnoDB索引原理詳解實踐教程【圖】

MySQL數據庫InnoDB索引原理詳解實踐教程【圖】

MySQL數據庫InnoDB索引原理詳解實踐教程【圖】

B/B+/B*三種樹有相似的操作,比如檢索/插入/刪除節點。這裡只重點關注插入節點的情況,且只分析他們在當前節點已滿情況下的插入操作,因為這個動作稍微復雜且能充分體現幾種樹的差異。與之對比的是檢索節點比較容易實現,而刪除節點只要完成與插入相反的過程即可(在實際應用中刪除並不是插入的完全逆操作,往往只刪除數據而保留下空間為後續使用)。

先看B樹的分裂,下圖的紅色值即為每次新插入的節點。每當一個節點滿後,就需要發生分裂(分裂是一個遞歸過程,參考下面7的插入導致了兩層分裂),由於B樹的非葉子節點同樣保存了鍵值,所以已滿節點分裂後的值將分布在三個地方:1原節點,2原節點的父節點,3原節點的新建兄弟節點(參考5,7的插入過程)。分裂有可能導致樹的高度增加(參考3,7的插入過程),也可能不影響樹的高度(參考5,6的插入過程)。

MySQL數據庫InnoDB索引原理詳解實踐教程【圖】

B+樹的分裂:當一個結點滿時,分配一個新的結點,並將原結點中1/2的數據復制到新結點,最後在父結點中增加新結點的指針;B+樹的分裂只影響原結點和父結點,而不會影響兄弟結點,所以它不需要指向兄弟節點的指針。

MySQL數據庫InnoDB索引原理詳解實踐教程【圖】

B*樹的分裂:當一個結點滿時,如果它的下一個兄弟結點未滿,那麼將一部分數據移到兄弟結點中,再在原結點插入關鍵字,最後修改父結點中兄弟結點的關鍵字(因為兄弟結點的關鍵字范圍改變了)。如果兄弟也滿了,則在原結點與兄弟結點之間增加新結點,並各復制1/3的數據到新結點,最後在父結點增加新結點的指針。可以看到B*樹的分裂非常巧妙,因為B*樹要保證分裂後的節點還要2/3滿,如果采用B+樹的方法,只是簡單的將已滿的節點一分為二,會導致每個節點只有1/2滿,這不滿足B*樹的要求了。所以B*樹采取的策略是在本節點滿後,繼續插入兄弟節點(這也是為什麼B*樹需要在非葉子節點加一個兄弟間的鏈表),直到把兄弟節點也塞滿,然後拉上兄弟節點一起湊份子,自己和兄弟節點各出資1/3成立新節點,這樣的結果是3個節點剛好是2/3滿,達到B*樹的要求,皆大歡喜。

MySQL數據庫InnoDB索引原理詳解實踐教程【圖】

B+樹適合作為數據庫的基礎結構,完全是因為計算機的內存-機械硬盤兩層存儲結構。內存可以完成快速的隨機訪問(隨機訪問即給出任意一個地址,要求返回這個地址存儲的數據)但是容量較小。而硬盤的隨機訪問要經過機械動作(1磁頭移動 2盤片轉動),訪問效率比內存低幾個數量級,但是硬盤容量較大。典型的數據庫容量大大超過可用內存大小,這就決定了在B+樹中檢索一條數據很可能要借助幾次磁盤IO操作來完成。如下圖所示:通常向下讀取一個節點的動作可能會是一次磁盤IO操作,不過非葉節點通常會在初始階段載入內存以加快訪問速度。同時為提高在節點間橫向遍歷速度,真實數據庫中可能會將圖中藍色的CPU計算/內存讀取優化成二叉搜索樹(InnoDB中的page directory機制)。

MySQL數據庫InnoDB索引原理詳解實踐教程【圖】

真實數據庫中的B+樹應該是非常扁平的,可以通過向表中順序插入足夠數據的方式來驗證InnoDB中的B+樹到底有多扁平。我們通過如下圖的CREATE語句建立一個只有簡單字段的測試表,然後不斷添加數據來填充這個表。通過下圖的統計數據(來源見參考文獻1)可以分析出幾個直觀的結論,這幾個結論宏觀的展現了數據庫裡B+樹的尺度。

1 每個葉子節點存儲了468行數據,每個非葉子節點存儲了大約1200個鍵值,這是一棵平衡的1200路搜索樹!

2 對於一個22.1G容量的表,也只需要高度為3的B+樹就能存儲了,這個容量大概能滿足很多應用的需要了。如果把高度增大到4,則B+樹的存儲容量立刻增大到25.9T之巨!

3 對於一個22.1G容量的表,B+樹的高度是3,如果要把非葉節點全部加載到內存也只需要少於18.8M的內存(如何得出的這個結論?因為對於高度為2的樹,1203個葉子節點也只需要18.8M空間,而22.1G從良表的高度是3,非葉節點1204個。同時我們假設葉子節點的尺寸是大於非葉節點的,因為葉子節點存儲了行數據而非葉節點只有鍵和少量數據。),只使用如此少的內存就可以保證只需要一次磁盤IO操作就檢索出所需的數據,效率是非常之高的。

MySQL數據庫InnoDB索引原理詳解實踐教程【圖】

2 Mysql的存儲引擎和索引

可以說數據庫必須有索引,沒有索引則檢索過程變成了順序查找,O(n)的時間復雜度幾乎是不能忍受的。我們非常容易想象出一個只有單關鍵字組成的表如何使用B+樹進行索引,只要將關鍵字存儲到樹的節點即可。當數據庫一條記錄裡包含多個字段時,一棵B+樹就只能存儲主鍵,如果檢索的是非主鍵字段,則主鍵索引失去作用,又變成順序查找了。這時應該在第二個要檢索的列上建立第二套索引。  這個索引由獨立的B+樹來組織。有兩種常見的方法可以解決多個B+樹訪問同一套表數據的問題,一種叫做聚簇索引(clustered index ),一種叫做非聚簇索引(secondary index)。這兩個名字雖然都叫做索引,但這並不是一種單獨的索引類型,而是一種數據存儲方式。對於聚簇索引存儲來說,行數據和主鍵B+樹存儲在一起,輔助鍵B+樹只存儲輔助鍵和主鍵,主鍵和非主鍵B+樹幾乎是兩種類型的樹。對於非聚簇索引存儲來說,主鍵B+樹在葉子節點存儲指向真正數據行的指針,而非主鍵。

InnoDB使用的是聚簇索引,將主鍵組織到一棵B+樹中,而行數據就儲存在葉子節點上,若使用”where id = 14″這樣的條件查找主鍵,則按照B+樹的檢索算法即可查找到對應的葉節點,之後獲得行數據。若對Name列進行條件搜索,則需要兩個步驟:第一步在輔助索引B+樹中檢索Name,到達其葉子節點獲取對應的主鍵。第二步使用主鍵在主索引B+樹種再執行一次B+樹檢索操作,最終到達葉子節點即可獲取整行數據。

MyISM使用的是非聚簇索引,非聚簇索引的兩棵B+樹看上去沒什麼不同,節點的結構完全一致只是存儲的內容不同而已,主鍵索引B+樹的節點存儲了主鍵,輔助鍵索引B+樹存儲了輔助鍵。表數據存儲在獨立的地方,這兩顆B+樹的葉子節點都使用一個地址指向真正的表數據,對於表數據來說,這兩個鍵沒有任何差別。由於索引樹是獨立的,通過輔助鍵檢索無需訪問主鍵的索引樹。

為了更形象說明這兩種索引的區別,我們假想一個表如下圖存儲了4行數據。其中Id作為主索引,Name作為輔助索引。圖示清晰的顯示了聚簇索引和非聚簇索引的差異。

MySQL數據庫InnoDB索引原理詳解實踐教程【圖】

MySQL數據庫InnoDB索引原理詳解實踐教程【圖】

我們重點關注聚簇索引,看上去聚簇索引的效率明顯要低於非聚簇索引,因為每次使用輔助索引檢索都要經過兩次B+樹查找,這不是多此一舉嗎?聚簇索引的優勢在哪?

1 由於行數據和葉子節點存儲在一起,這樣主鍵和行數據是一起被載入內存的,找到葉子節點就可以立刻將行數據返回了,如果按照主鍵Id來組織數據,獲得數據更快。

2 輔助索引使用主鍵作為”指針” 而不是使用地址值作為指針的好處是,減少了當出現行移動或者數據頁分裂時輔助索引的維護工作,使用主鍵值當作指針會讓輔助索引占用更多的空間,換來的好處是InnoDB在移動行時無須更新輔助索引中的這個”指針”。也就是說行的位置(實現中通過16K的Page來定位,後面會涉及)會隨著數據庫裡數據的修改而發生變化(前面的B+樹節點分裂以及Page的分裂),使用聚簇索引就可以保證不管這個主鍵B+樹的節點如何變化,輔助索引樹都不受影響。

3 Page結構

如果說前面的內容偏向於解釋原理,那後面就開始涉及具體實現了。

理解InnoDB的實現不得不提Page結構,Page是整個InnoDB存儲的最基本構件,也是InnoDB磁盤管理的最小單位,與數據庫相關的所有內容都存儲在這種Page結構裡。Page分為幾種類型,常見的頁類型有數據頁(B-tree Node)Undo頁(Undo Log Page)系統頁(System Page) 事務數據頁(Transaction System Page)等。單個Page的大小是16K(編譯宏UNIV_PAGE_SIZE控制),每個Page使用一個32位的int值來唯一標識,這也正好對應InnoDB最大64TB的存儲容量(16Kib * 2^32 = 64Tib)。一個Page的基本結構如下圖所示:

MySQL數據庫InnoDB索引原理詳解實踐教程【圖】

每個Page都有通用的頭和尾,但是中部的內容根據Page的類型不同而發生變化。Page的頭部裡有我們關心的一些數據,下圖把Page的頭部詳細信息顯示出來:

MySQL數據庫InnoDB索引原理詳解實踐教程【圖】

我們重點關注和數據組織結構相關的字段:Page的頭部保存了兩個指針,分別指向前一個Page和後一個Page,頭部還有Page的類型信息和用來唯一標識Page的編號。根據這兩個指針我們很容易想象出Page鏈接起來就是一個雙向鏈表的結構。

MySQL數據庫InnoDB索引原理詳解實踐教程【圖】

再看看Page的主體內容,我們主要關注行數據和索引的存儲,他們都位於Page的User Records部分,User Records占據Page的大部分空間,User Records由一條一條的Record組成,每條記錄代表索引樹上的一個節點(非葉子節點和葉子節點)。在一個Page內部,單鏈表的頭尾由固定內容的兩條記錄來表示,字符串形式的”Infimum”代表開頭,”Supremum”代表結尾。這兩個用來代表開頭結尾的Record存儲在System Records的段裡,這個System Records和User Records是兩個平行的段。InnoDB存在4種不同的Record,它們分別是1主鍵索引樹非葉節點 2主鍵索引樹葉子節點 3輔助鍵索引樹非葉節點 4輔助鍵索引樹葉子節點。這4種節點的Record格式有一些差異,但是它們都存儲著Next指針指向下一個Record。後續我們會詳細介紹這4種節點,現在只需要把Record當成一個存儲了數據同時含有Next指針的單鏈表節點即可。

MySQL數據庫InnoDB索引原理詳解實踐教程【圖】

User Record在Page內以單鏈表的形式存在,最初數據是按照插入的先後順序排列的,但是隨著新數據的插入和舊數據的刪除,數據物理順序會變得混亂,但他們依然保持著邏輯上的先後順序。

MySQL數據庫InnoDB索引原理詳解實踐教程【圖】

把User Record的組織形式和若干Page組合起來,就看到了稍微完整的形式。

MySQL數據庫InnoDB索引原理詳解實踐教程【圖】

現在看下如何定位一個Record:

1 通過根節點開始遍歷一個索引的B+樹,通過各層非葉子節點最終到達一個Page,這個Page裡存放的都是葉子節點。

2 在Page內從”Infimum”節點開始遍歷單鏈表(這種遍歷往往會被優化),如果找到該鍵則成功返回。如果記錄到達了”supremum”,說明當前Page裡沒有合適的鍵,這時要借助Page的Next Page指針,跳轉到下一個Page繼續從”Infimum”開始逐個查找。

MySQL數據庫InnoDB索引原理詳解實踐教程【圖】

詳細看下不同類型的Record裡到底存儲了什麼數據,根據B+樹節點的不同,User Record可以被分成四種格式,下圖種按照顏色予以區分。

1 主索引樹非葉節點(綠色)

1 子節點存儲的主鍵裡最小的值(Min Cluster Key on Child),這是B+樹必須的,作用是在一個Page裡定位到具體的記錄的位置。

2 最小的值所在的Page的編號(Child Page Number),作用是定位Record。

2 主索引樹葉子節點(黃色)

1 主鍵(Cluster Key Fields),B+樹必須的,也是數據行的一部分

2 除去主鍵以外的所有列(Non-Key Fields),這是數據行的除去主鍵的其他所有列的集合。

這裡的1和2兩部分加起來就是一個完整的數據行。

3 輔助索引樹非葉節點非(藍色)

1 子節點裡存儲的輔助鍵值裡的最小的值(Min Secondary-Key on Child),這是B+樹必須的,作用是在一個Page裡定位到具體的記錄的位置。

2 主鍵值(Cluster Key Fields),非葉子節點為什麼要存儲主鍵呢?因為輔助索引是可以不唯一的,但是B+樹要求鍵的值必須唯一,所以這裡把輔助鍵的值和主鍵的值合並起來作為在B+樹中的真正鍵值,保證了唯一性。但是這也導致在輔助索引B+樹中非葉節點反而比葉子節點多了4個字節。(即下圖中藍色節點反而比紅色多了4字節)

3 最小的值所在的Page的編號(Child Page Number),作用是定位Record。

4 輔助索引樹葉子節點(紅色)

1 輔助索引鍵值(Secondary Key Fields),這是B+樹必須的。

2 主鍵值(Cluster Key Fields),用來在主索引樹裡再做一次B+樹檢索來找到整條記錄。

MySQL數據庫InnoDB索引原理詳解實踐教程【圖】

下面是本篇最重要的部分了,結合B+樹的結構和前面介紹的4種Record的內容,我們終於可以畫出一幅全景圖。由於輔助索引的B+樹與主鍵索引有相似的結構,這裡只畫出了主鍵索引樹的結構圖,只包含了”主鍵非葉節點”和”主鍵葉子節點”兩種節點,也就是上圖的的綠色和黃色的部分。

MySQL數據庫InnoDB索引原理詳解實踐教程【圖】

把上圖還原成下面這個更簡潔的樹形示意圖,這就是B+樹的一部分。注意Page和B+樹節點之間並沒有一一對應的關系,Page只是作為一個Record的保存容器,它存在的目的是便於對磁盤空間進行批量管理,上圖中的編號為47的Page在樹形結構上就被拆分成了兩個獨立節點。

MySQL數據庫InnoDB索引原理詳解實踐教程【圖】

至此本篇就算結束了,本篇只是對InnoDB索引相關的數據結構和實現進行了一些梳理總結,並未涉及到Mysql的實戰經驗。這主要是基於幾點原因:

1 原理是基石,只有充分了解InnoDB索引的工作方式,我們才有能力高效的使用好它。

2 原理性知識特別適合使用圖示,我個人非常喜歡這種表達方式。

3 關於InnoDB優化,在《高性能Mysql》裡有更加全面的介紹,對優化Mysql感興趣的同學完全可以自己獲取相關知識,我自己的積累還未達到能分享這些內容的地步。

copyright © 萬盛學電腦網 all rights reserved