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

清华大学数据库access课件-第08章：索引和散列资料§8.1基本概念索引技术的评价标准没有哪一种索引技术是最好的，每种索引都有自己适合的数据库应用。对索引技术的评价必须考虑以下因素：访问类型：能有效支持的数据访问类型，包括根据指定的属性值进行查询，或根据给定属性值的范围进行查询。访问时间：访问一个或多个数据项所需要的时间。插入时间：在文件中插入一个新数据项所需要的时间，包括找到插入该项的正确位置和修改索引所需要的时间。1/13/20232§8.1基本概念索引技术的评价标准没有哪一种索引技术是最好的，每种索引都有自己适合的数据库应用。对索引技术的评价必须考虑以下因素：删除时间：在文件中删除一个数据项所需要的时间，包括找到待删除项的正确位置和修改索引所需要的时间。更新时间：U=D+I（在位与异位）空间开销：索引结构所需要的额外存储空间；索引是用空间的代价来换取系统性能的提高。索引实现的难度决定了该索引技术是否实用、能否推广。1/13/20233§8.2顺序索引顺序索引的作用能迅速地按顺序或随机地访问文件中的记录顺序索引的结构在逻辑上按顺序存储搜索码的值，并将搜索码值与包含该搜索码值的记录关联起来。顺序索引的特征一个文件可以有多个索引，对应于不同的搜索码。根据索引结构中搜索码值的逻辑顺序和数据文件中记录的物理存储顺序之间的关系，顺序索引分为主索引和辅助索引。1/13/20234§8.2顺序索引基本概念主索引与辅助索引如果数据文件中记录按照某个搜索码指定的顺序物理存储，则该搜索码对应的索引称为主索引或簇集索引；相反，搜索码顺序与数据文件中记录的物理顺序不同的那些索引称为辅助索引或非簇集索引；显然，一个数据文件只能有一个主索引，但可以有多个辅助索引，为什么？堆文件与索引顺序文件没有主索引的数据文件就是堆文件；而拥有主索引的数据文件就是索引顺序文件。1/13/20235§8.2顺序索引索引顺序文件数据文件中的记录按照某个搜索码值的顺序物理存储：1/13/20236§8.2顺序索引顺序索引的分类按照索引结构中搜索码值与数据文件中搜索码值的对应关系，顺序索引又分为：稠密索引稀疏索引稠密索引：对应文件中搜索码的每一个值都有一个索引记录(或索引项)，它包括：搜索码值；指向具有该搜索码值的第一个数据记录的指针。1/13/20237§8.2顺序索引顺序索引的分类稀疏索引：只为搜索码的部分值建立索引项；与稠密索引一样，每个索引项也包括搜索码值和指向具有该搜索码值的第一个数据记录的指针。问题：如何利用稀疏索引进行查询呢？1/13/20238SQLSERVER主索引的问题？搜索码链表的作用记录的惟一标识是F#:P#:S#索引中索引项的指针是？页头：96字节数据行，即记录176行偏移数组：链表095Mianus(96)…Downtown(136).Brighton(176).Downtown(216).13621696

