清华大学数据库access课件-第08章：索引和散列

《清华大学数据库access课件-第08章：索引和散列》由会员分享，可在线阅读，更多相关《清华大学数据库access课件-第08章：索引和散列（47页珍藏版）》请在金锄头文库上搜索。

1、2019/4/17,1,第8章 索引和散列,讲课内容： 索引的目的就是为了能够快速地在文件中定位要访问的记录，当然，理想的做法是系统能够直接定位这些记录！为了实现这种访问数据的方式，需要一些附加结构索引，并将索引同数据文件联系起来。在本章，只要不是特别指明，数据文件一般是指存储数据记录的文件，我们简称文件，而索引文件是指存储索引记录（或称之为索引项）的文件。 基本概念 散列文件组织 SQL中索引的定义 顺序索引 散列索引 多码访问 B树索引文件 两种索引的比较本章总结,2019/4/17,2,8.1基本概念,基本索引 顺序索引： 基于对值的一种排序； 结构：顺序文件和B树文件 散列索引： 基于

2、将值平均、随机地分布到若干存储桶中： 由1至32个连续的物理块构成的一种存储结构； 与物理块不同的是，存储桶只能包含整记录，即记录可以跨块存储但不能跨桶存储。 一个值所属的存储桶由一个函数来决定，该函数称为散列函数，也叫哈稀函数； 索引结构是散列文件！,2019/4/17,3,8.1基本概念,索引技术的评价标准 没有哪一种索引技术是最好的，每种索引都有自己适合的数据库应用。对索引技术的评价必须考虑以下因素： 访问类型： 能有效支持的数据访问类型，包括根据指定的属性值进行查询，或根据给定属性值的范围进行查询。 访问时间： 访问一个或多个数据项所需要的时间。 插入时间： 在文件中插入一个新数据项所

3、需要的时间，包括找到插入该项的正确位置和修改索引所需要的时间。,2019/4/17,4,8.1基本概念,索引技术的评价标准 没有哪一种索引技术是最好的，每种索引都有自己适合的数据库应用。对索引技术的评价必须考虑以下因素： 删除时间： 在文件中删除一个数据项所需要的时间，包括找到待删除项的正确位置和修改索引所需要的时间。 更新时间：U = D + I （在位与异位） 空间开销： 索引结构所需要的额外存储空间； 索引是用空间的代价来换取系统性能的提高。 索引实现的难度 决定了该索引技术是否实用、能否推广。,2019/4/17,5,8.2顺序索引,顺序索引的作用 能迅速地按顺序或随机地访问文件中的记

4、录 顺序索引的结构 在逻辑上按顺序存储搜索码的值，并将搜索码值与包含该搜索码值的记录关联起来。 顺序索引的特征 一个文件可以有多个索引，对应于不同的搜索码。根据索引结构中搜索码值的逻辑顺序和数据文件中记录的物理存储顺序之间的关系，顺序索引分为主索引和辅助索引。,2019/4/17,6,8.2顺序索引,基本概念 主索引与辅助索引 如果数据文件中记录按照某个搜索码指定的顺序物理存储，则该搜索码对应的索引称为主索引或簇集索引； 相反，搜索码顺序与数据文件中记录的物理顺序不同的那些索引称为辅助索引或非簇集索引； 显然，一个数据文件只能有一个主索引，但可以有多个辅助索引，为什么？ 堆文件与索引顺序文件

5、没有主索引的数据文件就是堆文件； 而拥有主索引的数据文件就是索引顺序文件。,2019/4/17,7,8.2顺序索引,索引顺序文件 数据文件中的记录按照某个搜索码值的顺序物理存储：,2019/4/17,8,8.2顺序索引,顺序索引的分类 按照索引结构中搜索码值与数据文件中搜索码值的对应关系，顺序索引又分为： 稠密索引 稀疏索引 稠密索引： 对应文件中搜 索码的每一个 值都有一个索 引记录(或索引项)，它包括： 搜索码值； 指向具有该搜索码值的第一个数据记录的指针。,2019/4/17,9,8.2顺序索引,顺序索引的分类 稀疏索引： 只为搜索码的部分值建立索引项； 与稠密索引一样，每个索引项也包括

