NBTree: a Lock-free PM-friendly Persistent B -Tree for eADR-enab(13)

表2 The latest and clean leaves in diferent phases of SMO.
(The latest leaf contains all committed writes. The Clean leaf
does not contain any uncommitted dirty write. )
4.3 Inner Node Operations 作者提出了一种移位感知的搜索算法，并利用这种基于HTM的更新来协调并发的内部节点操作。
HTM-based Update.NBTree使用HTM原子地更新FPTree之后的内部节点。HTM是一个乐观并发控制工具，它使用硬件事务使多个写操作原子可见。它是非阻塞的，因为它只有在检测到冲突时才会中止。在HTM中包装更新是有效的，因为内部节点修改的冲突很少发生。此外，更新不会将中间状态暴露给其他线程，这避免了读线程查看不一致的状态。

Shif-aware Search.虽然对内部结点的修改是原子的，但由于读写冲突，无锁的内部结点搜索可能会找到错误的子结点指针。如图4所示，搜索操作执行线性搜索(search(18))以检索键20(②)。但是，在获取对应的指针P2之前，一次插入(Insert(PL,15,PR))会修改节点。因此，搜索操作加载了错误的指针PR(③)，而不是P2或PR。因此，搜索操作可能会遗漏一个已存在的键。
图4 NBTree提出了一种移位感知的搜索算法，保证了在同一节点上并发写事务(插入或删除)时无锁的内部节点搜索的正确性。如图4所示，在通过PL继续到树的下一层之前，NBTree会检查获取的键(②中的20)是否被并发写事务移动了。如果是，NBTree从当前位置(④-⑥)重新搜索节点，确保目标键位于返回的指针所指向的子树中。移位感知搜索算法总是能找到正确的指针，原因如下。首先，NBTree保持搜索，数据向同一个方向移动。如图4所示，在搜索期间，插入将数据从左向右移动。如果沿着相同的方向搜索，就不会错过新插入的键。受FAST&FAIR的启发，我们在每个节点中维护一个switch_counter，当内部节点的插入和删除操作轮流进行时，这个计数器就会增加。其次，采用B-link树的并发协议[33]来处理SMO。