《索引与散列》PPT课件.ppt

《《索引与散列》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章索引与散列张建英内容提要1索引1.1作用1.2分类及术语1.3SQL中索引的定义2树型索引2.1静态索引ISAM2.2动态索引B+Tree3散列索引3.1散列文件3.2散列索引3.3可扩充的散列索引多码访问1概述有时要通过限定某些列的取值来查找数据如：在学生表里，查找系别是计算机的学生查找年龄小于18的学生。文件上的索引是基于磁盘的数据结构，它能加快查找特定条件数据的速度。一个关系的列的所有子集都可能做为一个查询条件。索引键（搜索码）不一定是关系的主键。一个索引包含一个数据入口的集合，根据检索码，支持高效检索所有符合条件的数据。1.1问

2、题使用索引支持什么样的选择?选择的条件如：fieldNamevalue等值选择：=范围选择：>,>=,<,<=,between更复杂的选择两维范围查询：长江以北，黄河以南；京广线以西，京九线以东的地区。两维距离查询：北京200公里内的地区。查询结果排序：离北京最近的10个地级城市。染色体组匹配常见的n维索引：R-tree(oracle中支持)1.2索引的分类支持什么样的选择:范围、等值索引中数据入口的表示1、真实数据2、<搜索码值，rowid>3、<搜索码值，rowid,rowid,…>聚集（Clustered）索引与非聚集索引单键索

3、引与复合键索引基于树的索引、基于hash的索引稀疏索引与稠密索引注：一个文件可以有多个索引。一般来讲，索引含有些辅助信息帮助找到所需的数据入口。1.2索引项中是真实数据的索引该索引结构是数据组织在一起的文件（如堆文件或索引文件）。在一个给定的数据集上，只能有一个这样的索引。即只能排一个次序存放数据。节省用指针搜索数据的时间，但插入数据与删除数据开销大。1.2索引中数据入口的表示2、<搜索码值，rowid>3、<搜索码值，rowid,rowid,…>对于上面的两种方案来说，比存放真实数据的要易于维护。方案3比2要节省空间，但要用变长记录，且长度

4、不定，有可能超过磁盘块的大小。1.2聚集与非聚集索引聚集索引：如果搜索码值顺序与记录的物理顺序一致，那么在这个搜索码上建立的索引就是主索引，主索引也叫聚集索引。假定索引项采用<搜索码值，rowid>形式，且数据记录存储在一个堆文件中。IndexentriesDataentriesdirectsearchfor(IndexFile)(Datafile)DataRecordsdataentriesDataentriesDataRecordsCLUSTEREDUNCLUSTERED1.2采用聚集索引的利弊好处有利于范围选择。可以有一定程度的压缩（稀

5、疏索引）。由于位置的原因，带来好的效益。（按所排序访问数据，减少I/O）弊维护较复杂,立即或批量整理。1.2稀疏索引与稠密索引稠密索引：对应文件中搜索码的每一个值有一个索引记录（或索引项）。索引记录包括搜索码值和指向具有该搜索码值的数据记录的指针。稀疏索引：只为搜索码的某些值建立索引记录。和稠密索引一样，每个索引记录也包括搜索码值和指向具有该搜索码值的第一个数据记录的指针。DataRecords稠密索引DataRecords稀疏索引1.2复合索引在列的组合上建立为何需要复合索引？单独的条件查找的结果都很多，结合在一起的查询结果一般却很少。或复

6、合条件查询的比例特别高。1.2多级索引多级索引：象对待任何其他顺序文件那样来对待索引结构，即在主索引上再构造一个稀疏索引，以避免要访问的索引结构过于庞大而影响性能；......数据块0数据块1数据块m数据块n内层索引1.3SQL中索引的定义⑴创建索引createindexon()createindexstdno_indexonstudents(stdno)⑵删除索引dropindexDropindexstdno_index2树形索引树

7、形索引支持等值检索与范围检索。有多种索引方法可以对数据进行定位，对于同一数据可以有多个索引。ISAM:静态的结构;B+tree:动态结构,在插入与删除时处理得很好。ISAM:IndexedSequentialAccessMethod是一种很老的索引方法，通常来讲B+Tree会更好些。比B+tree简单，但有许多相似的思想。2树形检索与二分查找对于排序后的数据，通过二分查找有助于加快索引速度。平均检索时间是O(log2n)。若每次都要访问一次磁盘，需要O(log2n)次访盘。当n很大时，需要的I/O会难以接受。解决办法，2->大。通过创建索引，

8、加大每次查找的分支来实现。Page1Page2PageNPage3DataFilek2kNk1IndexFile2.1ISAM为什么要按页组织各个节点？P0K1P1