数据库系统原理与应用教程ch11

1、数据库系统原理与应用教程(第二版)第11章 索引和散列技术第1页第第11章章 索引和散列技术索引和散列技术本章概述本章的学习目标 主要内容数据库系统原理与应用教程(第二版)第11章 索引和散列技术第2页本章概述本章概述l学习和掌握了前面的数据库建模和编程内容之后，我们已学习和掌握了前面的数据库建模和编程内容之后，我们已经可以创建和使用数据库了。但是，这只是知其然而不知经可以创建和使用数据库了。但是，这只是知其然而不知其所以然。如果希望创建和使用高效率的数据库，单单掌其所以然。如果希望创建和使用高效率的数据库，单单掌握前面这些内容还是不够的，还需要进一步地学习和掌握握前面这些内容还是不够的，还需

2、要进一步地学习和掌握数据库的一些关键实现技术，知其然更知其所以然。从本数据库的一些关键实现技术，知其然更知其所以然。从本章开始，我们将学习有关数据库实现的内容，例如，学习章开始，我们将学习有关数据库实现的内容，例如，学习索引和散列、查询和并发控制等技术，掌握为什么使用索索引和散列、查询和并发控制等技术，掌握为什么使用索引可以加快数据的检索速度、如何实现引可以加快数据的检索速度、如何实现SQL语句的操作、语句的操作、如何保证多个用户同时使用同一个数据等知识，这些内容如何保证多个用户同时使用同一个数据等知识，这些内容有助于我们深入理解数据库的内部结构，有助于我们建立有助于我们深入理解数据库的内部结

3、构，有助于我们建立高效率、结构合理的数据库模式。高效率、结构合理的数据库模式。l本章将要结合具体的数据库系统向读者全面介绍有关索引本章将要结合具体的数据库系统向读者全面介绍有关索引和散列技术的内容。和散列技术的内容。数据库系统原理与应用教程(第二版)第11章 索引和散列技术第3页本章的学习目标本章的学习目标l了解文件内部数据元组的组织方式；了解文件内部数据元组的组织方式；l理解和掌握索引的基本概念；理解和掌握索引的基本概念；l理解和掌握顺序索引的结构和作用；理解和掌握顺序索引的结构和作用；l理解和掌握平衡树索引文件的结构和作用；理解和掌握平衡树索引文件的结构和作用；l理解和掌握散列技术的概念、

4、类型和作用；理解和掌握散列技术的概念、类型和作用；l了解了解Microsoft SQL Server系统的索引结构。系统的索引结构。数据库系统原理与应用教程(第二版)第11章 索引和散列技术第4页主要内容主要内容11.1 概述概述 11.2 索引技术索引技术 11.3 散列技术散列技术 11.4 Microsoft SQL Server系统中的索引系统中的索引 11.5 本章小结本章小结 数据库系统原理与应用教程(第二版)第11章 索引和散列技术第5页11.1 概述概述l在逻辑上，所有的数据元组在文件中称为在逻辑上，所有的数据元组在文件中称为记录，文件就是纪录的序列。文件是由操记录，文件就是纪

5、录的序列。文件是由操作系统作为一种基本结构提供的。我们知作系统作为一种基本结构提供的。我们知道关系实例就是数据元组的集合，也是给道关系实例就是数据元组的集合，也是给定记录的集合。定记录的集合。l下面我们研究如何在文件中组织这些数据下面我们研究如何在文件中组织这些数据元组或记录。文件组织方式是理解索引和元组或记录。文件组织方式是理解索引和散列技术的基础。散列技术的基础。数据库系统原理与应用教程(第二版)第11章 索引和散列技术第6页文件组织方式文件组织方式 l一般地，可以把文件中记录的组织形式分为四种，即堆文件组织、顺一般地，可以把文件中记录的组织形式分为四种，即堆文件组织、顺序文件组织、散列文

6、件组织和聚集文件组织。序文件组织、散列文件组织和聚集文件组织。l在堆文件组织中，记录可以放在文件中的任何位置。实际上，堆的含在堆文件组织中，记录可以放在文件中的任何位置。实际上，堆的含义就是没有顺序、乱七八糟。一般地，依记录的输入顺序为序，只要义就是没有顺序、乱七八糟。一般地，依记录的输入顺序为序，只要有空间，就可以存储记录。记录的存储顺序与键码没有直接的联系。有空间，就可以存储记录。记录的存储顺序与键码没有直接的联系。删除操作只是在删除的记录旁边增加一个删除标记，新插入的记录总删除操作只是在删除的记录旁边增加一个删除标记，新插入的记录总是排在文件尾。通常一个关系是一个单独的文件。是排在文件尾

