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

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

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