主存数据库中Cache敏感索引机制的研究与实现.pdf

东北大学
硕士学位论文
主存数据库中Cache敏感索引机制的研究与实现
姓名:孙丽梅
申请学位级别:硕士
专业:计算机软件与理论
指导教师:宋宝燕
20050101
东北大学硕士学位论文摘要
主存数据库中敏感索引机制的研究与实现
摘要
近年来,随着计算机芯片技术的不断改进,中央处理器的速度和主
存速度之间的差距逐渐扩大,系统对主存的存取访问成为新的瓶颈。是一种
容量非常小、但速度非常快的静态存储器,设置在和主存之间。由于
中保存着主存中最常使用的数据和指令,因此可以有效地减少的等待
时间。命中率越高,的运算效率就越高。命中率对数据库系统索
引结构的性能影响非常大,尤其是对主存数据库索引结构的性能,更是至关重要。
鉴于此,在主存数据库系统处理过程中,如何提高的命中率,即减少
与主存之间的数据交换次数,提高的运算效率,进而对实时应用提供有效支
持,成为一项至关重要的内容。
本文对敏感技术进行了深入研究,分析了现有
的主存数据库索引结构,并根据“”结构定义方法,在树的基
础上提出了一种适合于主存数据库的敏感索引
结构,可以有效地支持实时应用。由于树的结点大小通常大于块的大小,
因此不能一次被全部命中。树是把原来树结点中的内容根据访问频
率高低划分为“高频”部分和“低频”部分,在结点中只保留“高频”部分,而
将“低频”部分单独保存,这样可以使结点的大小总是小于块的大小,使
一个结点一次就可以被完全命中,从而可以获得比树更高的命中
率,并且不需要使用额外的空间。实验结果表明,在大多数情况下,树的整
体性能与原来的树相比有明显提高。和另一种高效的敏感型主存数据库
索引结构树相比,树与其最好的一种变形一树性能接近,而
使用空间远远小于一树。
关键词索引结构,主存数据库,实时应用,树索
引,树索引
东北大学硕士学位论文
独创性声明
本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果
除加以标注和致谢的地方外,不包含其他人己经发表或撰写过的研究成果,也不包
括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何
贡献均已在论文中作了明确的说明并表示谢意。
学位论文作者签名漪
日期·日
学位论文版权使用授权书
本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规
定即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘,允许论
文被查阅和借阅。本人授权东北大学可以将学位论文的全部或部分内容编入有关
数据库进行检索、交流。
如作者和导师同意网上交流,请在下方签名否则视为不同意。
学位论文作者签名孙丽俩导师签名宋么
签字日期乡签字日期
东北大学硕士学位论文第一章前言
第一章前言
实时主存数据库系统简介
数据库理论与技术的发展极其迅速,其应用日益广泛,在当今的信息社会中,
它几乎无所不在。以关系型为代表的三大经典层次、网状、关系型数据库在
传统的商务和管理的事务型应用领域获得了极大成功,然而它们在现代的非传
统工程和时间关键型应用面前却显得软弱无力,面临着新的严峻的挑战,由此
导致了实时数据库的产生和发展。实时数据库就是
近年来在数据库技术全新发展过程中产生并蓬勃发展起来的数据库领域一个新的
分支。
实时数据库系统就是其数据和事务都
具有定时特性或显式定时限制的数据库系统。系统
的正确性不仅依赖于事务的逻辑结果,而且依赖于该逻辑结果所产生的时间
主存数据库系统又称为内存数据库系统
,是指数据库的主拷贝或工作版本当然也不排除整个数据库常驻于内
存的数据库系统。由于在中,事务的工作数据存在于内存中,因而它
的执行过程中没有内外存的。这样就消除了事务处理的瓶颈问题,因此主
存数据库是支持实时事务的最佳技术。近年来,存储器的容量迅速增长,平
均每个月就翻一番,而成本大幅下降,为计算机配置较大容量的主存己不足为
奇。这使得许多数据库可以直接装入主存中,主存数据库的大范围应用在经济上
更为可行,逐渐成为主流数据库产品。
在主存数据库中,磁盘在正常情况下己经极少甚至消除,其目标由减少磁
盘变为时间和主存空间的高效使用
主存—新的访问瓶颈
最近几年,随着计算机芯片技术的不断改进,运算速度每年提高
平均每个月就翻一番,而主存速度的增长则相对较慢,每年仅增长,如
图执行指令时,会将执行结果放在集成在内部的寄存器中但寄
东北大学硕士学位论文第一章前言
第一章前言
实时主存数据库系统简介
数据库理论与技术的发展极其迅速,其应用日益广泛,在当今的信息社会中,
它几乎无所不在。以关系型为代表的三大经