寻杨　柳欣

[摘 要]当前，数据结构课程受教学内容所限，教师无法使学生掌握知识的全貌。其教学若不能从后续课程中提炼数据结构并结合现实问题进行分析，则不利于培养学生根据问题需求选择适当数据结构的能力，也容易使学生产生数据结构课程无用论。文章提出在课程群视域下对多门相关课程进行整体教学设计的思想，并且以B+树为例设计了可应用于三门专业核心课程的共享案例。这种新的教学形式有利于打破课程间的知识壁垒，分阶段引导学生进行知识建构，促进学生创新意识和问题解决能力的培养。

[关键词]数据结构;B+树;案例教学;图解教学;建构主义教学

[中图分类号] G642 [文献标识码] A [文章编号] 2095-3437（2021）08-0019-03

引言

《国家中长期教育改革和发展规划纲要（2010—2020年）》指出，要牢固确立人才培养在高校工作中的中心地位，着力培养信念执著、品德优良、知识丰富、本领过硬的高素质专门人才和拔尖创新人才[1]。数据结构既是计算机科学与技术专业（简称计算机专业）的专业基础课程之一，也是培养计算机专业学生创新意识和问题解决能力的核心课程。该课程的教学内容是围绕数据元素的逻辑关系、关系描述以及相互操作而展开的[2]。由于教学内容的理论性强，算法底层的逻辑结构较为抽象，复杂算法的执行过程难以理解等，因此采用传统教学方式往往难以取得理想效果[3]。另外，为了培养学生的创新意识，也有必要探索新的教学方法，帮助学生形成算法思维模式，增强学生根据实际问题需要选择高效数据结构并进行性能分析的能力[4]。

数据结构课程侧重于在逻辑层面分析和讨论问题，所讲授的存储结构仅限于利用高级程序设计语言对逻辑结构进行编码实现。该课程对问题的讨论并不完整。其教学内容仅限于宏观层面，而无法涉及针对特定数据结构（如二叉树）在硬盘中的存储问题以及如何从磁盘读入主存等微观层面上的问题。另外，尽管课程讲授了线性、树型和图状结构的抽象数据类型定义以及相关算法，但是学生仍然抱有许多疑问，诸如所讲授的数据结构知识在今后的专业课学习中能否用到，这些数据结构在现实的软件系统开发过程中是否得到使用，等等。计算机组成原理是硬件类的专业基础课程，着重讲授计算机的硬件工作原理以及数据在物理层面上的存储和运算原理。因此，这门课对问题的讨论比较微观，这就有助于学生深入理解各类数据结构在计算机中的物理存储方式。数据库原理与应用是软件类的专业基础课程。尽管许多数据结构（如多链表排序、B+树索引等）在商业数据库系统的开发过程中得到应用，但是如果教师无法在教学中对这些数据结构进行提炼，学生往往会产生数据结构技术在数據库领域并未得到应用的错觉。为了了解上述问题，应当组织讲授上述课程的教师进行专门研讨，精心遴选与现实应用紧密结合且能渗透于三门课程教学内容中的综合性案例，通过开发共享的教学案例，实现专业基础知识的全面贯通。

一、专业核心课程群视域下的总体教学设计思路

课程群是由多门教学内容密切相关的课程构成的集合。这些课程适合在更大的框架下进行整体建设，以达到优化教学资源配置和提高教学质量的效果[5]。可以基于课程群的思路对密切相关的专业核心课程进行整体教学设计，开发可以共享的教学案例。开发共享教学案例的意义主要有以下几方面：（1）训练学生从现实应用中提炼数据内容和数据结构，形成“站在计算机角度”进行思维的意识，提高逻辑思维和创新能力。（2）打破相关课程之间的知识壁垒，促进学生对知识的全面掌握。（3）围绕复杂问题和复杂算法设计综合案例，在不同课程中讲授案例的某一部分，有利于降低难度，实现认识水平的螺旋式上升。（4）为地方院校开展以“专业核心课程深度融合和整体建设”为抓手的系列教学改革积累经验，为后期开展工程教育专业认证奠定基础。

