主题：课件8下载——索引和查询

Flash课件浏览为：

http://www.njmars.net/UploadFile/DB/八）索引和查询_.swf

课件下载链接为：点击下载（SWF文档）

1 索引 1.1 主索引（顺序文件的索引） 一种最简单的索引结构要求文件按索引的属性排序，这样的文件称为顺序文件，然后构建排序字段索引 可以分为：稠密索引、稀疏索引、多级索引

1.1.1 稠密索引 对每个字段值都在索引中表示出来 特点在于索引数据全面，查询速度较快

1.1.2 稀疏索引 较前者节省存储，只对每个存储块设一个索引键值对 需要二次访问外存才能实现信息搜索

1.1.3 多级索引 对索引文件本身建立的索引 通常一级索引可以为稠密型，也可以为稀疏型，而二级索引必须为稀疏型才有意义 需要多次访问外存才能检索信息

1.1.4 重复字段的索引 可以使用稠密索引，允许索引文件中出现重复的查找键。查找时，一旦在索引文件中找到具有匹配键值的第一个索引项，后面紧接着就是其他的具有相同键值的索引项，然后依据这些索引的指针找出所有具有此键值的记录 更为有效的方法是为每个不同键值只设一个索引项，该索引项的指针指向此键值的第一个记录，由于在排序的数据文件中，记录一定紧跟在所找到的记录后存放，所以只需在数据文件中顺序向前查找即可

重复字段索引的查找之一 先在索引中找键值指定的索引项 并顺着它的指针找到第一个匹配键值的记录，然后在数据文件中继续往前找，直到找完为止

重复字段的索引的查找之二 先找到索引中键值大于或等于指定键值的最后一个索引项 然后往索引起始的方向找，直到碰到第一个索引项或碰到一个严格小于指定键值的索引项为止

重复字段的索引的查找之三 为数据块中新的、即未在前一块中出现过的最小键值设一个索引项 如没有新键值出现，就为该块中唯一的键值设一个索引块 查找第一个键值满足等于或者小于指定键值的索引项，然后继续查找其他数据块

1.2 辅助索引 辅助索引可用于任何索引目的：这种数据结构有助于查找给定一个或多个字段值的记录 辅助索引与主索引最大的差别在于辅助索引不决定数据文件中记录的存放位置。而仅能告诉我们记录的当前存放位置，这一位置可能是由建立在其他某个字段上的主索引确定的 辅助索引和主索引的这一差别有一个有趣的推论：辅助索引总是稠密索引

1.2.1 辅助索引的设计

1.2.2 辅助索引的应用

1.2.3 辅助索引中桶的使用 在桶中求交集

1.2.4 辅助索引的功能 不仅加快记录定位，而且只利用索引本身也可以进行一般的查询

1.2.5 倒排索引 多年来，信息检索界都在处理文档的存储和按关键字集高效检索文档的问题 随着WWW的出现以及在线保存所有文档成为可能，基于关键字的文档检索已成为数据库最大的难题之一

常见的形式是将每一个文档看成是关系的一个的元组，这个关系有很多属性，每个属性对应于文档可能出现的一个词，每个属性都是布尔型：表明该词在该文档出现还是没有出现 因此，这一关系模式可以被看作：Doc（word1，word2，…），其中wordi取值为真当且仅当该文档中至少出现一次该词

关系的每个属性上都建有辅助索引，不过不必为属性值为FALSE的元组建索引项；相反，索引只会给值为真的词语建立索引 并且索引文件不是给每个属性（即每个词）建立一个单独的索引，而是把所有的索引合成一个，称为倒排索引，这个索引一般使用桶文件来提高空间利用率

倒排索引本身由一系列词-指针对组成；词实际上是索引的查找键 和其他任何一种索引一样，倒排索引被存储在连续的块中。不过，在一些文档检索应用中，数据的变化不像典型数据库中那样频繁，因而通常也就不用提供应付块溢出或索引变化的措施

