MySQL B+樹索引結(jié)構(gòu)

看了很多關(guān)于MySQL B+樹索引的文檔,但一直有些問題沒搞明白:

  • B+樹索引在磁盤上是怎么存儲的如输?
  • 內(nèi)節(jié)點躬翁、葉子節(jié)點的物理結(jié)構(gòu)又是什么樣子的昧旨?

直到看到一份資料《MySQL 是怎樣運行的:從根兒上理解 MySQL》,基本解決了我的現(xiàn)有疑惑抽减。但好的資料就是看著看著又能讓你思考更多問題允青,有新的疑惑,再去解決新的疑惑讓自己不斷提升卵沉。下面我將把從這個資料學(xué)習(xí)到的B+樹索引結(jié)構(gòu)的知識按自己的邏輯整理后分享給大家颠锉,以此角度來給大家安利這份學(xué)習(xí)資料,大綱如下:

  • B+樹索引結(jié)構(gòu)的推導(dǎo)過程

    1. 數(shù)據(jù)行結(jié)構(gòu)--單向鏈表史汗;
    2. 數(shù)據(jù)頁結(jié)構(gòu)--通過頁目錄使用二分法快速找到目標(biāo)行琼掠;
    3. 目錄項--多個數(shù)據(jù)頁時如何定位到目標(biāo)行所在的數(shù)據(jù)頁;
    4. B+樹索引--目錄項太多停撞,大目錄嵌套小目錄瓷蛙,就形成了B+樹
  • 聚簇索引

    1. 特點;
    2. 主鍵的選擇以及原因戈毒。
  • 二級索引結(jié)構(gòu)和特點

  • MyISAM 索引結(jié)構(gòu)和特點

B+樹索引結(jié)構(gòu)的推導(dǎo)過程

1. 數(shù)據(jù)行結(jié)構(gòu)

一切要從數(shù)據(jù)行結(jié)構(gòu)說起艰猬,這里特指 InnoDB 行結(jié)構(gòu):

看起來很復(fù)雜,不過此文章只需要關(guān)注數(shù)據(jù)行結(jié)構(gòu)的記錄頭信息中有個 next_record 結(jié)構(gòu)埋市,它表示從當(dāng)前記錄的真實數(shù)據(jù)到下一條記錄的真實數(shù)據(jù)的地址偏移量冠桃,所以在一個數(shù)據(jù)頁里行與行根據(jù)這個設(shè)計可以組成一個有序的單向鏈表(按照主鍵排序):
InnoDB行--單向鏈表
2. 數(shù)據(jù)頁結(jié)構(gòu)

一個數(shù)據(jù)頁默認(rèn)16KB,可以存放很多行數(shù)據(jù)道宅,那如何在一個數(shù)據(jù)頁中快速找到一行數(shù)據(jù)呢食听?在數(shù)據(jù)頁中有個叫“頁目錄”的結(jié)構(gòu):

  • 把數(shù)據(jù)頁里的數(shù)據(jù)行按規(guī)則分成 n 個組;
  • 每個組中主鍵最大的那一行數(shù)據(jù)的地址偏移量存到“頁目錄”的“槽”中污茵。

這樣就可以根據(jù)主鍵值使用二分法進行快速查找到目標(biāo)行所在位置:

多個數(shù)據(jù)頁之間樱报,根據(jù)頁結(jié)構(gòu)中的 File Header 中的 FIL_PAGE_PREV、FIL_PAGE_NEXT 記錄上一個頁號和下一個頁號泞当,把許許多多頁建立一個雙向鏈表串聯(lián)起來:
3. 目錄項

如果一張表的數(shù)據(jù)存在很多個數(shù)據(jù)頁里迹蛤,如何找到目標(biāo)行數(shù)據(jù)在哪一個數(shù)據(jù)頁中呢?

簡單的實現(xiàn)方法是給這些數(shù)據(jù)頁做一個目錄:取出每個數(shù)據(jù)頁中最小那行數(shù)據(jù)的主鍵值零蓉,和頁號(page_no)笤受,組成一行數(shù)據(jù)穷缤,也稱為目錄項敌蜂,記錄到目錄中。這樣也可以通過二分法來查找一個指定的主鍵值在哪個數(shù)據(jù)頁上:

但是對目錄使用二分法查找的前提是:這個目錄的內(nèi)容(目錄項)是連續(xù)存放在某個地方的津肛。但實際上 IoonDB 的存儲的最小單位是頁章喉,默認(rèn)只有 16K,所以這個方法在實現(xiàn)上不可行。

由于目錄中的內(nèi)容“目錄項”跟真實的用戶記錄類似:

  • 每個數(shù)據(jù)頁中最小的主鍵值秸脱;
  • 頁號落包,也叫 page_no。

