1. 論文背景

PostgreSQL資料庫的nbtree索引參考了2篇論文：

《Efficient Locking for Concurrent Operations on B-Trees》：高并發讀寫的原理；
《A SYMMETRIC CONCURRENT B-TREE ALGORITHM》：高并發删除的原理；

B+Tree基礎

PostgreSQL B+Tree論文解讀1 - 《Efficient Locking for Concurrent Operations on B-Trees》1. 論文背景2. 概述3. Btree并發操作的算法演進4. LY算法的存儲模型和資料結構6.正确性論證8. DELETION9. LOCKING EFFICIENCY10. 結束

是一種平衡多路搜尋樹，最大化中間節點數目以減少樹的高度，平衡操作不經常發生，減少随機通路，适用于節點間通路時間（從一個page跳到另一個page）遠遠大于節點内部（解析和二分搜尋page内部）的場景，用來組織外部媒體上的索引布局。

樹的高度更少，它的中間節點不存儲關鍵字對應的記錄，隻存儲索引關鍵字，使得每個中間節點能夠最大量的儲存關鍵字；
搜尋時間恒定，葉子節點儲存了所有父節點關鍵字的記錄，每次都要到葉子節點搜尋；
自帶排序，葉子節點之間是有序的，可以支援範圍搜尋，緩存命中率更高；
全表周遊，隻需要周遊全部的葉子節點；

上面介紹的隻是B+Tree的靜态結構，在并發的搜尋，插入，删除時如何盡量少的上鎖，提高整體的并發度就是本篇論文的核心點。

2. 概述

本片論文首次提出了在标準的Btree資料結構基礎上，增加兩個機制來優化并發讀寫的性能。

1. right link；
2. high key；

論文假設所有的buffer都是私有的，可以做到：

讀操作無需上鎖；
更新隻需要上常量數目的鎖；

也稱為B-link-Tree（PostgreSQL的buffer是全局的，讀需要上讀鎖。如果産生了頁面分裂需要對新頁面及其右鄰居上鎖）

3. Btree并發操作的算法演進

在B-link-Tree之前對Btree的并發操作的方法是基于lock-coupling和lock-subtree的算法。就是通過對多個父子節點上鎖或者子樹上鎖，使得search/insert/delete互相隔離，如果串行執行一般。

lock-coupling(讀寫隔離)

從父節點到子節點descengding操作需要：先對子節點上鎖，再釋放目前父節點的鎖。

這裡，需要同時對父子節點上鎖，否則其他writer就可能有機會同時得到這兩個鎖并完成分裂過程。

一個執行時序：

write1開始執行search(d)搜尋；
writer1對父節點進行的搜尋，發現需要進入‘abd’的子節點進行搜尋；
writer1釋放d的鎖；
writer2執行insert(c)操作；
writer2上鎖'd'節點成功；
writer2上鎖‘abd'節點成功；
writer2對’abd‘進行了分裂，産生了’ab','cd'兩個節點；
writer1再去原來'abd'頁面上搜尋'd'時就找不到了；

lock-subtree(寫寫隔離)

writer操作需要對subtree上鎖，理論上鎖的最小粒度是在他們的公共祖先地方上鎖，達到寫寫互斥。分裂的過程是自底向上進行的，writer1對一個節點n上鎖并且更新了，此時writer2可能已經在這個子樹下面它最終也要修改n，如果不在subtree地方上鎖，當一個writer1修改了n，另外一個自底向上後發現n已經變化了，導緻插入的地方不對。

lock-subtree本身是比較難以實作的，一個最直覺的做法是對root節點上鎖，但是這樣就徹底阻止其他的操作了，尤其是并發的lock-coupling，更加劇了沖突。

optimitic descending(樂觀更新)

writer過程中對中間節點上讀鎖，對真正要更新的葉子節點上寫鎖，如果最終沒有發生分裂或者合并，則更新成功，否則需要從root開始執行lock-subtree算法。

update during decending(自上向下更新)

避免了lock-subtree，在更新操作的descending過程中，同時對節點重構。過程中仍然需要lock-coupling。

Lehman and Yao 提出的B-link-tree算法

LY算法的思想是不通過鎖來互斥btree的操作（lock-coupling和lock-subtree），而是允許btree操作并發的進行，通過其他手段來恢複出btree的結構。

B-link-tree

這是LY的原創發明，B+tree每個節點都額外增加一個‘rightlink’指向它的右鄰居節點。允許btree的操作并發執行，後續再根據rightlink來複原出完整的btree。

比如，分裂操作分成2個階段：

水準操作：将原節點n分成n和n'，将key也分成兩撥，同時節點n指向節點n'；
垂直操作：将新的節點n'插入父節點中；

