6.1 实时查询系统中数据的组织-教学设计 (1)

教学设计
课程基本信息
课题 6.1实时查询系统中数据的组织
教学目标
1.了解大数据处理过程中常见的数据组织与处理方式 2. 能结合已知的数据结构知识，选用合理的数据结构去解决问题 3. 能用迭代的思想去看待数据结构的设计、数据的组织与存储 4. 能激发进一步学习数据的组织与存储、数据结构与算法设计的兴趣
教学内容
教学重点： 能用迭代的思想去看待数据结构的设计、数据的组织与存储
教学难点： 能用迭代的思想去看待数据结构的设计、数据的组织与存储
教学过程
一、情境导入 1、师：生活中人们为了方便，很多时候会选择在网络平台进行购物，新学期要开始了，小陈同学想在网购平台购买一只书包，我们一起来看看他是如何选择心仪的书包的？ ▲在观看过程中，请同学们思考：小陈同学在该平台查询信息的方式和特点？ （播放视频） 2、请几位同学来说一说在视频中看到的信息查询的方式和特点。 二、实时查询系统中的数据业务特点 师生共同小结： 像这样实现实时查询的系统中，我们可以发现其数据业务呈现以下特殊性： （1）能实现上千个请求的实时响应 （2）支持后续商品信息的更改
三、实时查询系统中的数据结构和算法设计 1、数组 可以比较直接的表示商品之间按照某种属性呈现的有序线性关系。当数据从数据库读取到数组后，我们可以按照各个属性进行排序后，把他们分类存储。 ▲请同学们小组讨论并完成学生任务单中的“学习任务一”(1)(2)(3)。 （1）有数组如下，若要插入数字7，使数组仍然有序，该如何操作？ 索引0123456789元素13456891215
（2）程序实现：完成以下代码填空 a=[1,3,4,5,6,8,9,12,15,0] #0表示该位置未存储元素 num=int(input("输入需要插入的数据：")) for i in range(len(a)): if a[i]>num: for j in range(len(a)-1,i-1,-1): _____①_______ ____②_______ break else: a[-1]=num print(a) （3）思考：如果数据量较多时，我们可以采用什么方法来查找位置？ ____________________________ 师生共同分析回顾在数组中查找与插入的操作，引出为提高查找效率，可使用二分查找，简单回顾二分查找的过程，比较顺序查找与二分查找的效率。 2、链表 ▲请同学们小组讨论并完成学生任务单中的“学习任务二”(1)(2)(3)。 （1）有链表如下，若要插入数字26，使链表仍然有序，该如何操作？ （2）程序实现： a=[[12,1],[15,2],[22,3],[29,4],[35,5],[46,-1]] num=int(input("输入需要插入的数据：")) head=0 p=head if numa[p][0]and p!=-1: q=p p=a[p][1] a.append([num,p]) ______②______ p=head while a[p][1]!=-1: print(a[p][0],end='->') _____③_______ print(a[p][0]) （3）思考：请同学们讨论交流，分析数组与链表各自的优势和劣势。 优势劣势数组链表
师生共同分析回顾在链表中查找与插入的操作，结合程序代码直观的感知具体的算法实现。师生共同分析数组与链表各自的优势与劣势。 优势劣势数组利用二分查找 时间复杂度：O(log2n) 查找速度比较快插入位置之后的所有元素都必须往后移位，时间复杂度较大：O(n)链表插入新元素效率高，时间复杂度仅为O(1)查找时必须从头节点开始依次遍历，时间复杂度为O(n)
四、基于链表的数据结构和算法优化 1、由于链表的处理，只是在查找时效率较低，而插入操作却完全能满足要求，所以可以在链表的基础上继续加以改进，以解决顺序查找导致的低效问题。我们可以按以下思路来考虑： （1）减少查找插入位置过程中的比较次数 （2）借鉴二分查找算法的思想 2、这里我们引入一个新的数据结构------跳跃表。 原链表如下，若要在原链表中查找18，我们需要比较6次，现在，我们通过抛硬币的方式来提取一组关键节点放到上层作为一级索引，此时，我们只需要比较5次就可以找到18。如果用同样的方法，为一级索引建立二级索引，我们只需要比较4次就可以找到18。 由此可见，关键节点起到一个索引表的作用，能快速定位到一个较小的查找区间，然后只需将索引位置对应到原链表，就可以找到了。如果数据比较多时，还可以继续增设三、四级索引，进一步提升查找的速度。 跳跃表的时间复杂度：O(log2n) （1）跳跃表------增设关键节点 例如，原链表增加了新节点24，我们仍然采用抛硬币的方式来决定是否把24提升为上一层的关键节点，如果抛硬币结果为不提升，那么24只出现在原链表中，如果抛硬币结果为提升，那么把24提升到上一层索引，用同样的方法来确定24要不要继续往上提升。 （2）跳跃表------删除关键节点 例如要删除13，从二级索引开始，依次往下删除各层的13。由于二级索引在删除13以后只剩下一个关键节点，对于区间划分和提高查找效率没有任何意义，所以将剩下的节点1也删除。 3、师生共同小结： 从数组到链表，再到跳跃表，我们可以发现，一个切合实际的数据结构和算法不是一蹴而就的，而是根据问题中的数据及其关系的特点，通过迭代逐步优化得到的。 五、其他数据组织与处理方式 单纯的采用传统的磁盘数据库来组织、处理海量的数据，其固有的数据组织、存取、处理等模式已经无法适应当今很多数据业务对实时数据管理和查询的需求，为了提升数据的处理性能，人们发明了内存数据库。 大部分的内存数据库主要从以下几个方面来提升数据的处理性能： （1）减少对磁盘的访问 （2）对数据进行分级存储 （3）采用改进后的数据结构来组织、存储数据 六、小结与拓展 师生共同小结： 本节课，我们了解了大数据处理过程中常见的数据组织与处理方式，以及在数据业务中，数据进行分类、整理等组织工作的必要性，还一起感受了数据结构设计过程中的迭代思想。 ▲课外拓展： 除了本节课提到的几种数据结构，是否还有其他的数据结构来解决数据的组织与存储问题呢？请同学们课后讨论交流。如果有，请简要描述该数据结构组织数据并处理的算法，并尝试分析用该数据结构解决问题的时间复杂度。