廉價(jià)且眾多的信息傳感設(shè)備、社交網(wǎng)絡(luò)、電子商務(wù)和在線游戲以前所未有的速度生產(chǎn)數(shù)據(jù),這使得數(shù)據(jù)量日益龐大。索引樹(shù)面臨著高效加載、更新、搜索和分析大量數(shù)據(jù)的挑戰(zhàn)。傳統(tǒng)的索引樹(shù),如B樹(shù),寫(xiě)性能差,不適用于大數(shù)據(jù)背景下寫(xiě)密集的場(chǎng)景中。而日志結(jié)構(gòu)的歸并樹(shù)（Log-StructuredMerge-Tree,LSM樹(shù)）廣泛應(yīng)用于近些年的鍵值存儲(chǔ)系統(tǒng)中。LSM樹(shù)因?yàn)橥耆舜疟P(pán)上的隨機(jī)讀寫(xiě),充分的利用了磁盤(pán)的順序讀寫(xiě),而大幅提高了傳統(tǒng)索引樹(shù)的寫(xiě)性能。然而,在插入大量數(shù)據(jù)的情況下,LSM樹(shù)會(huì)產(chǎn)生頻繁的歸并操作,所以其遭受著嚴(yán)重的寫(xiě)放大問(wèn)題。這不僅使寫(xiě)操作的吞吐量降低,而且使像SSD這一類擦除次數(shù)有限制的存儲(chǔ)設(shè)備更容易耗盡壽命。與此同時(shí),因?yàn)檩^大的寫(xiě)放大會(huì)在用戶進(jìn)行查詢操作的同時(shí)產(chǎn)生大量的磁盤(pán)寫(xiě)而占用查詢操作的帶寬,所以還會(huì)降低查詢性能。為了解決這個(gè)問(wèn)題,我們首先設(shè)計(jì)了日志結(jié)構(gòu)的追加樹(shù)（Log-Structured Append-Tree,LSA樹(shù)）,其用追加操作來(lái)替代LSM樹(shù)中的歸并操作。然而,LSA樹(shù)在遍歷時(shí)會(huì)引起更大的讀放大以及空間放大。為了解決引起的新問(wèn)題,通過(guò)在LSA樹(shù)中引入歸并操作,提出了具有... 

【文章來(lái)源】：武漢大學(xué)湖北省 211工程院校 985工程院校 教育部直屬院校

【文章頁(yè)數(shù)】：59 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

圖１?Ｂ樹(shù)的基本結(jié)構(gòu)

?Ｍｅｍｏｒｙ??圖２?ＬＳＭ樹(shù)的基本結(jié)構(gòu)。??通常，ＬＳＭ樹(shù)由ｎ＋１個(gè)組件Ｃ〇，Ｃｉ，?Ｃ２，?．．．，Ｃｎ組成，如圖２所示，每個(gè)??組件的大小呈指數(shù)增長(zhǎng)（兩個(gè)相鄰組件之間的容量閾值的倍數(shù)相同）。內(nèi)存駐留??組件Ｃ０是一種內(nèi)存排序樹(shù)，可累積用戶寫(xiě)的數(shù)據(jù)，直到達(dá)到其存儲(chǔ)容量的閾值。??其他組件（＾?（ｌＳｘ?Ｓｎ）都駐留在磁盤(pán)，其存儲(chǔ)的記錄可以通過(guò)順序讀寫(xiě)性能好??的Ｂ樹(shù)，如ＳＢ樹(shù)［４７］，進(jìn)行組織。每當(dāng)較小的組件Ｃｍ超過(guò)其容量閾值時(shí)，ＬＳＭ??樹(shù)通過(guò)壓縮將Ｃｍ的記錄移動(dòng)到Ｃｘ組件。這里的壓縮操作為歸并排序操作。??２．２．２?ＬｅｖｅｌＤＢ?和?ＲｏｃｋｓＤＢ??圖３顯示了?ＬｅｖｅｌＤＢ的基本結(jié)構(gòu)，該結(jié)構(gòu)為ＬＳＭ樹(shù)典型的實(shí)現(xiàn)結(jié)構(gòu)。??ＲｏｃｋｓＤＢ的基本結(jié)構(gòu)與ＬｅｖｅｌＤＢ的相同。該結(jié)構(gòu)中ｍｅｍｔａｂｌｅ和ｉｍｍｕｔａｂｌｅ??ｍｅｍｔａｂｌｅ都存儲(chǔ)于內(nèi)存中的，即對(duì)應(yīng)于ＬＳＭ樹(shù)的Ｃ〇組件，其實(shí)現(xiàn)為跳表［３１］類??型的排序結(jié)構(gòu)。Ｌｘ?（１分公１）中的所有數(shù)據(jù)存儲(chǔ)在磁盤(pán)上，對(duì)應(yīng)于ＬＳＭ樹(shù)的組??件Ｃｘ。每層都有一個(gè)容量閾值，隨著層數(shù)的增加，該閾值會(huì)增加１〇倍。例如，??６??

樹(shù)通過(guò)壓縮將Ｃｍ的記錄移動(dòng)到Ｃｘ組件。這里的壓縮操作為歸并排序操作。??２．２．２?ＬｅｖｅｌＤＢ?和?ＲｏｃｋｓＤＢ??圖３顯示了?ＬｅｖｅｌＤＢ的基本結(jié)構(gòu)，該結(jié)構(gòu)為ＬＳＭ樹(shù)典型的實(shí)現(xiàn)結(jié)構(gòu)。??ＲｏｃｋｓＤＢ的基本結(jié)構(gòu)與ＬｅｖｅｌＤＢ的相同。該結(jié)構(gòu)中ｍｅｍｔａｂｌｅ和ｉｍｍｕｔａｂｌｅ??ｍｅｍｔａｂｌｅ都存儲(chǔ)于內(nèi)存中的，即對(duì)應(yīng)于ＬＳＭ樹(shù)的Ｃ〇組件，其實(shí)現(xiàn)為跳表［３１］類??型的排序結(jié)構(gòu)。Ｌｘ?（１分公１）中的所有數(shù)據(jù)存儲(chǔ)在磁盤(pán)上，對(duì)應(yīng)于ＬＳＭ樹(shù)的組??件Ｃｘ。每層都有一個(gè)容量閾值，隨著層數(shù)的增加，該閾值會(huì)增加１〇倍。例如，??６??


本文編號(hào)：3462108