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

1、2022-5-291第第8 8章索引和散列章索引和散列索引的目的就是为了能够快速地在文件文件中定位要访问的记录，当然，理想的做法是系统能够直接定位这些记录！为了实现这种访问数据的方式，需要一些附加结构索引索引，并将索引同数据文数据文件件联系起来。在本章，只要不是特别指明，数据数据文件一般是指存储数据记录的文件，我们简称文文件一般是指存储数据记录的文件，我们简称文件，而索引文件是指存储索引记录（或称之为索件，而索引文件是指存储索引记录（或称之为索引项）的文件。引项）的文件。基本概念基本概念 散列文件组织散列文件组织 SQLSQL中索引的定义中索引的定义顺序索引顺序索引 散列索引散列索引 多码访问

2、多码访问B B树索引文件树索引文件两种索引的比较两种索引的比较本章总结本章总结2022-5-2928.18.1基本概念基本概念基本索引 顺序索引： 基于对值的一种排序； 结构：顺序文件和B树文件 散列索引： 基于将值平均、随机地分布到若干存储桶中：由1至32个连续的物理块构成的一种存储结构；与物理块不同的是，存储桶只能包含整记录，即记录可以跨块存储但不能跨桶存储。 一个值所属的存储桶由一个函数来决定，该函数称为散列函数，也叫哈稀函数； 索引结构是散列文件！2022-5-2938.18.1基本概念基本概念索引技术的评价标准 没有哪一种索引技术是最好的，每种索引都有自己适合的数据库应用。对索引技术

3、的评价必须考虑以下因素： 访问类型：能有效支持的数据访问类型，包括根据指定的属性值进行查询，或根据给定属性值的范围进行查询。 访问时间：访问一个或多个数据项所需要的时间。 插入时间：在文件中插入一个新数据项所需要的时间，包括找到插入该项的正确位置和修改索引所需要的时间。2022-5-2948.18.1基本概念基本概念索引技术的评价标准 没有哪一种索引技术是最好的，每种索引都有自己适合的数据库应用。对索引技术的评价必须考虑以下因素： 删除时间：在文件中删除一个数据项所需要的时间，包括找到待删除项的正确位置和修改索引所需要的时间。 更新时间：U = D + I （在位与异位） 空间开销：索引结构所

4、需要的额外存储空间；索引是用空间的代价来换取系统性能的提高。 索引实现的难度决定了该索引技术是否实用、能否推广。2022-5-2958.28.2顺序索引顺序索引顺序索引的作用 能迅速地按顺序或随机地访问文件中的记录顺序索引的结构 在逻辑上按顺序存储搜索码的值，并将搜索码值与包含该搜索码值的记录关联起来。顺序索引的特征 一个文件可以有多个索引，对应于不同的搜索码。根据索引结构中搜索码值的逻辑顺序和数据文件中记录的物理存储顺序之间的关系，顺序索引分为主索引和辅助索引。2022-5-2968.28.2顺序索引顺序索引基本概念 主索引与辅助索引 如果数据文件中记录按照某个搜索码指定的顺序物理存储，则该

5、搜索码对应的索引称为主索引或簇集索引； 相反，搜索码顺序与数据文件中记录的物理顺序不同的那些索引称为辅助索引或非簇集索引； 显然，一个数据文件只能有一个主索引，但可以有多个辅助索引，为什么？ 堆文件与索引顺序文件 没有主索引的数据文件就是堆文件； 而拥有主索引的数据文件就是索引顺序文件。2022-5-2978.28.2顺序索引顺序索引索引顺序文件 数据文件中的记录按照某个搜索码值的顺序物理存储：2022-5-2988.28.2顺序索引顺序索引顺序索引的分类 按照索引结构中搜索码值与数据文件中搜索码值的对应关系，顺序索引又分为：稠密索引稀疏索引 稠密索引：对应文件中搜 索码的每一个 值都有一个索

6、 引记录(或索引项)，它包括：搜索码值；指向具有该搜索码值的第一个数据记录的指针。2022-5-2998.28.2顺序索引顺序索引顺序索引的分类 稀疏索引： 只为搜索码的部分值建立索引项； 与稠密索引一样，每个索引项也包括搜索码值和指向具有该搜索码值的第一个数据记录的指针。问题：如何利用稀疏索引进行查询呢？2022-5-2910SQL SERVER 主索引的问题？ 搜索码链表的作用 记录的惟一标识是F#:P#:S# 索引中索引项的指针是？页头：96字节数据行，即记录176行偏移数组：链表095Mianus (96)Downtown(136).Brighton(176).Downtown(216

