数据结构与算法“索引”教学设计 北京大学信息科学技术学院张铭 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）基于属性、正文文件的倒排索引的基本概念
索引难点如下: (1)B/B+树的性能分析 (2)红黑树的基本概念和插入、删除算法。 5.授课提示 开展研究型教学,挖掘知识背后的内容,通过提出问题、探讨方法、研究思想、比较性 培养学生的创新意识、创新能力 下面是索引部分的重点和难点内容的讲授注意事项。 (1)B/B+树的查找、插入、删除、访外次数和性能分析 B/B+树是动态的索引结构,允许动态地插入或删除记录,索引结构本身也可能发生改 变。改变索引结构的目的是为保持较好的性能,例如较高的检索效率。 B+树是B树的一种变形树,他们的区别如下:(1)B树有k个子结点的结点拥有k-1 个关键码;B树有k个子结点的结点必然有k个关键码。(2)B树中关键码没有重复,父结 点中的关键码是其子结点的分界;B+树内部分支结点仅具有索引作用,可以看作是从叶往 根的方向一层层复写子结点中的最大(或最小)关键码。(3)B+中叶结点是关键码的一个 全集,跟实际数据记录有关的信息均存放在叶结点中。B+树本身也有很多变体。 B树、B+树的插入与删除都要特别注意保持其平衡性质,特别是等高、子结点个数、 关键码个数的上下界限制。由于B树和B+树本身具有相似性,又略微不同,因此其它们的 操作过程类似,但是有一些差别 学生容易不能理解B/B+树插入删除的具体过程,细节容易忽略,可以采用动画等直观 地进行演示,尤其是分裂合并的过程 对B树的査找和插入算法进行性能分析。通过公式演算让学生了解B树性能分析的具 体计算过程。 (2)线性索引的基本概念及优缺点、二级线性索引 线性索引被组织成简单的(关键码,指针)的序列,按照关键码的顺序进行排序,其常 用检索技术是二分检索。数据规模太大,索引文件无法完全存储到内存时,可以采用二级线 性索引。 (3)静态索引及多分树的基本概念 多分树静态索引结构在文件创建、初始装入记录时生成,并固定不变,插入和删除操作 非常不方便。只有当文件再组织时才允许改变索引结构 (4)基于属性、正文文件的倒排索引的基本概念 在实际应用中,我们需要按照记录中的属性记录项来查找记录,这样就需要按属性值建 立索引。而随着电子数据的告诉增长,为了更好地利用越来越多的文本数据,对文本数据的 检索和管理变得越发重要。正文索引就是处理对文本内容的快速检索的方法。 通过一些实际例子和应用来让学生更加了解倒排索引在实际应用中的作用。 (5)红黑树的基本概念和插入、删除算法 红黑树也是一种二叉搜索树,它没有AVL树那样完全平衡的特性。而是利用对树中结 点红黑着色的要求降低了平衡性的条件,达到局部平衡,从而既能提高红黑树增删记录的性 能,又能达到高效率的检索要求。它的统计性能要好于AⅥL树,且增删记录算法性能好、 易实现,因此,红黑树是一种很好的索引结构,C++STL应用了红黑树的变体, Linux内核 中的用户态地址空间管理也使用了红黑树
索引难点如下： （1）B/B+树的性能分析； （2）红黑树的基本概念和插入、删除算法。 5．授课提示 开展研究型教学，挖掘知识背后的内容，通过提出问题、探讨方法、研究思想、比较性 能，培养学生的创新意识、创新能力。 下面是索引部分的重点和难点内容的讲授注意事项。 （1）B/B+树的查找、插入、删除、访外次数和性能分析 B/B+树是动态的索引结构，允许动态地插入或删除记录，索引结构本身也可能发生改 变。改变索引结构的目的是为保持较好的性能，例如较高的检索效率。 B+树是 B 树的一种变形树，他们的区别如下：（1）B 树有 k 个子结点的结点拥有 k-1 个关键码；B 树有 k 个子结点的结点必然有 k 个关键码。（2）B 树中关键码没有重复，父结 点中的关键码是其子结点的分界；B+树内部分支结点仅具有索引作用，可以看作是从叶往 根的方向一层层复写子结点中的最大（或最小）关键码。（3）B+中叶结点是关键码的一个 全集，跟实际数据记录有关的信息均存放在叶结点中。B+树本身也有很多变体。 B 树、B+树的插入与删除都要特别注意保持其平衡性质，特别是等高、子结点个数、 关键码个数的上下界限制。由于 B 树和 B+树本身具有相似性，又略微不同，因此其它们的 操作过程类似，但是有一些差别。 学生容易不能理解 B/B+树插入删除的具体过程，细节容易忽略，可以采用动画等直观 地进行演示，尤其是分裂合并的过程。 对 B 树的查找和插入算法进行性能分析。通过公式演算让学生了解 B 树性能分析的具 体计算过程。 （2）线性索引的基本概念及优缺点、二级线性索引 线性索引被组织成简单的（关键码，指针）的序列，按照关键码的顺序进行排序，其常 用检索技术是二分检索。数据规模太大，索引文件无法完全存储到内存时，可以采用二级线 性索引。 （3）静态索引及多分树的基本概念 多分树静态索引结构在文件创建、初始装入记录时生成，并固定不变，插入和删除操作 非常不方便。只有当文件再组织时才允许改变索引结构。 （4）基于属性、正文文件的倒排索引的基本概念 在实际应用中，我们需要按照记录中的属性记录项来查找记录，这样就需要按属性值建 立索引。而随着电子数据的告诉增长，为了更好地利用越来越多的文本数据，对文本数据的 检索和管理变得越发重要。正文索引就是处理对文本内容的快速检索的方法。 通过一些实际例子和应用来让学生更加了解倒排索引在实际应用中的作用。 （5）红黑树的基本概念和插入、删除算法 红黑树也是一种二叉搜索树，它没有 AVL 树那样完全平衡的特性。而是利用对树中结 点红黑着色的要求降低了平衡性的条件，达到局部平衡，从而既能提高红黑树增删记录的性 能，又能达到高效率的检索要求。它的统计性能要好于 AVL 树，且增删记录算法性能好、 易实现，因此，红黑树是一种很好的索引结构，C++ STL 应用了红黑树的变体，Linux 内核 中的用户态地址空间管理也使用了红黑树
红黑树的插入、删除算法比较复杂,应动态地演示插入、删除的过程,便于学生理解。 6.课后练习和实习 融合经典的理论教学内容与学科的前沿新技术和发展方向,设计验证型、探索型、综合 应用型的习题和上级题,帮助学生更好地掌握多种索引技术的基本原理,训练学生的创新思 维能力训练、算法实践能力 索引可以安排46题书面作业,1-2道综合上级实习题。安排一次习题讲评 采用 ACM/ICPO程序竞赛题库POJ系统进行BST索引的验证型小实验。 http://acm.pku.edu.cn/judgeonline/problem?id=1240 http://acm.pku.edu.cn/judgeonline/problem?id=1463 比较适合在最后的综合实现项目中布置索引练习,可以与内排序、外排序、检索等技术 结合起来。安排不同的数据规模:能力稍弱的学生可以只处理小规模数据,完全用内存的索 引:能力较强的,可以采用外存索引技术来索引大规模数据。 7.教学案例 图1是在一棵5阶B树中删除关键码150的示意过程。首先,150与后继156交换,换 到叶结点i中。删除叶结点i中的150后,只剩下177一个关键码,产生下溢出。此时其左 兄弟h无关键码可借,因此h、156、i合并为新i结点,释放空结点h。合并后,父结点 也下溢出,b、103、c继续合并为新根结点,释放空结点b、c,产生图1(e)的B树 上述两个连续删除的操作,其访外次数是一起考虑的。删除120,读盘(a、c、h、g), 写盘h、g、c。继续删除150,可以认为相关的a、c、h已经在内存,只要新读入i;合并时 写出i,读入b,写出a。 b g 35 st 95 10 1ON 110 115134 146 (a)5阶B树,准备删除150 b e g 8195100 108110115 120146 15017 (b)150与后继156交换,产生临时结果(不是严格的B树)
红黑树的插入、删除算法比较复杂，应动态地演示插入、删除的过程，便于学生理解。 6．课后练习和实习 融合经典的理论教学内容与学科的前沿新技术和发展方向，设计验证型、探索型、综合 应用型的习题和上级题，帮助学生更好地掌握多种索引技术的基本原理，训练学生的创新思 维能力训练、算法实践能力。 索引可以安排 4-6 题书面作业，1-2 道综合上级实习题。安排一次习题讲评。 采用 ACM/ICPC 程序竞赛题库 POJ 系统进行 BST 索引的验证型小实验。 http://acm.pku.edu.cn/JudgeOnline/problem?id=1240 http://acm.pku.edu.cn/JudgeOnline/problem?id=1463 比较适合在最后的综合实现项目中布置索引练习，可以与内排序、外排序、检索等技术 结合起来。安排不同的数据规模：能力稍弱的学生可以只处理小规模数据，完全用内存的索 引；能力较强的，可以采用外存索引技术来索引大规模数据。 7．教学案例 图 1 是在一棵 5 阶 B 树中删除关键码 150 的示意过程。首先，150 与后继 156 交换，换 到叶结点 i 中。删除叶结点 i 中的 150 后，只剩下 177 一个关键码，产生下溢出。此时其左 兄弟 h 无关键码可借，因此 h、156、i 合并为新 i 结点，释放空结点 h。合并后，父结点 c 也下溢出，b、103、c 继续合并为新根结点，释放空结点 b、c，产生图 1(e)的 B 树。 上述两个连续删除的操作，其访外次数是一起考虑的。删除 120，读盘（a、c、h、g）， 写盘 h、g、c。继续删除 150，可以认为相关的 a、c、h 已经在内存，只要新读入 i；合并时 写出 i，读入 b，写出 a。 118 150 25 50 103 a c d e f g h b i 11 15 35 43 81 95 100 108 110 115 134 146 156 177 （a）5 阶 B 树，准备删除 150 134 156 25 50 103 a c d e f g h b i 11 15 35 43 81 95 100 108 110 115 120 146 150 177 （b）150 与后继 156 交换，产生临时结果（不是严格的 B 树）
b e g 3[8%51【0s (c)删除了150,结点i下溢出 b e 108110115 146156177 (d)删除了150,结点i下溢出与h合并;c又溢出了,与左邻居b合并,并涉及根a a g 108I10115 134146156177 (e)bc与根结点a一起合并,树高降低一层 图1.一棵5阶B树的结点删除示意图 8.总结 索引这一部分的内容训练学生预处理数据的思维方法,以及数据结构的平衡思想。防止 树形结构退化为线性结构。 除了上述教学注意事项之外。还需要提醒学生注意在数据库、搜索引擎等现实系统中, 索引得到了广泛应用。可以安排对B/B+树的插入、删除算法的实际运用和红黑树的具体问 题的应用。 参考文献 1.张铭,王腾蛟,赵海燕,《数据结构与算法》,高等教育出版社,2008年6月。—一普 通高等教育“十一五”国家级规划教材
118 156 25 50 103 a c d e f g h b i 11 15 35 43 81 95 100 108 110 115 146 177 （c）删除了 150，结点 i 下溢出 118 25 50 103 a c d e f g h’ b 11 15 35 43 81 95 100 108 110 115 146 156 177 （d）删除了 150，结点 i 下溢出与 h 合并；c 又溢出了，与左邻居 b 合并，并涉及根 a d e f g h’ 11 15 35 43 81 95 100 108 110 115 134 146 156 177 25 50 103 118 a’ （e）b,c 与根结点 a 一起合并，树高降低一层 图 1. 一棵 5 阶 B 树的结点删除示意图 8．总结 索引这一部分的内容训练学生预处理数据的思维方法，以及数据结构的平衡思想。防止 树形结构退化为线性结构。 除了上述教学注意事项之外。还需要提醒学生注意在数据库、搜索引擎等现实系统中， 索引得到了广泛应用。可以安排对 B/B+树的插入、删除算法的实际运用和红黑树的具体问 题的应用。 参考文献： 1. 张铭，王腾蛟，赵海燕，《数据结构与算法》，高等教育出版社，2008 年 6 月。——普 通高等教育“十一五”国家级规划教材
2.张铭、赵海燕、王腾蛟、宋国杰、高军,北京大学“数据结构与算法”教学设计,《计 算机教育》2008第20期。获得“英特尔杯2008年全国计算机教育优秀论文评比”一等 奖 3.北京大学《数据结构与算法》精品课程网站(2008年北京市“精品课程”暨国家“精品 课程),http://www.jpk.pkueducn/pkujpk/course/sjjg 4.蒋宗礼,“编译原理教学设计”。《计算机教育》,2008.3 5.张铭、许卓群、杨冬青、唐世渭,“数据结构知识系统及教学实践”。《计算机教育》。《计 算机教育》,2004年2、3月合刊,PP89-91
2. 张铭、赵海燕、王腾蛟、宋国杰 、高军，北京大学“数据结构与算法”教学设计，《计 算机教育》2008 第 20 期。获得“英特尔杯 2008 年全国计算机教育优秀论文评比”一等 奖。 3. 北京大学《数据结构与算法》精品课程网站（2008 年北京市“精品课程”暨国家“精品 课程”）， http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 4. 蒋宗礼，“编译原理教学设计”。《计算机教育》, 2008.3。 5. 张铭、许卓群、杨冬青、唐世渭，“数据结构知识系统及教学实践”。《计算机教育》。《计 算机教育》，2004 年 2、3 月合刊，PP89-91
