主要内容 数据结构与算法 基本概念 第十章索引技术 Q101线性索引 任课教员:张铭 Q102静态索引 http:/db.pku.edu.cn/mzhang/ds mzhang@db.pku.edu.cn 103倒排索引 北京大学信息科学与技术学院 令104动态索引 网络与信息系统研究所 ⊙版权所有,转载或翻印必究 105动态、静态索引性能比较 北大驰鑫 张帖写 基本概念 输入顺序文件 输入顺序文件 输入顺序文件( entry- sequenced file) 令主码与辅码 按照记录进入系统的顺序存储记录 令索引与索引文件 般说来,输入顺序文件的结构相当 一个磁盘中未排序的线性表 ◇密索引与稀疏索引 因此不支持高效率的检索 京大息 张帖写 权新有,轨敢向究 北大恤 张帖写 主码 辅码 ■主码( primary key)是数据库中的每 辅码( secondary key)是数据库中可以出 条记录的唯一标识 现重复值的码 ■例如,公司职员信息的记录的主码可 ■辅码索引把一个辅码值与具有这个辅码 以是职员的身份证号码 值的每一条记录的主码值关联起来 如果只有主码,不便于各种灵活检索 大多数检索都是利用辅码索引来完成的 张帖情 权新有:轨即癣究1 数据结构与算法 第十章 索引技术 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 2 主要内容 „ 基本概念 „ 10.1 线性索引 „ 10.2 静态索引 „ 10.3 倒排索引 „ 10.4 动态索引 „ 10.5 动态、静态索引性能比较 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 3 基本概念 „ 输入顺序文件 „ 主码与辅码 „ 索引与索引文件 „ 稠密索引与稀疏索引 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 4 输入顺序文件 „ 输入顺序文件( entry-sequenced file ) 按照记录进入系统的顺序存储记录 „ 一般说来，输入顺序文件的结构相当 于一个磁盘中未排序的线性表 „ 因此不支持高效率的检索 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 5 主码 „ 主码( primary key )是数据库中的每 条记录的唯一标识 „ 例如，公司职员信息的记录的主码可 以是职员的身份证号码 „ 如果只有主码，不便于各种灵活检索 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 6 辅码 „ 辅码( secondary key )是数据库中可以出 现重复值的码 „ 辅码索引把一个辅码值与具有这个辅码 值的每一条记录的主码值关联起来 „ 大多数检索都是利用辅码索引来完成的