MySQL 12 深入理解MySQL索引底層數(shù)據(jù)結(jié)構(gòu)與算法

MySQL實(shí)戰(zhàn) 目錄

前言

磁盤存取時(shí)間

  • 尋道時(shí)間(速度慢,費(fèi)時(shí))
  • 旋轉(zhuǎn)時(shí)間(速度較快)


    image.png

    image.png
局部性原理與磁盤預(yù)讀

為了提升效率蛔糯,要盡量減少磁盤IO的次數(shù)拯腮。實(shí)際過(guò)程中,磁盤并不是每次嚴(yán)格按需讀取蚁飒,而是每次都會(huì)預(yù)讀动壤。磁盤讀取完需要的數(shù)據(jù)后,會(huì)按順序再多讀一部分?jǐn)?shù)據(jù)到內(nèi)存中淮逻,這樣做的理論依據(jù)是計(jì)算機(jī)科學(xué)中注明的局部性原理:

當(dāng)一個(gè)數(shù)據(jù)被用到時(shí)琼懊,其附近的數(shù)據(jù)也通常會(huì)馬上被使用

程序運(yùn)行期間所需要的數(shù)據(jù)通常比較集中
(1)由于磁盤順序讀取的效率很高(不需要尋道時(shí)間,只需很少的旋轉(zhuǎn)時(shí)間)爬早,
因此對(duì)于具有局部性的程序來(lái)說(shuō)哼丈,預(yù)讀可以提高I/O效率.預(yù)讀的長(zhǎng)度一般為頁(yè)(page)的整倍數(shù)。
(2)MySQL(默認(rèn)使用InnoDB引擎),將記錄按照頁(yè)的方式進(jìn)行管理,每頁(yè)大小默認(rèn)為16K(這個(gè)值可以修改)筛严。linux 默認(rèn)頁(yè)大小為4K醉旦。

1. 索引到底是什么

索引是幫助MySQL高效獲取數(shù)據(jù)的排好序數(shù)據(jù)結(jié)構(gòu)
索引存儲(chǔ)在文件里
索引結(jié)構(gòu)

可視化數(shù)據(jù)結(jié)構(gòu)演示

為什么不用二叉樹、紅黑樹桨啃、HASH 作為索引結(jié)構(gòu)

二叉樹 數(shù)據(jù)向一方偏離车胡,一個(gè)節(jié)點(diǎn)的左鍵點(diǎn)小于該節(jié)點(diǎn),右節(jié)點(diǎn)大于該節(jié)點(diǎn)照瘾,但是如果插入二叉樹的數(shù)據(jù)是有序的匈棘,就會(huì)形成二叉樹的極端情況,形成鏈表析命,我們知道樹的查詢復(fù)雜度跟樹的高度有關(guān)主卫,樹越高逃默,那么查詢事件復(fù)雜度就越高,并且需要更多的磁盤IO队秩,所以需要通過(guò)某種約束來(lái)保證樹的平衡笑旺,
紅黑樹

雖然數(shù)據(jù)較二叉樹樹形能翻轉(zhuǎn)保持平衡,數(shù)據(jù)大量的時(shí)候馍资,數(shù)據(jù)深度會(huì)很大
紅黑樹就是平衡二叉樹中的一種筒主,它通過(guò)一系列的規(guī)則來(lái)保證樹的平衡。但是在大規(guī)模數(shù)據(jù)存儲(chǔ)的時(shí)候鸟蟹,紅黑樹常常會(huì)因?yàn)闃涞纳疃冗^(guò)高而導(dǎo)致磁盤IO讀寫過(guò)于頻繁乌妙,導(dǎo)致效率底下,為什么會(huì)形成這種情況呢建钥,我們知道要獲取磁盤上的數(shù)據(jù)藤韵,必須通過(guò)磁盤移動(dòng)臂移動(dòng)到數(shù)據(jù)所在的柱面,然后找到指定盤面熊经,接著旋轉(zhuǎn)盤面找到數(shù)據(jù)所在的磁道泽艘,最后進(jìn)行讀寫,這種涉及到物理操作情況下镐依,性能自然會(huì)很低下匹涮。
HASH

