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

摘要：

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

关键词：事务、索引、B+tree(BT)、多版本并发、写时复制(COW)

所属期刊栏目：27

分类号：TP3;F72

资助基金：国家科技支撑计划2012BAH45B01;国家自然科学基金61100189,61370215,61370211;国家信息安全计划2014A085,2015A072

在线出版日期：2017-09-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：9-19