7、。通常一个关系是一个单独的文件。l在顺序文件组织中，记录是按照有关键码值的升序或降序的顺序存储在顺序文件组织中，记录是按照有关键码值的升序或降序的顺序存储的。后面将对这种文件组织方式进行详细研究。的。后面将对这种文件组织方式进行详细研究。l在散列文件组织中，需要对每一个记录的同一个属性计算出一个散列在散列文件组织中，需要对每一个记录的同一个属性计算出一个散列函数。散列函数的结果确定了记录的存储顺序。这种技术与散列索引函数。散列函数的结果确定了记录的存储顺序。这种技术与散列索引技术是紧密关联的，本章后面对此内容将详细讨论。技术是紧密关联的，本章后面对此内容将详细讨论。l在聚集文件组织中，一个文件

8、可以存储多个关系的记录。不同关系中在聚集文件组织中，一个文件可以存储多个关系的记录。不同关系中有联系的记录存储在同一个数据块中，这样可以提高系统的查询速度有联系的记录存储在同一个数据块中，这样可以提高系统的查询速度和输入输出速度。和输入输出速度。 数据库系统原理与应用教程(第二版)第11章 索引和散列技术第7页顺序文件组织顺序文件组织 l根据搜索键码值的高根据搜索键码值的高低顺序存储的记录文低顺序存储的记录文件称为顺序文件。在件称为顺序文件。在该文件中，对每一个该文件中，对每一个记录增加了一个指针记录增加了一个指针字段，根据搜索键码字段，根据搜索键码值的大小使用指针把值的大小使用指针把记录链接

9、起来。文件记录链接起来。文件初始建立时，存储记初始建立时，存储记录应该尽可能地使物录应该尽可能地使物理顺序和搜索键码值理顺序和搜索键码值的顺序一致，这样可的顺序一致，这样可以减少访问数据的次以减少访问数据的次数。数。数据库系统原理与应用教程(第二版)第11章 索引和散列技术第8页聚集文件组织聚集文件组织 l在一些小型数据库系统中，数据量很小，系统把在一些小型数据库系统中，数据量很小，系统把每一个关系处理成一个文件。这种文件称为单记每一个关系处理成一个文件。这种文件称为单记录类型文件，文件中每一个记录都是定长的。文录类型文件，文件中每一个记录都是定长的。文件之间是分割开的，没有联系。数据联系需要

10、通件之间是分割开的，没有联系。数据联系需要通过搜索键码值和查询语句来实现。这时，一般的过搜索键码值和查询语句来实现。这时，一般的操作系统可以管理这种文件。随着数据量的增大，操作系统可以管理这种文件。随着数据量的增大，这时需要采用一种新的文件结构，这种文件称为这时需要采用一种新的文件结构，这种文件称为聚集文件。这种文件允许一个文件由多个关系的聚集文件。这种文件允许一个文件由多个关系的记录组成，也称为多记录类型文件。记录组成，也称为多记录类型文件。数据库系统原理与应用教程(第二版)第11章 索引和散列技术第9页主要内容主要内容11.1 概述概述 11.2 索引技术索引技术 11.3 散列技术散列技

11、术 11.4 Microsoft SQL Server系统中的索引系统中的索引 11.5 本章小结本章小结 数据库系统原理与应用教程(第二版)第11章 索引和散列技术第10页11.2 索引技术索引技术l当文件中的记录很少时，系统把这些记录当文件中的记录很少时，系统把这些记录按照顺序读出的效率虽然比较低，但还是按照顺序读出的效率虽然比较低，但还是可以忍受的。可以忍受的。l随着数据量的剧增，在文件中从开始读数随着数据量的剧增，在文件中从开始读数据的查询速度就会大大降低。为了提高查据的查询速度就会大大降低。为了提高查询速度，必须对文件建立索引。询速度，必须对文件建立索引。l下面介绍索引的基本概念和类

12、型。下面介绍索引的基本概念和类型。数据库系统原理与应用教程(第二版)第11章 索引和散列技术第11页基本概念基本概念 l在实际的数据库中，常用的索引类型有两种，即顺序索引在实际的数据库中，常用的索引类型有两种，即顺序索引和散列索引。顺序索引是根据记录的某种排列顺序建立的和散列索引。顺序索引是根据记录的某种排列顺序建立的索引，这是一般意义上的索引技术。根据记录中的某个属索引，这是一般意义上的索引技术。根据记录中的某个属性值，通过散列函数得到的函数值作为存储地址建立起来性值，通过散列函数得到的函数值作为存储地址建立起来的索引称为散列索引。的索引称为散列索引。l对于每一种散列技术，又有许多实现方法，

