一汽烦，索引數(shù)據(jù)結(jié)構(gòu)紅黑樹那婉，Hash粟瞬，B+樹詳解
索引是幫助MySQL高效獲取數(shù)據(jù)的排好序的數(shù)據(jù)結(jié)構(gòu)
????????????????這篇文章主要寫一下mysql的底層數(shù)據(jù)結(jié)構(gòu)以及索引是怎么支撐千萬級(jí)表的快速查找短荐。直接進(jìn)入在正題并闲，比如說细睡，我們現(xiàn)在以Col2作為查詢條件寫一個(gè)sql：select * from t? where Col2=89 ，通過這樣的一個(gè)sql可以發(fā)現(xiàn)帝火，mysql在不使用索引的情況下溜徙。會(huì)進(jìn)行全表掃描。會(huì)從第一條記錄開始查詢犀填，一共進(jìn)行6次查找蠢壹，每次查找都會(huì)進(jìn)行一次IO磁盤查找，這種效率是非常低的九巡。那么Mysql顯然如果不使用索引這種效率低到無法想象图贸。所以就引入今天的話題，mysql的底層索引以及實(shí)現(xiàn)原理冕广。先拋出結(jié)論Mysql底層使用的是B+樹索引疏日。
? ? ? ? ? ? ? ? 先不說B+樹索引，咱們先一個(gè)一個(gè)分析撒汉。然后在講為什么使用B+樹沟优。這樣更有助于理解Mysql為什么使用B+數(shù)索引作為底層的索引數(shù)據(jù)結(jié)構(gòu)，就針對(duì)剛才那條sql語(yǔ)句神凑。
select * from t? where Col2=89
? ? ? ? ? ? ? ? 1净神，我們知道在不使用索引的情況下要進(jìn)行6次的磁盤IO何吝。那么如果說使用索引的話，到底如何去選擇合適的數(shù)據(jù)結(jié)構(gòu)呢鹃唯？先來分析一下爱榕，如果說使用二叉樹數(shù)據(jù)結(jié)構(gòu)，就像下圖顯示的這種葉子節(jié)點(diǎn)比非葉子節(jié)點(diǎn)小的就放在左面坡慌，如果大的就放在右面黔酥，基于這種數(shù)據(jù)結(jié)構(gòu)，只要進(jìn)行兩次磁盤IO就可以輕松的去找到89這個(gè)磁盤的指針洪橘。先說一下二叉樹的這種存儲(chǔ)方式跪者，首先是以Key-value的形式去存儲(chǔ)的。34是或者89是Key熄求，value就是對(duì)應(yīng)的磁盤文件指針渣玲。通過value找到那一條數(shù)據(jù)。
雖然說二叉樹的這種索引數(shù)據(jù)結(jié)構(gòu)可以提高效率弟晚。但是存在一個(gè)問題忘衍。如果說我們的索引是自增的形式呢？此時(shí)這種二叉樹的數(shù)據(jù)結(jié)構(gòu)還有效嗎卿城？顯然是沒有效的枚钓。以下圖為證，因?yàn)槊看涡略黾右粋€(gè)元素都是遞增的瑟押。所以樹的高度還是會(huì)很高搀捷。如果有500萬條數(shù)據(jù)呢？如果我要檢索0006這個(gè)索引字段多望，是不是也要經(jīng)過6次磁盤IO嫩舟。所以二叉樹不能解決這個(gè)問題。所以mysql不可能使用這種二叉樹的方式便斥。
然后再說說第二個(gè)至壤，在這個(gè)基礎(chǔ)上威始，我們可以使用紅黑樹枢纠，來達(dá)到樹的平衡機(jī)制，如下圖黎棠。雖然說這個(gè)紅黑樹解決了遞增索引的平衡問題晋渺，但是還是不能解決樹的高度問題，比如說現(xiàn)在有500萬條數(shù)據(jù)脓斩，這個(gè)樹的高度至少有20個(gè)高度木西。顯然也要進(jìn)行大量的磁盤IO。所以說Mysql也不會(huì)使用這種數(shù)據(jù)結(jié)構(gòu)作為底層的實(shí)現(xiàn)随静。
????????????????????然后再說第三個(gè)八千，有的人可能已經(jīng)想到了吗讶。用B樹啊。沒錯(cuò)恋捆，下面我要說的就是B樹這種數(shù)據(jù)結(jié)構(gòu)照皆，B樹是解決二叉平衡樹的高度問題，那么是如何解決的呢沸停？如下圖：比如說15,56,77.....比如他們是主鍵索引膜毁，先說一下B樹索引的特點(diǎn)：葉節(jié)點(diǎn)具有相同的深度，葉節(jié)點(diǎn)的指針為空愤钾。所有索引元素不重復(fù)瘟滨。節(jié)點(diǎn)中的數(shù)據(jù)索引從左到右遞增排列。通過這幾個(gè)特點(diǎn)可知能颁，也就是說杂瘸，B樹索引是默認(rèn)排好了序的，從左向右是遞增的形式伙菊，每一個(gè)節(jié)點(diǎn)可以更多的存儲(chǔ)索引胧沫，通過增加點(diǎn)個(gè)節(jié)點(diǎn)的寬度來解決樹的高度的問題。每一個(gè)節(jié)點(diǎn)有多個(gè)索引占业，然后每一個(gè)索引都有一個(gè)指針绒怨，這個(gè)指針是指向了下一個(gè)節(jié)點(diǎn)的地址。并且每一個(gè)節(jié)點(diǎn)的索引都對(duì)應(yīng)了一個(gè)data數(shù)據(jù)空間谦疾，這個(gè)data就是對(duì)應(yīng)的一條數(shù)據(jù)記錄南蹂。它的工作原理是什么呢？比如說念恍，我要查找49這個(gè)記錄六剥，那么首先，會(huì)進(jìn)行一次磁盤IO把第一個(gè)節(jié)點(diǎn)的索引集合load到內(nèi)存中來峰伙，然后跟49進(jìn)行比較疗疟，比如說沒找到49，那么就會(huì)從左向右進(jìn)行比較瞳氓。比如說找到了15和56之間的這個(gè)節(jié)點(diǎn)指針策彤，那么就會(huì)通過這個(gè)指針再進(jìn)行一次磁盤IO把與之對(duì)應(yīng)的那個(gè)節(jié)點(diǎn)的數(shù)據(jù)load到內(nèi)存中來。從左向右找到49.一共進(jìn)行了2次磁盤IO匣摘。就找到了店诗。但是這種B樹的數(shù)據(jù)結(jié)構(gòu)還是有一些小問題的。我們知道每一個(gè)小節(jié)點(diǎn)是Key-Value形式存儲(chǔ)的音榜，那么如果說這個(gè)data占用的數(shù)據(jù)量比較大的話也就意味著占用的空間就會(huì)增大庞瘸，因?yàn)閙ysql的一個(gè)節(jié)點(diǎn)默認(rèn)存儲(chǔ)是16KB。如果data的數(shù)據(jù)量大的話赠叼，也就意味著擦囊，橫向的存儲(chǔ)的節(jié)點(diǎn)就少了违霞。高度還是存在不可控，但是比紅黑樹的高度肯定要矮一些瞬场。所以說mysql對(duì)B樹進(jìn)行了一點(diǎn)兒修改葛家，變成了B+樹。現(xiàn)在說完了為什么mysql底層使用B+樹這種數(shù)據(jù)結(jié)構(gòu)泌类，我們?cè)趤砣娴姆治鲆幌翨+樹這種數(shù)據(jù)結(jié)構(gòu)是在怎么回事兒癞谒，以及是如何存儲(chǔ)的。
B+樹刃榨，首先看一下B+樹有哪些特點(diǎn)：1首先非葉子節(jié)點(diǎn)是不存儲(chǔ)data數(shù)據(jù)的弹砚。而且節(jié)點(diǎn)是可以重復(fù)的。只存儲(chǔ)索引(冗余)枢希，可以放更多的索引桌吃，葉子節(jié)點(diǎn)包含所有索引字段。葉子節(jié)點(diǎn)用指針連接苞轿，提高區(qū)間訪問的性能茅诱。然后我們說一下存儲(chǔ)結(jié)構(gòu)，比如說搬卒，我們用的是主鍵索引瑟俭，一個(gè)整形的索引Key大概占8B的字節(jié)空間，然后與之對(duì)應(yīng)的指向下一個(gè)節(jié)點(diǎn)的指針占用6B契邀，（這是計(jì)算基底層規(guī)定的指針大邪诩摹）。也就說6+8=14B坯门。然后Mysql規(guī)定一個(gè)節(jié)點(diǎn)可以存儲(chǔ)16KB微饥，也就是說這一個(gè)節(jié)點(diǎn)能存儲(chǔ)多少個(gè)索引呢？用16KB/14B=1170個(gè)古戴。一個(gè)節(jié)點(diǎn)就是1170個(gè)索引欠橘，那么每一個(gè)與之對(duì)應(yīng)的下一個(gè)節(jié)點(diǎn)還是1170個(gè)。那你可能會(huì)說现恼。你的葉子節(jié)點(diǎn)肃续，有data數(shù)據(jù)，假設(shè)一個(gè)data存儲(chǔ)是1KB肯定夠了述暂。那么一個(gè)節(jié)點(diǎn)存儲(chǔ)16個(gè)痹升。那么我們算一下建炫∑杈拢可以存儲(chǔ)多少數(shù)據(jù)。我直接說結(jié)果是1170*1170*16=21902400條數(shù)據(jù)肛跌。這也就是為什么艺配，B+樹索引這么牛逼的原因察郁。2千多萬條數(shù)據(jù)，只要進(jìn)行3次磁盤IO就可以解決转唉。其實(shí)實(shí)際上皮钠，第一層的節(jié)點(diǎn)，會(huì)被加載到內(nèi)存里赠法。所以說麦轰，只要進(jìn)行2次磁盤IO就足夠了。如果數(shù)據(jù)超過2千萬條應(yīng)該就要做分表操作了砖织。這里不做介紹款侵。了解了這些之后咱們?cè)僬f說，B+樹索引下面的指針侧纯，為什么會(huì)有這個(gè)指針新锈，而且B+樹的葉子節(jié)點(diǎn)是雙向的指針，說這個(gè)問題之前眶熬，先做一點(diǎn)兒鋪墊妹笆，我們只mysql中，除了B+樹鎖引以外還有一種hash索引娜氏，就是說在查找的時(shí)候拳缠，先對(duì)這個(gè)索引進(jìn)行一次hash運(yùn)算。每一個(gè)索引值經(jīng)過hash算法之后贸弥，會(huì)和磁盤文件指針形成一個(gè)映射關(guān)系脊凰。通過這個(gè)關(guān)系就可以快速定位到那個(gè)索引所在的磁盤文件指針。所以hash索引是最快的茂腥。跟多少數(shù)據(jù)量也沒有關(guān)系狸涌。但是hash索引有一個(gè)弊端，如果是范圍查找那hash索引就沒用了最岗。索引我們百分之90的情況下用的都是B+樹索引帕胆。那么再說，葉子節(jié)點(diǎn)上的雙向鏈表指針的作用般渡，就是說當(dāng)我們用范圍查找的時(shí)候懒豹，把葉子節(jié)點(diǎn)load到內(nèi)存之后，通過這個(gè)指針可以快速的進(jìn)行范圍查找驯用。起到的作用就是用來進(jìn)行范圍查找的脸秽。B+樹索引到現(xiàn)在就寫清楚了。下面咱們?cè)僬f說Mysql的存儲(chǔ)引擎蝴乔。
二：Mysq存儲(chǔ)引擎索引實(shí)現(xiàn)
mysql提供了多種存儲(chǔ)引擎记餐，我只介紹兩種，一種是Myisam和innoDB引擎薇正。myisam存儲(chǔ)引擎是索引文件和數(shù)據(jù)文件是分離的(非聚集)片酝。
mysiam存儲(chǔ)引擎有三個(gè)文件一個(gè)是frm文件囚衔，一個(gè)是myi文件，一個(gè)是myd文件雕沿。myd文件存儲(chǔ)是數(shù)據(jù)练湿，myi存儲(chǔ)是索引關(guān)系，frm存儲(chǔ)是表的結(jié)構(gòu)大概可以這樣理解审轮。mysiam存儲(chǔ)引擎比如說我們查詢49肥哎，經(jīng)過兩次磁盤IO以后，拿到葉子節(jié)點(diǎn)對(duì)應(yīng)的data疾渣，其中data存儲(chǔ)的是myd文件的磁盤文件指針贤姆。拿到這個(gè)磁盤文件指針以后。就可以找到myd文件磁盤文件指針?biāo)诘男形瘸摹＿@樣就可已找到數(shù)據(jù)了霞捡。
再來說一下innodb引擎。innodb是聚集索引薄疚，葉子節(jié)點(diǎn)存儲(chǔ)的是一整行的數(shù)據(jù)碧信，表數(shù)據(jù)文件本身就是按B+Tree組織的一個(gè)索引結(jié)構(gòu)文件，聚集索引-葉節(jié)點(diǎn)包含了完整的數(shù)據(jù)記錄街夭。而且砰碴，innodb引擎只有兩個(gè)數(shù)據(jù)庫(kù)文件一個(gè)是frm，一個(gè)bid文件板丽。索引結(jié)構(gòu)和數(shù)據(jù)存儲(chǔ)在一個(gè)文件里呈枉。下面這張圖的例子是主鍵索引。然后在看看非主鍵索引的存儲(chǔ)結(jié)構(gòu)是什么樣的埃碱？在說非主鍵索引結(jié)構(gòu)之前先提兩個(gè)問題：為什么InnoDB表必須有主鍵猖辫，并且推薦使用整型的自增主鍵？先說第一問題砚殿，如果說innoDB沒有主鍵的話啃憎，那么mysql會(huì)因?yàn)橐獫M足B+樹的結(jié)構(gòu)就會(huì)去找你的唯一索引列，找不到就會(huì)生成一個(gè)類似于Rowid的東西似炎。第二個(gè)問題辛萍，為什么是整形而且自增，因?yàn)槿绻皇钦蔚脑捪勖辏谝粋€(gè)因?yàn)榇鎯?chǔ)空間可能會(huì)變大贩毕，假設(shè)你存儲(chǔ)的是字符串，而且在進(jìn)行節(jié)點(diǎn)插入的時(shí)候仆嗦，兩個(gè)節(jié)點(diǎn)直接會(huì)進(jìn)行比較大小辉阶，我們知道B+樹是從左向右遞增的形式。如果是整形就不需要ASCII的計(jì)算了。也提高了效率睛藻。然后為什么是遞增呢启上？如果說我現(xiàn)在有個(gè)幾點(diǎn)是10邢隧，那么剛好我要存儲(chǔ)一個(gè)8的節(jié)點(diǎn)店印，那么此時(shí)我發(fā)現(xiàn)10的這個(gè)節(jié)點(diǎn)正好存滿了16KB。那么此時(shí)Mysql為了滿足B+樹的結(jié)構(gòu)就會(huì)進(jìn)行結(jié)構(gòu)分裂倒慧。性能會(huì)下降按摘。所以要求是遞增。
innodb非主鍵索引的存儲(chǔ)結(jié)構(gòu)：非主鍵的索引葉子節(jié)點(diǎn)的data存儲(chǔ)的是主鍵纫谅，為什么要這么做呢炫贤？因?yàn)槿绻f我們有主鍵索引，又有非主鍵索引的情況下付秕，我們又要維護(hù)主鍵索引又要維護(hù)非主鍵索引兰珍，當(dāng)我們insert的一條數(shù)據(jù)的時(shí)候，必須主鍵索引和非主鍵索引的數(shù)據(jù)同時(shí)維護(hù)完了才可以寫入數(shù)據(jù)表询吴。那么這種情況就有可能產(chǎn)生類似于分布式事務(wù)的問題掠河，所以mysql基于這個(gè)問題，選擇了非主鍵索引的data值存儲(chǔ)的是主鍵猛计。說白了唠摹。你的主鍵索引數(shù)據(jù)維護(hù)好了。我只要引入你的id就可以了奉瘤。保證了一致性勾拉，也保證了節(jié)省空間的問題。缺點(diǎn)是做了2次磁盤IO盗温。但是效率依然是很高的藕赞。
最后再說一下聯(lián)合索引的概念。為什么要使用聯(lián)合索引呢卖局？如果說有三個(gè)索引找默，那么每一個(gè)索引單獨(dú)建立的話，就會(huì)建立三個(gè)索引樹吼驶，很費(fèi)空間惩激，如果使用聯(lián)合索引，就會(huì)降低空間蟹演，我們知道B+樹的存儲(chǔ)結(jié)構(gòu)是從左向右一次遞增风钻，并且排好序的。如果是聯(lián)合索引首先會(huì)先根據(jù)第一個(gè)字段進(jìn)行排序酒请，從左向右骡技，如果第一個(gè)字段相等，那么就會(huì)根據(jù)第二字段進(jìn)行從左向右的排序，以此類推布朦。
