基于第三级存储器的海量数据管理技术研究

摘要

本文以第三级存储器技术为研究对象，研究海量数据管理中的关键性问题，在第三级存储器的存储管理、基于第三级存储器的数据操作、基于第三级存储器的查询优化和海量多媒体中的第三级存储器技术等方面取得了一系列研究成果。　　提出了单磁带数据I/O调度算法TIOCN2，与其他算法相比，在没有增加算法复杂度的前提下，第三级存储器的访问性能得到了提高。交换磁带是第三级存储设备中的机械操作，费时很多，因此仔细地选择装载磁带的顺序，可以节省第三级存储器上请求的总体执行时间。本文根据系统的当前状态和请求负载，提出四种磁带选择算法，并结合单磁带I/O调度算法，其实验结果表明磁带库的整体访问性能得到了明显的改善。根据SCSI接口原理和Exabyte公司提供的符合SCSI-Ⅱ标准的SCSI命令集，设计与实现了基于第三级存储器的虚拟文件系统，屏蔽磁带物理访问细节，为上层应用程序提供编程接口，实现磁带信息的“按名存取”。该虚拟文件系统包括磁带文件创建、文件读取、文件更新、文件删除、文件拷贝、文件重命名以及磁带存储空间碎片整理等操作。　　设计与实现一种新的基于第三级存储器的海量数据索引THB-tree结构，创造性地将索引分成三个层次进行存储，并利用叶子节点上数据元组的有序性，有效地支持了基于索引的海量数据库关系代数操作。本文分别给出聚簇THB-tree索引和非聚簇THB-tree索引的构建方法及维护算法。研究了磁带库中的数据优化存放问题，给出最优化的磁带文件存放定理和证明。　　设计了一种新的海量数据排序算法STESort，充分利用存储设备的物理特点，巧妙地分布排序子段，仅用两个磁带驱动器实现海量数据排序，明显优于传统排序算法。在排序算法的基础上，设计与实现基于排序的海量数据库集合操作算法和海量数据库的关系代数操作算法。给出一种基于第三级存储器的海量数据库查询优化方法。　　研究第三级存储器在海量多媒体系统中的应用，设计了一个局域网环境中的海量多媒体系统TSMS。在TSMS中，提出基于磁带Strip技术的多媒体数据存储方法、基于RIV矢量的多媒体请求调度算法和混合负载下的海量多媒体数据存储和数据提交算法。

目录

文摘

英文文摘

论文说明：图表索引

第1章绪论

1.1研究的目的和意义

1.2国内外研究现状

1.3本文研究内容及组织

1.3.1主要研究内容

1.3.2本文的研究方法和技术路线

1.3.3主要研究成果

1.3.4章节内容安排

第2章预备知识

2.1引言

2.2第三级存储器技术

2.2.1磁带技术

2.2.2光盘技术

2.2.3磁带库和光盘库技术

2.2.4 Exabyte 220磁带库特点

2.3第三级存储器数据访问的数学模型

2.3.1磁带库访问模型

2.3.2锯齿型磁带库的数学访问模型

2.3.3蛇型磁带库的数学访问模型

2.4实验环境和实验数据

2.4.1 SCSI工作原理和SCSI命令集

2.4.2 TPC-H数据

2.4.3黑龙江省移动公司移动电话通话数据

2.5本章小结

第3章第三级存储器中的数据访问调度策略

3.1第三级存储器单磁带I/O调度算法TIO CN2

3.1.1引言

3.1.2第三级存储器I/O调度算法TIO_CN2

3.1.3实验结果

3.2第三级存储器中的磁带选择算法

3.2.1引言

3.2.2第三级存储器中的磁带选择算法

3.2.3实验结果

3.3基于第三级存储器的虚拟文件系统

3.3.1问题的提出

3.3.2虚拟文件系统设计与数据结构

3.3.3虚拟文件系统算法实现

3.4本章小结

第4章第三级存储器中的索引结构和优化存储

4.1基于第三级存储器的多层索引结构THB-tree

4.1.1引言

4.1.2 THB-tree索引结构

4.1.3 THB-Tree索引的查找

4.1.4 THB-Tree索引的合并

4.1.5 THB-Tree索引的建立

4.1.6 THB-Tree索引的维护

4.1.7磁带逻辑块大小的确定方法

4.1.8对比分析与实验

4.2磁带库中的文件最优化存放

4.2.1引言

4.2.2文件优化存放定理

4.2.3文件优化存放算法

4.2.4实验结果

4.3本章小结

第5章第三级存储器上的查询处理

5.1第三级存储器上的外排序算法

5.1.1问题的提出

5.1.2“败者树”归并算法

5.1.3外排序算法STESort

5.1.4算法分析

5.1.5实验结果

5.2第三级存储器上的关系集合操作

5.2.1关系并操作算法

5.2.2关系交操作算法

5.2.3关系差操作算法

5.2.4关系选择操作

5.2.5关系连接操作

5.2.6实验结果

5.3基于第三级存储器的数据库查询优化

5.3.1查询执行计划模型

5.3.2基于第三级存储器访问代价的查询计划代价模型

5.3 3基于第三级存储器的查询优化算法

5.3.4实验结果

5.4本章小结

第6章海量多媒体中的第三级存储器技术

6.1问题的提出

6.2基于第三级存储器的多媒体系统框架

6.3基于磁带Strip技术的多媒体数据存储

6.3.1磁带Strip技术

6.3.2盘预留片头大小的确定

6.3.3对比分析

6.4 TSMS中的多媒体服务请求调度算法

6.4.1用户请求分类

6.4.2 RIV矢量偏移和合并

6.4.3根据不同策略选择候选请求的初始化时间

6.4.4用户请求调度算法

6.5混合负载多媒体服务器的数据存储和数据提交

6.5.1多媒体数据的存储

6.5.2磁带上多媒体数据的存储算法

6.5.3混合负载多媒体数据提交策略

6.6本章小结

结论

参考文献

攻读博士学位期间发表的学术论文

科研经历

攻读博士学位期间获得的奖励

哈尔滨工业大学博士学位论文原创性说明及使用授权书

致谢

个人简历