有很多技术可用于改进基于关键字的文档检索效率： 抽取词干：在将单词的出现放入索引中之前，删除词的后缀以找出它的“词干”，例如复数名词可被当作其单数形式处理 无用词：像“the”、“and”之类最常用的词称为无用词，通常不包含在倒排索引中，原因在于好几百个常用词出现在太多的文档中，以至于它根本无益于检索特定主题，而且还可以明显地缩小索引

Google数据库简介 和目录式搜索引擎不同，Google是一种索引式搜索引擎，因此，它的工作过程中几乎都是依*程序自动完成，而几乎不涉及人为的影响因素 步骤之一 Google使用高速的分布式爬行器Crawler系统中的漫游遍历器Googlebot定时地遍历网页，将遍历到的网页送到存储服务器Store Server 步骤之二 存储服务器使用bzip格式压缩软件将这些网页进行无损压缩后存入数据库Repository中 Repository获得了每个网页的完全Html代码后，对其压缩后的网页及URL进行分析，记录下网页长度、URL、URL长度和网页内容，并赋予每个网页一个文档号docID，以便当系统出现故障的时候，可以及时完整地进行网页的数据恢复 步骤之三 索引器Indexer从Repository中读取数据，以后做以下四步工作： 将读取的数据解压缩后进行分析，它将网页中每个有意义的词进行统计后转化为关键词wordID的若干索引项Hits，生成索引项列表，该列表包括关键词、关键词的位置、关键词的大小和大小写状态等 索引项列表被存入到数据桶Barrels中，并生成以文档号docID排序的顺排档索引。索引项根据其重要程度分为两种：当索引项中的关键词出现在URL、标题、锚文本AnchorText和标签中时，表示该索引项比较重要，称为特殊索引项FancyHits；其余情况则称为普通索引项PlainHits 索引器除了对网页中有意义的词进行分析外，还分析网页的所有超文本链接，将其Anchor Text、URL指向等关键信息存入到Anchor文档库中 索引器生成索引词表Lexicon，它包括两个部分：关键词的列表和指针列表（wordID和docID），用于倒排档文档相连接 索引器还将分析过的网页编排成一个与Repository相连接的文档索引Document Index，并记录下网页的URL和标题，以便可以准确查找出在Repository中存储的原网页内容。而且把没有分析的网页传给URL Server，以便在下一次工作流程中进行索引分析 步骤之四 URL分析器URL Resolver读取Anchor文档中的信息 将其锚文本Anchor Text所指向的URL转换成网页的docID 将该docID与原网页的docID形成“链接对”并存入Link数据库中，Link记录了网页的链接关系用来计算网页的PageRank值 将Anchor Text指向网页的docID与顺排档特殊索引项Anchor Hits相连接 步骤之五 文档索引Document Index把没有进行索引分析的网页传递给URL Server ，URL Server则向Crawler提供待遍历的URL，这样，这些未被索引的网页在下一次工作流程中将被索引分析 步骤之六 排序器Sorter对数据桶Barrels的顺排档索引重新进行排序，生成以关键词wordID为索引的倒排档索引 步骤之七 将生成的倒排档索引与先前由索引器产生的索引词表Lexicon相连接产生一个新的索引词表供搜索器Searcher使用。搜索器的功能是由网页服务器实现的，根据新产生的索引词表结合上述的文档索引Document Index和Link数据库计算的网页PageRank值来匹配检索 在执行检索时，Google通常遵循以下步骤（以下所指的是单个检索词的情况）： 将检索词转化成相应的wordID 利用Lexicon检索出包含该wordID网页的docID 根据与Lexicon相连的倒排档索引，分析各网页中的相关索引项的情况，计算各网页和检索词的匹配程度，必要时调用顺排档索引 根据各网页的匹配程度，结合根据Link产生的相应网页的PageRank情况，对检索结果进行排序 调用Document Index的docID及其相应的URL，将排序结果生成检索结果的最终列表，提供给检索用户 检索包含多个检索词的情况与此类似：先做单个检索词检索，然后根据检索式中检索要求进行必要的布尔操作或其它操作

