文章针对的索引按照B+树的方式进行组织，索引树提供单点检索(fetch)，范围检索(fetch next)，插入(insert)和删除(delete) 4项基本操作，同时索引更新可能导致树结构变更操作即SMOs(structure modification operations)。

索引的并发控制和故障恢复主要面临以下问题：

  1. 如何最小化并发更新索引的影响，提高并发效率
  2. 如何处理死锁问题
  3. 如何支持不同粒度的锁，锁对象该如何选取
  4. 如何解决phantom problem
  5. 唯一索引被删除后，如何确保该事务提交前该索引不被其他事务添加
  6. 如何让SMO和其他操作正确且高效地并行
  7. 如何记录索引变更日志使得故障恢复更加高效
  8. 当SMO操作部分成功时，故障恢复如何进行
  9. 如何保证SMO成功后，即使进行SMO的事务回滚，SMO不会回滚
  10. 事务回滚时如何检测SMO操作导致的数据移动，以保证回滚正确进行

ARIES/IM 能够很好的应对以上问题

ARIES/IM 中主要使用data-only lock 逻辑，不同操作下的Lock操作如下表

表1 Lock逻辑

Latch 逻辑

ARIES/IM 使用index page latch保证数据的物理一致性， 在遍历索引树时使用latch coupling逻辑，其加锁主要步骤为：

该逻辑保证任意时刻，一次索引树遍历最多只对两个节点持有锁（latch），同时加锁严格有序，可以避免死锁发生。SMO时的附加逻辑在后文介绍。

在ARIES/IM 中，SMO前必须先获取索引树的X latch，因此SMO操作是严格串行化的。 此外为了控制SMO和其他操作的并发，ARIES/IM 为每个节点引入了SM_BIT标志，SM_BIT为1时表明SMO 操作正在进行。因此索引树遍历的逻辑拓展为：

  2. Child := Root
  3. Parent := NIL
  4. IF child is a leaf AND Op is (insert OR delete) 
  5. THEN
  6.   X latch child
  7. ELSE 
  8.   S latch child
  9. Note child’s page LSN
  10. IF child is a nonleaf page THEN
  11.     IF nonempty child & 
  12.         ((input key <= highest key in child) 
  13.             OR (input key > highest key in child) & SM-Bit=0))
  14.   THEN
  15.             IF parent <> NIL THEN unlatch parent
  16.             Parent := Child
  17.             Child := Page-Search (Child)
  19.     ELSE 
  20.             Unlatch parent & child
  21.             S latch tree for instant duration
  22.                     /* Wait for unfinished SMO to finish */ 
  23.             Unwind recursion as far as necessary based on noted page_LSNs and go down again
  24. ELSE 
  25.     CASE Op 
  26.             Fetch:  . . .  /* invoke fetch action routine */
  27.             Insert: . . .  /* invoke insert action routine */
  28.     END

条件nonempty child & ((input key <= highest key in child) OR (input key > highest key in child) & SM-Bit=0))表明若没有SMO或本次操作的目标key不受SMO的影响，加锁逻辑与前文latch coupling逻辑一致，因此该算法允许部分操作和SMO操作并行执行，而对于必须等待SMO的操作，先释放其已持有的锁，防止阻塞其他事务，同时请求索引树的S latch，并等待。当锁获取成功后，通过调用链上记录的page_lsns判断相应节点是否变更，以快速恢复到断点，并继续进行。若已经遍历到叶节点，则执行相应的操作。

Fetch

该算法首先查询目标key或者下一个最小key（next higher key）然后对查找到的key（目标key或者next higher key）加S lock（若next higher key不存在，此时将对该索引树一个特定的key加锁，该key表征索引尾部边界）。之所以要对next higher key加commit-duration的S lock，是为了防止目标Key正被某个未提交的事务删除，或目标key被其他事务插入（回顾表1，insert/delete都需要对next higher key 加X lock）。若查找过程中出现跨页，获取下一个页的latch，同时前一个页的latch不能释放，否则前一个页可能会被插入数据。当锁获取失败时，记录page_lsn，和key的位置然后释放latch并等待lock，当lock获取成功后，根据page_lsn判断页是否被修改，然后执行相应操作。

Insert

  1. IF SM_Bit | Delete-Bit = 1 
  2. THEN
  3.     Instant S latch tree, set Bits to 0
  4. Unlatch parent
  5. Find key > insert key & X lock it for instant duration
  7.     /* Latch next page while holding latch on current page*/
  8.     /* Lock next key while holding latch on next page also*/
  9.     /* Unlatch next page after acquiring next key lock */
  10. Insert key, 1og and update page-LSN
  11. Release child latch

插入时，若目标key已经存在，且索引为唯一索引，则返回错误，并持有该key的S lock至事务提交，以保证RR；若不为唯一索引，则执行插入操作。

若目标key不存在，则insert操作将定位到next higher key或该索引的尾部边界key。此时将对该key加X lock，持有周期为instant-duration。此后，若索引为唯一索引，则必须检测目标key是否正在被删除。该目的通过判断Delete-Bit(见后文)实现，若Delete-Bit为1，则说明该页存在删除操作，此时需要等待获取索引树的S latch。

此外，插入操作可能面临需要SMO的情况，相应操作流程如下：

首先获取相应的页，然后对索引树加X latch，同时释放父节点的latch。然后进行split操作，完成后执行insert操作。

  1. IF SMO-Bit = 1 THEN 
  2.     Instant S latch tree and set SMO-Bit to 0
  3. Set Delete_Bit to 1 
  5. Unlatch parent
  6. Find key > delete key & X lock it for commit duration 
  8. IF delete key is smallest/largest on page 
  9. THEN 
  10.     S latch tree and set Delete-Bit to 0 
  12. Delete key, log and update page_LSN

删除操作开始时需要设置delete_bit标志位，以阻止insert的进行。删除操作还必须找到next higher key，并加X lock，且持有周期为commit-duration以防止phantom problem。此外若被删除的key是索引的边界，还需要对索引树加S latch，该操作是因为索引边界变更会影响故障恢复，具体逻辑将会在下一篇描述故障恢复逻辑时进行描述。如果删除的key是页的最后一个key，则需要SMO，进行一次merge操作，其逻辑见insert部分。