线性索引的优点 对变长的数据库记录的访问 可以对数据进行高效检索 二分检索 顺序处理 比较操作 批处理的操作 节省空间(相对其它索引结构) 北京大学信息学院 版权所有,转载或翻印必究 Page 16
北京大学信息学院 ©版权所有，转载或翻印必究 Page 16 线性索引的优点 ◼ 对变长的数据库记录的访问 ◼ 可以对数据进行高效检索 ◼ 二分检索 ◼ 顺序处理 ◼ 比较操作 ◼ 批处理的操作 ◼ 节省空间 (相对其它索引结构)
线性索引的问题 线性索引太大,存储在磁盘中 在一次检索过程中有可能多次访 问磁盘,从而影响检索的效率 n解决办法:使用二级线性索引 更新线性索引 在数据库中插入或者删除记录时 北京大学信息学院 版权所有,转载或翻印必究 Page 17
北京大学信息学院 ©版权所有，转载或翻印必究 Page 17 线性索引的问题 ◼ 线性索引太大，存储在磁盘中 ◼ 在一次检索过程中有可能多次访 问磁盘，从而影响检索的效率 ◼ 解决办法：使用二级线性索引 ◼ 更新线性索引 ◼ 在数据库中插入或者删除记录时
二级线性索引 每一条二级线性索引记录对应于 个一级线性索引文件的磁盘块 关键码的值与对应的线性索引文件的 磁盘块中第一条记录(从物理位置上看 的第一条)的关键码的值相同 记录中的指针则指向相应线性索引文 件的磁盘块的起始位置 北京大学信息学院 版权所有,转载或翻印必究 Page 18
北京大学信息学院 ©版权所有，转载或翻印必究 Page 18 二级线性索引 ◼ 每一条二级线性索引记录对应于一 个一级线性索引文件的磁盘块 ◼ 关键码的值与对应的线性索引文件的 磁盘块中第一条记录(从物理位置上看 的第一条)的关键码的值相同 ◼ 记录中的指针则指向相应线性索引文 件的磁盘块的起始位置
二级线性索引 例如,磁盘块的大小是1024字节,每个 关键码/指针记录需要8个字节,则每磁 盘块可以存储128条这样的记录 ■假设线性文件索引中包含10000条记录, 那么该线性索引占用79个磁盘块,相应 的,二级线性索引文件中有79项记录 北京大学信息学院 版权所有,转载或翻印必究 Page 19
北京大学信息学院 ©版权所有，转载或翻印必究 Page 19 二级线性索引 ◼ 例如，磁盘块的大小是1024字节，每个 关键码／指针记录需要8个字节，则每磁 盘块可以存储128条这样的记录 ◼ 假设线性文件索引中包含10000条记录， 那么该线性索引占用79个磁盘块，相应 的，二级线性索引文件中有79项记录
二级线性索引的例子 关键码与相应磁盘块中第一条记录的关键码的 值相同 ■指针指向相应磁盘块的起始位置 二级索引 2003 5744 10723 线性索引1 20022003 5583574492971072313293 磁盘块 北京大学信息学院 版权所有,转载或翻印必究 Page 20
北京大学信息学院 ©版权所有，转载或翻印必究 Page 20 二级线性索引的例子 ◼ 关键码与相应磁盘块中第一条记录的关键码的 值相同 ◼ 指针指向相应磁盘块的起始位置