高中信息技术浙教版（2019）选修1 第六章　课时1　实时查询系统中数据的组织（课件 学案，2份打包）

(课件网) 课时1　实时查询系统中数据的组织 第六章　大数据时代数据的组织 1.通过典型案例的剖析，了解数据结构设计的迭代思想。2.通过典型案例的剖析，了解大规模数据的典型数据组织与处理方式。 目 录 CONTENTS 知识梳理 01 例题精析 02 随堂检测 03 巩固与提升 04 知识梳理 1 1.实时查询系统中的数据业务特点 (1)大数据背景下的数据组织和存储方式采用_____存储系统。 (2)分布式存储系统 分布式存储系统利用分布在不同_____的服务器来分担系统存储任务，既能提高数据存储的_____，又能提升系统数据访问的_____，同时也具有较好的_____。 分布式 物理位置 安全性 速度 可扩展性 (3)实时查询系统中的数据业务特点 ①能实现上千个请求的_____。 ②支持后续信息的_____。 实时响应 更改 (4)解决频繁访问数据库的方法 为了减轻有磁盘数据库访问的负担，采用先将数据库中的信息读取出来并保存在_____中，大大提高了数据读取的速度。 内存 2.实时查询系统中的数据结构和算法设计 (1)基于数据间线性关系的数据结构设计 读取数据库中的数据并保存到内存中，可采用数组或链表结构来组织和存储。使用数组和链表的方式进行数据查找和插入的特点如下表所示。 数据结构 查找 插入 _____ 采用二分查找，时间复杂度为O(log2n)，速度快 数据移动较多，时间复杂度O(n)，速度较慢 _____ 需从头指针依次遍历，时间复杂度为O(n)，速度较慢 时间复杂度为O(1)，速度较快 数组 链表 (2)基于链表的数据结构和算法优化 ①优化方法 ⅰ.减少查找插入位置过程中的比较次数 ⅱ.借鉴二分查找算法的思想 ②跳跃表 跳跃表简称跳表，是一种立足_____，借鉴_____的思想而形成的数据结构。跳跃表是在原有的有序链表上增加了多级索引，通过索引来实现快速查询。 “跳跃表”以空间换时间，时间复杂度为O(log2n)。 缺点：维护成本高，增加删除都需要更新索引。 链表 二分查找 解决方法： ⅰ._____。基于“抛硬币”原则选拔，以确定是否把新增元素提升为上一层的关键节点，并且逐层进行。 ⅱ._____。删除时按照查找时的层次从上往下依次进行，每当找到对应的元素，就删除当前层的关键节点，直到最底层的原链表。 (3)其他数据组织与处理方式 ①采用_____代替传统的磁盘数据库来组织、处理海量的数据。 增设关键节点 删除关键节点 内存数据库 ②内存数据库进行数据处理的特点 ⅰ.减少对_____。 内存数据库通过对磁盘的访问，可将数据处理速度提高10～1000倍。 ⅱ.对数据进行_____。 内存数据库对所需要处理的数据重新进行组织，并进行数据分级，再在处理器缓存中进行分级存储，进一步提升数据的存取效率。 ⅲ.采用_____来组织、存储数据。 内存数据库将数据在内存中进行重新组织、存储，进行新的体系结构设计，用更快速的算法来处理数据。 磁盘的访问 分级存储 改进后的数据结构 例题精析 2 例1 大数据背景下的数据组织和存储方式，通常采用的技术是(　　) C 解析　本题主要考查的是分布式存储系统。大数据背景下的数据组织和存储方式采用的是分布式存储系统，分布式存储系统具有优秀的可扩展能力，在性能、维护性和容灾性等方面也具有不同程度的优势。 A.传统存储系统 B.云存储系统 C.分布式存储系统 D.集中式存储系统 例2 使用数组来组织并存储数据时，将一个新元素插入到数组中的某个位置的时间复杂度为(　　) A.O(1) B.O(n) C.O(log2n) D.O(n2) 解析　本题主要考查的是在数组中插入元素的时间复杂度。在数组中插入一个新数据时，须先将插入位置上及后面的元素往后移动一位，为新元素空出位置，因此时间复杂度为O(n)，答案为B。 B 例3 基于链表的数据结构，在数据查找时效率较低，下列方法不能提高查找效 ... ...