二、支撑性的教学理论及其内涵

我们的教学改革是在案例教学、图解教学和建构主义教学理论指导下开展的。（1）案例教学法起源于哈佛大学，其基本思想是将相关的案例引入课堂教学，通过设置案例展示和案例讨论环节，帮助学生理解抽象知识，并且展示它们在实践中的具体运用[6]。开展案例教学的目的在于创设情境以及引导学生深入思考，从而达成“知识+应用”的教学目标。（2）开展数据结构教学的难点在于如何展现抽象的逻辑结构、逻辑结构与存储结构的对应关系、复杂算法的求解过程以及如何将问题求解思路转换为代码描述。对此，一种行之有效的办法是使用结构图[7]。通过图解，可以直观地展示问题求解过程中数据逻辑结构的演进变化及其与代码描述之间的关系。鼓励学生进行算法的图解，有助于促进学生的思维训练，加深学生对存储结构的理解，提高学生解决问题的能力。（3）建构主义教学理论强调以学生的内在经验和知识为基础，通过创设教学情境引发知识冲突，以促进学生实现自我知识建构[8]。斯皮罗等人提出随机进入式教学的观点[9]。其基本思想是为了帮助学生全面掌握事物的内在性质以及事物间的联系，利用不同的途径与方式，在不同的时间进入同一教学内容的学习。但是，所谓的“多次进入”并不意味着相同内容的简单重复，而是每次进入着眼于问题的不同侧面，进而使学生通过多次学习认识事物的全貌，实现认识上的飞跃。

三、共享案例教学设计——以B+树索引为例

（一）案例选取

随着数据规模的日益扩大，数据查询效率成为影响数据库性能的关键因素之一。索引机制是提高数据查询效率的有效办法，B+树是一种在数据库索引领域得到广泛应用的树型结构。利用该结构的索引文件，有利于减少磁盘读取次数和提高内存的利用率[10]。鉴于B+树索引具有较大的现实意义且该项内容适合在数据结构、计算机组成原理和数据库原理与应用这三门课程中进行讲授，因此我们选取该项内容进行共享案例设计。该案例的设计目标是通过分阶段实施案例教学，将这三门课程涉及的十个左右的知识点贯穿起来（如表1所示），激发学生学习兴趣，促进学生深入思考，实现让学生从微观与宏观的角度全面掌握相关知识的目标。

（二）共享案例详细的教学设计

根据这三门课程的先修后修关系，我们将整个案例的实施过程分为以下三个阶段。

第一个阶段是在数据结构教学过程中完成的。在讲授完二叉排序树、B-树和B+树之后，教师给出一个有关B+树应用的综合案例，通过对相关逻辑结构进行性质比较，帮助学生加深对知识的理解。案例问题描述如下：给定一组关键字，要求学生构造三种面向动态查找法的树型结构，即二叉排序树、B-树和B+树（如图1所示），用结构图画出三种树型结构的构造过程，并且对它们的查找效率进行比较。在构造过程中，教师提示学生注意二叉排序树构造过程中的平衡调整问题，以及在B-/B+树构造过程中的结点分裂问题等。在效率比较过程中，教师提示学生将平均查找长度作为三种结构效率比较的重要依据。在案例总结阶段，教师引导学生得出以下结论：（1）对于给定关键字key，查找过程的效率取决于“从根结点到结点key的路径上”的结点个数（即比较次数）。（2）对于B-/B+树，可以将查找过程中的比较次数表示为logd[（N+1）/2]+1（N表示关键字总数，d表示内部结点的度数）。（3）与二叉排序树和B-树相比，B+树支持的查找方式更为灵活，即除了可以从根结点出发，“从上至下”进行查找，还可以在最底层沿水平方向进行查找。上述案例的教学目标是使学生在宏观层面上深入理解三种结构的特点，掌握基于平均查找长度的查找效率分析方法。