1.hash表只能匹配是否相等,不能實(shí)現(xiàn)范圍查找
select * from xx where id > 23; 這時(shí)就沒辦法索引了
2.當(dāng)需要按照索引進(jìn)行order by時(shí)槐壳,hash值沒辦法支持排序
select * from xx order by score desc;如果score為建立索引的字段然低,hash值沒辦法輔助排序。
3.組合索引可以支持部分索引查詢务唐,如(a,b,c)的組合索引雳攘,查詢中只用到了阿和b也可以查詢的,如果使用hash表枫笛,組合索引會(huì)將幾個(gè)字段合并hash吨灭,沒辦法支持部分索引
4.當(dāng)數(shù)據(jù)量很大時(shí),hash沖突的概率也會(huì)非常大

一般來(lái)說(shuō)有多少層高(數(shù)據(jù)深度)就有多少次IO耗時(shí)操作刑巧,減少層高非常有必要
BTree

  • 度(Degree)一節(jié)點(diǎn)的數(shù)據(jù)存儲(chǔ)個(gè)數(shù)
  • 葉子節(jié)點(diǎn)具有相同的深度
  • 葉子節(jié)點(diǎn)的指針為空
  • 節(jié)點(diǎn)中的數(shù)據(jù)key從左到右遞增排列
    注意:由于計(jì)算機(jī)硬件限制沃于,度(Degree)無(wú)限增大,并不能減少IO次數(shù)


    image.png

B+Tree(B-Tree上優(yōu)化)

  • 非葉子節(jié)點(diǎn)不存儲(chǔ)data海诲,只儲(chǔ)存key,可以增大度(Degree)
  • 葉子節(jié)點(diǎn)不存儲(chǔ)指針
  • 順序訪問(wèn)指針檩互,提高區(qū)間訪問(wèn)的性能


    image.png

B+Tree索引的性能分析

  • 一般使用磁盤I/O次數(shù)評(píng)價(jià)索引結(jié)構(gòu)的優(yōu)劣
  • 預(yù)讀:磁盤一般會(huì)順序向后讀取一定長(zhǎng)度的數(shù)據(jù)(頁(yè)的整數(shù)倍)放入內(nèi)存
  • 局部性原理:當(dāng)一個(gè)數(shù)據(jù)被用到時(shí)特幔,其附近的數(shù)據(jù)也通常會(huì)馬上被使用
  • B+Tree節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁(yè),每次新建節(jié)點(diǎn)直接申請(qǐng)一個(gè)頁(yè)的空間闸昨,這樣就保證一個(gè)節(jié)點(diǎn)物理上也存儲(chǔ)在一個(gè)頁(yè)里蚯斯,就實(shí)現(xiàn)了一個(gè)節(jié)點(diǎn)的載入只需一次I/O
  • B+Tree的度d一般會(huì)超過(guò)100薄风,因此h非常小(一般為3到5之間)
為什么mysql的索引使用B+樹而不是B樹呢?拍嵌?

