学位论文 > 优秀研究生学位论文题录展示

主存数据库索引机制的研究与改进

作　者: 杨朝辉
导　师: 王立松
学　校: 南京航空航天大学
专　业: 计算机科学与技术
关键词: 索引结构 主存数据库(MMDB) Cache-conscious CST-树索引 MCST-树索引
分类号: TP311.13
类　型: 硕士论文
年　份: 2011年
下　载: 21次
引　用: 0次
阅　读: 论文下载
 

内容摘要


随着主存速度和现代处理器的速度之间的差距逐渐扩大,系统对主存的存取访问成为新的瓶颈,Cache行为对主存数据库系统更加重要。高速缓冲存储器存(Cache)是在处理器与主存之间设置的静态随机访问存储器(SDRAM)。高速缓存装载系统运行时需要经常使用的数据,以减少处理器访问内存的次数,从而减少CPU等待时间。鉴于主存数据库本身的结构特点,Cache行为对主存数据库索引结构的设计显得更加重要。本文深入研究了高速缓存工作原理与Cache敏感(Cache-Conscious)技术,对现有的主存数据库索引结构进行了比较与分析。在CST-树的基础上提出一种改进的Cache敏感-T树—MCST-树(Improved Cache sensitive-Tree)索引结构。MCST-树的结构设计特点如下:(1)保留高频访问数据:构建了一个包含CST-树结点中最大关键字的折半查找树,使用这个折半查找树作为一个目录结构确定实际包含所要查找的关键字所在的结点。因为每次查找都会首先访问折半查找树,所以折半查找树中的内容被访问的频率很高。(2)指针的抽取:首先,将折半查找树保存在一个数组(结点组)中,不再保留指向父亲结点与孩子结点的指针。其次,结点组的孩子结点组连续存储,每个结点组仅保留一个指向其第一个孩子结点组的指针。(3)结点大小设计为Cache块大小:将存放折半查找树的数组设计为一个Cache块大小。结点组设计为一个Cache块大小时,在结点组内的访问不会发生Cache缺失。同时,本文还对应用预取技术时改进的Cache敏感型T-树结点组大小的设计进行分析,并且简单描述了应用预取技术时对改进的Cache敏感型T-树基本操作算法的关键部分的修改。实验结果表明,MCST-树索引结构在查找操作性能优势明显,同时MCST-树索引结构的空间代价最小。综合考虑空间代价与时间代价两个方面的因素,MCST-树的整体性能优于CSB+-树最好的一种变形——FULL CSB+-树。

全文目录


摘要  4-5
Abstract  5-11
第一章 绪论  11-24
  1.1 主存数据库系统概述  11-17
    1.1.1 主存数据库概念  11-12
    1.1.2 主存数据库技术  12-15
    1.1.3 主存数据库系统技术的发展  15-17
  1.2 主存与高速缓冲存储器对数据系统性能的影响  17-19
  1.3 主存数据库索引结构研究现状  19-22
  1.4 本文的研究内容  22-23
  1.5 文章的组织结构  23-24
第二章 传统索引结构与高速缓冲存储器  24-41
  2.1 传统索引机制  24-36
    2.1.1 哈希索引机制  24-26
    2.1.2 平衡二叉树（AVL 树）索引机制  26-30
    2.1.3 T-树索引机制  30-36
  2.2 高速缓冲存储器  36-40
    2.2.1 高速缓存的工作原理  36-38
    2.2.2 计算机各级存储层次与访问次序  38-40
  2.3 本章小结  40-41
第三章 Cache 敏感技术优化方法与索引结构设计  41-49
  3.1 Cache 敏感技术优化方法  41-45
    3.1.1 被动型Cache 敏感技术  41-43
    3.1.2 主动型Cache 敏感技术  43-45
  3.2 Cache 敏感型索引结构设计  45-48
    3.2.1 被动型Cache 敏感型索引结构  45-47
    3.2.2 主动型Cache 敏感型索引结构  47-48
  3.3 本章小结  48-49
第四章 改进的高速缓存敏感T-树  49-68
  4.1 CST-树与MCST-树  49-54
    4.1.1 CST-树  50-51
    4.1.2 MCST-树  51-54
  4.2 MCST-树索引机制上的基本操作  54-62
    4.2.1 查找算法  54-55
    4.2.2 插入算法  55-57
    4.2.3 删除算法  57-60
    4.2.4 旋转算法  60-61
    4.2.5 时间复杂度分析  61-62
  4.3 应用预取技术的MCST-树  62-67
    4.3.1 创建加宽索引结点进行索引查找  62-64
    4.3.2 结点大小设计的定性分析  64-67
    4.3.3 应用预取技术时对MCST-树算法的修改  67
  4.4 本章小结  67-68
第五章 性能测试与分析  68-74
  5.1 测试描述  68-69
    5.1.1 测试方法  68-69
    5.1.2 数据来源  69
  5.2 测试环境  69
  5.3 测试结果  69-73
  5.4 本章小结  73-74
第六章 全文总结与展望  74-77
  6.1 全文总结  74-75
  6.2 研究展望  75-77
参考文献  77-81
致谢  81-82
在学期间的研究成果及发表的学术论文  82

相似论文

  1. 存储系统中多维元数据索引的高效更新方法研究,TP333
  2. 基于结构化稀疏谱哈希的图像索引算法,TP391.41
  3. 关于XML的关系数据库存储查询技术研究,TP311.13
  4. ARTs-EDB系统的时态数据存储及索引技术研究,TP311.13
  5. 基于数值和名义属性空间数据的轮廓查询技术研究,TP311.13
  6. 图结构数据上的子图查询,TP301.6
  7. 面向基因组重测序的BWT索引压缩算法,TP311.13
  8. P2P网络中的Anytime查询处理,TP393.02
  9. 无线传感器数据库中KNN查询算法研究,TP212.9
  10. CBIR算法测试平台及其相关技术研究,TP391.41
  11. 多核处理器上的并行B+树索引算法研究与实现,TP311.13
  12. 主存数据库中Cache敏感索引机制的研究与实现,TP311.13
  13. 对等视频点播数据分发关键技术研究,TN948.64
  14. 基于XML的数据查询和信息检索集成化系统研究,TP311.52
  15. 对大信息量XML文档查询方法的研究,TP311.11
  16. HLR数据一致性的研究与实现,TP392
  17. 海量数据的高维索引结构研究,TP391.3
  18. 路网中基于RQN树的移动对象索引与查询,TP311.13
  19. 支持最近邻查找的高维空间索引,TP393.01
  20. 时空数据库索引技术研究,TP311.13

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机软件 > 程序设计、软件工程 > 程序设计 > 数据库理论与系统
© 2012 www.xueweilunwen.com