索引技术-数据结构与算法-课件-北京工业大学-11.pdf

2011/12/25 第11章 索引技术 基本概念——输入顺序文件 11.1 线性索引 所谓输入顺序文件是指按照记录进入 11.2 静态索引 系统的顺序存储记录。它的特点是： 11.3 倒排索引 输入顺序文件的结构相当于一个磁盘 11.4 动态索引 中未排序的线性表，因此不支持高效 11.5 位索引技术 率的检索。 11.6 红黑树 1 2 基本概念——主码、辅码 基本概念——索引 主码 ( primary key )是数据库中的每条记 索引( indexing )是把一个关键码与 录的唯一标识。例如，公司职员信息的记 它对应的数据记录的位置关联起来的 录的主码可以是职员的身份证号码。如果 只有主码，不便于各种灵活检索。 过程。索引技术是组织大型数据库的 辅码 ( secondary key )是数据库中可以出 一种重要技术。由于数据库组织将大 现重复值的码。辅码索引把一个辅码值与 量的记录存储在外存上，所以高效率 具有这个辅码值的每一条记录的主码值关 的检索和有效的插入、更新、删除十 联起来。大多数检索都是利用辅码索引来 分关键。 完成的。 3 4 基本概念——索引文件 索引文件并不需要重新排列记录在磁盘 索引文件 (index file)是用于记录这 中的顺序（不用重排主文件） 种联系（关键码与它对应的数据记录 的位置）的文件组织结构。 一个数据库可能有多个索引文件 索引文件的记录 每个索引文件往往支持一个关键码  （关键码/指针）对 可以通过索引文件高效地访问记录中这  将每个关键码和一个指针关联 个关键码值  指针指向主要数据库文件（也称为 “主文件”）中的完整记录 5 6 1 2011/12/25 基本概念——稠密索