一种面向事务型数据库的无锁并发B+tree索引结构

为了克服现有多版本并发控制(MVCC)进行数据的并发访问控制中短暂阻塞的缺点,达到读写完全并发,提出了一种基于写时复制的多版本并发B+tree(BCMVBT)索引结构。BCMVBT通过复制分离读写的操作空间以使读写事务在任意时刻完全并发执行,规避比较与交换(CAS)操作带来的高CPU消耗,达到一写多读场景下的完全并发。同时针对现有多版本开发B+tree(MVBT)范围查询的复杂操作,提出了无锁的BCMVBT的范围查询算法和回收机制,从而实现了索引的插入、查询、更新与回收的无锁并发操作。通过与事务型MVBT(transaction MVBT)的对比,在读写并发环境下BCMVBT的时间消耗降低了50%,实验进一步表明BCMVBT在大事务的场景下具有更高的优势。