7、).13621696 3 2 1 0 页号：0108.28.2顺序索引顺序索引各行顺序号(槽号)RID是01:010:01的记录的搜索码是Downtown2022-5-29118.28.2顺序索引顺序索引稠密索引和稀疏索引的比较 利用稠密索引通常可以比稀疏索引更快地定位一个记录的位置； 与稠密索引相比，稀疏索引占用空间小，插入和删除时的维护开销也小。实践中如何正确地建立稀疏索引？ 数据库查询的开销主要是由什么来决定的？ 在主存内扫描整个块的时间是可以忽略的； 考虑为每个块建一个索引项的稀疏索引，这样的索引可以定位包含所要查找记录的块。2022-5-29128.28.2顺序索引顺序索引多级索引

8、问题的提出：即使采用稀疏索引，索引本身有时也会变得非常庞大而难于有效处理，例如：一个文件有100000条记录；一个块存储10个记录，每个块有一个索引记录；一个块存储100个索引记录。索引过大在读索引时就必须有一部分放在磁盘上，搜索一个索引项就必须多次读磁盘块：当然在索引上可以用二分法来定位索引项，最坏需要读log2(b)次块，假设索引占据了b个块。如果索引小到一次I/O就能够放到主存里，搜索一个索引项的时间就很短，可以忽略不计。2022-5-29138.28.2顺序索引顺序索引多级索引 问题的解决： 像对待其他任何顺序文件那样对待索引结构，即在主索引上再构造一个稀疏索引，形成一个具有内层索引和

9、外层索引的多级索引结构：主索引结构本身就是一个顺序文件2022-5-29148.28.2顺序索引顺序索引索引的更新 删除数据记录，稠密索引的变化情况：删除数据文件中的“邓婉玲”记录；删除数据文件中“王小丽”的s000005记录；删除数据文件中“王小丽”的s000009记录。 2022-5-29158.28.2顺序索引顺序索引索引的更新 删除数据记录，稀疏索引的变化情况：删除文件中搜索码为“陈舒艺”的记录；删除文件中搜索码为“陈国国”的所有记录；删除文件中搜索码为“冯蔼妍”记录；删除文件中“王小丽”的s000005记录；删除文件中“王小丽”的s000007记录。2022-5-29168.28.2

10、顺序索引顺序索引索引的更新 插入数据记录，索引的变化情况： 若索引是稠密的，并且待插入记录的搜索码值不在索引中，就要把该搜索码值插入到索引中； 若索引是为每个块保存一个索引项的稀疏索引：只要没有新块产生，索引就无需做任何改动；在产生新块的情况下，新块中的第一个搜索码值将被插入到索引中。 多级索引： 删除和插入数据记录时，它的更新同上面类似：内层索引的更新同上；内层索引的变化，引起外层索引按上述算法更新。2022-5-29178.28.2顺序索引顺序索引辅助索引 在文件中，记录按主索引而不是辅助索引的搜索码值顺序物理存储； 具有同一个辅助搜索码值的记录可能分布在文件的各个地方，例如：2022-5

11、-29188.28.2顺序索引顺序索引辅助索引 其结构与主索引的结构是不同的： 辅助索引必须包含指向每一记录的指针； 辅助索引的指针并不直接指向文件，而是每个指针指向一个包含文件指针的存储桶； 存储桶中的每个指针才指向文件中的记录。2022-5-29198.28.2顺序索引顺序索引辅助索引 辅助索引的优缺点： 可以提高使用利用辅助搜索码查询记录的速度； 但辅助索引也大大增加了数据库更新的开销。2022-5-29208.3B8.3B+ +树索引文件树索引文件索引顺序文件的缺陷 性能： 索引顺序文件组织最大的缺点在于随着文件的增大，索引查找性能和顺序扫描性能都会下降。 文件重组： 而且随着频繁的删

12、除和插入记录，就会不断有溢出块出现，记录的物理顺序同主搜索码顺序的一致性就遭到破坏，这样就不得不重组文件。 解决方案呢？ 研究在插入和删除操作很频繁的情况下仍保持有效的索引结构：B+树索引就是其中的一种。2022-5-29218.3B8.3B+ +树索引文件树索引文件B+树索引结构 总体结构： 是一个多级索引，但其结构不同于多级顺序索引 采用平衡树结构：即每个叶结点到根的路径长度都相同。 每个非叶结点有n/2到n个子女，n对特定树是固定的； 它的所有结点结构都相同，最多包含n-1个搜索码值K1、K2、Kn-1及n个指针P1、P2、Pn； 每个结点中的搜索码值按次序存放，即若ij，那么一定有Ki

13、Kj。2022-5-29228.3B8.3B+ +树索引文件树索引文件B+树索引结构 叶结点： 指针Pi(i=1,2,n-1)指向具有搜索码值Ki的一个数据记录或一个指针桶，桶中的每个指针指向具有搜索码值Ki的一个数据记录。指针桶只在记录不按搜索码顺序物理存储时才使用指针Pn具有特殊的作用。 每个叶结点最多可有n-1个搜索码值，最少也要有(n-1)/2个搜索码值； 各个叶结点的搜索码值的范围互不相交； 要使B+树索引成为稠密索引，文件中各搜索码值就都必须在某个叶结点中出现且只能出现一次；2022-5-2923B+树索引结构 叶结点： 各叶结点按照所含的搜索码值有一个线性顺序，利用指针Pn将叶结

