数据库基本原理与应用 第12章 索引结构

时间: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字,全部文档内容请下载后查看。喜欢就下载吧 ……

数据库基本原理与应用 第12章 索引结构.doc 将本文的Word文档下载到电脑

    精彩图片

    热门精选

    大家正在看

    × 游客快捷下载通道(下载后可以自由复制和排版)

    限时特价:7 元/份 原价:20元

    支付方式:

    开通VIP包月会员 特价:29元/月

    注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
    微信:fanwen365 QQ:370150219