2 查询 查询处理的一般步骤 查询优化

2.1 查询处理的一般步骤 查询分析：语法分析、规范检查 查询检查：根据数据字典检查对象是否有效，权限和完整性的检查 查询优化：代数优化（改变表达式的次序和组合），物理优化（选择存取路径和底层操作算法） 查询执行：生成查询计划

2.2 查询优化 利用系统本身来完成查询优化：根据数据字典获取统计信息，如关系中的元组数量、字段建立索引的情况，比人工操作更为有效和全面

SQL优化：用户调整查询语句来完成的查询优化，需要经验的积累和对数据库管理系统的理解程度

2.2.1 系统本身完成的查询优化

2.2.1.1 算法的选择 选择 简单的全表顺序扫描（适用于小表） 利用索引扫描 利用索引确定应该命中的记录范围 有些操作直接利用索引即可得到结果

连接 嵌套循环方法 排序归并方法 索引连接方法 排序归并方法

2.2.1.2 查询优化的类型 代数优化就是通过对关系代数表达式的等价变换来提高查询效率 几个基本原则 选择应尽可能先做 将对同一个关系的投影和选择同时进行 将选择和连接同时进行 缓存公共表达式的计算结果

查询优化的例子 查询选修了A101课程的学生姓名： Select name from stu,grade where stu.number=grade.number and course=‘A101’ 三种处理方法之一 直接计算笛卡儿乘积，再进行选择和投影 利用自然连接替换笛卡儿乘积操作，再进行选择和投影 先对grade表格进行选择操作，将满足条件的记录与stu表进行自然连接，再进行投影

物理优化就是选择高效合理的操作算法或者存取路径，求得优化的查询计划 几个基本原则 对于小关系，建议使用全表顺序扫描 先估算查询结果元组数目，如果比例过小可以使用索引，如果过大，建议使用全表顺序扫描 对于组合字段查询，建议使用复合字段索引

2.2.2 SQL优化 SQL优化是指用户通过调整SQL语言实现的查询优化

当插入的数据为数据表中的记录数量的10%以上，首先需要删除该表的索引来提高数据的插入效率，当数据插入后，再建立索引

避免在索引列上使用函数或计算，在where子句中，如果索引是函数的一部分，优化器将不再使用索引而使用全表扫描，如： 低效做法：select * from emp where sal*12>2000 高效做法：select * from emp where sal>2000/12 非要对一个使用函数的列启用索引，基于函数的索引是一个较好的方案

避免在索引列上使用not和 “!=”，索引只能告诉什么存在于表中，而不能告诉什么不存在于表中，当数据库遇到not 和 “!=”时，就会停止使用索引而去执行全表扫描，如： 低效做法：select * from stu where sex<>0 高效做法：select * from stu where sex=1

在索引列上使用“>=”代替“>” 低效做法：select * from emp where deptno > 3 高效做法：select * from emp where deptno >=4 两者的区别在于，前者将首先定位到deptno等于3的记录并且向前扫描到第一个deptno大于3的，而后者将直接跳到第一个deptno等于4的记录

那些可以过滤掉大量记录的条件必须写在where子句的前面 如男员工较多而属于011部门的员工较少： 低效做法：select * from emp where depno=‘011’ and sex=1 高效做法：select * from emp where sex=1 and depno=‘011’

用exists替代in，用not exists替代not in都可以提高查询的效率

可以将不需要的记录在group by之前过滤掉 低效做法：select job, avg(sal) from emp group by job having job = ‘president’ or job=’manager’ 高效做法：select job, avg(sal) from emp where job=’president’ or job=’manager’ group by job