数据结构-王红梅-第9章_索引技术

清华大学出版社

数据结构(C++版)第2版

第9章

索引技术

本章的基本内容是： 索引的基本概念 线性索引技术 树形索引

清华大学出版社

数据结构(C++版)第2版

9.1 索引的基本概念数据结构的最终目的是提高数据的处理速度， 索引是为了加快查找速度而设计的一种数据结 构，索引技术是组织大型数据库以及磁盘文件 的一种重要技术。 在索引问题以及数据库中，常常将数据元素 称为记录。

清华大学出版社

数据结构(C++版)第2版

9.1 索引的基本概念索引的基本概念 文件：通常指存储在外存上的记录集合。 索引：把一个关键码与它对应的记录相关联的过程 称为索引。索引由若干索引项构成。 索引项至少应包含关键码和关键码对应的记录在存 储器中的位置等信息。 静态索引：索引结构在文件创建时生成，一旦生成 就固定下来，只有当文件再组织时才允许改变。 动态索引：在文件创建时生成索引结构，在文件执 行插入/删除操作时，索引结构本身也随之发生改变。

清华大学出版社

数据结构(C++版)第2版

9.1 索引的基本概念索引的基本概念 线性索引：若将索引项组织为线性结构，则称其 为线性索引或索引表； 树形索引：若将索引项组织为树结构，则称其为 树形索引。 多级索引：对索引再建立一个索引，就构成了多 级索引。 对一些大型文件，其索引本身可能也很大，在这种情 况下，可以建立多级索引。

清华大学出版社

数据结构(C++版)第2版

9.2 线性索引技术稠密索引 稠密索引：在线性索引中，若文件中的每个记录 对应一个索引项，则这种索引称为稠密索引。 在稠密索引中，无论文件是否按关键码有序，索 引项总是按关键码顺序排列。 只要内存空间允许，通常把稠密索引存储在内存 中，从而大大提高记录的查找速度。

稠密索引主要适用于静态索引。

清华大学出版社

数据结构(C++版)第2版

9.2 线性索引技术稠密索引示例关键码 指针 关键码 其它数据项

8 20 35 40 52 56 61索引表 有序

r1 r2 r3 r4 r5 r6 r7

8 20 52 35 40 61 56

… … … … … … …文件

无序或有序

清华大学出版社

数据结构(C++版)第2版

9.2 线性索引技术稠密索引文件外存

稠密索引内存

优点：实现对数据库记录有效的查找(采用折半查 找技术)和随机访问(按记录号访问)。 缺点：如果文件中包含的记录太多，索引表本身可 能会因为太大而无法在内存中存储；文件中插入或 删除记录，必须更新稠密索引，而稠密索引的插入 和删除操作代价很高。

清华大学出版社

数据结构(C++版)第2版

9.2 线性

索引技术分块索引稠密索引空间代价很大 减少索引项的个数

分块索引 每块建立一个索引项多级索引 分块索引需要将文件划分为若干块，且要求分块有序。

分块有序

块内无序：每一块内不要求有序

块间有序：块与块之间有序

清华大学出版社

数据结构(C++版)第2版

9.2 线性索引技术分块索引关键码 其他数据项 最大值 块长 块首地址

35 61 88有序

3 3 3索引表

35 20 8 52 40 61 65 88 76

… … … … … … … … …文件

第 1 块 第 2 块 第 3 块

清华大学出版社

数据结构(C++版)第2版

9.2 线性索引技术分块索引在分块索引表中进行的查找称为分块查找(也称 为索引顺序查找),分两步进行： ⑴ 在索引表中确定待查关键码所在的块； ⑵ 在相应块中查找待查关键码。 索引表查找 顺序查找

折半查找

块内查找——顺序查找

清华大学出版社

数据结构(C++版)第2版

9.2 线性索引技术分块索引设有n个记录的文件分为m个块，每个块均为t个 记录，则n=m×t。设Lb为查找索引表确定关键码所 在块的平均查找长度，Lw为在块内查找关键码的平 均查找长度，则分块查找的平均查找长度为： ASL=Lb + Lw 若采用顺序查找对索引表进行查找，则分块查 找的平均查找长度为：(m 1) (t 1) 1 m ( t) 1 ASL=Lb + Lw= 2 2 2 t

当 t 取 n 时，ASL取最小值 n +1。

清华大学出版社

数据结构(C++版)第2版

9.2 线性索引技术多重表为文件建立索引的目的是什么? 稠密索引、分块索引 对主关键码建立索引 对主关键码进行查找 多重表、倒排表 对次关键码建立索引 对次关键码进行查找

清华大学出版社

数据结构(C++版)第2版

9.2 线性索引技术多重表多重表除了为文件建立一个主索引外，还为每个 需要查找的次关键码建立一个索引。 在文件中，为建立索引的次关键码分别增设一个 指针域，用于将次关键码相同的记录链结在一起 (稠密索引),或将在同一块中的记录链结在一 起(分块索引)。

清华大学出版社

数据结构(C++版)第2版

9.2 线性索引技术多重表关键码 指针 0001 0002 0003 0004

职工号0001 0002 0003 0004 0005

姓名王刚 张亮 刘楠 齐梅 李爽

性 别男 男 女 女 女 02 06 04 05 ∧

年龄30 25 27 25 30 03 04 05 06 ∧

00050006

0006

王东

男

∧

24

∧

主索引次关键码 男 女 头指针 01 03 “性别”次索引 长度 3 3 次关键码 24~26 27~30

文件 头指针 02 01 长度 3 3

“年龄”次索引

清华大学出版社

数据结构(C++版)第2版

9.2 线性索引技术倒排表关键码 指针 0001 0002 0003 0004 职工号 0001 0002 0003 0004 0005 0006 姓名 王刚 张亮 刘楠 齐梅 李爽 王东 文件 性别 男 男 女 女 女 男

年龄 30 25 27 25 30 24

00050006

主索引

次关键码 男 女

记录号表 01, 02, 06 03, 04, 05

次关键码 24~26 27~30

记录号表 02, 04, 06 01, 03, 05

“性别”倒排

“年龄”倒排

清华大学出版社

数据结构(C++版)第2版

9.3 树形索引2–3树2-3树：是具有下列特性的树： ⑴ 一个结点包含1个或者2个关键码。 ⑵ 每个内部结点有2个子女(包含一个关键码)或者 3个子女(包含两个关键码)。 ⑶ 所有叶子结点都在树的同一层。