索引 索引文件 褰的位相类 码与它对应的数 个主文件可能有多个相关索引 文件 魏對腐主要数都库文件〔也称为主文件?)中的 每个索引文件往往支持一个关键 赛组爽菇和m)是用于记录这种联系的文 码字段 ■索引技术是组织大型数据库的一种重要技术 不需要重新排列重排主文件 高效率的检索 插入、更新、删除 可以通过该索引文件高效访问记 录中该关键码值 k 大学息 孔陪写 点权新有,郭究 北大驰鑫 张帖写 稠密索引vs稀疏索引 101线性索引 稠密索引:对每个记录建立一个索引项 基本概念 主文件不按照关键码的顺序排列 ■稀疏索引:对一组记录建立一个索引 个线性索引的优点 记录按照关键码的顺序存放 可以把记录分成多个组(块) 个线性索引的问题 紫引指针指向的这一组记录在磁盘中的起始位置 Q二级线性索引 京大息 张帖写 权新有,轨敢向究 孔写 线性索引文件 线性索引的优点 ■按照关键码的顺序进行排序 对变长的数据库记录的访问 文件中的指针指向存储在磁盘上的文件记录起 始位置或者主索引中主码的起始位置 可以对数据进行高效检索 ■二分检索 线性素引文件 顺序处理 比较操作 批处理的操作 数据库记录 ■节省空间(相对其它索引结构) 北京大息学 张铭 新,收即究 张帖写2 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 7 索引 „ 索引( indexing )是把一个关键码与它对应的数 据记录的位置相关联的过程 „ (关键码，指针)对，即(key, pointer) „ 指针指向主要数据库文件（也称为“主文件”）中的 完整记录 „ 索引文件( index file )是用于记录这种联系的文 件组织结构 „ 索引技术是组织大型数据库的一种重要技术 „ 高效率的检索 „ 插入、更新、删除 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 8 索引文件 „ 一个主文件可能有多个相关索引 文件 „ 每个索引文件往往支持一个关键 码字段 „ 不需要重新排列重排主文件 „ 可以通过该索引文件高效访问记 录中该关键码值 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 9 稠密索引 vs 稀疏索引 „ 稠密索引：对每个记录建立一个索引项 „ 主文件不按照关键码的顺序排列 „ 稀疏索引：对一组记录建立一个索引 „ 记录按照关键码的顺序存放 „ 可以把记录分成多个组（块） „ 索引指针指向的这一组记录在磁盘中的起始位置 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 10 10.1 线性索引 „ 基本概念 „ 线性索引的优点 „ 线性索引的问题 „ 二级线性索引 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 11 线性索引文件 „ 按照关键码的顺序进行排序 „ 文件中的指针指向存储在磁盘上的文件记录起 始位置或者主索引中主码的起始位置 37 55 73 92 92 73 37 55 线性索引文件 数据库记录 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 12 线性索引的优点 „ 对变长的数据库记录的访问 „ 可以对数据进行高效检索 „ 二分检索 „ 顺序处理 „ 比较操作 „ 批处理的操作 „ 节省空间 (相对其它索引结构)