上面大致介紹了B-樹遭赂,B+樹,哈希索引横辆。那么B+樹的優(yōu)勢(shì)大致總結(jié)如下

  • 不同于B-樹只適合隨機(jī)檢索撇他,B+樹同時(shí)支持隨機(jī)檢索和順序檢索;
  • B+樹的磁盤讀寫代價(jià)更低狈蚤。B+樹內(nèi)部結(jié)點(diǎn)比B-樹小困肩,盤塊能容納的結(jié)點(diǎn)中關(guān)鍵字?jǐn)?shù)量更多,一次性讀入內(nèi)存中可以查找的關(guān)鍵字也就越多脆侮,相對(duì)的锌畸,IO讀寫次數(shù)也就降低了。而IO讀寫次數(shù)是影響索引檢索效率的最大因素靖避。
  • B+樹的查詢效率更加穩(wěn)定潭枣。B-樹搜索有可能會(huì)在非葉子結(jié)點(diǎn)結(jié)束,越靠近根節(jié)點(diǎn)的記錄查找時(shí)間越短幻捏,只要找到關(guān)鍵字即可確定記錄的存在盆犁,其性能等價(jià)于在關(guān)鍵字全集內(nèi)做一次二分查找。而在B+樹中粘咖,順序檢索比較明顯蚣抗,隨機(jī)檢索時(shí),任何關(guān)鍵字的查找都必須走一條從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路瓮下,所有關(guān)鍵字的查找路徑長(zhǎng)度相同翰铡,導(dǎo)致每一個(gè)關(guān)鍵字的查詢效率相當(dāng)。
  • B-樹在提高了磁盤IO性能的同時(shí)并沒有解決元素遍歷的效率低下的問(wèn)題讽坏。B+樹的葉子節(jié)點(diǎn)使用指針順序連接在一起锭魔,只要遍歷葉子節(jié)點(diǎn)就可以實(shí)現(xiàn)整棵樹的遍歷。而且在數(shù)據(jù)庫(kù)中基于范圍的查詢是非常頻繁的路呜,而B-樹不支持這樣的操作(或者說(shuō)效率太低)迷捧。


    image.png

2. MySQL數(shù)據(jù)庫(kù)存儲(chǔ)引擎

MyISAM索引實(shí)現(xiàn)(非聚集)

MyISAM索引文件和數(shù)據(jù)文件是分離的
image.png

image.png

有些 MySQL 版本還缺乏完整的存儲(chǔ)過(guò)程支持 — 意味著不支持事務(wù),這是 MyISAM 系統(tǒng)的最大缺點(diǎn)胀葱。

InnoDB索引實(shí)現(xiàn)(聚集)

  • 數(shù)據(jù)文件本身就是索引文件
  • 表數(shù)據(jù)文件本身就是按B+Tree組織的一個(gè)索引結(jié)構(gòu)文件
  • 聚集索引-葉節(jié)點(diǎn)包含了完整的數(shù)據(jù)記錄

為什么InnoDB表必須有主鍵漠秋,并且推薦使用整型的自增主鍵?

首先抵屿,為了滿足MySQL的索引數(shù)據(jù)結(jié)構(gòu)B+樹的特性庆锦,必須要有索引作為主鍵,可以有效提高查詢效率轧葛,因此InnoDB必須要有主鍵搂抒。如果不手動(dòng)指定主鍵艇搀,InnoDB會(huì)從插入的數(shù)據(jù)中找出不重復(fù)的一列作為主鍵索引,如果沒找到不重復(fù)的一列求晶,這時(shí)候InnoDB會(huì)選擇內(nèi)置的ROWID作為主鍵焰雕,寫入順序和ROWID增長(zhǎng)順序一致;
其次芳杏,索引的數(shù)據(jù)類型是整型矩屁,一方面整型占有的磁盤空間或內(nèi)存空間相比字符串更少,另一方面整型比較比字符串比較更快速蚜锨,字符串比較是先轉(zhuǎn)換為ASCII碼档插,然后再比較的。
最后亚再,B+樹本質(zhì)是多路多叉樹郭膛,如果主鍵索引不是自增的,那么后續(xù)插入的索引就會(huì)引起B(yǎng)+樹的其他節(jié)點(diǎn)的分裂和重新平衡氛悬,影響數(shù)據(jù)插入的效率则剃,如果是自增主鍵,只用在尾節(jié)點(diǎn)做增加就可以如捅。

  • 為什么非主鍵索引結(jié)構(gòu)葉子節(jié)點(diǎn)存儲(chǔ)的是主鍵值棍现?(一致性和節(jié)省存儲(chǔ)空間)

