在我們的印象中，mysql數(shù)據(jù)表里無(wú)非就是存儲(chǔ)一行行的數(shù)據(jù)。跟個(gè)excel似的。

直接遍歷這一行行數(shù)據(jù)，性能就是O(n)，比較慢。為了加速查詢，使用了B+樹(shù)來(lái)做索引，將查詢性能優(yōu)化到了O(lg(n))。

但問(wèn)題就來(lái)了，查詢數(shù)據(jù)性能在 lg(n) 級(jí)別的數(shù)據(jù)結(jié)構(gòu)有很多，比如redis的zset里用到的跳表，也是lg(n)，并且實(shí)現(xiàn)還賊簡(jiǎn)單。

那為什么mysql的索引，不使用跳表呢?

我們今天就來(lái)聊聊這個(gè)話題。

B+樹(shù)的結(jié)構(gòu)

之前的一篇文章里，已經(jīng)提到過(guò)B+樹(shù)的結(jié)構(gòu)了。文章不長(zhǎng)，如果沒(méi)看過(guò)，建議先看下。

當(dāng)然，不看也行。

在這里，為了混點(diǎn)字?jǐn)?shù)，我簡(jiǎn)單總結(jié)下B+樹(shù)的結(jié)構(gòu)。

B+樹(shù)查詢過(guò)程

如上圖，一般B+樹(shù)是由多個(gè)頁(yè)組成的多層級(jí)結(jié)構(gòu)，每個(gè)頁(yè)16Kb，對(duì)于主鍵索引來(lái)說(shuō)，最末級(jí)的葉子結(jié)點(diǎn)放行數(shù)據(jù)，非葉子結(jié)點(diǎn)放的則是索引信息(主鍵id和頁(yè)號(hào))，用于加速查詢。

比方說(shuō)我們想要查找行數(shù)據(jù)5。會(huì)先從頂層頁(yè)的record們?nèi)胧?。record里包含了主鍵id和頁(yè)號(hào)(頁(yè)地址)。關(guān)注黃色的箭頭，向左最小id是1，向右最小id是7。那id=5的數(shù)據(jù)如果存在，那必定在左邊箭頭。于是順著的record的頁(yè)地址就到了6號(hào)數(shù)據(jù)頁(yè)里，再判斷id=5>4，所以肯定在右邊的數(shù)據(jù)頁(yè)里，于是加載105號(hào)數(shù)據(jù)頁(yè)。

在105號(hào)數(shù)據(jù)頁(yè)里，雖然有多行數(shù)據(jù)，但也不是挨個(gè)遍歷的，數(shù)據(jù)頁(yè)內(nèi)還有個(gè)頁(yè)目錄的信息，它可以通過(guò)二分查找的方式加速查詢行數(shù)據(jù)，于是找到id=5的數(shù)據(jù)行，完成查詢。

從上面可以看出，B+樹(shù)利用了空間換時(shí)間的方式(構(gòu)造了一批非葉子結(jié)點(diǎn)用于存放索引信息)，將查詢時(shí)間復(fù)雜度從O(n)優(yōu)化為O(lg(n))。

跳表的結(jié)構(gòu)

看完B+樹(shù)，我們?cè)賮?lái)看下跳表是怎么來(lái)的。

同樣的，還是為了存儲(chǔ)一行行的數(shù)據(jù)。

我們可以將它們用鏈表串起來(lái)。

單鏈表

想要查詢鏈表中的其中一個(gè)結(jié)點(diǎn)，時(shí)間復(fù)雜度是O(n)，這誰(shuí)頂?shù)米?，于是將部分鏈表結(jié)點(diǎn)提出來(lái)，再構(gòu)建出一個(gè)新的鏈表。

兩層跳表

這樣當(dāng)我想要查詢一個(gè)數(shù)據(jù)的時(shí)候，我先查上層的鏈表，就很容易知道數(shù)據(jù)落在哪個(gè)范圍，然后跳到下一個(gè)層級(jí)里進(jìn)行查詢。這樣就把搜索范圍一下子縮小了一大半。

比如查詢id=10的數(shù)據(jù)，我們先在上層遍歷，依次判斷1,6,12，很快就可以判斷出10在6到12之間，然后往下一跳，就可以在遍歷6,7,8,9,10之后，確定id=10的位置。直接將查詢范圍從原來(lái)的1到10，變成現(xiàn)在的1,6,7,8,9,10，算是砍半了。

兩層跳表查找id為10的數(shù)據(jù)

既然兩層鏈表就直接將查詢范圍砍半了，那我多加幾層，豈不妙哉?

于是跳表就這樣變成了多層。

三層跳表

如果還是查詢id=10的數(shù)據(jù)，就只需要查詢1,6,9,10就能找到，比兩層的時(shí)候更快一些。

三層跳表查詢id為10的數(shù)據(jù)

可以看出，跳表也是通過(guò)犧牲空間換取時(shí)間的方式提升查詢性能。時(shí)間復(fù)雜度都是lg(n)。

B+樹(shù)和跳表的區(qū)別