6、搜索码值和指向具有该搜索码值的第一个数据记录的指针。,问题：如何利用稀疏索引进行查询呢？,2019/4/17,10,SQL SERVER 主索引的问题？ 搜索码链表的作用 记录的惟一标识是F#:P#:S# 索引中索引项的指针是？,3 2 1 0,页号：010,8.2顺序索引,各行顺序号(槽号),RID是01:010:01的记录的搜索码是Downtown,2019/4/17,11,8.2顺序索引,稠密索引和稀疏索引的比较 利用稠密索引通常可以比稀疏索引更快地定位一个记录的位置； 与稠密索引相比，稀疏索引占用空间小，插入和删除时的维护开销也小。 实践中如何正确地建立稀疏索引？ 数据库查询的开销主要

7、是由什么来决定的？ 在主存内扫描整个块的时间是可以忽略的； 考虑为每个块建一个索引项的稀疏索引，这样的索引可以定位包含所要查找记录的块。,2019/4/17,12,8.2顺序索引,多级索引 问题的提出： 即使采用稀疏索引，索引本身有时也会变得非常庞大而难于有效处理，例如： 一个文件有100000条记录； 一个块存储10个记录，每个块有一个索引记录； 一个块存储100个索引记录。 索引过大在读索引时就必须有一部分放在磁盘上，搜索一个索引项就必须多次读磁盘块： 当然在索引上可以用二分法来定位索引项，最坏需要读log2(b)次块，假设索引占据了b个块。 如果索引小到一次I/O就能够放到主存里，搜索一

8、个索引项的时间就很短，可以忽略不计。,2019/4/17,13,8.2顺序索引,多级索引 问题的解决： 像对待其他任何顺序文件那样对待索引结构，即在主索引上再构造一个稀疏索引，形成一个具有内层索引和外层索引的多级索引结构：,主索引结构本身就是一个顺序文件,2019/4/17,14,8.2顺序索引,索引的更新 删除数据记录，稠密索引的变化情况： 删除数据文件中的“邓婉玲”记录； 删除数据文件中“王小丽”的s000005记录； 删除数据文件中“王小丽”的s000009记录。,2019/4/17,15,8.2顺序索引,索引的更新 删除数据记录，稀疏索引的变化情况： 删除文件中搜索码为“陈舒艺”的记录

9、； 删除文件中搜索码为“陈国国”的所有记录； 删除文件中搜索码为“冯蔼妍”记录； 删除文件中“王小丽”的s000005记录； 删除文件中“王小丽”的s000007记录。,2019/4/17,16,8.2顺序索引,索引的更新 插入数据记录，索引的变化情况： 若索引是稠密的，并且待插入记录的搜索码值不在索引中，就要把该搜索码值插入到索引中； 若索引是为每个块保存一个索引项的稀疏索引： 只要没有新块产生，索引就无需做任何改动； 在产生新块的情况下，新块中的第一个搜索码值将被插入到索引中。 多级索引： 删除和插入数据记录时，它的更新同上面类似： 内层索引的更新同上； 内层索引的变化，引起外层索引按上述

10、算法更新。,2019/4/17,17,8.2顺序索引,辅助索引 在文件中，记录按主索引而不是辅助索引的搜索码值顺序物理存储； 具有同一个辅助搜索码值的记录可能分布在文件的各个地方，例如：,2019/4/17,18,8.2顺序索引,辅助索引 其结构与主索引的结构是不同的： 辅助索引必须包含指向每一记录的指针； 辅助索引的指针并不直接指向文件，而是每个指针指向一个包含文件指针的存储桶； 存储桶中的每个指针才指向文件中的记录。,2019/4/17,19,8.2顺序索引,辅助索引 辅助索引的优缺点： 可以提高使用利用辅助搜索码查询记录的速度； 但辅助索引也大大增加了数据库更新的开销。,2019/4/1

11、7,20,8.3B+树索引文件,索引顺序文件的缺陷 性能： 索引顺序文件组织最大的缺点在于随着文件的增大，索引查找性能和顺序扫描性能都会下降。 文件重组： 而且随着频繁的删除和插入记录，就会不断有溢出块出现，记录的物理顺序同主搜索码顺序的一致性就遭到破坏，这样就不得不重组文件。 解决方案呢？ 研究在插入和删除操作很频繁的情况下仍保持有效的索引结构：B+树索引就是其中的一种。,2019/4/17,21,8.3B+树索引文件,B+树索引结构 总体结构： 是一个多级索引，但其结构不同于多级顺序索引 采用平衡树结构： 即每个叶结点到根的路径长度都相同。 每个非叶结点有n/2到n个子女，n对特定树是固定