主鍵索引和非主鍵索引維護(hù)各自的B+樹結(jié)構(gòu),當(dāng)插入的數(shù)據(jù)的時(shí)候镜遣,由于數(shù)據(jù)只有一份己肮,通過(guò)非主鍵索引獲取到主鍵值,然后再去主鍵索引的B+樹數(shù)據(jù)結(jié)構(gòu)中找到對(duì)應(yīng)的行數(shù)據(jù)悲关,節(jié)省了內(nèi)存空間谎僻;
如果非主鍵索引的葉子節(jié)點(diǎn)也存儲(chǔ)一份數(shù)據(jù),如果通過(guò)非主鍵索引插入數(shù)據(jù)寓辱,那么要向主鍵索引對(duì)應(yīng)的行數(shù)據(jù)進(jìn)行同步艘绍,那么會(huì)帶來(lái)數(shù)據(jù)一致性問(wèn)題★ぃ可以通過(guò)事務(wù)的方式解決诱鞠,我們都知道使用事務(wù)后,就會(huì)對(duì)性能有所消耗这敬。

image.png
image.png

image.png

聯(lián)合索引結(jié)構(gòu)

聯(lián)合索引的底層存儲(chǔ)結(jié)構(gòu)長(zhǎng)什么樣航夺?

定義聯(lián)合索引(員工級(jí)別,員工姓名崔涂,員工出生年月)敷存,將聯(lián)合索引按照索引順序放入節(jié)點(diǎn)中,新插入節(jié)點(diǎn)時(shí),先按照聯(lián)合索引中的員工級(jí)別比較锚烦,如果相同會(huì)按照是員工姓名比較,如果員工級(jí)別和員工姓名都相同 最后是員工的出生年月比較帝雇′潭恚可以從圖中從上到下,從左到右看尸闸,第一個(gè)B+樹的節(jié)點(diǎn) 是通過(guò)聯(lián)合索引的員工級(jí)別比較的彻亲,第二個(gè)節(jié)點(diǎn)是 員工級(jí)別相同,會(huì)按照員工姓名比較吮廉,第三個(gè)節(jié)點(diǎn)是 員工級(jí)別和員工姓名都相同苞尝,會(huì)按照員工出生年月比較。


image.png
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末宦芦,一起剝皮案震驚了整個(gè)濱河市宙址,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌调卑,老刑警劉巖抡砂,帶你破解...
    沈念sama閱讀 222,729評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異恬涧,居然都是意外死亡注益,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門溯捆,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)丑搔,“玉大人,你說(shuō)我怎么就攤上這事提揍∑≡拢” “怎么了?”我有些...
    開封第一講書人閱讀 169,461評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵碳锈,是天一觀的道長(zhǎng)顽冶。 經(jīng)常有香客問(wèn)我,道長(zhǎng)售碳,這世上最難降的妖魔是什么强重? 我笑而不...
    開封第一講書人閱讀 60,135評(píng)論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮贸人,結(jié)果婚禮上间景,老公的妹妹穿的比我還像新娘。我一直安慰自己艺智,他們只是感情好倘要,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,130評(píng)論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著,像睡著了一般封拧。 火紅的嫁衣襯著肌膚如雪志鹃。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,736評(píng)論 1 312
  • 那天泽西,我揣著相機(jī)與錄音曹铃,去河邊找鬼。 笑死捧杉,一個(gè)胖子當(dāng)著我的面吹牛陕见,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播味抖,決...
    沈念sama閱讀 41,179評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼评甜,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了仔涩?” 一聲冷哼從身側(cè)響起忍坷,我...
    開封第一講書人閱讀 40,124評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎红柱,沒想到半個(gè)月后承匣,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,657評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡锤悄,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,723評(píng)論 3 342
  • 正文 我和宋清朗相戀三年韧骗,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片零聚。...
    茶點(diǎn)故事閱讀 40,872評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡袍暴,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出隶症,到底是詐尸還是另有隱情政模,我是刑警寧澤,帶...
    沈念sama閱讀 36,533評(píng)論 5 351
  • 正文 年R本政府宣布蚂会,位于F島的核電站淋样,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏胁住。R本人自食惡果不足惜趁猴,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,213評(píng)論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望彪见。 院中可真熱鬧儡司,春花似錦、人聲如沸余指。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至碉碉,卻和暖如春柴钻,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背垢粮。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工顿颅, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人足丢。 一個(gè)月前我還...
    沈念sama閱讀 49,304評(píng)論 3 379
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像庇配,于是被迫代替她去往敵國(guó)和親斩跌。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,876評(píng)論 2 361