PostgreSQL B+Tree論文解讀1 - 《Efficient Locking for Concurrent Operations on B-Trees》1. 論文背景2. 概述3. Btree并發操作的算法演進4. LY算法的存儲模型和資料結構6.正确性論證8. DELETION9. LOCKING EFFICIENCY10. 結束

在1和2之間允許其他程序從父節點進行搜尋，進入節點n，如果：

目标key在節點n中，則搜尋n後傳回；
目标key在n'中，通過節點n跳到n'中搜尋；

lock-coupling不需要了，因為通過父節點descend到子節點的過程中，如果有對子節點進行的分裂沒有即使在插入父節點，導緻錯誤的進入了左子節點，此時隻需要通過rightlink往右搜尋就能找到正确的子節點；

lock-subtree不需要了，因為在ascend到父節點中進行插入新的n'時，此時如果父節點也發生了分裂，導緻進入了錯誤的父節點，那麼隻需要通過rightlink往右搜尋就能找到正确的父節點；

B-link樹允許插入和搜尋隻對一個page上（這裡有個假設，所有的page直接從磁盤上讀取到自己程序的local buffer中。PostgreSQL中B-link樹的page讀取到shared buffer中被所有程序共享，是以它需要鎖住更多的頁面。這是由具體的工程實作導緻的，并非算法本身的要求）。

4. LY算法的存儲模型和資料結構

database存儲在磁盤上，多個程序并發的行為是：

1. 讀取存儲媒體上的page到local buffer中；

2. 程序查找，修改；

3. 寫入磁盤上；

page的讀寫是原子的。允許程序對磁盤的page上鎖（可以在共享記憶體中實作一個page descriptor結構）。

符号

小寫字母：标記記憶體中的變量，比如x, t；

大寫字母：記憶體中的page，比如A, B, C；

lock(x)：對x指向的page上鎖；

unlock(x)：對x指向的page釋放鎖；

A <- get(x)：讀取x執行的page到記憶體A中；

put(A, x)：将記憶體中A的内容寫入到x指向的page；

典型的修改page x的過程：
lock(x);
A <- get(x);
modify A;
put(A, x);
unlock(x);

資料結構

highkey

每個節點額外增加一個highkey，代表該節點所有子樹的upper bond。

原來2k個key不能表達upper bond嗎？從上面的結構能夠看出來，預設2k個key對應2k+1個子樹，最右側的子樹它的upper bond并沒有記錄。

插入操作

如果葉子節點的key entry少于2k個，直接插入；
如果葉子節點已經有2k個key，那麼需要把原來的節點拆成2個，key集合也要分成2個，然後再把新的key插入到左或右節點中。

1. 左節點的highkey需要重新選出一個大概在1/2的位置；
2. 新節點的highkey就是原來節點的highkey；

對中間節點的插入過程類似，唯一不一樣的是中間節點的指向的是其他索引節點而不是記錄；

下圖：插入'47'後，導緻分裂。并且在父節點中插入了'51', '51'正好是左節點的highkey。

一個簡單的并發場景

在lock-coupling中提到的一個時序：

程序1執行搜尋15，在把x讀取到了記憶體中，得到y的指針，暫停執行；
程序2執行插入9，讀取x，得到指針y，讀取y，并分裂出了y'，并把y'指針插入到了父節點x中；
程序1恢複執行，在讀取y，找不到15；

出錯的本質原因是：程序1通過x得到了指針y，然後讀取y，在這連個操作之間程序2修改了y；

5. LY算法并發操作原理

rightlink

rightlink的本質是提供一個除了左右指針之外的通路節點的途徑。

被split出來的兩個node通過rightlink連接配接，在父節點加入對新節點的索引前，他們如同一個node一樣。

加入了rightlink後，對于任意節點（除最左側和root節點之外）都有2個指針指向它：一個是父節點，一個是左鄰居節點。當一個新節點插入時，這兩個指針中要有一個原子的指向它（減小上鎖），最合适的指針當然是左鄰居節點在分裂的時候順便指向它（本來左鄰居節點就是要更新它自己的内容）。

這樣，新節點沒有父節點，隻有一個左鄰居節點指向它，此時的btree仍然是合法的搜尋樹，因為新節點裡的鍵值能夠通過左邊節點找到它。另外，新節點應盡快的的在父節點中插入，以提高查詢效率，否則通過左節點繞一圈需要多讀取一次page。

如何識别出目前節點在搜尋的過程中産生了分裂了呢，當然可以每次在搜尋目前節點失敗時，盡量的嘗試在'right link'節點中搜尋一次，這樣需要多讀取n次page，而且分裂對于搜尋來說并非是常态。

如果從父節點descend到子節點A的搜尋key > A的highkey，則一定發生了分裂。

當程序1搜尋父節點時，節點A發生了分裂，新分裂出來的節點B還沒來得及插入到父節點中，程序1根據錯誤的'downlink‘（分裂之前節點A在父節點的highkey）進入到了老的A節點，而A節點的highkey在分裂時發生發生了變化，從downlink追随過來的highkey比節點A上看到的highkey要大，說明從父節點descend到子節點過程中一定發生了分裂。