3210页号：010§8.2顺序索引各行顺序号(槽号)RID是01:010:01的记录的搜索码是Downtown1/13/20239§8.2顺序索引稠密索引和稀疏索引的比较利用稠密索引通常可以比稀疏索引更快地定位一个记录的位置；与稠密索引相比，稀疏索引占用空间小，插入和删除时的维护开销也小。实践中如何正确地建立稀疏索引？数据库查询的开销主要是由什么来决定的？在主存内扫描整个块的时间是可以忽略的；考虑为每个块建一个索引项的稀疏索引，这样的索引可以定位包含所要查找记录的块。1/13/202310§8.2顺序索引多级索引问题的提出：即使采用稀疏索引，索引本身有时也会变得非常庞大而难于有效处理，例如：一个文件有100000条记录；一个块存储10个记录，每个块有一个索引记录；一个块存储100个索引记录。索引过大在读索引时就必须有一部分放在磁盘上，搜索一个索引项就必须多次读磁盘块：当然在索引上可以用二分法来定位索引项，最坏需要读log2(b)次块，假设索引占据了b个块。如果索引小到一次I/O就能够放到主存里，搜索一个索引项的时间就很短，可以忽略不计。1/13/202311§8.2顺序索引多级索引问题的解决：像对待其他任何顺序文件那样对待索引结构，即在主索引上再构造一个稀疏索引，形成一个具有内层索引和外层索引的多级索引结构：主索引结构本身就是一个顺序文件1/13/202312§8.2顺序索引索引的更新删除数据记录，稠密索引的变化情况：①删除数据文件中的“邓婉玲”记录；②删除数据文件中“王小丽”的s000005记录；③删除数据文件中“王小丽”的s000009记录。1/13/202313§8.2顺序索引索引的更新删除数据记录，稀疏索引的变化情况：①删除文件中搜索码为“陈舒艺”的记录；②删除文件中搜索码为“陈国国”的所有记录；③删除文件中搜索码为“冯蔼妍”记录；④删除文件中“王小丽”的s000005记录；⑤删除文件中“王小丽”的s000007记录。1/13/202314§8.2顺序索引索引的更新插入数据记录，索引的变化情况：若索引是稠密的，并且待插入记录的搜索码值不在索引中，就要把该搜索码值插入到索引中；若索引是为每个块保存一个索引项的稀疏索引：只要没有新块产生，索引就无需做任何改动；在产生新块的情况下，新块中的第一个搜索码值将被插入到索引中。多级索引：删除和插入数据记录时，它的更新同上面类似：内层索引的更新同上；内层索引的变化，引起外层索引按上述算法更新。1/13/202315§8.2顺序索引辅助索引在文件中，记录按主索引而不是辅助索引的搜索码值顺序物理存储；具有同一个辅助搜索码值的记录可能分布在文件的各个地方，例如：1/13/202316§8.2顺序索引辅助索引其结构与主索引的结构是不同的：辅助索引必须包含指向每一记录的指针；辅助索引的指针并不直接指向文件，而是每个指针指向一个包含文件指针的存储桶；存储桶中的每个指针才指向文件中的记录。1/13/202317§8.2顺序索引辅助索引辅助索引的优缺点：可以提高使用利用辅助搜索码查询记录的速度；但辅助索引也大大增加了数据库更新的开销。1/13/202318§8.3B+树索引文件索引顺序文件的缺陷性能：索引顺序文件组织最大的缺点在于随着文件的增大，索引查找性能和顺序扫描性能都会下降。文件重组：而且随着频繁的删除和插入记录，就会不断有溢出块出现，记录的物理顺序同主搜索码顺序的一致性就遭到破坏，这样就不得不重组文件。解决方案呢？研究在插入和删除操作很频繁的情况下仍保持有效的索引结构：B+树索引就是其中的一种。1/13/202319§8.3B+树索引文件B+树索引结构总体结构：是一个多级索引，但其结构不同于多级顺序索引采用平衡树结构：即每个叶结点到根的路径长度都相同。每个非叶结点有n/2到n个子女，n对特定树是固定的；它的所有结点结构都相同，最多包含n-1个搜索码值K1、K2、…、Kn-1及n个指针P1、P2、…、Pn；每个结点中的搜索码值按次序存放，即若i<j，那么一定有Ki<Kj。1/13/202320§8.3B+树索引文件B+树索引结构叶结点：指针Pi(i=1,2,…,n-1)指向具有搜索码值Ki的一个数据记录或一个指针桶，桶中的每个指针指向具有搜索码值Ki的一个数据记录。指针桶只在记录不按搜索码顺序物理存储时才使用指针Pn具有特殊的作用。每个叶结点最多可有n-1个搜索码值，最少也要有(n-1)/2个搜索码值；各个叶结点的搜索码值的范围互不相交；要使B+树索引成为稠密索引，文件中各搜索码值就都必须在某个叶结点中出现且只能出现一次；1/13/202321B+树索引结构叶结点：各叶结点按照所含的搜索码值有一个线性顺序，利用指针Pn将叶结点按搜索码顺序链接在一起；这种排序能高效地对文件进行顺序处理，而B+树索引的其他结构能高效地对文件进行随机处理。§8.3B+树索引文件1/13/202322B+树索引结构非叶结点：B+树索引的非叶结点形成叶结点上的一个多级稀疏索引；非叶结点的结构和叶结点的结构相同，即含有能够存储n-1个搜索码值和n个指针的存储单元。只不过非叶结点中的所有指针都指向树中的结点；如果一个非叶结点有m个指针，则n/2≤m≤n。若m<n，则非叶结点中指针Pm之后的所有空闲空间作为预留空间，与叶结点的区别在于结点的最后一个指针Pm和Pn的位置与指向；§8.3B+树索引文件1/13/202323§8.3B+树索引文件B+树索引结构非叶结点：在含有m个指针的非叶结点中，Pi(i=2,…,m-1)指向一棵子树，该子树的所有结点的搜索码值大于等于Ki-1而小于Ki；指针Pm指向子树中所含搜索码值大于等于Km-1的那一部分；而指针P1指向子树中所含搜索码值小于K1的那一部分。1/13/202324§8.3B+树索引文件B+树索引结构根结点：根结点的结构也与叶结点的结构相同；根结点包含的指针数可能小于n/2，除非整棵树只有一个结点，否则它至少包含两个指针。1/13/202325§8.3B+树索引文件B+树索引缺点B+树的“平衡”(Balance)特征保证了B+树索引具有良好的查找、插入和修改性能，但B+树索引也有以下缺陷：B+树索引结构会增加文件插入和删除处理的空间开销，以空间代价换取性能上的优势；B+树索引结构在极端情况下，结点可以是半空的(n/2到n)，这虽然造成了空间浪费，但缺保证了性能。B+树索引技术已经被广泛地应用到商业数据库管理系统中。1/13/202326§8.3B+树索引文件B+树上的查询如何利用B+树索引进行查询呢？假设要找出搜索码值为K的所有记录：首先检查根结点，找到大于K的最小搜索码值，假设是Ki，那么沿着指针Pi走到另一个结点；如果K<K1，则沿着指针P1走至另一个结点；如果K≥Km-1(m是该结点的指针数)，则沿着指针Pm走至另一个结点；对新到达的结点，重复以上步骤，最终到达一个叶结点。1/13/202327§8.3B+树索引文件B+树上的查询举例：利用student关系上的B+树索引，给出在该关系中查找student_name为“邓婉玲”的所有记录的过程：1/13/202328§8.3B+树索引文件B+树的更新很烦琐，《数据结构》课程讲的内容。B+树文件组织B+树索引通过在叶结点来组织包含真实记录的物理块来解决索引顺序文件组织随着文件的增大而性能下降的缺点：在B+树文件组织中，B+树结构不仅用做索引，同时也是文件中记录的组织者。树叶结点中存储的是记录而不是指向记录的指针。1/13/202329基本概念在前面介绍的索引类型中，必须访问该索引结构，才能在文件中定位记录。而基于散列(Hash)的文件组织能够避免访问索引结构；在散列文件组织中，用存储桶来表示能存储一条或多条记录的一个存储单位。通过计算搜索码上的一个函数，就可以确定包含该搜索码值的记录应该存储在哪个桶中；令K表示所有搜索码值的集合，令B表示所有桶地址的集合，散列函数h就是一个从K到B的函数：h(K)B或B=h(K)。§8.4散列文件组织1/13/202330散列文件的操作插入：为了插入一个搜索码为Ki的记录，通过计算h(Ki)获得存放该记录的桶地址。于是就把这条记录存入桶中或是相应的溢出桶中；删除：如果待删除记录的搜索码值是Ki，则计算h(Ki)，然后在相应的桶中搜寻此记录并删除它；基于搜索码值Ki的查找：首先计算h(Ki)，然后在计算出地址的桶中搜索所有的记录。因为不同的搜索码值对应相同的桶地址正是散列文件组织的最大特点。§8.4散列文件组织1/13/202331散列函数如果散列函数设计的不好，就有可能把所有的搜索码值都映射到同一个存储桶中，这时散列就失去了意义。因此，对散列函数的基本要求是：分布是均匀的：即每个存储桶从所有可能的搜索码值集合中分配到的值的个数差不多相同，例如将大写英文字母分配到5个存储桶中；分布是随机的：不管搜索码值的实际情况是怎样的，每个存储桶应分配到的搜索码值的个数也差不多相同。例如，假设实际的搜索码值是A、B、C、D、E五个字母。§8.4散列文件组织1/13/202332散列函数举例：假设将26个大写英文字母分布到5个存储桶中(地址从0到4)，那么散列函数h该如何设计呢？假设用code(A)表示A所对应的编号0，……；散列函数h=code(SearchKey)mod5。§8.4散列文件组织1/13/202333问题的提出散列不仅可以用于数据文件中记录的组织，还可以用于索引中索引项的组织。散列索引：将索引项中的搜索码及相应的指针按散列文件的形式进行组织。散列索引的构造首先将散列函数作用于索引项中的搜索码以确定对应的存储桶；然后将此搜索码及相应的指针存入此存储桶中，而指针指向数据文件中的记录。§8.5散列索引1/13/202334举例：为关系student上的student_number搜索码建立一个辅助的散列索引。§8.5散列索引散列函数h是学号各位数字之和后模3该散列索引共有3个桶，每个桶的大小为31/13/202335小结术语“散列文件”是指用来组织和存储文件中数据记录的散列文件结构。而散列索引是指将文件上的辅助索引的索引项按照散列文件的结构进行组织，不要将二者混淆；如果数据文件自身是按散列组织的，就认为该散列文件已经有了一个“主索引”，一般不必在其上另外创建独立的索引结构；散列索引只用来组织数据文件上的辅助索引数据文件上的主索引结构不应该是散列文件索引本身的文件结构有哪些？§8.5散列索引1/13/202336用索引还是散列？索引和散列都为访问数据提供了存取路径：索引需要通过值的比较，才能确定数据的位置；散列不通过值的比较，而通过值的含义来确定数据的位置的。用索引还是散列实际当中要考虑以下问题：索引或散列的周期性重组代价如何？在文件中插入和删除记录的频率如何？为了优化平均访问时间而导致最坏情况下的访问时间的做法是否可取？能够有效支持的查询类型是哪些？§8.6顺序索引和散列的比较1/13/202337散列支持的查询类型等值查询，或者叫点查询范围检索散列与索引比较举例之一selectA1,A2,…,AnfromrwhereAi=c顺序索引查找所需要的时间与关系r中Ai值的个数的对数成正比；而在散列文件中，平均查找时间是一个与数据库大小无关的常数；使用索引时，最坏情况下的查找时间和关系r中Ai值的个数的对数成正比；而散列文件在最坏情况下可能需要搜索所有记录。§8.6顺序索引和散列的比较1/13/202338索引支持的查询类型范围检索等值查询，或者叫点查询散列与索引比较举例之二selectA1,A2,…,AnfromrwhereAi>=c1ANDAi<=c2使用索引时，首先确定数据c1所在的位置，然后顺着索引顺序文件中的搜索码链表或B+树索引中的叶结点的Pn指针链继续查找，直到确定数据c2的位置为止；如果使用散列，由于散列函数的随机性，将不得不读取散列文件的所有存储桶。§8.6顺序索引和散列的比较1/13/202339索引的创建与删除原则上，DBMS可以自动决定创建什么样的索引，但实际上很少这样做。DBA和程序员都可以使用SQLDDL来创建和删除索引：创建索引createindex<index_name>on<relation_name>(<attribute_list>)createindexs_indexonstudent(student_name)删除索引dropindex<index-name>DBMS为优化查询而自动创建的索引是不能用drop语句删除的。§8.7SQL中索引的定义1/13/202340问题的提出到目前为止，都隐含地假设在关系上查询时只使用一个索引或散列；如果存在多个索引，该如何处理呢？例如：假设文件student上有两个索引，分别建立在student_name和department_name上。考虑如下查询：selectstudent_numberfromstudentwherestudent_name=“陈国围”ANDdepartment_name=“计算机系”问题：对于这