私はあなたの論文 ARIES/KVL[1] を学んでいます。論文から、B+tree 構造は次のようになります。
------------------------------------ | p0 | k0 | p1 | k1 | p2 | ------------------------------------ / \ / \ / \ / \ / \ -------- <----- -------- | c0 | | c1 | -------- -----> --------
SMO の完了後に検索を再開するため、検索疑似コードから、Fetch、Insert、および Delete は進行中の SMO を表示しません。Insert プロシージャに入ると、次の条件が保持されます。
- x ラッチ 1st_leaf、
- 1st_leaf を含む SMO は進行中です。
- 1st_leaf の最上位キー < 分離キー
- 2nd_leaf >= 分離キーのキー
- 1st_leaf のキー < 2nd_leaf のキー
- 挿入されるキー < 分離されたキー。
たとえば、上の図の場合、c0 にキーを挿入すると、
- c0 は x ラッチされます
- c0 が関与する SMO は進行していません。
- c0 < k0 の最上位キー
- c1 >= k0 のキー
- c0 のキー < c1 のキー
- 挿入されるキー < k0。
次のコードは [1] から抜粋したもので、質問の関係のない部分を削除します。
/*No Space for Insert of Key*/
.....
/* No Need to Lock Next Key */
.....
/* Insert Key Value NOT Already in 1st_Leaf */
IF No Higher Key Value in 1st_Leaf AND 2nd_leaf Exists THEN
S Latch 2nd_Leaf /* while Holding X Latch on 1st_Leaf */
IF 2nd_Leaf is Empty THEN /*Page Delete in Progress-Wait for it to be Over*/
Unlatch 1st_Leaf and 2nd_Leaf
S Latch Tree for Instant-Duration
Unwind Recursion as far as Necessary Based on Noted Page VNs and Go Down Again
ELSE /* 2nd_Leaf is NOT Empty */
IF Insert Key Value found in 2nd_Leaf THEN /* This Can't be a Unique Index */
IX Lock Insert Key Value for Commit Duration
Unlatch 2nd_Leaf, Insert Key in 1st_Leaf, Log, Unlatch 1st_leaf and Return
ELSE Next Key Value := First Key Value in 2nd_Leaf
ELSE
IF No Higher Key Value in 1st_Leaf THEN Next Key Value := End_Of_file
ELSE Next Key Value := Higher Key Value in 1st_Leaf
IX Lock Next Key Value for Instant Duration
/*Insert Key into 1st_leaf*/
.....
Q1: 2nd_leaf で Insert Key Value を見つけることができるのはなぜですか? 私の推測では、 1st_leaf の親のラッチを解放してから 2nd_leaf を s_latch しようとしている間に、他のトランザクションによって引き起こされた多くの更新があるため、挿入されるキーが 2nd_leaf で見つかります。ただし、それにより分離されたキーが変更されますが、それがどのように発生するのか理解できません。
- 挿入によって 2nd_page が分割される場合がありますが、分割は常に右に向かって行われるため、1st_leaf と 2nd_leaf の間で分離されたキーを変更する必要はありません。
- 削除すると 2nd_page が削除される可能性がありますが、分離されたキーを変更する必要はありません。
Q2: 2nd_leaf で Insert Key Value を見つけたとしても、なぜそのようなキーを 1st_leaf に挿入するのでしょうか? 明らかに b+tree プロパティ (1st_leaf のキー < 2nd_leaf のキー) に違反しているためです。上記の条件は #6 を除いて保持されますが、分離キーが変更されているため、挿入されるキーが 2nd_leaf にあることがわかります。
参照
- ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes、Proc. 第 16 回超大規模データベースに関する国際会議、ブリスベン、1990 年 8 月。