北京大学：《数据结构与算法》课程教学资源（PPT课件讲稿）11、索引技术

国家级精品课程—《数据结构与算法》 第11章索引 张铭、赵海燕、王腾蛟、宋国杰、高军 http:/www.ipk.pku.edu.cn/pkuipk/courselsig 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔:张铭 版权所有,转载或翻印必究

国家级精品课程—《数据结构与算法》 张铭、赵海燕、王腾蛟、宋国杰、高军 http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔：张铭 ©版权所有，转载或翻印必究 第11章 索引

主要内容 基本概念 11线性索引 112静态索引 113倒排索引 114动态索引—B/B+树 115位索引技术 116红黑树以前的录像 ohttp://www.jpk.pkuedu.cn/pkujpk/courselsjig/ honor/RBTree BSTAppPKUZM html “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 主要内容 ◼ 基本概念 ◼ 11.1 线性索引 ◼ 11.2 静态索引 ◼ 11.3 倒排索引 ◼ 11.4 动态索引 —— B/B+树 ◼ 11.5 位索引技术 ◼ 11.6 红黑树——以前的录像 ❑ http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ honor/RBTree_BSTAppPKUZM.html

基本概念 输入顺序文件 主码与辅码 索引与索引文件 稠密索引与稀疏索引 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 基本概念 ◼ 输入顺序文件 ◼ 主码与辅码 ◼ 索引与索引文件 ◼ 稠密索引与稀疏索引

输入顺序文件 输入顺序文件( entry- sequenced file)按 照记录进入系统的顺序存储记录 口一般说来,输入顺序文件的结构相当于 个磁盘中未排序的线性表 口因此不支持高效率的检索 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 输入顺序文件 ◼ 输入顺序文件( entry-sequenced file )按 照记录进入系统的顺序存储记录 ❑ 一般说来，输入顺序文件的结构相当于一 个磁盘中未排序的线性表 ❑ 因此不支持高效率的检索

主码 主码( primary key)是数据库中的每条 记录的唯一标识 口例如,公司职员信息的记录的主码可以是 职员的身份证号码 口如果只有主码,不便于各种灵活检索 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 主码 ◼ 主码( primary key )是数据库中的每条 记录的唯一标识 ❑ 例如，公司职员信息的记录的主码可以是 职员的身份证号码 ❑ 如果只有主码，不便于各种灵活检索

辅码 辅码( secondary key)是数据库中可以出 现重复值的码 辅码索引把一个辅码值与具有这个辅码 值的每一条记录的主码值关联起来 口大多数检索都是利用辅码索引来完成的 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 辅码 ◼ 辅码( secondary key )是数据库中可以出 现重复值的码 ◼ 辅码索引把一个辅码值与具有这个辅码 值的每一条记录的主码值关联起来 ❑ 大多数检索都是利用辅码索引来完成的

索引 索引( indexing)-—(关键码,指针) 口指针指向“主文件”中的完整记录 索引文件( index file) 索引技术是组织大型数据库的一种重要技术 口高效率的检索 口插入、更新、删除 (20,a9)(21,a10 (45a13(47,a14 (50,a5)(52,a16) “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 索引 ◼ 索引( indexing )——(关键码，指针) ❑ 指针指向 “主文件”中的完整记录 ◼ 索引文件( index file ) ◼ 索引技术是组织大型数据库的一种重要技术 ❑ 高效率的检索 ❑ 插入、更新、删除 (20,a9) (21,a10) (45,a13)(47,a14) (50,a5) (52,a16)

索引文件 个主文件可能有多个相关索引文件 每个索引文件往往支持一个关键码字段 口不需要重新排列重排主文件 可以通过该索引文件高效访问记录中该关键码 值 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 索引文件 ◼ 一个主文件可能有多个相关索引文件 ❑ 每个索引文件往往支持一个关键码字段 ❑ 不需要重新排列重排主文件 ◼ 可以通过该索引文件高效访问记录中该关键码 值

稠密索引vs稀疏索引 稠密索引:对每个记录建立一个索引项 口主文件不按照关键码的顺序排列 稀疏索引:对一组记录建立一个索引 口记录按照关键码的顺序存放 口可以把记录分成多个组(块) 索引指针指向的这一组记录在磁盘中的起始位置 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 稠密索引 vs 稀疏索引 ◼ 稠密索引：对每个记录建立一个索引项 ❑ 主文件不按照关键码的顺序排列 ◼ 稀疏索引：对一组记录建立一个索引 ❑ 记录按照关键码的顺序存放 ❑ 可以把记录分成多个组（块） ◼ 索引指针指向的这一组记录在磁盘中的起始位置

11.1线性索引 基本概念 线性索引的优点 线性索引的问题 二级线性索引 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 11.1 线性索引 ◼ 基本概念 ◼ 线性索引的优点 ◼ 线性索引的问题 ◼ 二级线性索引