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