论文部分内容阅读
现如今实时数据库(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树结点结构相结合,并且对每个结点进行了后序线索化。考虑了时间代价和空间代价两方面的因素,以求获得更好的数据库实时性能和最省的内存空间。