search

該算法僅僅是一個并發search的說明，沒有顯示的上鎖，是因為每次都從盤上讀取page到自己私有的buffer中。而一個資料庫中為了減少讀取的次數，讀取page到共享buffer中，是以需要對共享的buffer上一次讀鎖，僅此而已，無需對父節點上鎖；

procedure search(u)
current <- root;
A <- get(current);
while current is not a leaf do
begin
    current <- scannode(u, A);
    A <- get(current) 
end;
while t <- scannode(u, A) = link ptr of A do
begin
    current <- t ;
    A <- get(current);
end;
if v is in A then done “success” else done “failure”

insert

首先通過search(u)找到待插入的葉子節點，然後對這個節點上鎖。在search的過程中需要記錄從root到葉子節點的backtrack路徑，因為插入葉子節點會導緻分裂，需要在父節點插入新的highkey，繼而又可能會導緻父節點也發生了分裂，直到遇到了一個無需分裂的祖先節點，是以需要記錄這條路徑。

注意，在通過backtrack自底向上插入時，某個祖先節點也可能發生了分裂，導緻backtrack中記錄的節點已經不是原來的那個節點了，祖先節點是否發生分裂也可以通過比較highkey判斷，如果發生了分裂，則一直往右邊查找，直到找到了待插入的祖先節點。

如圖：

找到待分裂的節點a；
新配置設定一個節點b'，b'指向原來a的rightlink；
更新a的内容為a'（鍵值的個數接近原來的1/2，pg是按照長度來劃分)，并且a'指向b'；
更新父節點f'指向b‘；

procedure insert(u)
initialize stack;
current <- root;
A <- get(current);
while current is not a leaf do 
begin
    t <- current;
    current <- scannode( v, A);
    if new current was not link pointer in A then
        push(t);
    A <- get(current);
end;
lock(current); //找到了待插入的葉子節點
A <- get(current);
move.right;
if v is in A then stop “v already exists in tree”;
w <- pointer to pages allocated for record associated with v;
Doinsertion:
if A is safe then //無需分裂
begin
    A <- node.insert(A, w, v);
    put(A, current);
    unLock(current);
end else begin
    u<- allocate(1 new page for B);
    A, B <- rearrange old A, adding v and w, to make 2 nodes,
        where (link ptr of A, link ptr of B) <- (u, link ptr of old A);
    y <- highkey stored in new A; //節點A的highkey
    put(B, u); //先把新節點B寫入磁盤
    put(A, current); // 第二步更新current節點
    oldnode <- current; // 開始插入父節點
    v <- y;
    w <- u;
    current <- pop(stack); // 從棧中取出父節點
    lock(current);
    A <- get(current);
    move.right; // 嘗試向右移動找到正确的父節點
    unlock(oldnode); // 更新父節點前解鎖子節點
    goto Doinsertion
end

在發生分裂時，邏輯上是向右側分裂。過程中新的page在左邊，原來的page在右側，這是為了插入父節點時，僅需插入<左側節點的highkey, 左側節點指針>，無需操作右側節點，因為它在父節點中本來的kv就是對的。

當發生分裂時，最多對3個節點上鎖：

目前節點；
父節點；
父節點的右鄰居節點；

上鎖的必要性：

為什麼在move.right時，需要對2個相鄰節點上鎖？從一個節點跳轉到右邊節點間隙不發生并發的分裂（如果分裂，那麼通過左邊節點得到右節點的指針就變成了并發目前的右節點，因為中間插入了新的節點）；
為什麼在找到正确的父節點前，需要對子節點上鎖呢？同時，在從子節點進入父節點間隙中，其他程序可能對子節點再次進行了分裂，它的highkey就會發生變化；

6.正确性論證

沒有deadlock

上鎖的順序：

同一個層次，從左向右；
跨層次，自底向上；

證明：隻需要證明在這個樹中所有節點間都有"<"的關系(全序關系)：

不在同一個層上的兩個節點a和b，"a < b"當且僅當level(a) < level(b)；
在同一個層上的兩個節點a和b，"a < b"當且僅當a在b的左邊；

歸納法，假設t0時刻滿足"a > b"，那麼任意t > t0時刻始終滿足 "a > b"。

由于分裂是向右側進行，并且從節點x分裂出來x'和x''是緊跟在原來節點的後面，是以：

對于所有y，y < x，滿足 y < x';
對于所有y，x < y，滿足 x'' < y;
分裂之前小于x的還是小于，大于x的還是大于，是以節點之間仍然符合全序關系。

另外，插入過程中上鎖順序遵循全序關系：對節點A上鎖了，就不會對它的子節點上鎖，隻會對父節點上鎖；鄰居節點的上鎖也隻對右節點上鎖。

