別B+樹(shù)了，out了
本文轉(zhuǎn)載自微信公眾號(hào)「 yes的練級(jí)攻略」，作者 是Yes呀。轉(zhuǎn)載本文請(qǐng)聯(lián)系 yes的練級(jí)攻略公眾號(hào)。
你好，我是yes。
最近了解了下 PolarDB MySQL，后續(xù)有機(jī)會(huì)分享下學(xué)習(xí)心得。
今天這篇先聊聊其內(nèi)部引入 Blink Tree 來(lái)替換 B+Tree 的事情。
想必大伙都非常熟悉 B+Tree，面試?？?，但是 Blink Tree 確實(shí)很少有人提到，它是 B+Tree 的升級(jí)版，據(jù)阿里云文檔所述，通過(guò)對(duì) B+Tree 的優(yōu)化，可以將交易場(chǎng)景下 PolarDB 的讀寫(xiě)性能提升20%。
B+Tree 的問(wèn)題
那么 B+Tree 哪塊表現(xiàn)的不好呢？
主要是并發(fā)場(chǎng)景下，寫(xiě)操作導(dǎo)致節(jié)點(diǎn)分裂（SMO，Split Merge Operation）的時(shí)候，剛好有并發(fā)讀操作訪問(wèn)到錯(cuò)誤的葉子節(jié)點(diǎn)，查錯(cuò)了節(jié)點(diǎn)，那么目標(biāo)值肯定就搜索不到了，于是導(dǎo)致了錯(cuò)誤查詢。
舉個(gè)例子，比如現(xiàn)有如下的一個(gè) B+Tree：
圖片
此時(shí)，插入一個(gè)數(shù)據(jù) 27，恰好頁(yè)A滿了，需要觸發(fā)分裂，新增一個(gè)頁(yè)B，且同時(shí)有個(gè)讀取請(qǐng)求，想要訪問(wèn)數(shù)據(jù) 29。
圖片
那么很有可能在分裂的時(shí)候，讀請(qǐng)求訪問(wèn)到老的頁(yè)面指針，指向了頁(yè) A，而頁(yè) A 內(nèi)的 29 已經(jīng)被分裂到新的頁(yè) B 中，這樣一來(lái)讀請(qǐng)求就發(fā)現(xiàn)沒(méi)有 29 ，于是返回沒(méi)數(shù)據(jù)，這就錯(cuò)亂了。
而且，葉子節(jié)點(diǎn)的分裂，可能會(huì)導(dǎo)致父節(jié)點(diǎn)的分裂，這種調(diào)整最長(zhǎng)可能級(jí)聯(lián)到根節(jié)點(diǎn)，并發(fā)場(chǎng)景下很容易導(dǎo)致錯(cuò)誤，為了避免這種情況的發(fā)生，最簡(jiǎn)單的操作就是在發(fā)生節(jié)點(diǎn)分裂時(shí)，把整顆 B+Tree 都鎖了。
這樣一來(lái)數(shù)據(jù)的正確性得到了保證，但是性能就很低了，因?yàn)槿宙i會(huì)影響了對(duì)所有頁(yè)的訪問(wèn)。
后續(xù) MySQL 對(duì)其在 5.7 版本后做了優(yōu)化，但是整個(gè) B+Tree 同時(shí)只能支持一個(gè) SMO 操作的發(fā)生，高并發(fā)時(shí)大數(shù)據(jù)量插入導(dǎo)致多 SMO 的發(fā)生還是會(huì)被阻塞，影響性能。
Blink Tree
Blink Tree 主要引入了 high key 和 link 指針來(lái)解決并發(fā)讀寫(xiě)中間態(tài)數(shù)據(jù)訪問(wèn)出錯(cuò)問(wèn)題，能降低鎖的粒度，提高性能。
high key 存儲(chǔ)了每個(gè)節(jié)點(diǎn)的最大值，每個(gè)節(jié)點(diǎn)的 link 指針則指向了同層右側(cè)的兄弟節(jié)點(diǎn)，在寫(xiě)入數(shù)據(jù)的時(shí)候，僅需對(duì)當(dāng)前節(jié)點(diǎn)加鎖，當(dāng)前節(jié)點(diǎn)修改完畢后立馬解鎖，鎖的粒度很細(xì)，并發(fā)度很高。
那具體是如何解決并發(fā)時(shí)候 SMO 中間態(tài)問(wèn)題的呢？
我們直接來(lái)看來(lái)阿里云官網(wǎng)給的一個(gè)示意圖：
圖片
可以看到，相比于 B+Tree，Blink Tree的兄弟節(jié)點(diǎn)也進(jìn)行了指針相連，當(dāng)分裂在進(jìn)行中還未完成，也就是父節(jié)點(diǎn)到新的子節(jié)點(diǎn)的鏈接還沒(méi)有建立時(shí)，B+Tree 我們已經(jīng)演示過(guò)了，并發(fā)讀可能導(dǎo)致數(shù)據(jù)查詢不到。
而 Blink Tree 就能解決這個(gè)問(wèn)題，當(dāng)讀請(qǐng)求沿著老指針訪問(wèn)老頁(yè)面的時(shí)候，對(duì)比下 high key，發(fā)現(xiàn)查詢的值比當(dāng)前頁(yè) high key 大，那么就沿著 link 指針找到旁邊新分配的頁(yè)面，此時(shí)就可以找到要查詢的值了。
最后
這篇就簡(jiǎn)單介紹到這，對(duì)我們正常業(yè)務(wù)開(kāi)發(fā)同學(xué)來(lái)說(shuō) Blink Tree 的理解到這也就差不多了，有興趣的可以再看看 Blink Tree 的論文
還有這篇文章
