在我們的印象中,mysql數(shù)據(jù)表里無(wú)非就是存儲(chǔ)一行行的數(shù)據(jù)。跟個(gè)excel似的。
直接遍歷這一行行數(shù)據(jù),性能就是O(n),比較慢。為了加速查詢,使用了B+樹來(lái)做索引,將查詢性能優(yōu)化到了O(lg(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+樹的結(jié)構(gòu)
在這里,為了混點(diǎn)字?jǐn)?shù),我簡(jiǎn)單總結(jié)下B+樹的結(jié)構(gòu)。
B+樹查詢過程
如上圖,一般B+樹是由多個(gè)頁(yè)組成的多層級(jí)結(jié)構(gòu),每個(gè)頁(yè)16Kb
,對(duì)于主鍵索引來(lái)說,最末級(jí)的葉子結(jié)點(diǎn)放行數(shù)據(jù),非葉子結(jié)點(diǎn)放的則是索引信息(主鍵id和頁(yè)號(hào)),用于加速查詢。
比方說我們想要查找行數(shù)據(jù)5。會(huì)先從頂層頁(yè)的record們?nèi)胧帧?strong style="font-size:inherit;line-height:inherit;color:rgb(41,98,255);">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è)目錄的信息,它可以通過二分查找的方式加速查詢行數(shù)據(jù),于是找到id=5的數(shù)據(jù)行,完成查詢。
從上面可以看出,B+樹利用了空間換時(shí)間的方式(構(gòu)造了一批非葉子結(jié)點(diǎn)用于存放索引信息),將查詢時(shí)間復(fù)雜度從O(n)優(yōu)化為O(lg(n))。
跳表的結(jié)構(gòu)
看完B+樹,我們?cè)賮?lái)看下跳表是怎么來(lái)的。
同樣的,還是為了存儲(chǔ)一行行的數(shù)據(jù)。
我們可以將它們用鏈表串起來(lái)。
單鏈表想要查詢鏈表中的其中一個(gè)結(jié)點(diǎn),時(shí)間復(fù)雜度是O(n),這誰(shuí)頂?shù)米?,于是?strong style="font-size:inherit;line-height:inherit;color:rgb(41,98,255);">部分鏈表結(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ù)可以看出,跳表也是通過犧牲空間換取時(shí)間的方式提升查詢性能。時(shí)間復(fù)雜度都是lg(n)。
B+樹和跳表的區(qū)別
從上面可以看到,B+樹和跳表的最下面一層,都包含了所有的數(shù)據(jù),且都是順序的,適合用于范圍查詢。往上的層級(jí)都是構(gòu)建出來(lái)用于提升搜索性能的。這兩者實(shí)在是太像了。但他們兩者在新增和刪除數(shù)據(jù)時(shí),還是有些區(qū)別的。下面我們以新增數(shù)據(jù)為例聊一下。
B+樹新增數(shù)據(jù)會(huì)怎么樣
B+樹本質(zhì)上是一種多叉平衡二叉樹。關(guān)鍵在于"平衡"這兩個(gè)字,對(duì)于多叉樹結(jié)構(gòu)來(lái)說,它的含義是子樹們的高度層級(jí)盡量一致(一般最多差一個(gè)層級(jí)),這樣在搜索的時(shí)候,不管是到哪個(gè)子樹分支,搜索次數(shù)都差不了太多。
當(dāng)數(shù)據(jù)庫(kù)表不斷插入新的數(shù)據(jù)時(shí),為了維持B+樹的平衡,B+樹會(huì)不斷分裂調(diào)整數(shù)據(jù)頁(yè)。
我們知道B+樹分為葉子結(jié)點(diǎn)和非葉子結(jié)點(diǎn)。
當(dāng)插入一條數(shù)據(jù)時(shí),葉子結(jié)點(diǎn)和它上層的索引結(jié)點(diǎn)(非葉子結(jié)點(diǎn))最大容量都是16k,它們都有可能會(huì)滿。
為了簡(jiǎn)化問題,我們假設(shè)一個(gè)數(shù)據(jù)頁(yè)只能放三條行數(shù)據(jù)或索引。
加入一條數(shù)據(jù),根據(jù)數(shù)據(jù)頁(yè)會(huì)不會(huì)滿,分為三種情況。
-
葉子結(jié)點(diǎn)和索引結(jié)點(diǎn)都沒滿。這種情況最簡(jiǎn)單,直接插入到葉子結(jié)點(diǎn)中就好了。
-
葉子結(jié)點(diǎn)滿了,但索引結(jié)點(diǎn)沒滿。此時(shí)需要拆分葉子結(jié)點(diǎn),同時(shí)索引結(jié)點(diǎn)要增加新的索引信息。
-
葉子結(jié)點(diǎn)滿了,且索引結(jié)點(diǎn)也滿了。葉子和索引結(jié)點(diǎn)都要拆分,同時(shí)往上還要再加一層索引。
從上面可以看到,只有在葉子和索引結(jié)點(diǎn)都滿了的情況下,B+樹才會(huì)考慮加入一層新的結(jié)點(diǎn)。
要把三層B+樹塞滿,那大概需要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ù)的二分之一。
也就是說現(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ù),純粹靠隨機(jī)函數(shù),根本不關(guān)心前后上下結(jié)點(diǎn)。
好了,基礎(chǔ)科普也結(jié)束了,我們可以進(jìn)入正題了。
Mysql的索引為什么使用B+樹而不使用跳表?
B+樹是多叉樹結(jié)構(gòu),每個(gè)結(jié)點(diǎn)都是一個(gè)16k的數(shù)據(jù)頁(yè),能存放較多索引信息,所以扇出很高。三層左右就可以存儲(chǔ)2kw
左右的數(shù)據(jù)(知道結(jié)論就行,想知道原因可以看之前的文章)。也就是說查詢一次數(shù)據(jù),如果這些數(shù)據(jù)頁(yè)都在磁盤里,那么最多需要查詢三次磁盤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次磁盤IO。
因此存放同樣量級(jí)的數(shù)據(jù),B+樹的高度比跳表的要少,如果放在mysql數(shù)據(jù)庫(kù)上來(lái)說,就是磁盤IO次數(shù)更少,因此B+樹查詢更快。
而針對(duì)寫操作,B+樹需要拆分合并索引數(shù)據(jù)頁(yè),跳表則獨(dú)立插入,并根據(jù)隨機(jī)函數(shù)確定層數(shù),沒有旋轉(zhuǎn)和維持平衡的開銷,因此跳表的寫入性能會(huì)比B+樹要好。
其實(shí),mysql的存儲(chǔ)引擎是可以換的,以前是myisam
,后來(lái)才有的innodb
,它們底層索引用的都是B+樹。也就是說,你完全可以造一個(gè)索引為跳表的存儲(chǔ)引擎裝到mysql里。事實(shí)上,facebook
造了個(gè)rocksDB
的存儲(chǔ)引擎,里面就用了跳表。直接說結(jié)論,它的寫入性能確實(shí)是比innodb要好,但讀性能確實(shí)比innodb要差不少。
redis為什么使用跳表而不使用B+樹或二叉樹呢?
redis支持多種數(shù)據(jù)結(jié)構(gòu),里面有個(gè)有序集合,也叫ZSET。內(nèi)部實(shí)現(xiàn)就是跳表。那為什么要用跳表而不用B+樹等結(jié)構(gòu)呢?
這個(gè)幾乎每次面試都要被問一下。
雖然已經(jīng)很熟了,但每次都要裝作之前沒想過,現(xiàn)場(chǎng)思考一下才知道答案。
真的,很考驗(yàn)演技。
大家知道,redis 是純純的內(nèi)存數(shù)據(jù)庫(kù)。
進(jìn)行讀寫數(shù)據(jù)都是操作內(nèi)存,跟磁盤沒啥關(guān)系,因此也不存在磁盤IO了,所以層高就不再是跳表的劣勢(shì)了。
并且前面也提到B+樹是有一系列合并拆分操作的,換成紅黑樹或者其他AVL樹的話也是各種旋轉(zhuǎn),目的也是為了保持樹的平衡。
而跳表插入數(shù)據(jù)時(shí),只需要隨機(jī)一下,就知道自己要不要往上加索引,根本不用考慮前后結(jié)點(diǎn)的感受,也就少了旋轉(zhuǎn)平衡的開銷。
因此,redis選了跳表,而不是B+樹。
總結(jié)
-
B+樹是多叉平衡搜索樹,扇出高,只需要3層左右就能存放2kw左右的數(shù)據(jù),同樣情況下跳表則需要24層左右,假設(shè)層高對(duì)應(yīng)磁盤IO,那么B+樹的讀性能會(huì)比跳表要好,因此mysql選了B+樹做索引。
-
redis的讀寫全在內(nèi)存里進(jìn)行操作,不涉及磁盤IO,同時(shí)跳表實(shí)現(xiàn)簡(jiǎn)單,相比B+樹、AVL樹、少了旋轉(zhuǎn)樹結(jié)構(gòu)的開銷,因此redis使用跳表來(lái)實(shí)現(xiàn)ZSET,而不是樹結(jié)構(gòu)。
-
存儲(chǔ)引擎RocksDB內(nèi)部使用了跳表,對(duì)比使用B+樹的innodb,雖然寫性能更好,但讀性能屬實(shí)差了些。在讀多寫少的場(chǎng)景下,B+樹依舊YYDS。
-
數(shù)據(jù)
+關(guān)注
關(guān)注
8文章
6715瀏覽量
88311 -
MySQL
+關(guān)注
關(guān)注
1文章
789瀏覽量
26283 -
索引
+關(guān)注
關(guān)注
0文章
59瀏覽量
10446
原文標(biāo)題:Mysql索引為什么使用B+樹?
文章出處:【微信號(hào):良許Linux,微信公眾號(hào):良許Linux】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
評(píng)論