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