数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 1页第 11章 索引和散列技术本章概述本章的学习目标主要内容数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 2页本章概述
学习和掌握了前面的数据库建模和编程内容之后，我们已经可以创建和使用数据库了。但是，这只是知其然而不知其所以然。如果希望创建和使用高效率的数据库，单单掌握前面这些内容还是不够的，还需要进一步地学习和掌握数据库的一些关键实现技术，知其然更知其所以然。从本章开始，我们将学习有关数据库实现的内容，例如，学习索引和散列、查询和并发控制等技术，掌握为什么使用索引可以加快数据的检索速度、如何实现 SQL语句的操作、
如何保证多个用户同时使用同一个数据等知识，这些内容有助于我们深入理解数据库的内部结构，有助于我们建立高效率、结构合理的数据库模式。
本章将要结合具体的数据库系统向读者全面介绍有关索引和散列技术的内容。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 3页本章的学习目标
了解文件内部数据元组的组织方式；
理解和掌握索引的基本概念；
理解和掌握顺序索引的结构和作用；
理解和掌握平衡树索引文件的结构和作用；
理解和掌握散列技术的概念、类型和作用；
了解 Microsoft SQL Server系统的索引结构。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 4页主要内容
11.1 概述
11.2 索引技术
11.3 散列技术
11.4 Microsoft SQL Server系统中的索引
11.5 本章小结数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 5页
11.1 概述
在逻辑上，所有的数据元组在文件中称为记录，文件就是纪录的序列。文件是由操作系统作为一种基本结构提供的。我们知道关系实例就是数据元组的集合，也是给定记录的集合。
下面我们研究如何在文件中组织这些数据元组或记录。文件组织方式是理解索引和散列技术的基础。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 6页文件组织方式
一般地，可以把文件中记录的组织形式分为四种，即堆文件组织、顺序文件组织、散列文件组织和聚集文件组织。
在堆文件组织中，记录可以放在文件中的任何位置。实际上，堆的含义就是没有顺序、乱七八糟。一般地，依记录的输入顺序为序，只要有空间，就可以存储记录。记录的存储顺序与键码没有直接的联系。
删除操作只是在删除的记录旁边增加一个删除标记，新插入的记录总是排在文件尾。通常一个关系是一个单独的文件。
在顺序文件组织中，记录是按照有关键码值的升序或降序的顺序存储的。后面将对这种文件组织方式进行详细研究。
在散列文件组织中，需要对每一个记录的同一个属性计算出一个散列函数。散列函数的结果确定了记录的存储顺序。这种技术与散列索引技术是紧密关联的，本章后面对此内容将详细讨论。
在聚集文件组织中，一个文件可以存储多个关系的记录。不同关系中有联系的记录存储在同一个数据块中，这样可以提高系统的查询速度和输入输出速度。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 7页顺序文件组织
根据搜索键码值的高低顺序存储的记录文件称为顺序文件。在该文件中，对每一个记录增加了一个指针字段，根据搜索键码值的大小使用指针把记录链接起来。文件初始建立时，存储记录应该尽可能地使物理顺序和搜索键码值的顺序一致，这样可以减少访问数据的次数。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 8页聚集文件组织
在一些小型数据库系统中，数据量很小，系统把每一个关系处理成一个文件。这种文件称为单记录类型文件，文件中每一个记录都是定长的。文件之间是分割开的，没有联系。数据联系需要通过搜索键码值和查询语句来实现。这时，一般的操作系统可以管理这种文件。随着数据量的增大，
这时需要采用一种新的文件结构，这种文件称为聚集文件。这种文件允许一个文件由多个关系的记录组成，也称为多记录类型文件。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 9页主要内容
11.1 概述
11.2 索引技术
11.3 散列技术
11.4 Microsoft SQL Server系统中的索引
11.5 本章小结数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 10页
11.2 索引技术
当文件中的记录很少时，系统把这些记录按照顺序读出的效率虽然比较低，但还是可以忍受的。
随着数据量的剧增，在文件中从开始读数据的查询速度就会大大降低。为了提高查询速度，必须对文件建立索引。
下面介绍索引的基本概念和类型。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 11页基本概念
在实际的数据库中，常用的索引类型有两种，即顺序索引和散列索引。顺序索引是根据记录的某种排列顺序建立的索引，这是一般意义上的索引技术。根据记录中的某个属性值，通过散列函数得到的函数值作为存储地址建立起来的索引称为散列索引。
对于每一种散列技术，又有许多实现方法，用户可以根据下面一些因素来选择合适的索引方法：
访问类型
访问时间
插入时间
删除时间
索引空间开销数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 12页顺序索引
索引文件由两部分构成，即索引和主文件。由于主文件记录多、数据量大且占据着大量的物理块，因此在主文件中查找记录的速度非常慢。如果对记录建立索引，那么相对主文件而言，索引空间小，因而查找速度快。这里所说的主文件是记录按照某个属性值大小进行排列的文件。对主文件可以建立几套不同的索引。
如果索引的搜索键码值的顺序与主文件的顺序一致，那么这种索引称为主索引，也称为聚集索引。一般地，主索引的搜索键码往往是文件的主键码。
如果索引的搜索键码值的顺序与主文件的顺序不一致，那么这种索引称为辅助索引，也称为非聚集索引。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 13页聚集索引
当索引的搜索键码值的顺序与主文件的顺序一致，那么这种索引文件称为索引顺序文件。这种文件既适用于随机处理，也适用于顺序处理。下面介绍聚集索引的稠密索引、稀疏索引和多级索引等三种实现方法。
对于主文件中每一个搜索键码值建立一个索引记录 (索引项 )，索引记录包括搜索键码值和指向具有该值的记录链表中第一个记录的指针。这种索引称为稠密索引。
如果在主文件中，若干个搜索键码值建立一个索引记录，那么这种索引称为稀疏索引。这种索引记录的内容仍和稠密索引一样。
在如图 11-6所示的二级索引示例中，此时外层索引块可以常驻内存，
在查找记录时索引块只要读一次即可。如果外层索引块的数量比较多，
不能全部存入内存，那么可以对外层索引再建一层外层索引。这时就形成了多级索引技术。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 14页非聚集索引
在聚集索引中，可以根据某个搜索键码值查找记录。如果需要根据另外一个搜索键码值来寻找主文件的记录，那么可以使用非聚集索引方法。在聚集索引中，具有相同搜索键码值的记录在同一个或相邻的物理块中，因此查找速度比较快。但是，在非聚集索引中，具有相同搜索键码值的记录分散在文件的不同地方，因此查找速度比较慢，
并且查找时无法利用主文件中按照聚集索引建立起来的指针链。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 15页
B+树索引文件
索引顺序文件的最大缺点在于随着文件的增大，索引查找性能和数据顺序扫描性能都会下降。虽然可以通过对文件进行重组来提高索引的性能，但是频繁的重组增加了系统的负担。
为了改善索引结构的性能，可以采用多级索引。目前，广泛应用的一种多级索引技术称为平衡树。 B+树索引采用了平衡树结构，其中每一个叶节点到根的路径长度相同，
每个非叶节点有 [n/2]~n个子节点，其 n表示平衡树的阶数。
B+树索引是一个多级索引。典型的 B+树节点结构如图 11-
8所示。它最多包含 n-1个搜索键码值 K1,K2,…,Kn-1
和 n个指针 P1,P2,…,Pn。每一个节点中的索引键码值按照次序存放，即如果 i<j，则 Ki<Kj。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 16页主要内容
11.1 概述
11.2 索引技术
11.3 散列技术
11.4 Microsoft SQL Server系统中的索引
11.5 本章小结数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 17页
11.3 散列技术
前面提到的顺序文件组织的缺点是必须通过索引结构访问数据，且索引的组织空间大，操作时间长。
散列技术是一种不必通过索引就能访问数据的方法。
把散列技术和索引技术结合起来可以提高查询数据库中数据的效率。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 18页基本概念
在散列文件组织中，通过计算所需记录搜索键码上的一个函数直接获得包含该记录的磁盘块地址。在散列技术中，使用桶表示存储一条或多条记录的一个存储单位。
一般地，一个桶就是一个磁盘块，但是也可能大于或小于一个磁盘块。
令 K表示所有搜索键码值的集合,B表示所有桶地址的集合，散列函数 h就是一个从 K
到 B的函数。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 19页散列索引
散列方法不仅可以用在文件组织上，而且还可以用在索引结构的创建上。散列索引是把搜索键码值与指针组合在一起而称为散列结构的一种索引。
散列索引的构造方法如下：
第一步，为主文件中的每一个搜索键码值建立一个索引记录。
第二步，把这些索引记录组织成散列结构，不是稠密索引或稀疏索引。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 20页主要内容
11.1 概述
11.2 索引技术
11.3 散列技术
11.4 Microsoft SQL Server系统中的索引
11.5 本章小结数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 21页
11.4 Microsoft SQL Server系统中的索引
Microsoft SQL Server系统是一种广泛使用的数据库管理系统，其索引结构代表了当今数据库技术中索引技术的最新发展状况。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 22页索引类型
在 Microsoft SQL Server系统中，根据索引的顺序与数据表的物理顺序是否相同，
可以把索引分成两种类型。一种是数据表的物理顺序与索引顺序相同的聚集索引，
另一种是数据表的物理顺序与索引顺序不相同的非聚集索引。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 23页创建索引的方法
在 Microsoft SQL Server系统中，创建索引的方法可以分为直接方法和间接方法。
直接创建索引的方法就是使用命令和工具直接创建索引。间接创建索引就是通过创建其他对象而附加创建了索引，例如，在表中定义主键码约束或者唯一性键码约束时，同时也创建了索引。虽然，这两种方法都可以创建索引，但是，它们创建索引的具体内容是有区别的。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 24页主要内容
11.1 概述
11.2 索引技术
11.3 散列技术
11.4 Microsoft SQL Server系统中的索引
11.5 本章小结
学习和掌握了前面的数据库建模和编程内容之后，我们已经可以创建和使用数据库了。但是，这只是知其然而不知其所以然。如果希望创建和使用高效率的数据库，单单掌握前面这些内容还是不够的，还需要进一步地学习和掌握数据库的一些关键实现技术，知其然更知其所以然。从本章开始，我们将学习有关数据库实现的内容，例如，学习索引和散列、查询和并发控制等技术，掌握为什么使用索引可以加快数据的检索速度、如何实现 SQL语句的操作、
如何保证多个用户同时使用同一个数据等知识，这些内容有助于我们深入理解数据库的内部结构，有助于我们建立高效率、结构合理的数据库模式。
本章将要结合具体的数据库系统向读者全面介绍有关索引和散列技术的内容。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 3页本章的学习目标
了解文件内部数据元组的组织方式；
理解和掌握索引的基本概念；
理解和掌握顺序索引的结构和作用；
理解和掌握平衡树索引文件的结构和作用；
理解和掌握散列技术的概念、类型和作用；
了解 Microsoft SQL Server系统的索引结构。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 4页主要内容
11.1 概述
11.2 索引技术
11.3 散列技术
11.4 Microsoft SQL Server系统中的索引
11.5 本章小结数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 5页
11.1 概述
在逻辑上，所有的数据元组在文件中称为记录，文件就是纪录的序列。文件是由操作系统作为一种基本结构提供的。我们知道关系实例就是数据元组的集合，也是给定记录的集合。
下面我们研究如何在文件中组织这些数据元组或记录。文件组织方式是理解索引和散列技术的基础。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 6页文件组织方式
一般地，可以把文件中记录的组织形式分为四种，即堆文件组织、顺序文件组织、散列文件组织和聚集文件组织。
在堆文件组织中，记录可以放在文件中的任何位置。实际上，堆的含义就是没有顺序、乱七八糟。一般地，依记录的输入顺序为序，只要有空间，就可以存储记录。记录的存储顺序与键码没有直接的联系。
删除操作只是在删除的记录旁边增加一个删除标记，新插入的记录总是排在文件尾。通常一个关系是一个单独的文件。
在顺序文件组织中，记录是按照有关键码值的升序或降序的顺序存储的。后面将对这种文件组织方式进行详细研究。
在散列文件组织中，需要对每一个记录的同一个属性计算出一个散列函数。散列函数的结果确定了记录的存储顺序。这种技术与散列索引技术是紧密关联的，本章后面对此内容将详细讨论。
在聚集文件组织中，一个文件可以存储多个关系的记录。不同关系中有联系的记录存储在同一个数据块中，这样可以提高系统的查询速度和输入输出速度。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 7页顺序文件组织
根据搜索键码值的高低顺序存储的记录文件称为顺序文件。在该文件中，对每一个记录增加了一个指针字段，根据搜索键码值的大小使用指针把记录链接起来。文件初始建立时，存储记录应该尽可能地使物理顺序和搜索键码值的顺序一致，这样可以减少访问数据的次数。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 8页聚集文件组织
在一些小型数据库系统中，数据量很小，系统把每一个关系处理成一个文件。这种文件称为单记录类型文件，文件中每一个记录都是定长的。文件之间是分割开的，没有联系。数据联系需要通过搜索键码值和查询语句来实现。这时，一般的操作系统可以管理这种文件。随着数据量的增大，
这时需要采用一种新的文件结构，这种文件称为聚集文件。这种文件允许一个文件由多个关系的记录组成，也称为多记录类型文件。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 9页主要内容
11.1 概述
11.2 索引技术
11.3 散列技术
11.4 Microsoft SQL Server系统中的索引
11.5 本章小结数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 10页
11.2 索引技术
当文件中的记录很少时，系统把这些记录按照顺序读出的效率虽然比较低，但还是可以忍受的。
随着数据量的剧增，在文件中从开始读数据的查询速度就会大大降低。为了提高查询速度，必须对文件建立索引。
下面介绍索引的基本概念和类型。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 11页基本概念
在实际的数据库中，常用的索引类型有两种，即顺序索引和散列索引。顺序索引是根据记录的某种排列顺序建立的索引，这是一般意义上的索引技术。根据记录中的某个属性值，通过散列函数得到的函数值作为存储地址建立起来的索引称为散列索引。
对于每一种散列技术，又有许多实现方法，用户可以根据下面一些因素来选择合适的索引方法：
访问类型
访问时间
插入时间
删除时间
索引空间开销数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 12页顺序索引
索引文件由两部分构成，即索引和主文件。由于主文件记录多、数据量大且占据着大量的物理块，因此在主文件中查找记录的速度非常慢。如果对记录建立索引，那么相对主文件而言，索引空间小，因而查找速度快。这里所说的主文件是记录按照某个属性值大小进行排列的文件。对主文件可以建立几套不同的索引。
如果索引的搜索键码值的顺序与主文件的顺序一致，那么这种索引称为主索引，也称为聚集索引。一般地，主索引的搜索键码往往是文件的主键码。
如果索引的搜索键码值的顺序与主文件的顺序不一致，那么这种索引称为辅助索引，也称为非聚集索引。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 13页聚集索引
当索引的搜索键码值的顺序与主文件的顺序一致，那么这种索引文件称为索引顺序文件。这种文件既适用于随机处理，也适用于顺序处理。下面介绍聚集索引的稠密索引、稀疏索引和多级索引等三种实现方法。
对于主文件中每一个搜索键码值建立一个索引记录 (索引项 )，索引记录包括搜索键码值和指向具有该值的记录链表中第一个记录的指针。这种索引称为稠密索引。
如果在主文件中，若干个搜索键码值建立一个索引记录，那么这种索引称为稀疏索引。这种索引记录的内容仍和稠密索引一样。
在如图 11-6所示的二级索引示例中，此时外层索引块可以常驻内存，
在查找记录时索引块只要读一次即可。如果外层索引块的数量比较多，
不能全部存入内存，那么可以对外层索引再建一层外层索引。这时就形成了多级索引技术。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 14页非聚集索引
在聚集索引中，可以根据某个搜索键码值查找记录。如果需要根据另外一个搜索键码值来寻找主文件的记录，那么可以使用非聚集索引方法。在聚集索引中，具有相同搜索键码值的记录在同一个或相邻的物理块中，因此查找速度比较快。但是，在非聚集索引中，具有相同搜索键码值的记录分散在文件的不同地方，因此查找速度比较慢，
并且查找时无法利用主文件中按照聚集索引建立起来的指针链。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 15页
B+树索引文件
索引顺序文件的最大缺点在于随着文件的增大，索引查找性能和数据顺序扫描性能都会下降。虽然可以通过对文件进行重组来提高索引的性能，但是频繁的重组增加了系统的负担。
为了改善索引结构的性能，可以采用多级索引。目前，广泛应用的一种多级索引技术称为平衡树。 B+树索引采用了平衡树结构，其中每一个叶节点到根的路径长度相同，
每个非叶节点有 [n/2]~n个子节点，其 n表示平衡树的阶数。
B+树索引是一个多级索引。典型的 B+树节点结构如图 11-
8所示。它最多包含 n-1个搜索键码值 K1,K2,…,Kn-1
和 n个指针 P1,P2,…,Pn。每一个节点中的索引键码值按照次序存放，即如果 i<j，则 Ki<Kj。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 16页主要内容
11.1 概述
11.2 索引技术
11.3 散列技术
11.4 Microsoft SQL Server系统中的索引
11.5 本章小结数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 17页
11.3 散列技术
前面提到的顺序文件组织的缺点是必须通过索引结构访问数据，且索引的组织空间大，操作时间长。
散列技术是一种不必通过索引就能访问数据的方法。
把散列技术和索引技术结合起来可以提高查询数据库中数据的效率。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 18页基本概念
在散列文件组织中，通过计算所需记录搜索键码上的一个函数直接获得包含该记录的磁盘块地址。在散列技术中，使用桶表示存储一条或多条记录的一个存储单位。
一般地，一个桶就是一个磁盘块，但是也可能大于或小于一个磁盘块。
令 K表示所有搜索键码值的集合,B表示所有桶地址的集合，散列函数 h就是一个从 K
到 B的函数。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 19页散列索引
散列方法不仅可以用在文件组织上，而且还可以用在索引结构的创建上。散列索引是把搜索键码值与指针组合在一起而称为散列结构的一种索引。
散列索引的构造方法如下：
第一步，为主文件中的每一个搜索键码值建立一个索引记录。
第二步，把这些索引记录组织成散列结构，不是稠密索引或稀疏索引。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 20页主要内容
11.1 概述
11.2 索引技术
11.3 散列技术
11.4 Microsoft SQL Server系统中的索引
11.5 本章小结数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 21页
11.4 Microsoft SQL Server系统中的索引
Microsoft SQL Server系统是一种广泛使用的数据库管理系统，其索引结构代表了当今数据库技术中索引技术的最新发展状况。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 22页索引类型
在 Microsoft SQL Server系统中，根据索引的顺序与数据表的物理顺序是否相同，
可以把索引分成两种类型。一种是数据表的物理顺序与索引顺序相同的聚集索引，
另一种是数据表的物理顺序与索引顺序不相同的非聚集索引。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 23页创建索引的方法
在 Microsoft SQL Server系统中，创建索引的方法可以分为直接方法和间接方法。
直接创建索引的方法就是使用命令和工具直接创建索引。间接创建索引就是通过创建其他对象而附加创建了索引，例如，在表中定义主键码约束或者唯一性键码约束时，同时也创建了索引。虽然，这两种方法都可以创建索引，但是，它们创建索引的具体内容是有区别的。
数据库系统原理与应用教程 (第二版 ) 第 11章 索引和散列技术 第 24页主要内容
11.1 概述
11.2 索引技术
11.3 散列技术
11.4 Microsoft SQL Server系统中的索引
11.5 本章小结