13、用户可以根据对于每一种散列技术，又有许多实现方法，用户可以根据下面一些因素来选择合适的索引方法：下面一些因素来选择合适的索引方法：访问类型访问类型访问时间访问时间插入时间插入时间删除时间删除时间索引空间开销索引空间开销 数据库系统原理与应用教程(第二版)第11章 索引和散列技术第12页顺序索引顺序索引 l索引文件由两部分构成，即索引和主文件。由于主文件记索引文件由两部分构成，即索引和主文件。由于主文件记录多、数据量大且占据着大量的物理块，因此在主文件中录多、数据量大且占据着大量的物理块，因此在主文件中查找记录的速度非常慢。如果对记录建立索引，那么相对查找记录的速度非常慢。如果对记录建立索引，那

14、么相对主文件而言，索引空间小，因而查找速度快。这里所说的主文件而言，索引空间小，因而查找速度快。这里所说的主文件是记录按照某个属性值大小进行排列的文件。对主主文件是记录按照某个属性值大小进行排列的文件。对主文件可以建立几套不同的索引。文件可以建立几套不同的索引。l如果索引的搜索键码值的顺序与主文件的顺序一致，那么如果索引的搜索键码值的顺序与主文件的顺序一致，那么这种索引称为主索引，也称为聚集索引。一般地，主索引这种索引称为主索引，也称为聚集索引。一般地，主索引的搜索键码往往是文件的主键码。的搜索键码往往是文件的主键码。l如果索引的搜索键码值的顺序与主文件的顺序不一致，那如果索引的搜索键码值的顺

15、序与主文件的顺序不一致，那么这种索引称为辅助索引，也称为非聚集索引。么这种索引称为辅助索引，也称为非聚集索引。数据库系统原理与应用教程(第二版)第11章 索引和散列技术第13页聚集索引聚集索引l当索引的搜索键码值的顺序与主文件的顺序一致，那么这种索引文件当索引的搜索键码值的顺序与主文件的顺序一致，那么这种索引文件称为索引顺序文件。这种文件既适用于随机处理，也适用于顺序处理。称为索引顺序文件。这种文件既适用于随机处理，也适用于顺序处理。下面介绍聚集索引的稠密索引、稀疏索引和多级索引等三种实现方法。下面介绍聚集索引的稠密索引、稀疏索引和多级索引等三种实现方法。l对于主文件中每一个搜索键码值建立一个

16、索引记录对于主文件中每一个搜索键码值建立一个索引记录(索引项索引项)，索引记，索引记录包括搜索键码值和指向具有该值的记录链表中第一个记录的指针。录包括搜索键码值和指向具有该值的记录链表中第一个记录的指针。这种索引称为稠密索引。这种索引称为稠密索引。 l如果在主文件中，若干个搜索键码值建立一个索引记录，那么这种索如果在主文件中，若干个搜索键码值建立一个索引记录，那么这种索引称为稀疏索引。这种索引记录的内容仍和稠密索引一样。引称为稀疏索引。这种索引记录的内容仍和稠密索引一样。 l在如图在如图11-6所示的二级索引示例中，此时外层索引块可以常驻内存，所示的二级索引示例中，此时外层索引块可以常驻内存，

17、在查找记录时索引块只要读一次即可。如果外层索引块的数量比较多，在查找记录时索引块只要读一次即可。如果外层索引块的数量比较多，不能全部存入内存，那么可以对外层索引再建一层外层索引。这时就不能全部存入内存，那么可以对外层索引再建一层外层索引。这时就形成了多级索引技术。形成了多级索引技术。数据库系统原理与应用教程(第二版)第11章 索引和散列技术第14页非聚集索引非聚集索引 l在聚集索引中，可以根据某个搜索键码值查找记在聚集索引中，可以根据某个搜索键码值查找记录。如果需要根据另外一个搜索键码值来寻找主录。如果需要根据另外一个搜索键码值来寻找主文件的记录，那么可以使用非聚集索引方法。在文件的记录，那么

18、可以使用非聚集索引方法。在聚集索引中，具有相同搜索键码值的记录在同一聚集索引中，具有相同搜索键码值的记录在同一个或相邻的物理块中，因此查找速度比较快。但个或相邻的物理块中，因此查找速度比较快。但是，在非聚集索引中，具有相同搜索键码值的记是，在非聚集索引中，具有相同搜索键码值的记录分散在文件的不同地方，因此查找速度比较慢，录分散在文件的不同地方，因此查找速度比较慢，并且查找时无法利用主文件中按照聚集索引建立并且查找时无法利用主文件中按照聚集索引建立起来的指针链。起来的指针链。数据库系统原理与应用教程(第二版)第11章 索引和散列技术第15页B+树索引文件树索引文件 l索引顺序文件的最大缺点在于随

