第11章索引和散列技术 本章概迷 本章的学习目标 至要内容 数据库系统原理与应用教程(第二版) 第11章索引和散列技术 第1页
数据库系统原理与应用教程(第二版) 第11章 索引和散列技术 第1页 第11章 索引和散列技术 本章概述 本章的学习目标 主要内容
本章概述 学习和掌握了前面的数据库建模和编程内容之后,我们已 经可以创建和使用数据库了。但是,这只是知其然而不知 基所以然。如果希望创建和使用高效率的数据库,单单掌 握前面这些内容还是不够的,还需要进一步地学习和掌握 数据库的一些关键实现技术,知其然更知其所以然。从本 章开始,我们将学习有关数据库实现的内容,例如,学习 索引和教烈№甕沏和并发制等接术-掌握沟什么德甩索 如何保证多个用户同时使用同一个数据等知识,这些内容 有助于我们深入理解数据產的内部结构,有助于我们建立 高效率、结构合理的数据库模式。 本章将要结合具体的数据库系统向读者全面介绍有关索引 数据库系统原理与应用教程(第二版) 第11章索引和散列技术 第2页
数据库系统原理与应用教程(第二版) 第11章 索引和散列技术 第2页 本章概述 ⚫ 学习和掌握了前面的数据库建模和编程内容之后，我们已 经可以创建和使用数据库了。但是，这只是知其然而不知 其所以然。如果希望创建和使用高效率的数据库，单单掌 握前面这些内容还是不够的，还需要进一步地学习和掌握 数据库的一些关键实现技术，知其然更知其所以然。从本 章开始，我们将学习有关数据库实现的内容，例如，学习 索引和散列、查询和并发控制等技术，掌握为什么使用索 引可以加快数据的检索速度、如何实现SQL语句的操作、 如何保证多个用户同时使用同一个数据等知识，这些内容 有助于我们深入理解数据库的内部结构，有助于我们建立 高效率、结构合理的数据库模式。 ⚫ 本章将要结合具体的数据库系统向读者全面介绍有关索引 和散列技术的内容
本章的学习目标 ●了解文件内部数据元组的组织方式; 理解和掌握索引的基本概念; ●理解和掌握顺序索引的结构和作用; ●理解和掌握平衡树索引文件的结构和作用 ●理解和掌握散列技术的概念、类型和作用; ●了解 Microsoft SQL Server系统的索引结构。 数据库系统原理与应用教程(第二版) 第11章索引和散列技术 第3页
数据库系统原理与应用教程(第二版) 第11章 索引和散列技术 第3页 本章的学习目标 ⚫ 了解文件内部数据元组的组织方式； ⚫ 理解和掌握索引的基本概念； ⚫ 理解和掌握顺序索引的结构和作用； ⚫ 理解和掌握平衡树索引文件的结构和作用； ⚫ 理解和掌握散列技术的概念、类型和作用； ⚫ 了解Microsoft SQL Server系统的索引结构
主要内容 111概述 112索引技术 113散列技术 114 Microsoft SQL Server系统中的索引 115本章小结 数据库系统原理与应用教程(第二版) 第11章索引和散列技术 第4页
数据库系统原理与应用教程(第二版) 第11章 索引和散列技术 第4页 主要内容 11.1 概述 11.2 索引技术 11.3 散列技术 11.4 Microsoft SQL Server系统中的索引 11.5 本章小结
11.1概述 ●在逻辑上,所有的数据元组在文件中称为 记录,文件就是纪录的序列。文件是由操 作系统作为一种基本结构提供的。我们知 道关系实例就是数据元组的集合,也是给 定记录的集合。 ●下面我们研究如何在文件中组织这些数据 元组或记录。文件组织方式是理解索引和 散列技术的基础。 数据库系统原理与应用教程(第二版) 第11章索引和散列技术 第5页
数据库系统原理与应用教程(第二版) 第11章 索引和散列技术 第5页 11.1 概述 ⚫ 在逻辑上，所有的数据元组在文件中称为 记录，文件就是纪录的序列。文件是由操 作系统作为一种基本结构提供的。我们知 道关系实例就是数据元组的集合，也是给 定记录的集合。 ⚫ 下面我们研究如何在文件中组织这些数据 元组或记录。文件组织方式是理解索引和 散列技术的基础
文件组织方式 般 可以把文件中记录的组织形式分为四种,即堆文件组织、顺 序父件组织、散列文件组续和聚集攴件组纹。 在堆吝件组织中,记录可以放在文件中的任何位買。实际上,堆的含 文就是没有顺序、乱七八糟。一般地,依记录的输入颀序为序,只要 有空间就可以存储记录。记录的存储顺序与键码没有直接的联系 型输操作星量在擱除的误圣爱迄增架删除桠记,新插入的记录总 在顺序文件组级中 是按照有关键码值的升序或降序的顺序存储 的。后面将对这种文件组织方式进行详细研究。 在散列文件组织中,需要对每一个记录的同一个属性计算出一个散列 顺序。这种技术与散列索引 技术是紧密关联的,本章后面对此閃容将详细讨论 在聚集文件组织中,二个文件可以存储多个关系的记录。不同关系 有联系的记录在储在同一个数据块中,这样可以提高系统的查询速度 莉输入输出速度。 数据库系统原理与应用教程(第二版) 第11章索引和散列技术 第6页
数据库系统原理与应用教程(第二版) 第11章 索引和散列技术 第6页 文件组织方式 ⚫ 一般地，可以把文件中记录的组织形式分为四种，即堆文件组织、顺 序文件组织、散列文件组织和聚集文件组织。 ⚫ 在堆文件组织中，记录可以放在文件中的任何位置。实际上，堆的含 义就是没有顺序、乱七八糟。一般地，依记录的输入顺序为序，只要 有空间，就可以存储记录。记录的存储顺序与键码没有直接的联系。 删除操作只是在删除的记录旁边增加一个删除标记，新插入的记录总 是排在文件尾。通常一个关系是一个单独的文件。 ⚫ 在顺序文件组织中，记录是按照有关键码值的升序或降序的顺序存储 的。后面将对这种文件组织方式进行详细研究。 ⚫ 在散列文件组织中，需要对每一个记录的同一个属性计算出一个散列 函数。散列函数的结果确定了记录的存储顺序。这种技术与散列索引 技术是紧密关联的，本章后面对此内容将详细讨论。 ⚫ 在聚集文件组织中，一个文件可以存储多个关系的记录。不同关系中 有联系的记录存储在同一个数据块中，这样可以提高系统的查询速度 和输入输出速度
顺序文件组织 根据搜索键码值的高鲁斯·大卫 美 低顺序存储的记录文 道格拉斯·康姆 美国 件称为顺序文件。在蒋仁言 长沙 该文件中,对每 拉利·彼特森 美国 记录增加了一个指针布,皮克 美国 字段,根据搜索键码理查:斯夫 美国 值的大小使用指针把 玛格利特·米切尔 美国 记录链接起来。文件 马克·吐温 美国 初始建立时,存储记 潘承毅 杭州 琼瑶 录应该尽可能地使物 长沙 盛骤 杭州 理顺序和搜索键码值式千 男男男男男男女男男女男男男男 宁波 的顺序一致,这样可 亚历山大·大仲马 以减少访问数据的次左明健 济南 数据库系统原理与应用教程(第二版) 第11章索引和散列技术 第7页
数据库系统原理与应用教程 (第二版 ) 第11 章 索引和散列技术 第 7 页 顺序文件组织 ⚫ 根据搜索键码值的高 低顺序存储的记录文 件称为顺序文件。在 该文件中，对每一个 记录增加了一个指针 字段，根据搜索键码 值的大小使用指针把 记录链接起来。文件 初始建立时，存储记 录应该尽可能地使物 理顺序和搜索键码值 的顺序一致，这样可 以减少访问数据的次 数
聚集文件组织 ●在一些小型数据库系统中,数据量很小,系统把 每一个关系处理成一个文件。这种文件称为单记 录类型文件,文件中每一个记录都是定长的。文 件之间是分割开的,没有联系。数据联系需要通 过搜索键码值和查询语句来实现。这时,一般的 操作系统可以管理这种文件。随着数据量的增大, 这时需要采用一种新的文件结构,这种文件称为 聚集文件。这种文件允许一个文件由多个关系的 记录组成,也称为多记录类型文件。 数据库系统原理与应用教程(第二版) 第11章索引和散列技术 第8页
数据库系统原理与应用教程(第二版) 第11章 索引和散列技术 第8页 聚集文件组织 ⚫ 在一些小型数据库系统中，数据量很小，系统把 每一个关系处理成一个文件。这种文件称为单记 录类型文件，文件中每一个记录都是定长的。文 件之间是分割开的，没有联系。数据联系需要通 过搜索键码值和查询语句来实现。这时，一般的 操作系统可以管理这种文件。随着数据量的增大， 这时需要采用一种新的文件结构，这种文件称为 聚集文件。这种文件允许一个文件由多个关系的 记录组成，也称为多记录类型文件
主要内容 111概述 112索引技术 113散列技术 114 Microsoft SQL Server系统中的索引 115本章小结 数据库系统原理与应用教程(第二版) 第11章索引和散列技术 第9页
数据库系统原理与应用教程(第二版) 第11章 索引和散列技术 第9页 主要内容 11.1 概述 11.2 索引技术 11.3 散列技术 11.4 Microsoft SQL Server系统中的索引 11.5 本章小结
112索引技术 ●当文件中的记录很少时,系统把这些记录 按照顺序读出的效率虽然比较低,但还是 可以忍受的。 ●随着数据量的剧增,在文件中从开始读数 据的査询速度就会大大降低。为了提高查 询速度,必须对文件建立索引。 °下面介绍索引的基本概念和类型。 数据库系统原理与应用教程(第二版) 第11章索引和散列技术 第10页
数据库系统原理与应用教程(第二版) 第11章 索引和散列技术 第10页 11.2 索引技术 ⚫ 当文件中的记录很少时，系统把这些记录 按照顺序读出的效率虽然比较低，但还是 可以忍受的。 ⚫ 随着数据量的剧增，在文件中从开始读数 据的查询速度就会大大降低。为了提高查 询速度，必须对文件建立索引。 ⚫ 下面介绍索引的基本概念和类型