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

4 LOCK-FREE DESIGN4.1 Leaf Node Operations 我们将NBTree中的基本操作分为两类。第一类是insert，它将新数据添加到空闲槽位。第二类是UDS的操作，包括更新、删除、查询。UDS的操作总是对提交的插入操作有效。接下来，我们将讨论NBTree如何解决insert-insert、UDS-UDS和insert-UDS冲突。
Insert-Insert Conflicts.我们使用原子基元来序列化并发插入。如图2所示，为了开始插入，NBTree使用fetch_and_add原子性地增加num，占用下一个空闲槽。这确保了并发的插入操作被放置在不同的位置上。在一次插入操作结束时，NBTree使用CAS以原子方式更新bitmap，从而提交插入操作。通过这种方式，NBTree实现了对叶子节点的无锁插入。
Insert-UDS Conflicts.这些冲突在NBTree中自然地得到了解决。首先，插入操作会将数据写入未使用的空间，不影响系统的正常操作;其次，NBTree通过原子性更新bitmap来提交插入操作，这使得新的插入操作对UDS操作可见。因此，UDS的操作总是对已完成的插入操作进行操作。