1

我正在学习你的论文 ARIES/KVL[1]，从论文中，B+树结构看起来像：

                    ------------------------------------
                    |  p0  |  k0  |  p1  |  k1  |  p2  |
                    ------------------------------------
                     /                \                                      
                    /                  \                                   
                   /                    \                                  
                  /                      \                                 
                 /                        \                               
             --------      <-----      --------
             |  c0  |                  |  c1  |
             --------      ----->      --------

从 Search 伪代码中，Fetch、Insert 和 Delete 永远不会在 progrss SMO 中看到，因为在 SMO 完成后重新启动搜索。有一次，我们进入插入过程，满足以下条件：

  1. x 锁存第一叶，
  2. 没有涉及 1st_leaf 的 SMO 正在进行中。
  3. 1st_leaf 的最高键 < 分隔键
  4. 2nd_leaf 的键 >= 分隔键
  5. 1st_leaf 的键 < 2nd_leaf 的键
  6. 要插入的密钥 < 分隔的密钥。

例如，给定上图，当我们在 c0 中插入一个键时，那么

  1. c0 被 x 锁存
  2. 没有涉及 c0 的 SMO 正在进行。
  3. c0 < k0 的最高键
  4. c1 >= k0 的键
  5. c0 的键 < c1 的键
  6. 待插入密钥 < 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 中找到插入键值？我的猜测是，从释放 1st_leaf 的父级闩锁到尝试 s_latch 2nd_leaf期间，其他事务引起了许多更新，因此在 2nd_leaf 中找到了一个待插入的密钥。但是，这将导致分隔键被更改，我无法理解它是如何发生的。

  1. 插入可能会导致拆分第二页，但不需要更改第一页和第二页之间的分隔键，因为拆分总是向右。
  2. 删除可能会导致删除 2nd_page，但它仍然不需要更改分隔键。

Q2：即使我们在2nd_leaf中找到了一个Insert Key Value，为什么还要把这样的key插入到1st_leaf中？因为它显然违反了 b+tree 属性（1st_leaf 的键 < 2nd_leaf 的键）。除了#6，上述条件仍然成立，因为分隔键被改变了，所以我们可以在2nd_leaf中找到to-be-inserted-key。

参考

  1. Mohan, C. ARIES/KVL：一种键值锁定方法，用于对 B 树索引上操作的多操作事务进行并发控制，Proc。第 16 届超大型数据库国际会议，布里斯班，1990 年 8 月。
4

0 回答 0