论文部分内容阅读
B+树的并发控制协议有二阶段锁协议和多版本协议两种。二阶段锁协议是利用适当的封锁协议，实现多个用户的并发操作，但是读写同一对象冲突。多版本协议是使用多个版本的数据项来实现读写操作互不冲突，但是多版本B+树只支持多个读事务和一个写事务的并发操作。 本文提出了一种具有高并发读写性能的多版本B+树结构模型—SSMD(SingleStructureMulti-versionData)-B+Tree。SSMD-B+Tree属于单版本非叶页面，多版本叶页面。SSMD-B+Tree是基于页面的多版本，修改操作无需在相应的行上记录版本信息，而是在页面头部中记录下此次修改操作的回滚信息。当读事务需要读取页面时，可以根据记录的回滚信息回滚相应的修改操作构造出一个符合要求的历史版本页面，读事务不阻塞写事务，多个读写事务可以并行操作。同时，SSMD-B+Tree还实现了高效并行的结构修改操作，一次结构修改操作最多阻塞两个页面的并行结构修改操作，并且不阻塞相关页面的读写操作。最后，二阶锁协议实现的B+树仍是目前读写并发性能最好的模型，本文以实验证实了SSMD-B+Tree在高并发读写环境下比其具有更好的性能。