分裂的性質和插入時上鎖的順序，保證了：

程序P1在t0時刻對(a,b)上鎖；
t1時刻，其他程序上鎖的順序也是(a,b)，而不是(b,a)；

是以，不會産生死鎖。

insert的正确性

為了保證tree的結構在任何時刻都是一緻的，對所有可能修改樹的操作進行論證。實際上插入操作無論是否分裂，最終都是通過"put"寫入磁盤，插入操作有3個地方調用了put:

"put(A, current)"，對沒有分裂的節點，直接寫入磁盤；
"put(B, u)"，對于分類的節點，将新産生的節點寫入磁盤；
"put(A, current)"，對于分類的節點，對左邊的節點寫入磁盤，實際上覆寫寫，同時原子的修改了rightlink指向了步驟2中新産生的節點；

注意通過加鎖，執行完步驟2立即執行步驟3，對于breee來說，這兩次寫可以規約到一次原子寫。

LEMMA: 兩次寫磁盤操作"put(B, u), put(A, current)"，等價于對btree的一次修改。

證明過程也很顯而易見，

先配置設定新的節點B，同時B指向原來A的右節點；
更新節點A内容時，同時指向了新的節點B，這是一個原子操作，既成功的修改了A，又把B引入了btree中；

是以，可以證明：

ThEOREM：作用在btree上的所有操作時刻維護btree的一緻性

根據LEMMA的論證，分裂時的2次寫磁盤對于btree來說等價于一次，同時，修改btree時上了一次鎖，是以分裂不會破壞btree的一緻性。

insert時并發search的正确性

Type1 中間節點沒有分裂

程序1在底層發生了分裂，在父節點插入新節點的kv，該父節點沒有分離；
程序2在程序1插入父節點前讀取到了這個中間節點，它看不到新增的子節點，會找到左子節點，可以通過左子節點的rightlink找到新增的節點；

Type2 葉子節點發生分裂

程序1在底層發生了分裂，在父節點插入新節點的kv，該父節點也發生了分裂；
程序2在程序1分裂父節點前讀取到了這個中間節點，它可能在這個節點上搜尋不到，需要往右移動到叔父節點，最終通過叔父節點找到了原來的左節點（成功的對叔父節點上鎖，說明上一輪分裂已經完成），進入到下一層節點，該節點可能再次發生了分裂，是以仍然需要往右移動；

Type3 backtrack

當子節點發生了split，而需要在父節點插入時，從stack中取出父節點，進行backtrack，此時該父節點可能已經發生了多次split，通過right pointer依次向右查找到真正需要插入的叔父節點；

在父節點分裂的同時，子節點分裂出來的靠右節點的key，也在父節點這一層逐漸的往右移動；

而對父節點的插入是左子節點的high value，該值在父節點一系列的右指針中是可達的；

Type4 鎖等待

程序P在search到要修改的節點後，進行lock時，會等待，因為程序I正在持有鎖，并進行修改該node；等到程序I釋放鎖後，程序P得到鎖，此時的node已經不是需要修改的node了（被程序I改過後進行了split），此時程序P需要move.right，找到需要修改的節點；

每一次獲得鎖之後的第一件事情就是move.right；

7. 活鎖

某個插入程序P執行的比較慢，而其他程序執行的快，一直有右指針誕生，P一直在向右查找；

可以通過程序優先級解決cpu快慢問題；

8. DELETION

删除隻發生在葉子節點上，删除過程也需要上鎖，允許葉子節點的key個數少于k個。這對于insert遠比delete大的場景是可以接收的。

如果delete操作也很頻繁，可以通過鎖住整個樹，然後進行批量的delete操作。

9. LOCKING EFFICIENCY

LY算法中的鎖：插入時至少一個鎖，如果發生了分裂則3個鎖。

3個鎖分别是：

目前被分裂的節點；
在上一層中查找正确的父節點時，對父節點上鎖；
對父節點右鄰居上鎖；

10. 結束

LY算法從理論上設計了一個高并發的B-link-tree結構，最多隻需要3個鎖。

然而在實踐中，僅有該算法還遠遠不夠。比如在PostgreSQL中還需要考慮：

key可能是不唯一的；
key的長度是變長的；
page在共享記憶體中，可以被多個程序看到，是以search的時候也需要上讀鎖；
需要支援雙向周遊（從右往左），是以需要維護rightlink和leftlink，由此會引入更複雜的鎖管理；
root的分裂；

PostgreSQL B+Tree論文解讀1 - 《Efficient Locking for Concurrent Operations on B-Trees》1. 論文背景2. 概述3. Btree并發操作的算法演進4. LY算法的存儲模型和資料結構6.正确性論證8. DELETION9. LOCKING EFFICIENCY10. 結束