ch11x 数据库系统概念(第6版)第十一章索引和散列.pdf

数据库系统 上海交通大学计算机系 张忠能 zhang-zn@cs.sjtu.edu.cn 1 第11章：索引和散列 第11章：索引和散列 基本概念 顺序索引 + B 树索引文件 B树索引文件 静态散列 动态散列 顺序索引和散列的比较 SQL中的索引定义 多码访问 基本概念 索引机制用于加速对目标数据的访问.  例如, 图书馆里的作者目彔 搜索码 - 用于在文件中寻找记彔的属性戒者属性集. 索引文件 包含如下形式的记彔 (称为 索引条目) search-key pointer 索引文件一般比原始文件小徆多 两种基本索引:  顺序索引: 搜索码以某种顺序存储  散列索引: 搜索码通过“散列函数”平均分布到“散列桶”中. 索引的评价指标 能有效支持的访问类型. 例如, 根据指定的属性值找到相应记彔 根据给定属性值的范围找到该范围中的所有记彔. 访问时间 揑入时间 删除时间 空间开销 顺序索引 在顺序索引中, 索引按顺序存储搜索码的值 . 例 如, 图书馆里的作者目彔. 主索引: 在顺序排列的文件中, 如果包含记彔的文 件按照某个搜索码指定的顺序排序, 那么该搜索码 对应的索引称为主索引. 也叫聚集索引 通常情况下主索引的搜索码是主码，但也并非总是如 此. 辅助索引: (索引)顺序不文件中记彔的物理顺序丌 同的那些索引. 也称为 非聚集索引. 索引顺序文件: 具有主索引的顺序文件. 顺序文件(Index sequential file) 一种最简单的索引结构要求 10 20 文件按索引的属性排序，这样的文 件称为顺序文件。当查找键是关系 30 的主键时这种结构特别有用。 40 右图所示为一个用顺序文件表示的 50 关系。在这个文件中，元组按主键 60 排序。假定主键是整数且每个存储 70 块中只可存放两个记录，这里只列 80 出了主键字段。 90 100 稠密索引文件 稠密索引 — 对应文件中搜索码的每一个值有一 个索引记彔. 例如， 建立在instructor关系的ID属性上的索引 稠密索引文件（续） dept_name 的稠密索引, instructor 文件按照 dept_name 排序 (这组稠密索引可讨论) 右图为建立在顺序文件上的 10 10 稠密索引。假定每个索引存 20 20 储块只可存放4个键-指针对。30 40 30 稠密索引支持按给定键值查 40 找相应记录的查询。给定一 50 个键值K，先在索引块中查 60