追加和归并结合的存储树研究

发布时间：2021-10-27 18:11

　　廉价且众多的信息传感设备、社交网络、电子商务和在线游戏以前所未有的速度生产数据,这使得数据量日益庞大。索引树面临着高效加载、更新、搜索和分析大量数据的挑战。传统的索引树,如B树,写性能差,不适用于大数据背景下写密集的场景中。而日志结构的归并树（Log-StructuredMerge-Tree,LSM树）广泛应用于近些年的键值存储系统中。LSM树因为完全消除了磁盘上的随机读写,充分的利用了磁盘的顺序读写,而大幅提高了传统索引树的写性能。然而,在插入大量数据的情况下,LSM树会产生频繁的归并操作,所以其遭受着严重的写放大问题。这不仅使写操作的吞吐量降低,而且使像SSD这一类擦除次数有限制的存储设备更容易耗尽寿命。与此同时,因为较大的写放大会在用户进行查询操作的同时产生大量的磁盘写而占用查询操作的带宽,所以还会降低查询性能。为了解决这个问题,我们首先设计了日志结构的追加树（Log-Structured Append-Tree,LSA树）,其用追加操作来替代LSM树中的归并操作。然而,LSA树在遍历时会引起更大的读放大以及空间放大。为了解决引起的新问题,通过在LSA树中引入归并操作,提出了具有... 

【文章来源】：武汉大学湖北省 211工程院校 985工程院校 教育部直属院校

【文章页数】：59 页

【学位级别】：硕士

【部分图文】：

图１?Ｂ树的基本结构

?Ｍｅｍｏｒｙ??图２?ＬＳＭ树的基本结构。??通常，ＬＳＭ树由ｎ＋１个组件Ｃ〇，Ｃｉ，?Ｃ２，?．．．，Ｃｎ组成，如图２所示，每个??组件的大小呈指数增长（两个相邻组件之间的容量阈值的倍数相同）。内存驻留??组件Ｃ０是一种内存排序树，可累积用户写的数据，直到达到其存储容量的阈值。??其他组件（＾?（ｌＳｘ?Ｓｎ）都驻留在磁盘，其存储的记录可以通过顺序读写性能好??的Ｂ树，如ＳＢ树［４７］，进行组织。每当较小的组件Ｃｍ超过其容量阈值时，ＬＳＭ??树通过压缩将Ｃｍ的记录移动到Ｃｘ组件。这里的压缩操作为归并排序操作。??２．２．２?ＬｅｖｅｌＤＢ?和?ＲｏｃｋｓＤＢ??图３显示了?ＬｅｖｅｌＤＢ的基本结构，该结构为ＬＳＭ树典型的实现结构。??ＲｏｃｋｓＤＢ的基本结构与ＬｅｖｅｌＤＢ的相同。该结构中ｍｅｍｔａｂｌｅ和ｉｍｍｕｔａｂｌｅ??ｍｅｍｔａｂｌｅ都存储于内存中的，即对应于ＬＳＭ树的Ｃ〇组件，其实现为跳表［３１］类??型的排序结构。Ｌｘ?（１分公１）中的所有数据存储在磁盘上，对应于ＬＳＭ树的组??件Ｃｘ。每层都有一个容量阈值，随着层数的增加，该阈值会增加１〇倍。例如，??６??

树通过压缩将Ｃｍ的记录移动到Ｃｘ组件。这里的压缩操作为归并排序操作。??２．２．２?ＬｅｖｅｌＤＢ?和?ＲｏｃｋｓＤＢ??图３显示了?ＬｅｖｅｌＤＢ的基本结构，该结构为ＬＳＭ树典型的实现结构。??ＲｏｃｋｓＤＢ的基本结构与ＬｅｖｅｌＤＢ的相同。该结构中ｍｅｍｔａｂｌｅ和ｉｍｍｕｔａｂｌｅ??ｍｅｍｔａｂｌｅ都存储于内存中的，即对应于ＬＳＭ树的Ｃ〇组件，其实现为跳表［３１］类??型的排序结构。Ｌｘ?（１分公１）中的所有数据存储在磁盘上，对应于ＬＳＭ树的组??件Ｃｘ。每层都有一个容量阈值，随着层数的增加，该阈值会增加１〇倍。例如，??６??


本文编号：3462108