分布数据存储（两个人的团队）开题报告

1. 研究目的与意义

目前,微处理器已经从提高工作频率和指令级并行性发展到通过多个处理器核来提升性能。

多核时代的到来,对传统的串行编程模型带来了巨大的冲击:需要软件能充分利用多核处理器的线程级并行性来提高应用的性能。

数据库管理系统(database management systems)是非常重要的核心软件,如何开发多核处理器的潜力,提升数据库管理系统的性能是当前数据库系统研究中的重要方向。

2. 课题关键问题和重难点

目前，索引技术广泛应用于数据库中数字数据的搜索查询，b 树由于其自身的特点决定其适合应用于数据索引系统．在b 树应用中，其节点记录了每个子节点附加的数据信息，并将键值和附加数据相结合．一棵节点数量很多的b 树，在构建过程中时间和空间开销也较大，因此，有必要将b 树事先写人磁盘．不同类型的节点所需空间和实际附加数据大小直接关联，节点读取效率及其存储介质读取方式直接关联．b 树特性：1)b 树中子树节点和关键字的数量相同；2)关键字和叶子节点相对应并且是有序的；3)非叶子节点不存储数据；4)非叶子节点被当做索引部分，叶子节点包含子树的关键字；5)随机和顺序查找可同时进行。

数据容量的增加需要解决数据存储的可扩展性问题。

b 树是数据存储的基本模式，在分布存储环境中需要解决分布式的b 树存储问题。

3. 国内外研究现状（文献综述）

树叶(最底层的索引块)的b 树往往与另一个链表;这使得范围查询或(命令)迭代通过块更简单和更有效率的(虽然可以实现上述上界即使没有这个之外)。 这并不显著增加空间消费在树上或维护。 这说明的一个显著的优势b 树/ b - tree;b -树,因为并不是所有的钥匙都出现在叶子,这样不能构建有序链表。 b 树作为数据库系统指数,因此特别有用,通常驻留在磁盘上的数据,因为它允许b 树实际上提供了一种有效的住房结构数据本身(这是中描述(4]:238作为索引结构替代1)。如果一个存储系统b的块大小字节,和密钥存储大小的k,可以说是一个最有效的b 树。 虽然理论上一次性是不必要的,在实践中通常会有一些额外的空间被索引块(例如,链表引用的叶块)。 有一个索引块比存储系统的实际块代表一个显著的性能下降,因此谨慎的犯错者优先。如果b 树的节点组织为数组的元素,那么它可能需要相当长的时间来插入或删除一个元素数组的一半平均需要转移。 为了克服这个问题,元素在一个节点可以在一棵二叉树组织或b 树,而不是一个数组。b 树也可以用于数据存储在ram中。 在这种情况下的合理选择大小的块大小将处理器的高速缓存线路。空间效率的b 树可以通过压缩技术提高。 一种可能性是使用脉冲编码压缩密钥存储在每个数据块。 为内部块,节约空间可以通过压缩键或指针。 字符串键,可以节省空间,使用以下技术:正常th条目的一个内部块包含的第一个关键块i 1。 而不是存储完整的关键,我们可以存储的第一关键块的最短前缀i 1(词典顺序)是严格大于阻止我的最后关键。还有一个简单的方法来压缩指针:如果我们假设一些连续的块连续存储,那么它将足以只存储一个指针指向第一个块和连续的数块。上面所有的压缩技术有一些缺点。 首先,一个完整的块必须解压提取单个元素。 克服这个问题的一种技术是将每一块分成子块和压缩分开。 在这种情况下搜索或插入一个元素只需要解压压缩区块,而不是一个完整的块。 压缩技术的另一个缺点是存储元素的数量可能相差很大从一个街区到另一个,这取决于每个块中的元素被压缩。主要参考文献（3～5篇）：

1. https://en.wikipedia.org/wiki/b+_tree

2. 大规模分布式存储系统

3. 文件系统

4. 研究方案

在B 树应用中，其节点记录了每个子节点附加的数据信息，并将键值和附加数据相结合．一棵节点数量很多的B 树，在构建过程中时间和空间开销也较大，因此，有必要将B 树事先写人磁盘．不同类型的节点所需空间和实际附加数据大小直接关联，节点读取效率及其存储介质读取方式直接关联．B 树特性：1)B 树中子树节点和关键字的数量相同；2)关键字和叶子节点相对应并且是有序的；3)非叶子节点不存储数据；4)非叶子节点被当做索引部分，叶子节点包含子树的关键字；5)随机和顺序查找可同时进行。

5. 工作计划

1～2周：查找资料，阅读文献，熟悉并掌握B 树的基本概念，B 数据存储技术的基本概念和实现技术方法，完成英文翻译和文献综述；3～6周：根据查找的文献资料和调研报告进行分析并研究分布数据存储，制定分布B 树的实现方案；7～10周：需要处理数据量是10万量级以上的记录，操作需要完成：1. 完成数据的查询2. 完成数据的插入3. 完成数据的删除4.实现原型并测试10～周：总结并撰写论文，准备答辩。