第二个阶段是在计算机组成原理课程教学过程中完成的。介绍完硬盘存取原理和主存工作原理之后，教师再次向学生提出上述案例，并且将讨论重点转向以下内容。首先，介绍上述三种结构的现实应用是作为数据库索引文件的组织形式。然后，介绍三种索引文件在硬盘中的存储方法以及将位于硬盘上的结点读入内存的过程。在此阶段，教师需要引导学生深入思考以下问题：（1）每读入一个结点（即执行1次I/O操作）需要多少时间。（2）如何从微观角度理解B+树索引的检索过程（如图2所示），以及如何对检索过程的时间效率进行分析。在案例总结阶段，教师引导学生得出以下结论：在关键字检索过程中，每访问一个内部结点/叶结点，就需要执行1次I/O操作。因此，索引文件的检索效率取决于检索过程中的I/O操作次数。通过上述案例教学过程，学生会在微观层面上对这三种树型结构产生新的认识。

第三个阶段是在数据库原理与应用课程教学过程中完成的。在介绍完索引原理之后，教师第三次提出上述案例，并对案例的描述做出以下调整：假设员工信息表包含“工号”和“姓名”两个字段。为了提高查找效率，要求基于二叉排序树、B-树和B+树技术分别构造索引文件，并且利用结构图画出员工信息表与三种索引文件的存储结构。在图解过程中，教师指导学生设计结构图，着重体现索引与数据库记录的对照关系（如图3所示），并介绍选取B+树作为商业数据库（如MySQL）索引的原因。

在此阶段，教师需要引导学生深入思考以下问题：（1）如何统计三种索引结构在查找过程中的比较次数？（2）假设关键字总数为N，且d表示B-/B+树中每个内部结点的度数，为何B+树索引优于另外两种索引（如表2所示）？在案例总结阶段，教师引导学生得出以下结论：在B-/B+树中，查找过程的关键字比较次数约为[logdN]。

四、结束语

本文 在专业核心课程群视域下，研究了对数据结构课程与后续的计算机组成原理课程和数据库原理与应用课程进行整体教学设计的问题。选取B+树作为联系这三门课程的教学内容，并且基于建构主义教学理论，围绕B+树的相关知识进行“分阶段多次进入”的共享案例教学设计。同时，利用结构图技术对二叉排序树、B-树和B+树的复杂逻辑结构进行直观展示。本文提出的案例有利于帮助学生从宏观和微观层面全面掌握B+树相关知识，培养逻辑思维和问题解决能力。

[ 参 考 文 献 ]

[1] 教育部.国家中长期教育改革和发展规划纲要（2010—2020年）[EB/OL]. （2010-07-29）[2020-04-02].http：//old.moe.gov.cn/publicfiles/business/htmlfiles/moe/info_list/201407/xxgk_171904.html

[2] 张铭，耿国华，陈卫卫，等. 数据结构与算法课程教学实施方案[J].中国大学教学，2011（3）：56-60.

[3] 柳欣，张斌，张波.复杂算法的案例教学设计[J].计算机时代，2020（2）：109-111+116.

[4] 罗丽燕，邓小芳，林乐平.“双一流”建设背景下数据结构课程教学初探[J].大学教育，2020（3）： 80-82.

[5] 張映辉， 陶霞. 地方本科院校数学与应用数学专业课程群建设的理论与实践[J]. 湖南理工学院学报（自然科学版）， 2016（1）： 92-94.

[6] 钱明辉，李天明，舒诗雅，等.教学案例开发框架模型的构建及其应用[J].管理案例研究与评论，2018（2）：210-220.

[7] 农国才. 浅谈图示在数据结构教学中的应用[J]. 广西民族师范学院学报，2013（3）：70-72.

[8] 李雪珊. 基于建构主义理论的教学策略初探：以《高等数学》课程教学为例[J]. 西南师范大学学报（自然科学版），2014（2）：152-155.

[9] 李晓波，刘磊. 建构主义理论及其在《数据结构》教学中的应用探索[J]. 潍坊学院学报，2008（6）：155-156.

[10] 施恩，顾大权，冯径，等. B+树索引机制的研究及优化[J].计算机应用研究， 2017（6）：1766-1769.

[责任编辑：庞丹丹]