数据库基本原理与应用第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