所以可以用數(shù)據(jù)行結(jié)構(gòu)摊唇、頁結(jié)構(gòu)來存儲目錄項咐蝇,為了和真實的用戶記錄做區(qū)分传轰,在數(shù)據(jù)行結(jié)構(gòu)的記錄頭信息中把目錄項紀(jì)錄的 record_type 屬性設(shè)置為“1”动猬,而普通的用戶記錄則為“0”殖侵。所以目錄項放到數(shù)據(jù)頁中就被設(shè)計成這樣了:
4. B+樹索引

如上圖幢尚,如果一張表的行數(shù)很多玛臂,勢必就會有很多數(shù)據(jù)頁压怠,那么就可能出現(xiàn)一個頁存不下所有“目錄項紀(jì)錄”的情況芥映,所以可能會有很多個“目錄項數(shù)據(jù)頁”溅话,那又怎么快速知道應(yīng)該在哪個“目錄項數(shù)據(jù)頁”上查找目標(biāo)數(shù)據(jù)在哪個“數(shù)據(jù)頁”上呢崇败?

也很簡單盅称,再為“目錄項數(shù)據(jù)頁”生成一個更高一級的目錄即可,即大目錄嵌套小目錄后室,直到最頂級的那個目錄只需要一個“頁”就能存下第二級目錄的所有目錄項:

這就是 B+樹索引結(jié)構(gòu):

  • 實際用戶記錄其實都存放在B+樹的最底層的節(jié)點上缩膝,這些節(jié)點也被稱為葉子節(jié)點或葉節(jié)點;
  • 其余用來存放目錄項的節(jié)點稱為非葉子節(jié)點或者內(nèi)節(jié)點岸霹;
  • 其中 B+樹最上邊的那個節(jié)點也稱為根節(jié)點逞盆。
5. 時間復(fù)雜度

索引樹的高度決定了查找數(shù)據(jù)的速度,而索引樹的高度 h 取決于:

  • 每個葉子節(jié)點(即數(shù)據(jù)頁)中能存放多少條“用戶記錄”松申,m云芦;
  • 每個內(nèi)節(jié)點或非葉子節(jié)點能存放多少條“目錄項記錄”,n贸桶;
  • 表的總行數(shù) X舅逸。

m*n^(h-1)=X ,則 ??1=log????/?? 皇筛,這就是常說的B+樹索引查找的時間復(fù)雜度為O(log n) 的由來琉历。(一個頁面最少存儲2條記錄的設(shè)計,就是為了讓索引的效果更好)

假設(shè)每行數(shù)據(jù)大約1K水醋,innodb 數(shù)據(jù)頁大小默認(rèn)為16K旗笔,也就是大約每個葉子結(jié)點可以存放16條用戶記錄,即 m=16拄踪;
主鍵ID一般為bigint 類型蝇恶,占 8 字節(jié),指針大小在 InnoDB 源碼中設(shè)置為 6 字節(jié)惶桐,這樣一共 14 字節(jié)撮弧,所以每個非葉子結(jié)點大約可以存放 16384/14=1170 條目錄項紀(jì)錄潘懊,即n=1170;
要想控制樹高為3贿衍,則表的總行數(shù)應(yīng)該是:16*1170^(3-1)=21902400

所以InnoDB表行數(shù)一般建議在 2000 萬行以內(nèi)授舟,這樣查詢效率較高。

聚簇索引

1. 特點

其實聚簇索引的特點屬于老生常談了贸辈,但按例還是得介紹一下释树。
在 InnoDB 中聚簇索引(主鍵)就是數(shù)據(jù)的存儲方式(所有的用戶記錄都存儲在了葉子節(jié)點),也就是所謂的索引即數(shù)據(jù)擎淤,數(shù)據(jù)即索引躏哩。

  • 使用記錄主鍵值的大小進行記錄和頁的排序,這包括三個方面的含義:

    1. 頁內(nèi)的記錄是按照主鍵的大小順序排成一個單向鏈表揉燃;
    2. 各個存放用戶記錄的頁也是根據(jù)頁中用戶記錄的主鍵大小順序排成一個雙向鏈表扫尺;
    3. 存放目錄項記錄的頁分為不同的層次,在同一層次中的頁也是根據(jù)頁中目錄項記錄的主鍵大小順序排成一個雙向鏈表炊汤。
  • B+樹的葉子節(jié)點存儲的是完整的用戶記錄正驻。
    所謂完整的用戶記錄,就是指這個記錄中存儲了所有列的值(包括隱藏列)抢腐。

2. 主鍵的選擇

聚簇索引是底層的說法姑曙,而主鍵是運維層面的說法(因為有語法 primary key(id)),通常主鍵的選擇是:id int auto_increment迈倍,為什么呢伤靠?

  • int 或者 bigint 類型占用字節(jié)少節(jié)省空間,因為二級索引的葉子節(jié)點啼染、非葉子節(jié)點上都要保存主鍵鍵值宴合;
  • 索引是有序的,auto_increment 自增屬性會保證按順序插入數(shù)據(jù)迹鹅,不會造成數(shù)據(jù)頁的分裂(因為數(shù)據(jù)頁中數(shù)據(jù)行是按照主鍵的順序組成的單向鏈表卦洽,數(shù)據(jù)一旦變化,是需要維護這種順序的)斜棚,減少性能開銷阀蒂;
  • id 字段沒有業(yè)務(wù)含義,本身不會被更新弟蚀,所以記錄基本不會挪動在數(shù)據(jù)頁中的位置蚤霞。