從上面可以看到，B+樹(shù)和跳表的最下面一層，都包含了所有的數(shù)據(jù)，且都是順序的，適合用于范圍查詢。往上的層級(jí)都是構(gòu)建出來(lái)用于提升搜索性能的。這兩者實(shí)在是太像了。但他們兩者在新增和刪除數(shù)據(jù)時(shí)，還是有些區(qū)別的。下面我們以新增數(shù)據(jù)為例聊一下。

B+樹(shù)新增數(shù)據(jù)會(huì)怎么樣

B+樹(shù)本質(zhì)上是一種多叉平衡二叉樹(shù)。關(guān)鍵在于"平衡"這兩個(gè)字，對(duì)于多叉樹(shù)結(jié)構(gòu)來(lái)說(shuō)，它的含義是子樹(shù)們的高度層級(jí)盡量一致(一般最多差一個(gè)層級(jí))，這樣在搜索的時(shí)候，不管是到哪個(gè)子樹(shù)分支，搜索次數(shù)都差不了太多。

當(dāng)數(shù)據(jù)庫(kù)表不斷插入新的數(shù)據(jù)時(shí)，為了維持B+樹(shù)的平衡，B+樹(shù)會(huì)不斷分裂調(diào)整數(shù)據(jù)頁(yè)。

我們知道B+樹(shù)分為葉子結(jié)點(diǎn)和非葉子結(jié)點(diǎn)。

當(dāng)插入一條數(shù)據(jù)時(shí)，葉子結(jié)點(diǎn)和它上層的索引結(jié)點(diǎn)(非葉子結(jié)點(diǎn))最大容量都是16k，它們都有可能會(huì)滿。

為了簡(jiǎn)化問(wèn)題，我們假設(shè)一個(gè)數(shù)據(jù)頁(yè)只能放三條行數(shù)據(jù)或索引。

加入一條數(shù)據(jù)，根據(jù)數(shù)據(jù)頁(yè)會(huì)不會(huì)滿，分為三種情況。

• 葉子結(jié)點(diǎn)和索引結(jié)點(diǎn)都沒(méi)滿。這種情況最簡(jiǎn)單，直接插入到葉子結(jié)點(diǎn)中就好了。

葉子和非葉子都未滿

• 葉子結(jié)點(diǎn)滿了，但索引結(jié)點(diǎn)沒(méi)滿。此時(shí)需要拆分葉子結(jié)點(diǎn)，同時(shí)索引結(jié)點(diǎn)要增加新的索引信息。

葉子滿了但非葉子未滿.drawio

葉子結(jié)點(diǎn)滿了，且索引結(jié)點(diǎn)也滿了。葉子和索引結(jié)點(diǎn)都要拆分，同時(shí)往上還要再加一層索引。

葉子和非葉子都滿了

從上面可以看到，只有在葉子和索引結(jié)點(diǎn)都滿了的情況下，B+樹(shù)才會(huì)考慮加入一層新的結(jié)點(diǎn)。

而從之前的文章知道，要把三層B+樹(shù)塞滿，那大概需要2kw左右的數(shù)據(jù)。

跳表新增數(shù)據(jù)

跳表同樣也是很多層，新增一個(gè)數(shù)據(jù)時(shí)，最底層的鏈表需要插入數(shù)據(jù)。

此時(shí)，是否需要在上面的幾層中加入數(shù)據(jù)做索引呢?

這個(gè)就純靠隨機(jī)函數(shù)了。

理論上為了達(dá)到二分的效果，每一層的結(jié)點(diǎn)數(shù)需要是下一層結(jié)點(diǎn)數(shù)的二分之一。

也就是說(shuō)現(xiàn)在有一個(gè)新的數(shù)據(jù)插入了，它有50%的概率需要在第二層加入索引，有25%的概率需要在第三層加個(gè)索引，以此類推，直到最頂層。

舉個(gè)例子，如果跳表中插入數(shù)據(jù)id=6，且隨機(jī)函數(shù)返回第三層(有25%的概率)，那就需要在跳表的最底層到第三層都插入數(shù)據(jù)。

跳表插

入數(shù)據(jù)

如果這個(gè)隨機(jī)函數(shù)設(shè)計(jì)成上面這樣，當(dāng)數(shù)據(jù)量樣本足夠大的時(shí)候，數(shù)據(jù)的分布就符合我們理想中的"二分"。

跟上面B+樹(shù)不一樣，跳表是否新增層數(shù)，純粹靠隨機(jī)函數(shù)，根本不關(guān)心前后上下結(jié)點(diǎn)。

好了，基礎(chǔ)科普也結(jié)束了，我們可以進(jìn)入正題了。

Mysql的索引為什么使用B+樹(shù)而不使用跳表?

B+樹(shù)是多叉樹(shù)結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)都是一個(gè)16k的數(shù)據(jù)頁(yè)，能存放較多索引信息，所以扇出很高。三層左右就可以存儲(chǔ)2kw左右的數(shù)據(jù)(知道結(jié)論就行，想知道原因可以看之前的文章)。也就是說(shuō)查詢一次數(shù)據(jù)，如果這些數(shù)據(jù)頁(yè)都在磁盤(pán)里，那么最多需要查詢?nèi)未疟P(pán)IO。

