為什么MySQL的常用引擎都默認(rèn)使用B+樹(shù)作為索引？
一、前言
為了講清楚這個(gè)問(wèn)題，阿粉先帶大家了解一下什么是索引。
我記得剛剛學(xué)習(xí)數(shù)據(jù)庫(kù)的時(shí)候，老師喜歡用書(shū)本的目錄來(lái)類比數(shù)據(jù)庫(kù)的索引，并告訴我們索引能夠像目錄一樣，讓我們更快地找到想要找到的數(shù)據(jù)。
如果是第一次接觸索引，這個(gè)比喻能夠讓我們有一個(gè)直觀的印象。但是當(dāng)深入去學(xué)習(xí)索引的時(shí)候，我們不能繼續(xù)持有索引即目錄的思想，我們要跳出來(lái)去思考索引的本質(zhì)是什么。
二、索引的本質(zhì)
在沒(méi)有索引的情況下，我們查找數(shù)據(jù)只能按照從頭到尾的順序逐行查找，每查找一行數(shù)據(jù)，意味著我們要到到磁盤(pán)相應(yīng)的位置去讀取一條數(shù)據(jù)。
如果把查詢一條數(shù)據(jù)分為到磁盤(pán)中查詢和比對(duì)查詢條件兩步的話，到磁盤(pán)中查詢的時(shí)間會(huì)遠(yuǎn)遠(yuǎn)大于比對(duì)查詢條件的時(shí)間，這意味著在一次查詢中，磁盤(pán)io占用了大部分的時(shí)間。更進(jìn)一步地說(shuō)，一次查詢的效率取絕于磁盤(pán)io的次數(shù)，如果我們能夠在一次查詢中盡可能地降低磁盤(pán)io的次數(shù)，那么我們就能加快查詢的速度。
在知道了減少磁盤(pán)io能加快查詢速度后，我們就要聚焦于如何減少磁盤(pán)io。如果按照原表逐行查詢的話，n條數(shù)據(jù)就要查詢n次，也就是O(N)的時(shí)間復(fù)雜度，為了減少磁盤(pán)io的次數(shù)，我們必須用一種查詢時(shí)間復(fù)雜度更低的數(shù)據(jù)結(jié)構(gòu)來(lái)保存數(shù)據(jù)。
這種查詢時(shí)間復(fù)雜度低的數(shù)據(jù)結(jié)構(gòu)，我們稱之為索引。所以通俗來(lái)說(shuō)，索引其實(shí)就是某種數(shù)據(jù)結(jié)構(gòu)，能充當(dāng)索引的數(shù)據(jù)結(jié)構(gòu)是多種多樣的。
三、索引的選擇
既然索引是一種便于查詢的數(shù)據(jù)結(jié)構(gòu)，如果大家對(duì)數(shù)據(jù)結(jié)構(gòu)有一定了解的話，大概率會(huì)首選樹(shù)型結(jié)構(gòu)。畢竟樹(shù)型結(jié)構(gòu)普遍有著O(logN)的查詢時(shí)間復(fù)雜度，而且插入刪除數(shù)據(jù)的性能也比較平均。(可能你會(huì)說(shuō)數(shù)組，哈希表的查詢速度也很高啊，這個(gè)后面也會(huì)分析)
雖然我們都已經(jīng)知道Mysql中最常用的引擎像InnoDB和MyISAM，最終都選擇了B+樹(shù)作為索引，但是這里我還是打算從最常見(jiàn)的二叉樹(shù)開(kāi)始講起，推導(dǎo)一下為什么最終選擇了B+樹(shù)作為索引，并比較一下幾種樹(shù)型結(jié)構(gòu)在充當(dāng)索引時(shí)的優(yōu)劣。
二叉樹(shù)
最普通的二叉樹(shù)的問(wèn)題在于他不能保證O(logN)的查詢時(shí)間復(fù)雜度，我們看下面的圖：
由于插入的元素逐漸增大，元素始終在右邊進(jìn)行插入，好好的一棵二叉樹(shù)最終變成了一條“鏈表”。在這種極端的情況下，二叉樹(shù)的查詢時(shí)間復(fù)雜度不再是O(logN)，而是退化為O(N)，這樣顯然不符合索引的要求。
平衡二叉樹(shù)(紅黑樹(shù))
像紅黑樹(shù)這樣的平衡二叉樹(shù)，無(wú)論如何插入元素，他都可以通過(guò)一些旋轉(zhuǎn)的方法調(diào)整樹(shù)的高度，使得整棵樹(shù)的查詢效率維持在O(logN)，如下圖所示：
這么來(lái)說(shuō)他已經(jīng)符合了成為索引的必備條件，但是最終沒(méi)有選擇他作為索引說(shuō)明還有不足的地方。仔細(xì)看看可以發(fā)現(xiàn)平衡二叉樹(shù)的每個(gè)節(jié)點(diǎn)只有兩個(gè)孩子節(jié)點(diǎn)，如果一張表的數(shù)據(jù)量特別大，整棵樹(shù)的高度也會(huì)隨之上升。一個(gè)千萬(wàn)級(jí)別的表如果用平衡二叉樹(shù)作為索引的話，樹(shù)高將會(huì)達(dá)到二十多層。這也就意味著做一次查詢需要二十多次磁盤(pán)io，這是一個(gè)不小的開(kāi)銷。
那么有沒(méi)有能在大數(shù)據(jù)量的情況下，還能保持一個(gè)較小樹(shù)高的樹(shù)型結(jié)構(gòu)呢?
B樹(shù)和B+樹(shù)
答案就是B樹(shù)。上面我們說(shuō)到了平衡二叉樹(shù)的瓶頸在于一個(gè)節(jié)點(diǎn)只有兩個(gè)孩子節(jié)點(diǎn)，而B(niǎo)樹(shù)一個(gè)節(jié)點(diǎn)可以存放N個(gè)孩子節(jié)點(diǎn)，這就完美解決了樹(shù)高的問(wèn)題，我們可以把B樹(shù)稱為平衡多叉樹(shù)，B樹(shù)作為索引如下圖所示：
圖片來(lái)源網(wǎng)絡(luò)
但是以B樹(shù)的結(jié)構(gòu)作為索引仍有可以優(yōu)化的地方，我們先看看最終的B+樹(shù)，再仔細(xì)分析B+樹(shù)在B樹(shù)的基礎(chǔ)上作了哪些改進(jìn)，為什么B+樹(shù)最終能夠勝任索引的工作：
圖片來(lái)源網(wǎng)絡(luò)
從圖片中可以看到B+樹(shù)同樣是一棵多差平衡樹(shù)，和B樹(shù)一樣很好地解決了樹(shù)高的問(wèn)題。
改進(jìn)點(diǎn)一：
但仔細(xì)看可以發(fā)現(xiàn)，B樹(shù)的節(jié)點(diǎn)中既存儲(chǔ)索引，也存儲(chǔ)表對(duì)應(yīng)的數(shù)據(jù);而B(niǎo)+樹(shù)的非葉子節(jié)點(diǎn)是不存儲(chǔ)數(shù)據(jù)的，只存儲(chǔ)索引，數(shù)據(jù)全部存儲(chǔ)在葉子節(jié)點(diǎn)上。
為什么要做這樣的改進(jìn)?我們做一次算術(shù)就知道了。
假設(shè)樹(shù)高為2，主鍵ID為bigint類型，長(zhǎng)度為8字節(jié)，節(jié)點(diǎn)指針為6字節(jié)，一行數(shù)據(jù)記錄的大小為1k，一次io操作能獲得一頁(yè)16k的數(shù)據(jù)。
在索引為B+樹(shù)的情況下，根節(jié)點(diǎn)能存儲(chǔ)：16k / (6 + 8) = 1170 條索引指針;到了第一層，一共能指向 1170 * 1170 = 1368900 條索引指針;到了最底一層葉子節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)能存儲(chǔ)16k / 1k = 16 條記錄，一共能存儲(chǔ) 1170 * 1170 * 16 = 21902400 條記錄
在B樹(shù)的情況下，由于非葉子節(jié)點(diǎn)使用了大量空間存儲(chǔ)數(shù)據(jù)，存放的索引指針肯定就少，最終整棵樹(shù)如果想要存儲(chǔ)和B+樹(shù)一樣多的數(shù)據(jù)就必須要增加樹(shù)高，這樣一來(lái)就增加了磁盤(pán)io，所以說(shuō)B+樹(shù)作為索引的性能比B樹(shù)高。
改進(jìn)點(diǎn)二：
葉子節(jié)點(diǎn)之間使用指針連接，提高區(qū)間訪問(wèn)效率。如果我們要進(jìn)行范圍查詢，可以輕松通過(guò)B+樹(shù)葉子節(jié)點(diǎn)之間的指針進(jìn)行遍歷，減少了不必要的磁盤(pán)io。
總結(jié)
看到這里，相信大家對(duì)為什么Mysql的常用引擎都默認(rèn)使用B+樹(shù)作為索引已經(jīng)有了初步的認(rèn)知。我們只要牢記一點(diǎn)：索引是為了減少磁盤(pán)io提高查詢性能而存在的。
最后回應(yīng)一下為什么不常用哈希表和數(shù)組作為索引
哈希表雖然單一個(gè)值的查詢效率很高，但是撐不住范圍查詢，哪個(gè)公司的業(yè)務(wù)還沒(méi)個(gè)范圍查詢呢?
而數(shù)組雖然查詢的效率高，但是增加和刪除的效率低，由于記錄在增加和刪除的時(shí)候索引也得跟著維護(hù)，這會(huì)導(dǎo)致大數(shù)據(jù)量的情況下，增加或刪除一條記錄效率較低。