二級索引

二級索引是一個與聚簇索引獨立的 B+ 樹,葉子節(jié)點不再保存完整的用戶記錄义钉,只保存索引列鍵值和主鍵鍵值昧绣,二級索引中無論是數(shù)據(jù)行之間的單向鏈表還是數(shù)據(jù)頁之間的雙向鏈表都是按照二級索引列的鍵值進行排序的:

注意這里畫的內(nèi)節(jié)點只包含索引列的值和頁號,但實際上還應(yīng)包含主鍵值断医,原文中后面是有單獨一章“內(nèi)節(jié)點中目錄項記錄的唯一性”滞乙,說明存主鍵值是為了解決有二級索引允許重復(fù)值奏纪,但在B+樹索引結(jié)構(gòu)中需要唯一性鉴嗤,這樣插入數(shù)據(jù)才能按序插入到準(zhǔn)確位置斩启。

MyISAM

MyISAM 存儲引擎與 InnoDB 是不一樣的,數(shù)據(jù)和索引分開存放:

  • 將表中的記錄按照記錄的插入順序單獨存儲在一個文件中醉锅,稱之為數(shù)據(jù)文件兔簇。這個文件并不劃分為若干個數(shù)據(jù)頁,有多少記錄就往這個文件中塞多少記錄就成了硬耍。我們可以通過行號而快速訪問到一條記錄垄琐;
  • 使用MyISAM存儲引擎的表會把索引信息另外存儲到一個稱為索引文件的另一個文件中。
    MyISAM表的主鍵索引经柴,葉子節(jié)點中存儲的不是完整的用戶記錄狸窘,而是主鍵值 + 行號的組合。也就是先通過索引找到對應(yīng)的行號坯认,再通過行號去找對應(yīng)的記錄翻擒;
    二級索引類似,葉子節(jié)點存儲的是對應(yīng)字段的值 + 行號牛哺。
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末陋气,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子引润,更是在濱河造成了極大的恐慌巩趁,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,807評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件淳附,死亡現(xiàn)場離奇詭異议慰,居然都是意外死亡,警方通過查閱死者的電腦和手機奴曙,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,284評論 3 399
  • 文/潘曉璐 我一進店門褒脯,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人缆毁,你說我怎么就攤上這事番川。” “怎么了脊框?”我有些...
    開封第一講書人閱讀 169,589評論 0 363
  • 文/不壞的土叔 我叫張陵颁督,是天一觀的道長。 經(jīng)常有香客問我浇雹,道長沉御,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,188評論 1 300
  • 正文 為了忘掉前任昭灵,我火速辦了婚禮吠裆,結(jié)果婚禮上伐谈,老公的妹妹穿的比我還像新娘。我一直安慰自己试疙,他們只是感情好诵棵,可當(dāng)我...
    茶點故事閱讀 69,185評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著祝旷,像睡著了一般履澳。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上怀跛,一...
    開封第一講書人閱讀 52,785評論 1 314
  • 那天距贷,我揣著相機與錄音,去河邊找鬼吻谋。 笑死忠蝗,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的漓拾。 我是一名探鬼主播阁最,決...
    沈念sama閱讀 41,220評論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼晦攒!你這毒婦竟也來了闽撤?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,167評論 0 277
  • 序言:老撾萬榮一對情侶失蹤脯颜,失蹤者是張志新(化名)和其女友劉穎哟旗,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體栋操,經(jīng)...
    沈念sama閱讀 46,698評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡闸餐,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,767評論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了矾芙。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片舍沙。...
    茶點故事閱讀 40,912評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖剔宪,靈堂內(nèi)的尸體忽然破棺而出拂铡,到底是詐尸還是另有隱情,我是刑警寧澤葱绒,帶...
    沈念sama閱讀 36,572評論 5 351
  • 正文 年R本政府宣布感帅,位于F島的核電站,受9級特大地震影響地淀,放射性物質(zhì)發(fā)生泄漏失球。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,254評論 3 336
  • 文/蒙蒙 一帮毁、第九天 我趴在偏房一處隱蔽的房頂上張望实苞。 院中可真熱鬧豺撑,春花似錦、人聲如沸黔牵。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,746評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽荧止。三九已至屹电,卻和暖如春阶剑,著一層夾襖步出監(jiān)牢的瞬間跃巡,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,859評論 1 274
  • 我被黑心中介騙來泰國打工牧愁, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留素邪,地道東北人。 一個月前我還...
    沈念sama閱讀 49,359評論 3 379
  • 正文 我出身青樓猪半,卻偏偏與公主長得像兔朦,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子磨确,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,922評論 2 361

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