12、的； 它的所有结点结构都相同，最多包含n-1个搜索码值K1、K2、Kn-1及n个指针P1、P2、Pn； 每个结点中的搜索码值按次序存放，即若ij，那么一定有KiKj。,2019/4/17,22,8.3B+树索引文件,B+树索引结构 叶结点： 指针Pi(i=1,2,n-1)指向具有搜索码值Ki的一个数据记录或一个指针桶，桶中的每个指针指向具有搜索码值Ki的一个数据记录。 指针桶只在记录不按搜索码顺序物理存储时才使用 指针Pn具有特殊的作用。 每个叶结点最多可有n-1个搜索码值，最少也要有(n-1)/2个搜索码值； 各个叶结点的搜索码值的范围互不相交； 要使B+树索引成为稠密索引，文件中各搜索码值

13、就都必须在某个叶结点中出现且只能出现一次；,2019/4/17,23,B+树索引结构 叶结点： 各叶结点按照所含的搜索码值有一个线性顺序，利用指针Pn将叶结点按搜索码顺序链接在一起； 这种排序能高效地对文件进行顺序处理，而B+树索引的其他结构能高效地对文件进行随机处理。,8.3B+树索引文件,2019/4/17,24,B+树索引结构 非叶结点： B+树索引的非叶结点形成叶结点上的一个多级稀疏索引； 非叶结点的结构和叶结点的结构相同，即含有能够存储n-1个搜索码值和n个指针的存储单元。只不过非叶结点中的所有指针都指向树中的结点； 如果一个非叶结点有m个指针，则n/2mn。若mn，则非叶结点中指针

14、Pm之后的所有空闲空间作为预留空间，与叶结点的区别在于结点的最后一个指针Pm和Pn的位置与指向；,8.3B+树索引文件,2019/4/17,25,8.3B+树索引文件,B+树索引结构 非叶结点： 在含有m个指针的非叶结点中，Pi(i=2,m-1)指向一棵子树，该子树的所有结点的搜索码值大于等于Ki-1而小于Ki； 指针Pm指向子树中所含搜索码值大于等于Km-1的那一部分； 而指针P1指向子树中所含搜索码值小于K1的那一部分。,2019/4/17,26,8.3B+树索引文件,B+树索引结构 根结点： 根结点的结构也与叶结点的结构相同； 根结点包含的指针数可能小于n/2，除非整棵树只有一个结点，否

15、则它至少包含两个指针。,2019/4/17,27,8.3B+树索引文件,B+树索引缺点 B+树的“平衡”(Balance)特征保证了B+树索引具有良好的查找、插入和修改性能，但B+树索引也有以下缺陷： B+树索引结构会增加文件插入和删除处理的空间开销，以空间代价换取性能上的优势； B+树索引结构在极端情况下，结点可以是半空的(n/2到n)，这虽然造成了空间浪费，但缺保证了性能。 B+树索引技术已经被广泛地应用到商业数据库管理系统中。,2019/4/17,28,8.3B+树索引文件,B+树上的查询 如何利用B+树索引进行查询呢？假设要找出搜索码值为K的所有记录： 首先检查根结点，找到大于K的最小

16、搜索码值，假设是Ki，那么沿着指针Pi走到另一个结点； 如果KK1，则沿着指针P1走至另一个结点； 如果KKm-1(m是该结点的指针数)，则沿着指针Pm走至另一个结点； 对新到达的结点，重复以上步骤，最终到达一个叶结点。,2019/4/17,29,8.3B+树索引文件,B+树上的查询 举例： 利用student关系上的B+树索引，给出在该关系中查找student_name为“邓婉玲”的所有记录的过程：,2019/4/17,30,8.3B+树索引文件,B+树的更新 很烦琐，数据结构课程讲的内容。 B+树文件组织 B+树索引通过在叶结点来组织包含真实记录的物理块来解决索引顺序文件组织随着文件的增大而性能下降的缺点： 在B+树文件组织中，B+树结构不仅用做索引，同时也是文件中记录的组织者。树叶结点中存储的是记录而不是指向记录的指针。,2019/4/17,31,基本概念 在前面介绍的索引