内存数据库索引技术研究+文献综述
时间:2017-03-21 21:12 来源:毕业论文 作者:毕业论文 点击:次
| 摘 要：内存数据库已经成为当今数据库研究的热点领域，在内存数据库中，内存空间极其宝贵，原有的磁盘数据库的索引结构查找时间长且占用空间大，不适用于内存数据库，需研究新的适合内存数据库的索引结构，以提高数据库操作的性能。本课题研究了内存数据库中常见的数组、平衡二叉树、T树、B+树和B-树等索引结构的优缺点，重点描述了B-树的查找、插入和删除过程。研究表明，B-树是目前内存数据库中最广泛使用的索引结构，能提高内存数据库中数据的操作效率。6721 关键词:内存数据库；索引；T树；B-树 Index Technology Research of main Memory Database Abstract:Main memory database,which has become the hot fields in today's database research, the memory space of main memory database is extremely valuable, the index structure of original disk database seeks for a long time and takes up big space, which is not suitable for the main memory database,so as to improve the performance of database operations,the index structure which is suitable for the main memory database must be studied.This topic studies the advantages and disadvantages of the index structures ,such as the common arrays in memory database, balance binary tree, the T tree, B+tree and B-tree and so on, and mainly describes the process of B- tree search, insertion and deletion. Studies have shown that B- tree is the most widely used index structure in the memory database at present, which can improve the operation efficiency of data in main memory database. Key words:Main memory database;index;T tree;B- tree 引 言 数据库诞生近半个世纪后，已经具有成熟的理论基础和商业产品，从传统的数据处理到人工智能、科技计算以CAD等领域都得到了广泛的应用，给由计算机形成的信息社会带来革命性的变化，这些都吸引着众多的研究者痴迷于此，数据库的研究正成为热点研究领域。对于一个国家来说，较大的信息系统都是建立在数据库设计之上，由于数据库具有易于扩充、数据结构化、较高的程序与数据独立性、最低冗余度、易于编制应用程序等优点[1]，目前，数据库的数据信息量的大小、建设规模和使用频度已成为衡量这个国家信息化程度的重要标志。 1．概论 1.1研究背景和意义 传统磁盘关系数据库将主版本放在硬盘上，数据库执行的过程中把数据调入内存，操作完成后将被修改的数据和产生的日志调回硬盘，在这个过程中，需要执行大量的I/O操作，耗费很多时间，不能满足对数据库要求速度快，实时性高的应用领域的需求。随着存储器芯片集成度的提高和价格的降低，内存的容量在不断增大[2]，当前存储容量达到GB的内存产品已比较普遍，人们开始思考将数据库放在内存中运行。内存数据库应用而生，并逐渐成为当今数据库研究的热点，而索引能够极大地提高数据库操作的性能。磁盘数据库系统的瓶颈是磁盘I/O，故查询处理的优化策略主要是减少磁盘的存取次数，并且尽量存储临时结果，以“空间”换“时间”。而在内存数据库中，由于内存空间极其宝贵，其查询处理算法则要极力减少比较次数，并且尽量不存储临时结果，以“时间”换“空间”。在这样的前提下，原有的磁盘数据库的索引结构对内存数据库来说就不再适用了，研究新的适合内存数据库的索引结构也就自然而然的成了研究者关注的问题。 1.2研究现状 常用的磁盘数据库的索引方法有线性索引，树结构索引。线性索引文件被组织成一组简单的关键码和指针对的序列。线性索引文件按照关键码的顺序进行排序，文件中的指针则指向存储在磁盘上的文件记录起始位置或主索引中主码的起始位置。树结构索引主要有两类: 索引顺序存取方法（ISAM）和多层索引树的索引[3]。多层索引树的索引主要包括B树，平衡二叉树，AVL树等。早在20 世纪80 年代, 便有学者开始研究内存数据库的索引。至今, 常用的内存数据库索引结构主要包括数组，平衡二叉树（AVL 树），B树，B-树与B+树，T树，T-tail树，SB树等操作方法[4]。其中，它们具有各自的优点，但是又有其缺点，数组作为索引需要移动大量的数据，AVL树存储利用率低，每一节点只能存储一个数据项，B树及其变种B+树操作性能好，能动态文护，目前内存数据库最广泛使用索引结构的是B-树。 (责任编辑：qin) |