跳表是鏈表結(jié)構(gòu)，一條數(shù)據(jù)一個(gè)結(jié)點(diǎn)，如果最底層要存放2kw數(shù)據(jù)，且每次查詢都要能達(dá)到二分查找的效果，2kw大概在2的24次方左右，所以，跳表大概高度在24層左右。最壞情況下，這24層數(shù)據(jù)會(huì)分散在不同的數(shù)據(jù)頁(yè)里，也即是查一次數(shù)據(jù)會(huì)經(jīng)歷24次磁盤(pán)IO。

因此存放同樣量級(jí)的數(shù)據(jù)，B+樹(shù)的高度比跳表的要少，如果放在mysql數(shù)據(jù)庫(kù)上來(lái)說(shuō)，就是磁盤(pán)IO次數(shù)更少，因此B+樹(shù)查詢更快。

而針對(duì)寫(xiě)操作，B+樹(shù)需要拆分合并索引數(shù)據(jù)頁(yè)，跳表則獨(dú)立插入，并根據(jù)隨機(jī)函數(shù)確定層數(shù)，沒(méi)有旋轉(zhuǎn)和維持平衡的開(kāi)銷，因此跳表的寫(xiě)入性能會(huì)比B+樹(shù)要好。

其實(shí)，mysql的存儲(chǔ)引擎是可以換的，以前是myisam，后來(lái)才有的innodb，它們底層索引用的都是B+樹(shù)。也就是說(shuō)，你完全可以造一個(gè)索引為跳表的存儲(chǔ)引擎裝到mysql里。事實(shí)上，facebook造了個(gè)rocksDB的存儲(chǔ)引擎，里面就用了跳表。直接說(shuō)結(jié)論，它的寫(xiě)入性能確實(shí)是比innodb要好，但讀性能確實(shí)比innodb要差不少。感興趣的話，可以在文章最后面的參考資料里看到他們的性能對(duì)比數(shù)據(jù)。

redis為什么使用跳表而不使用B+樹(shù)或二叉樹(shù)呢?

redis支持多種數(shù)據(jù)結(jié)構(gòu)，里面有個(gè)有序集合，也叫ZSET。內(nèi)部實(shí)現(xiàn)就是跳表。那為什么要用跳表而不用B+樹(shù)等結(jié)構(gòu)呢?

這個(gè)幾乎每次面試都要被問(wèn)一下。

雖然已經(jīng)很熟了，但每次都要裝作之前沒(méi)想過(guò)，現(xiàn)場(chǎng)思考一下才知道答案。

真的，很考驗(yàn)演技。

大家知道，redis 是純純的內(nèi)存數(shù)據(jù)庫(kù)。

進(jìn)行讀寫(xiě)數(shù)據(jù)都是操作內(nèi)存，跟磁盤(pán)沒(méi)啥關(guān)系，因此也不存在磁盤(pán)IO了，所以層高就不再是跳表的劣勢(shì)了。

并且前面也提到B+樹(shù)是有一系列合并拆分操作的，換成紅黑樹(shù)或者其他AVL樹(shù)的話也是各種旋轉(zhuǎn)，目的也是為了保持樹(shù)的平衡。

而跳表插入數(shù)據(jù)時(shí)，只需要隨機(jī)一下，就知道自己要不要往上加索引，根本不用考慮前后結(jié)點(diǎn)的感受，也就少了旋轉(zhuǎn)平衡的開(kāi)銷。

因此，redis選了跳表，而不是B+樹(shù)。

總結(jié)

• B+樹(shù)是多叉平衡搜索樹(shù)，扇出高，只需要3層左右就能存放2kw左右的數(shù)據(jù)，同樣情況下跳表則需要24層左右，假設(shè)層高對(duì)應(yīng)磁盤(pán)IO，那么B+樹(shù)的讀性能會(huì)比跳表要好，因此mysql選了B+樹(shù)做索引。
• redis的讀寫(xiě)全在內(nèi)存里進(jìn)行操作，不涉及磁盤(pán)IO，同時(shí)跳表實(shí)現(xiàn)簡(jiǎn)單，相比B+樹(shù)、AVL樹(shù)、少了旋轉(zhuǎn)樹(shù)結(jié)構(gòu)的開(kāi)銷，因此redis使用跳表來(lái)實(shí)現(xiàn)ZSET，而不是樹(shù)結(jié)構(gòu)。
• 存儲(chǔ)引擎RocksDB內(nèi)部使用了跳表，對(duì)比使用B+樹(shù)的innodb，雖然寫(xiě)性能更好，但讀性能屬實(shí)差了些。在讀多寫(xiě)少的場(chǎng)景下，B+樹(shù)依舊YYDS。

參考資料

• 《MYSQL內(nèi)核：INNODB存儲(chǔ)引擎 卷1》。
• 《RocksDB和Innodb引擎性能PK勝負(fù)難料?》。
• https://cloud.tencent.com/developer/article/1813695。