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

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

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

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

【部分圖文】：

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

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

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


本文編號：3462108