国家级精品课程—《数据结构与算法》
张铭、赵海燕、王腾蛟、宋国杰、高军http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/北京大学信息科学与技术学院"数据结构与算法"教学小组本章主笔:张铭版权所有,转载或翻印必究
第11章 索引
主要内容
基本概念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
基本概念
输入顺序文件主码与辅码索引与索引文件稠密索引与稀疏索引
输入顺序文件
输入顺序文件( entry-sequenced file )按照记录进入系统的顺序存储记录一般说来,输入顺序文件的结构相当于一个磁盘中未排序的线性表因此不支持高效率的检索
主码
主码( primary key )是数据库中的每条记录的唯一标识例如,公司职员信息的记录的主码可以是职员的身份证号码 如果只有主码,不便于各种灵活检索
辅码
辅码( secondary key )是数据库中可以出现重复值的码辅码索引把一个辅码值与具有这个辅码值的每一条记录的主码值关联起来大多数检索都是利用辅码索引来完成的
索引
索引( indexing )——(关键码,指针)指针指向 "主文件"中的完整记录索引文件( index file )索引技术是组织大型数据库的一种重要技术高效率的检索插入、更新、删除
(20,a9) (21,a10)
(45,a13)(47,a14)
(50,a5) (52,a16)
索引文件
一个主文件可能有多个相关索引文件每个索引文件往往支持一个关键码字段不需要重新排列重排主文件可以通过该索引文件高效访问记录中该关键码值
稠密索引 vs 稀疏索引
稠密索引:对每个记录建立一个索引项主文件不按照关键码的顺序排列稀疏索引:对一组记录建立一个索引记录按照关键码的顺序存放可以把记录分成多个组(块)索引指针指向的这一组记录在磁盘中的起始位置
11.1 线性索引
基本概念线性索引的优点线性索引的问题二级线性索引
线性索引文件
按照关键码的顺序进行排序文件中的指针指向存储在磁盘上的文件记录起始位置或者主索引中主码的起始位置
92
73
37
55
数据库记录
线形索引文件
线性索引的优点
对变长的数据库记录的访问可以对数据进行高效检索二分检索 顺序处理比较操作批处理的操作节省空间 (相对其它索引结构)
线性索引的问题
线性索引太大,存储在磁盘中在一次检索过程中可能多次访问磁盘,从而影响检索的效率使用二级线性索引更新线性索引在数据库中插入或者删除记录时
二级线性索引
例如,磁盘块的大小是1024字节,一个(key,point)索引对需要8个字节1024 / 8 = 128每个磁盘块可以存储128条这样的索引对假设数据文件包含10000条记录稠密一级线性索引中包含10000条记录10000/128 = 78.1那么一级线性索引占用79个磁盘块相应地,二级线性索引文件中有79项索引对这个二级线性索引文件可以在一个磁盘块
二级线性索引的例子
关键码与相应磁盘块中第一条记录的关键码的值相同指针指向相应磁盘块的起始位置
一级索引

下一页