高并發(fā)讀寫性能的多版本B+樹研究.pdf

1、B+樹的并發(fā)控制協(xié)議有二階段鎖協(xié)議和多版本協(xié)議兩種。二階段鎖協(xié)議是利用適當?shù)姆怄i協(xié)議，實現(xiàn)多個用戶的并發(fā)操作，但是讀寫同一對象沖突。多版本協(xié)議是使用多個版本的數(shù)據(jù)項來實現(xiàn)讀寫操作互不沖突，但是多版本B+樹只支持多個讀事務和一個寫事務的并發(fā)操作。
　　本文提出了一種具有高并發(fā)讀寫性能的多版本B+樹結(jié)構(gòu)模型—SSMD(SingleStructureMulti-versionData)-B+Tree。SSMD-B+Tree屬于單版本非葉

2、頁面，多版本葉頁面。SSMD-B+Tree是基于頁面的多版本，修改操作無需在相應的行上記錄版本信息，而是在頁面頭部中記錄下此次修改操作的回滾信息。當讀事務需要讀取頁面時，可以根據(jù)記錄的回滾信息回滾相應的修改操作構(gòu)造出一個符合要求的歷史版本頁面，讀事務不阻塞寫事務，多個讀寫事務可以并行操作。同時，SSMD-B+Tree還實現(xiàn)了高效并行的結(jié)構(gòu)修改操作，一次結(jié)構(gòu)修改操作最多阻塞兩個頁面的并行結(jié)構(gòu)修改操作，并且不阻塞相關(guān)頁面的讀寫操作。最后，二