6.1 实时查询系统中数据的组织（教学课件）信息技术浙教版2019选择性必修1

第1节 实时查询系统中数据的组织 （2课时） 第6章 大数据时代数据的组织 浙教版（2019） 选修一 实时查询系统中的数据业务特点 01 实时查询系统中的数据结构和算法设计 02 其他数据组织与处理方式 03 学习目录 通过典型案例的剖析，使学生能感受、理解数据结构设计的迭代思想。 01 通过典型案例的剖析，使学生了解对于大规模数据的典型数据组织与处理方式。 02 学习目标 PART 01 实时查询系统中的 数据业务特点 新课导入 看 看 一 查话费、查流量 新课导入 想 想 一 网购平台购物，如何查询和选择商品? 思考:打开京东购物商城，解决以下问题： 要购买一本有关信息技术的书籍，预算在35元以内？ 想要知道目前哪本信息技术书籍最畅销？ 想要知道哪个店铺的好评率最高？ 操作与体验： 新课导入 新课导入 看 看 一 人们经常会提出实时查询各种信息的请求，如电信业务中实时话费与剩余网络流量的查询、网购用户对特定商品的各种信息查询等。面对这种实时访问，系统必须在瞬间给出结果并呈现给用户。 大数据背景下，全部数据的组织、存储和处理，仅凭单个服务器和数据库的数据组织与存储方式，无论从存储容量还是处理速度上都不能满足实际应用的需求。 此时，采用分布式存储技术，将所有数据分别保存在不同的服务器中，需要时从中提取并进行合并，就可以满足海量数据的存储与处理需求。 实时查询系统中的数据业务特点 一 拓展链接 分布式存储系统 分布式存储系统利用分布在不同物理位置的服务器来分担系统存储任务，既能提高数据存储的安全性，又能提升系统数据访问的速度，同时也具有较好的可扩展性。当用户提出访问请求时，系统根据元数据服务器（进行数据访问索引的服务器）将访问定位到目标数据的服务器上。 实时查询系统中的数据业务特点 一 02 01 支持后续商品信息的更改 当用户选择了某种查询后，可能马上又有另一名用户提出其他方式的查询请求，而此时恰好网站中更改了某个商品的属性，也或者是删除、增加了商品，那么这个修改信息应该体现在最新的查询结果中。 能实现上千个请求的实时响应 网站应能做到“即点即现”，即当某用户选择一种查询方式后，系统能马上呈现结果，而且同一时刻可能有上千名用户提出了查询请求。 实时查询系统的两个特殊性： 实时查询系统中的数据业务特点 一 计算机硬盘 数据库 内存 访问 保存 系统崩溃 用户流失 提高读取速度 实时查询系统中的数据业务特点 一 1 2 一方面将增加系统的负担，甚至在访问量增大的瞬间出现系统崩溃； 另一方面，会造成用户较长的等待时间，结果导致用户的流失。 为了减轻磁盘数据库访问的负担，可事先将数据库中的商品信息读取出来并保存在内存中，这样用户的查询就能直接面对内存进行，大大提高数据读取的速度。 面对这种查询业务，如果直接从数据库中提取查询结果，特别是在上千名用户同时发出请求的情况下，系统需频繁地读取计算机硬盘并访问数据库。 实时查询系统中的数据业务特点 一 1 2 用某种数据结构组织并存储数据： ※能体现数据间的逻辑关系 ※能为后续查询提供算法支持 实时查询系统中的数据结构和算法设计 PART 02 实时查询系统中的数据结构和算法设计 二 基于数据间线性关系的数据结构设计 1 数组 原数据(商品名称，人气，销量，信用，价格) 数据2：按销量排序 数据3：按信用排序 数据4：按价格排序 数据1：按人气排序 1.体现商品间的有序线性关系； 2.数据读取到数组后，先按各属性（销量、信用、价格等）进行排序并分类存储。 数据5：按综合排序 分类 存储 实时查询系统中的数据结构和算法设计 二 查询过程中涉及的主要操作： 数据查找 数据插入 例如：新增商品时，需要插入一个新数据并维持数组元素继续有序。 实时查询系统中的数据结构和算法设计 二 查询过程中涉及的主要操作： 数据查找 数据插入 在一个有序序列中查找新增元素的插入位置，可以采用二分查找算法，时间复杂度为〇(log2n)（n表示数组元素的总个数），速度比较快； 在找到可以插入的位置x后，将新元素插入到找到的位置x中，但必须先将位置x到n之间的所有元素往后移一位，为新元素空出位置，这个时间复杂度就比较大，为〇(n)。当瞬间有上千名用户提出请求，同时进行上千个这样的处理时，时效性较差。 〇(log2n) 插入位置x到n中的元素均后移一位 二分查找 〇(n) 上千名用户提出请求时，时效性较差 实时查询系统中的数据结构和算法设计 二 链表 在数组中插入新元素时引起的数据移动低效的问题 链表 数组 替 换 在一个链表中插入一个新元素，时间复杂度为〇(1)，大大优于采用数组时〇(n)的线性复杂度。 实时查询系统中的数据结构和算法设计 二 插入操作主要涉及查找和插入两个关键操作 查找 插入 〇(n) 需从链表的一端依次遍历 〇(1) 整体复杂度有所下降，但还是达不到现实的需求。 只在查找过程低效。 实时查询系统中的数据结构和算法设计 二 只需知道数据之间相互链接的顺序 探讨与讨论 一 除了数组和链表，是否还有其他的数据结构来组织并存储数据？ 非线性数据： 树结构 实时查询系统中的数据结构和算法设计 二 2 基于链表的数据结构和算法优化设计 各种数据结构是人们在用计算机解决问题的过程中，根据数据特点不断研究、探索所得到的。因此，随着数据业务的发展，既有的数据结构就得以不断改进，甚至演变出新的数据结构。 由于基于链表的处理，只是在查找时效率较低，而插入操作却完全能满足要求，所以可以在链表的基础上继续加以改进，以解决顺序查找导致的低效问题。 减少查找插入位置过程中的比较次数 1 链表结构数据主要消耗在插入位置的查找中，可减少查找过程中的数据两两比较的次数来优化数据结构。 实时查询系统中的数据结构和算法设计 二 借鉴二分查找算法的思想 2 确定比较的关键节点 数据进行有序化处理 （1） （2） 二分查找算法之所以效率较高，首先是因为数据是有序的，其次是利用有序性进行跨区间、跳跃性的比较，从而避免低效的逐个依次比较。 实时查询系统中的数据结构和算法设计 二 关键节点：对每个节点采用抛硬币的方法确定是否放在关键节点中 关键节点 原链表 1 4 10 15 1 3 4 10 13 15 20 实时查询系统中的数据结构和算法设计 二 关键节点 原链表 1 4 10 15 1 3 4 10 13 15 20 6 抛硬币的次数越多，其正反的概率越趋向于1/2 分别与1, 4,10比较 分别与1, 3，4,10比较 例如：查找元素6 实时查询系统中的数据结构和算法设计 二 关键节点 原链表 1 4 10 15 1 3 4 10 13 15 20 6 从整体效率分析：增设关键节点后，查找速度是原来的2倍 分别与1, 4,10比较 分别与1, 3，4,10比较 例如：查找元素6 索引表 实时查询系统中的数据结构和算法设计 二 建立二级索引 一级索引 原链表 1 4 10 15 1 3 4 10 13 15 20 二级索引 1 10 实时查询系统中的数据结构和算法设计 二 插入数据元素6 一级索引 原链表 1 4 10 15 1 3 4 10 13 15 20 二级索引 1 10 原一级索引的比较次数减少一半，数据多，还可增设三、四级索引 总体来说,通过对链表改进可实现 实时查询系统中的数据结构和算法设计 二 因为数据序列在不断地变化，所以需要对关键节点进行动态的调整，即数据增加时增设关键节点，而数据减少时删除关键节点。对各级索引表中的关键节点进行增加和删除的实现方法如下： ①增设关键节点。 随着数据元素的增加，原链表会变得越来越长，结果导致区间内查找效率降低。为了解决这个问题，可以考虑对新增元素基于“抛硬币”原则的选拔，以确定是否把新增元素提升为上一层的关键节点，并且逐层进行。 实时查询系统中的数据结构和算法设计 二 若新增元素为24，通过“抛硬币”发现需要提升为关键节点，则新的链表组织结构如下图所示。 第一次抛硬币，结果是“正”，因此把节点24提升到上一层索引。 将新增元素24所在节点提升为关键节点 实时查询系统中的数据结构和算法设计 二 若通过“抛硬币”发现不需要提升为关键节点，则新的链表组织结构如下图所示（新增元素只在原链表中出现）。 新增元素24所在节点不提升为关键节点 实时查询系统中的数据结构和算法设计 二 ②删除关键节点。随着原链表中数据元素的不断删除，各级索引中的关键节点也需要随之删除。删除时按照查找时的层次从上往下依次进行，每当找到对应的元素，就删除当前层的关键节点，直到最底层的原链表。若原来链表的状态如下图所示，现在要删除原链表中的元素10，则从顶层索引开始，依次往下删除各层的元素10。 删除元素10之前的链表状态 实时查询系统中的数据结构和算法设计 二 二级索引中删除元素10所在的节点后，因为只剩下一个关键节点，对于区间划分和提高查找效率没有任何意义，所以将剩下一个节点也删除，得到的最终状态如下图所示。 删除元素10之后的链表状态 因为上述数据结构是在一个有序链表中通过索引表跳跃着进行查找，所以称为“跳跃表”，跳跃表是威廉 · 皮尤（William Pugh）于1990年发明并提出的一种数据结构。 实时查询系统中的数据结构和算法设计 二 数组 链表 跳跃表 一个切合实际的数据结构和算法不是一蹴而就的，而是根据问题中数据及其关系的特点，通过迭代逐步优化得到的。 实时查询系统中的数据结构和算法设计 二 只需知道数据之间相互链接的顺序 探讨与讨论 1.“跳跃表”是立足链表，是借鉴二分思想形成的数据结构。能否立足数组，借鉴链表的思想构造一种新的数据结构来解决数组数据移动的低效问题？ 能，有序数组在查找数据方面的效率较高,但在插入新数据的效率较低,因为新数据后面的数据元素需要连续后移,因此需要进行优化。将原来一个数组中的数据均匀分解存储到k个数组中,这样就将原来O(n)的移动复杂度降为O(n/k)。 参考方向：将原来一个数组中的数据均匀地分解存储到k个数组中，这样就将原来(𝑛)的移动复杂度降为(n/k)，虽然数量级没变，但至少是原来的k倍速度 其他数据组织与处理方式 PART 03 其他数据组织与处理方式 三 单纯采用传统的磁盘数据库来组织、处理海量的数据，其固有的数据组织、存取、处理等模式无法适应当今很多数据业务对实时数据管理和查询的需求。于是，人们针对磁盘数据库存在的瓶颈，发明了内存数据库，并于1994年推出了第一个商业化的、实际应用的内存数据库。 推出内存数据库 采用改进后的数据结构来组织、存储数据 AVL树、Sorted-set技术 减少对磁盘的访问 1 对数据进行分级存储 2 3 其他数据组织与处理方式 三 只需知道数据之间相互链接的顺序 探讨与讨论 1.若数据库中有10万条记录以链表形式有序存放，先要在原链表基础上增设关键节点创建索引，若以二分的形式创建每一级索引，则最多需要创建索引的级数是（ ） A.8 B.17 C.100 D.1000 B 2.若使用跳跃表查询，则对于下图所示的链表： 假如要查找元素9，则需要从头结点开始遍历______次才能找到。 0 1 2 3 4 5 6 7 8 9 10 null 8 课堂小练 四 只需知道数据之间相互链接的顺序 探讨与讨论 1.有以下Python代码段: def jishu(n): s=0 while n>0: s+=n%2 n//=2 return s n=int(input("输入一个正整数:")) ans=jishu(n) print(ans) 阅读以上代码,回答以下问题: (1)该程序运行后输入整数23,输出结果为 。 (2)若输入整数23,则程序中自定义函数jishu( )中语句"s+=n%2”执行的次数是 。 (3)函数jishu( )的时间复杂度为 (单选:A.〇(n) B.〇(log2n))。 B 4 5 课堂小练 三 只需知道数据之间相互链接的顺序 探讨与讨论 2.由于元素的有序性，可以通过增加一些路径（索引）来加快查找速度 通过这种方法，我们只需要遍历元素______________________，共遍历____次就可以找到数字9，还可以增加二级索引。 通过这种方法，我们只需要遍历元素________________，共遍历____次就可以找到数字9。 B 0-2-6-8-10-9 5 4 一级索引 二级 索引 一级索引 小结 五 小 结 一、实时查询系统中的数据业务特点 1.能实现上千个请求的实时响应。 2.支持后续商品信息的更改。 二、实时查询系统中的数据结构和算法设计 1.基于数据间线性关系的数据结构设计 （1）数组（2）链表 2.基于链表的数据结构和算法优化设计 （1）减少查找插入位置过程中的比较次数 （2）借鉴二分查找算法的思想 三、其他数据组织与处理方式 1.减少对磁盘的访问 2.对数据进行分级存储 3.采用改进后的数据结构来组织、存储数据 谢谢观看 第1节 实时查询系统中数据的组织 浙教版（2019） 选修一 $$