数据结构与算法“索引”教学设计 北京大学信息科学技术学院张铭 1.索引在课程中的定位和前测知识点 数据结构设计的重要目标之一是提高操作速度,对数据库而言,主要是检索速度。实际 上索引是为检索服务的,而排序又是为索引服务的。散列方法,其实是对关键码的索引,与 关键码对应的记录数据可能存放在其他地方;局部平衡的红黑树、平衡的AVL树、自组织 的伸展树等二叉搜索树具有良好的检索性能,非常适合于基于内存的索引。 前测知试点要求如下,可以根据需要给学生补充 (1)索引、主码、辅码的基本概念; (2)二分查找的概念 (3)二叉搜索树的查找和插入操作。 2.学习目标 (1)理解几种重要的基于磁盘的索引文件组织方式 (2)能比较各种索引技术的性能并进行简单的分析 (3)掌握B/B+树动态索引技术; (4)了解位图索引技术以及文本信息检索中的签名文件索引 (5)了解高效率的常用二叉搜索树索引结构红黑树。 3.知识点和学时分配 理论授课4学时,建议安排实验10学时。 以下内容是本课程要求的基本教学内容,在授课中必须完全涵盖,主讲教师可以根据学 生的状况、教师的科研背景等在某些方面进行扩展和对学生进行引导,以扩大适当学生的涉 猎面。对于非计算机类的学生,可以不讲红黑树部分。 各知识点建议授课时间如下 索引技术的基本概念0.1小时 线性索引 0.1小时 静态索引 倒排索引 0.5小时 动态索引 1小时 位索引技术 0.5小时 红黑树 5小时 4.重点和难点 索引重点如下 (1)B/B+树的查找、插入、删除、访外次数分析 (2)线性索引的基本概念及优缺点、二级线性索引 (3)静态索引及多分树的基本概念; (4)基于属性、正文文件的倒排索引的基本概念数据结构与算法“索引”教学设计 北京大学信息科学技术学院 张铭 1. 索引在课程中的定位和前测知识点 数据结构设计的重要目标之一是提高操作速度，对数据库而言，主要是检索速度。实际 上索引是为检索服务的，而排序又是为索引服务的。散列方法，其实是对关键码的索引，与 关键码对应的记录数据可能存放在其他地方；局部平衡的红黑树、平衡的 AVL 树、自组织 的伸展树等二叉搜索树具有良好的检索性能，非常适合于基于内存的索引。 前测知试点要求如下，可以根据需要给学生补充： （1）索引、主码、辅码的基本概念； （2）二分查找的概念； （3）二叉搜索树的查找和插入操作。 2．学习目标 （1）理解几种重要的基于磁盘的索引文件组织方式； （2）能比较各种索引技术的性能并进行简单的分析； （3）掌握 B/B+树动态索引技术； （4）了解位图索引技术以及文本信息检索中的签名文件索引； （5）了解高效率的常用二叉搜索树索引结构红黑树。 3. 知识点和学时分配 理论授课 4 学时，建议安排实验 10 学时。 以下内容是本课程要求的基本教学内容，在授课中必须完全涵盖，主讲教师可以根据学 生的状况、教师的科研背景等在某些方面进行扩展和对学生进行引导，以扩大适当学生的涉 猎面。对于非计算机类的学生，可以不讲红黑树部分。 各知识点建议授课时间如下： 索引技术的基本概念 0.1 小时 线性索引 0.1 小时 静态索引 0.3 小时 倒排索引 0.5 小时 动态索引 1 小时 位索引技术 0.5 小时 红黑树 1.5 小时 4．重点和难点 索引重点如下： （1）B/B+树的查找、插入、删除、访外次数分析； （2）线性索引的基本概念及优缺点、二级线性索引； （3）静态索引及多分树的基本概念； （4）基于属性、正文文件的倒排索引的基本概念