【11.1】 索引--线性索引

一、基本概念

输入顺序文件 ( entry-sequenced file )

按照记录进入系统的顺序存储记录

• 输入顺序文件相当于一个磁盘中未排序的线性表
• 因此丌支持高效率的检索

主码

主码( primary key ) 是数据库中的每 条记录的 唯一 标识

• 例如，公司职员信息的记录的主码可以是职 员的身份证号码
• 如果只有主码，丌便于各种灵活检索

辅码( secondary key )

是数据库中可以出现重复值的码

• 辅码索引把一个辅码值不具有这个辅 码值的每一条记录的主码值关联起来
• 大多数检索都是利用辅码索引来完成的

索引

• 索引( indexing ) 是把一个关键码不它对应的数 据记录的位置相关联的过程

• (关键码，指针)对，即( key, pointer )

• 指针指向主要数据库文件(即“主文件”)中的完整记录

• 索引文件( index file ) 是用于记录这种联系的文 件组织结构

• 索引技术是组织大型数据库的一种重要技术

• 高效率的检索

• 插入、更新、删除

索引文件

• 一个主文件可以有多个相关索引文件
• 每个索引文件往往支持一个关键码字段 * 不需要重新排列重排主文件
• 可以通过该索引文件高效访问记录中 该关键码值

稠密索引 vs 稀疏索引

• 稠密索引:对 每个 记录建立一个索引项

• 主文件不按照关键码的顺序排列

• 稀疏索引:对 一组记录建立一个索引项

• 记录按照关键码的顺序存放

• 可以把记录分成多个组(块)

• 索引指针指向的这一组记录在磁盘中的起始位置

线性索引文件

• 按照关键码的顺序进行排序
• 文件中的指针指向存储在磁盘上的文件记录起始位置或者主索引中主码的起始位置

二、线性索引的问题

• 线性索引太大，存储在磁盘中

• 在一次检索过程中可能多次访问磁盘， 从而影响检索的效率

• 使用二级线性索引

• 更新线性索引

• 在数据库中插入或者删除记录时

三、二级线性索引

• 例如，磁盘块的大小是 1024 字节，每对 (关键码，指针)索引对需要 8 个字节

• 1024 / 8 = 128

• 每磁盘块可以存储 128 条这样的索引对

• 假设数据文件包含 10000 条记录

• 稠密一级线性索引中包含 10000 条记录 。 10000/128 = 78.1 ； 那么一级线性索引占用 79 个磁盘块

• 相应地，二级线性索引文件中有 79 项索引对

• 这个二级线性索引文件可以在一个磁盘块

二级线性索引的例子

• 关键码与相应磁盘块中第一条记录的关键码的值相同
• 指针指向相应磁盘块的起始位置

1. 二级线性索引文件读入内存
2. 二分法找关键码的值小于等于2555的最大关键码所在一级索引磁盘块地址—— 关键码为2003的记录
3. 根据记录2003中的地址指针找到其对应的一级线性索引文件的磁盘块，并把该块读入内存
4. 按照二分法对该块进行检索，找到所需要的记录在磁盘上的位置
5. 最后把所需记录读入，完成检索操作

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