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

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

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