数据库基本原理与应用 第12章 索引结构
时间:2025-07-10
时间:2025-07-10
交通大学计算机系张教授上课用PPT。不是为了卖钱赚分,而是为了上课留个纪念。如果教授觉得有任何不妥,我会立即删除。
数据库系统上海交通大学计算机系
张忠能zhang-zn@http://www.77cn.com.cn
交通大学计算机系张教授上课用PPT。不是为了卖钱赚分,而是为了上课留个纪念。如果教授觉得有任何不妥,我会立即删除。
第12章:索引结构本章中,考虑下面几种设计和实现索引的方法:
排序文件上的简单索引(主索引) 非排序文件上的辅助索引
B树,一种可在任何文件上建立索引的常用方法 散列表,另一种有用而重要的索引结构
网格与位图
交通大学计算机系张教授上课用PPT。不是为了卖钱赚分,而是为了上课留个纪念。如果教授觉得有任何不妥,我会立即删除。
索引结构 索引的数据结构:它以记录的特征(通常是一个或多个字段的值)为输入,并能“快速地”找出具有该特征的记录。具体来说,索引使我们只需察看所有可能记录中的一小部分就能找到所需记录。建立索引的字段(组合)称为查找键,在索引时不言而喻也可称“键”。
值
索引
包含记录的块
对应的记录3
交通大学计算机系张教授上课用PPT。不是为了卖钱赚分,而是为了上课留个纪念。如果教授觉得有任何不妥,我会立即删除。
顺序文件上的索引 顺序文件
稠密索引 稀疏索引 多级索引 重复查找键的索引 数据修改期间的索引维护
交通大学计算机系张教授上课用PPT。不是为了卖钱赚分,而是为了上课留个纪念。如果教授觉得有任何不妥,我会立即删除。
顺序文件(Index sequential file)
一种最简单的索引结构要求文件按索引的属性排序,这样的文件称为顺序文件。当查找键是关系的主键时这种结构特别有用。右图所示为一个用顺序文件表示的关系。在这个文件中,元组按主键排序。假定主键是整数且每个存储块中只可存放两个记录,这里只列出了主键字段。
10 2030 40 50 60
70 8090 1005
交通大学计算机系张教授上课用PPT。不是为了卖钱赚分,而是为了上课留个纪念。如果教授觉得有任何不妥,我会立即删除。
稠密索引(Dense index)
稠密索引的块中只存放记录的键和指向记录本身的指针
数据文件中的每个键在索引中都被表示出来 存储索引文件比存储数据文件所需的块少得多。当内存容纳不下数据文件但能容纳下索引文件时,索引的优势尤为明显。
交通大学计算机系张教授上课用PPT。不是为了卖钱赚分,而是为了上课留个纪念。如果教授觉得有任何不妥,我会立即删除。
右图为建立在顺序文件上的 10稠密索引。假定每个索引存 20储块只可存放4个键-指针对。 30 40稠密索引支持按给定键值查找相应记录的查询。给定一 50个键值K,先在索引块中查 60找K。当找到K后,按照K所 70 80对应的指针到数据文件中寻找相应的记录。 90100以下几个因素使基于索引的 110查找更有效: 120
10 20 30 40 50 60 70 80 90 100
索引块数量通常比数据块数量少。 由于键被排序,可使用二分查找法来查找K 索引文件可能足够小,可以永久存放在主存缓冲区中。7
交通大学计算机系张教授上课用PPT。不是为了卖钱赚分,而是为了上课留个纪念。如果教授觉得有任何不妥,我会立即删除。
稀疏索引(Sparse index) 稠密索引太大时,可使用稀疏索引 稀疏索引节省存储空间,但查找给定值的记录需更多的时间
稀疏索引只为每个存储块设一个键-指针对,键值是每个数据块中第一个记录的对应值。 稀疏索引要求文件按索引键排序
交通大学计算机系张教授上课用PPT。不是为了卖钱赚分,而是为了上课留个纪念。如果教授觉得有任何不妥,我会立即删除。
右图所示为建立在顺序文件上的稀疏索引。要找出键值为K的记录,我们得在索引中查找键值小于或等于K的最大键值。由于索引文件已经按键排序,我们可以使用二分查找法来
定位这个索引项,然后根据它的指针找到相应的数据块。
10 30 50 70 90 110 130 150 170 190 210 230
10 20
30 4050 60 70 80
90 100
交通大学计算机系张教授上课用PPT。不是为了卖钱赚分,而是为了上课留个纪念。如果教授觉得有任何不妥,我会立即删除。
多级索引(Multi-level index) 索引文件本身可能占据多个存储块,要是这些存储块不能很快找到的某个地方,就可能需要另一种数据结构来找到这些索引存储块。
通过在索引上再建索引,能够使第一级索引更为有效。
交通大学计算机系张教授上课用PPT。不是为了卖钱赚分,而是为了上课留个纪念。如果教授觉得有任何不妥,我会立即删除。
右图是在稀疏 10索引的基础上 90增加二级索引 170 250得到的。我们还可以在二级 330索引的基础上 410建立三级索引。490在这个例子中,570一级索引是稀疏的,也可以选择稠密索引作为一级索引。但二级和更高级的索引必须是稀疏的。
10 30 50 70 90 110 130 150 170 190 210 230
10 20 30 40 50 60 70 80 90 100
交通大学计算机系张教授上课用PPT。不是为了卖钱赚分,而是为了上课留个纪念。如果教授觉得有任何不妥,我会立即删除。
稠密索引和稀疏索引的比较 稠密索引: …… 此处隐藏:962字,全部文档内容请下载后查看。喜欢就下载吧 ……
下一篇:我国现阶段人口问题及其对策