分布B 树存储结构实现开题报告

1. 研究目的与意义

随着人们对移动数据处理和管理需求的不断提高，与各种手持设备能够紧密结合在一起的嵌入式数据库逐渐为人们研究的热点。

而b 树作为一种成熟的数据结构，在数据库索引构建以及文件索引数据组织方面具有及其广泛的评估测试。

测试结果表明。

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

课题关键问题：1)查找操作 对b 树可以进行两种查找运算：　a.从最小关键字起顺序查找；　b.从根结点开始，进行随机查找。

在查找时，若非终端结点上的剧组机等于给定值，并不终止，而是继续向下直到叶子结点。

因此，在b 树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。

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

摘要随着人们对移动数据处理和管理需求的不断提高，与各种手持设备能够紧密结合在一起的嵌入式数据库逐渐为人们研究的热点。

而b 树作为一种成熟的数据结构，在数据库索引构建以及文件索引数据组织方面具有及其广泛的评估测试。

测试结果表明。

4. 研究方案

B 树的实现需满足，（1）MAX_KEYS>=2；（2）每个节点最多可以保存MAX_KEYS条记录，当记录数超过MAX_KEYS,节点发生分裂；（3）节点中，指针数量比记录数量多4个，其中leftMostChild用来指向键小于该节点内最小键的子树，left用来指向同一层左侧的节点，right用来指向同层右侧的节点，parent用来指向父节点；（4）当树只有一层，即只有一个节点时（此时它既是根结点，也是叶节点），该节点可以含0至MAX_KEYS条记录；（5）当树只有两层时，由根节点和叶节点构成，没有中间层，根节点至少要有1条记录，叶节点记录数量的下限为MAX_KEYS/2上取整；（6）当树高超过两层时，由根节点、中间节点记录数量的下限为MAX_KEYS/2下取整；（7）叶节点存储的记录由键和值构成；（8）树高超过一层时，内部节点（根结点和中间节点）存储的记录由键和子节点指针构成，最左边的指针指向键=k1且=ki且=kn的子树；（9）不允许出现重复的键；

5. 工作计划

1．开题报告 2022 年12月20日2022年02月20日3．收集资料 2022 年02月21日2022年03月01日4．系统开发 2022 年03月10日2022年04月10日5．完成论文修改稿 2022 年04月11日2022年05月11日6．完成论文定稿 2022 年05月11日2022年05月12日7．答辩 2022 年05月12日