14、点按搜索码顺序链接在一起； 这种排序能高效地对文件进行顺序处理，而B+树索引的其他结构能高效地对文件进行随机处理。8.3B8.3B+ +树索引文件树索引文件2022-5-2924B+树索引结构非叶结点： B+树索引的非叶结点形成叶结点上的一个多级稀疏索引； 非叶结点的结构和叶结点的结构相同，即含有能够存储n-1个搜索码值和n个指针的存储单元。只不过非叶结点中的所有指针都指向树中的结点； 如果一个非叶结点有m个指针，则n/2mn。若mn，则非叶结点中指针Pm之后的所有空闲空间作为预留空间，与叶结点的区别在于结点的最后一个指针Pm和Pn的位置与指向；8.3B8.3B+ +树索引文件树索引文件202

15、2-5-29258.3B8.3B+ +树索引文件树索引文件B+树索引结构 非叶结点： 在含有m个指针的非叶结点中，Pi(i=2,m-1)指向一棵子树，该子树的所有结点的搜索码值大于等于Ki-1而小于Ki； 指针Pm指向子树中所含搜索码值大于等于Km-1的那一部分； 而指针P1指向子树中所含搜索码值小于K1的那一部分。P P1 1K K1 1K Ki i- -1 1P Pi iK Ki iK Km m- -1 1P Pm m2022-5-29268.3B8.3B+ +树索引文件树索引文件B+树索引结构 根结点： 根结点的结构也与叶结点的结构相同； 根结点包含的指针数可能小于n/2，除非整棵树只有

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

17、记录： 首先检查根结点，找到大于K的最小搜索码值，假设是Ki，那么沿着指针Pi走到另一个结点； 如果K= c1 AND Ai = c2 使用索引时，首先确定数据c1所在的位置，然后顺着索引顺序文件中的搜索码链表或B+树索引中的叶结点的Pn指针链继续查找，直到确定数据c2的位置为止； 如果使用散列，由于散列函数的随机性，将不得不读取散列文件的所有存储桶。8.68.6顺序索引和散列的比较顺序索引和散列的比较2022-5-2941索引的创建与删除 原则上，DBMS可以自动决定创建什么样的索引，但实际上很少这样做。DBA和程序员都可以使用SQL DDL来创建和删除索引：创建索引create index

18、 on ()create index s_index on student (student_name)删除索引drop index DBMS为优化查询而自动创建的索引是不能用drop语句删除的。8.7SQL8.7SQL中索引的定义中索引的定义2022-5-2942问题的提出 到目前为止，都隐含地假设在关系上查询时只使用一个索引或散列； 如果存在多个索引，该如何处理呢？例如： 假设文件student上有两个索引，分别建立在student_name和department_name上。考虑如下查询：select student_number from student where student_n

19、ame = “陈国围” AND department_name = “计算机系” 问题：对于这个查询，如何利用上面已有的两个索引呢？8.88.8多码访问多码访问2022-5-2943多个索引的利用 处理前面的查询有三种策略： 利用student_name上的索引，找出“陈国围”的所有记录，然后检查每条记录是否满足条件：department_name = “计算机系”； 利用department_name上的索引，找出所有“计算机系”的记录，然后检查每条记录是否满足条件：student_name = “陈国围”； 利用上述两个索引分别找出指向满足各自条件的所有记录的索引指针，然后计算这两个指针集

20、的交集即可得到结果。8.88.8多码访问多码访问2022-5-2944多个索引的利用 上面三种策略中，只有第三个方案同时利用了两个索引。但它有可能是最糟糕的选择： 名字是“陈国围”的记录太多； “计算机系”的学生记录太多； “计算机系”中名字为“陈国围”的记录很少。 这样的话，为了得到一个很小的结果，将不得不扫描大量的指针； 最好的解决方案是在复合搜索码： (student_name, department_name) 上建立并使用索引，这样的索引叫复合索引8.88.8多码访问多码访问2022-5-2945B+树与B树结构 簇集索引采用B+树结构： 簇集索引的叶级页是真正的数据页。 非簇集索引采用B树结构。8.9SQL Server8.9SQL Server的索引结构的索引结构2022-5-2946B+树与B树结构 查询举例：8.9SQL Server8.9SQL Server的索引结构的索引结构2022-5-2947小结：索引与散列小结：索引与散列存取路径的实现策略 索引、散列、簇集索引本身的文件结构类型主索引的特征与结构散列文件与散列索引的区别B+树索引的结构特征实践中如何正确地建立索引？ 一个巨大的关系表 DBMS的参数与性能调整工具 复合索引