19、着文件的增大，索引查找索引顺序文件的最大缺点在于随着文件的增大，索引查找性能和数据顺序扫描性能都会下降。虽然可以通过对文件性能和数据顺序扫描性能都会下降。虽然可以通过对文件进行重组来提高索引的性能，但是频繁的重组增加了系统进行重组来提高索引的性能，但是频繁的重组增加了系统的负担。的负担。l为了改善索引结构的性能，可以采用多级索引。目前，广为了改善索引结构的性能，可以采用多级索引。目前，广泛应用的一种多级索引技术称为平衡树。泛应用的一种多级索引技术称为平衡树。B+树索引采用树索引采用了平衡树结构，其中每一个叶节点到根的路径长度相同，了平衡树结构，其中每一个叶节点到根的路径长度相同，每个非叶节点有

20、每个非叶节点有n/2n个子节点，其个子节点，其n表示平衡树的阶数。表示平衡树的阶数。lB+树索引是一个多级索引。典型的树索引是一个多级索引。典型的B+树节点结构如图树节点结构如图11-8所示。它最多包含所示。它最多包含n-1个搜索键码值个搜索键码值K1，K2，Kn-1和和n个指针个指针P1，P2，Pn。每一个节点中的索引键码。每一个节点中的索引键码值按照次序存放，即如果值按照次序存放，即如果ij，则，则KiKj。 数据库系统原理与应用教程(第二版)第11章 索引和散列技术第16页主要内容主要内容11.1 概述概述 11.2 索引技术索引技术 11.3 散列技术散列技术 11.4 Microso

21、ft SQL Server系统中的索引系统中的索引 11.5 本章小结本章小结 数据库系统原理与应用教程(第二版)第11章 索引和散列技术第17页11.3 散列技术散列技术l前面提到的顺序文件组织的缺点是必须通前面提到的顺序文件组织的缺点是必须通过索引结构访问数据，且索引的组织空间过索引结构访问数据，且索引的组织空间大，操作时间长。大，操作时间长。l散列技术是一种不必通过索引就能访问数散列技术是一种不必通过索引就能访问数据的方法。据的方法。l把散列技术和索引技术结合起来可以提高把散列技术和索引技术结合起来可以提高查询数据库中数据的效率。查询数据库中数据的效率。数据库系统原理与应用教程(第二版)

22、第11章 索引和散列技术第18页基本概念基本概念 l在散列文件组织中，通过计算所需记录搜在散列文件组织中，通过计算所需记录搜索键码上的一个函数直接获得包含该记录索键码上的一个函数直接获得包含该记录的磁盘块地址。在散列技术中，使用桶表的磁盘块地址。在散列技术中，使用桶表示存储一条或多条记录的一个存储单位。示存储一条或多条记录的一个存储单位。一般地，一个桶就是一个磁盘块，但是也一般地，一个桶就是一个磁盘块，但是也可能大于或小于一个磁盘块。可能大于或小于一个磁盘块。l令令K表示所有搜索键码值的集合，表示所有搜索键码值的集合，B表示所表示所有桶地址的集合，散列函数有桶地址的集合，散列函数h就是一个从就

23、是一个从K到到B的函数。的函数。数据库系统原理与应用教程(第二版)第11章 索引和散列技术第19页散列索引散列索引 l散列方法不仅可以用在文件组织上，而且散列方法不仅可以用在文件组织上，而且还可以用在索引结构的创建上。散列索引还可以用在索引结构的创建上。散列索引是把搜索键码值与指针组合在一起而称为是把搜索键码值与指针组合在一起而称为散列结构的一种索引。散列结构的一种索引。l散列索引的构造方法如下：散列索引的构造方法如下：第一步，为主文件中的每一个搜索键码值建立第一步，为主文件中的每一个搜索键码值建立一个索引记录。一个索引记录。第二步，把这些索引记录组织成散列结构，不第二步，把这些索引记录组织成散列结构，不是稠密索引或稀疏索引。是稠密索引或稀疏索引。数据库系统原理与应用教程(第二版)第11章 索引和散列技术第20页主要内容主要内容11.1 概述概述 11.2 索引技术索引技术 11.3 散列技术散列技术 11.4 Microsoft SQL Server系统中的索引系统中的索引 11.5 本章小结本章小结 数据库系统原理与应用教程(第二版)第11章 索引和散列技术第21页11.4 Microsoft SQL Server系统中系统中的索引的索引lMicrosoft SQL Server系统是一种广泛使系统是一种广泛使用的数据库管理系统