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

基于红黑树平衡机制的RTDB索引结构的研究与优化

作　者: 李娟
导　师: 王华军
学　校: 成都理工大学
专　业: 计算机软件与理论
关键词: 索引结构平衡机制实时数据库红黑树
分类号: TP311.13
类　型: 硕士论文
年　份: 2012年
下　载: 18次
引　用: 0次
阅　读: 论文下载

内容摘要

现如今实时数据库(RTDB)已获得越来越广泛的应用,实时数据库必须保持数据对象的一致性约束和保证每一个请求到达系统所规定的时间限制。随着系统存储的数据量越来越大,复杂性也越来越高,实时数据库的实时性能会下降,那如何提高实时数据库的整体性能已经成为研究者的研究重点。其中索引是常用的提高数据库性能的方法之一,通常在实时数据库(RTDB)(?)户是以内存数据库(MMDB)作为底层支持来提高实时性能。实时数据库系统的“瓶颈”不再是外存的I/0,因此算法的设计目标成为内存空间和CPU的高效使用。传统磁盘数据库(DRDB)的索引机制不能满足内存空间的高效利用和高存取性能。针对上述问题设计具有现代应用特征的内存数据的索引结构,已经成为实时数据库系统研究的重点。经典的索引机制主要分为三大类：一类是基于HASH函数对数据随机组织的索引机制；另一类是基于查询树对数据有序组织的索引机制；最后一类ChanboRyu等提出的综合HASH表和查询树特点的混合索机制hybrid—HT。经过分析这些传统的索引机制在内存环境下都有各自的优势和缺点。因而设计一种合适的实时数据库索引机制就有了突出的意义。本文根据实时数据库索引的研究现状,针对T树在系统频繁的执行结点的插入和删除操作时需要不断进行平衡旋转操作,导致T树的效率大大降低。以T树和红黑树数据结构的技术特点为基础,为了最大程度的提高实时数据库的实时性能,在此基础上提出了一种基于红黑树平衡机制的RB-T树数据结构算法模型,研究了RB-T树索引数据结构的设计思路、实现过程和基本操作算法。本文主要取得了如下的研究成果：(1)研究了实时数据库的概念和相关技术,主要包括实时数据库的体系结构、内存数据库、实时事物处理调度和并发控制。(2)研究了几种常用的索引结构,重点分析了这几种索引结构应用于实时数据库中的优点和不足之处。包括数组、哈希索引、B树、T树和hvbrid-HT索引。(3)研究了红黑树数据结构的特点和其高效的平衡原理机制。(4)提出了一种基于红黑树平衡机制的RB-T树数据结构算法模型,是一种把红黑树中的平衡原理与T树结点结构相结合的算法模型。(5)最后对RB-T树算法模型和T树进行了相应的性能分析和对比实验测试,理论结合实际,实验验证理论。并在此基础上做了以下创新：提出了一种基于红黑树平衡机制的RB-T树算法模型。RB-T树算法模型是指把红黑树中的平衡原理与T树结点结构相结合,并且对每个结点进行了后序线索化。考虑了时间代价和空间代价两方面的因素,以求获得更好的数据库实时性能和最省的内存空间。

全文目录

摘要  4-6
ABSTRACT  6-10
第1章绪论  10-15
  1.1 研究背景与意义  10-11
  1.2 国内外研究现状  11-12
  1.3 论文的主要研究内容  12-13
  1.4 论文的组织结构  13-15
第2章实时数据库研究  15-27
  2.1 实时数据库  15-17
    2.1.1 实时数据库(RTDB)的特性  15-16
    2.1.2 RTDB的实时数据特点  16
    2.1.3 实时数据库RTDB的体系结构  16-17
  2.2 内存数据库研究  17-22
    2.2.1 实时数据库与内存数据库  17-18
    2.2.2 内存数据库MMDB  18-20
    2.2.4 MMDB与共享内存技术  20-22
  2.3 实时事务处理调度与并发控制  22-25
    2.3.1 实时事务分类  22-23
    2.3.2 实时事务处理流程  23
    2.3.3 实时事务调度策略  23-24
    2.3.4 实时并发控制  24-25
  2.4 实时内存数据库的索引  25
  本章小结  25-27
第3章常用的几种索引机制研究  27-38
  3.1 数组索引  27
  3.2 哈希(HASH)索引  27-29
    3.2.1 哈希索引介绍  27-28
    3.2.2 常见的几种HASH索引分析  28-29
  3.3 平衡二叉树(AVL)索引  29-32
    3.3.1 AVL树的定义  29-31
    3.3.2 AVL树的基本操作  31-32
  3.4 B树和B+树索引  32-33
  3.5 T树索引  33-36
  3.6 hybrid-HT索引  36-37
  本章小结  37-38
第4章改进索引机制的研究与分析  38-55
  4.1 红黑树  38-44
    4.1.1 红黑树定义  38-39
    4.1.2 红黑树插入操作分析  39-41
    4.1.3 红黑树删除操作分析  41-44
    4.1.4 红黑树性能分析  44
  4.2 改进的T树索引  44-52
    4.2.1 改进T树索引机制的定义  44-46
    4.2.2 RB-T树等值查询和区间查询算法描述  46-49
    4.2.3 RB-T树插入操作算法描述  49-51
    4.2.4 RB-T树删除操作算法描述  51-52
  4.3 RB-T树索引机制性能分析  52-54
    4.3.1 时间复杂度  52-53
    4.3.2 空间复杂度  53-54
  本章小结  54-55
第5章性能测试与分析  55-62
  5.1 测试描述  55-57
  5.2 性能测试分析  57-61
  5.3 测试结论  61
  本章小结  61-62
总结与展望  62-64
致谢  64-65
参考文献  65-68
攻读学位期间发表的学术论文  68

基于红黑树平衡机制的RTDB索引结构的研究与优化

内容摘要

全文目录

相似论文