数据库系统原理与应用-索引和散列技术.ppt

第11章 索引和散列技术 本章概述 学习和掌握了前面的数据库建模和编程内容之后，我们已经可以创建和使用数据库了。但是，这只是知其然而不知其所以然。如果希望创建和使用高效率的数据库，单单掌握前面这些内容还是不够的，还需要进一步地学习和掌握数据库的一些关键实现技术，知其然更知其所以然。从本章开始，我们将学习有关数据库实现的内容，例如，学习索引和散列、查询和并发控制等技术，掌握为什么使用索引可以加快数据的检索速度、如何实现SQL语句的操作、如何保证多个用户同时使用同一个数据等知识，这些内容有助于我们深入理解数据库的内部结构，有助于我们建立高效率、结构合理的数据库模式。 本章将要结合具体的数据库系统向读者全面介绍有关索引和散列技术的内容。 本章的学习目标 了解文件内部数据元组的组织方式； 理解和掌握索引的基本概念； 理解和掌握顺序索引的结构和作用； 理解和掌握平衡树索引文件的结构和作用； 理解和掌握散列技术的概念、类型和作用； 了解Microsoft SQL Server系统的索引结构。 主要内容 11.1 概述 11.2 索引技术 11.3 散列技术 11.4 Microsoft SQL Server系统中的索引 11.5 本章小结 11.1 概述 在逻辑上，所有的数据元组在文件中称为记录，文件就是纪录的序列。文件是由操作系统作为一种基本结构提供的。我们知道关系实例就是数据元组的集合，也是给定记录的集合。 下面我们研究如何在文件中组织这些数据元组或记录。文件组织方式是理解索引和散列技术的基础。 文件组织方式 一般地，可以把文件中记录的组织形式分为四种，即堆文件组织、顺序文件组织、散列文件组织和聚集文件组织。 在堆文件组织中，记录可以放在文件中的任何位置。实际上，堆的含义就是没有顺序、乱七八糟。一般地，依记录的输入顺序为序，只要有空间，就可以存储记录。记录的存储顺序与键码没有直接的联系。删除操作只是在删除的记录旁边增加一个删除标记，新插入的记录总是排在文件尾。通常一个关系是一个单独的文件。 在顺序文件组织中，记录是按照有关键码值的升序或降序的顺序存储的。后面将对这种文件组织方式进行详细研究。 在散列文件组织中，需要对每一个记录的同一个属性计算出一个散列函数。散列函数的结果确定了记录的存储顺序。这种技术与散列索引技术是紧密关联的，本章后面对此内容将详细讨论。 在聚集文件组织中，一个文件可以存储多个关系的记录。不同关系中有联系的记录存储在同一个数据块中，这样可以提高系统的查询速度和输入输出速度。 顺序文件组织 根据有哪些信誉好的足球投注网站键码值的高低顺序存储的记录文件称为顺序文件。在该文件中，对每一个记录增加了一个指针字段，根据有哪些信誉好的足球投注网站键码值的大小使用指针把记录链接起来。文件初始建立时，存储记录应该尽可能地使物理顺序和有哪些信誉好的足球投注网站键码值的顺序一致，这样可以减少访问数据的次数。 聚集文件组织 在一些小型数据库系统中，数据量很小，系统把每一个关系处理成一个文件。这种文件称为单记录类型文件，文件中每一个记录都是定长的。文件之间是分割开的，没有联系。数据联系需要通过有哪些信誉好的足球投注网站键码值和查询语句来实现。这时，一般的操作系统可以管理这种文件。随着数据量的增大，这时需要采用一种新的文件结构，这种文件称为聚集文件。这种文件允许一个文件由多个关系的记录组成，也称为多记录类型文件。 11.2 索引技术 当文件中的记录很少时，系统把这些记录按照顺序读出的效率虽然比较低，但还是可以忍受的。 随着数据量的剧增，在文件中从开始读数据的查询速度就会大大降低。为了提高查询速度，必须对文件建立索引。 下面介绍索引的基本概念和类型。 基本概念 在实际的数据库中，常用的索引类型有两种，即顺序索引和散列索引。顺序索引是根据记录的某种排列顺序建立的索引，这是一般意义上的索引技术。根据记录中的某个属性值，通过散列函数得到的函数值作为存储地址建立起来的索引称为散列索引。 对于每一种散列技术，又有许多实现方法，用户可以根据下面一些因素来选择合适的索引方法： 访问类型 访问时间 插入时间 删除时间 索引空间开销 顺序索引 索引文件由两部分构成，即索引和主文件。由于主文件记录多、数据量大且占据着大量的物理块，因此在主文件中查找记录的速度非常慢。如果对记录建立索引，那么相对主文件而言，索引空间小，因而查找速度快。这里所说的主文件是记录按照某个属性值大小进行排列的文件。对主文件可以建立几套不同的索引。 如果索引的有哪些信誉好的足球投注网站键码值的顺序与主文件的顺序一致，那么这种索引称为主索引，也称为聚集索引。一般地，主索引的有哪些信誉好的足球投注网站键码往往是文件的主键码。 如果索引的有哪些信誉好的足球投注网站键码值的顺序与主文件的顺序不一致，那么这种索引称为辅助索引，也称为非聚集索引。 聚集索引 当索引的有哪些信誉好的足球投注网站键码值的顺序与主文件的顺序一致，那么这种索引文件