高中信息技术浙教版（2019）选修1 第六章　课时1　实时查询系统中数据的组织 课件.pptxVIP

课时1实时查询系统中数据的组织;1.通过典型案例的剖析，了解数据结构设计的迭代思想。2.通过典型案例的剖析，了解大规模数据的典型数据组织与处理方式。;;;1.实时查询系统中的数据业务特点;(4)解决频繁访问数据库的方法

为了减轻有磁盘数据库访问的负担，采用先将数据库中的信息读取出来并保存在______中，大大提高了数据读取的速度。;2.实时查询系统中的数据结构和算法设计;(2)基于链表的数据结构和算法优化

①优化方法

ⅰ.减少查找插入位置过程中的比较次数

ⅱ.借鉴二分查找算法的思想

②跳跃表

跳跃表简称跳表，是一种立足______，借鉴____________的思想而形成的数据结构。跳跃表是在原有的有序链表上增加了多级索引，通过索引来实现快速查询。“跳跃表”以空间换时间，时间复杂度为O(log2n)。

缺点：维护成本高，增加删除都需要更新索引。;解决方法：

ⅰ.__________________。基于“抛硬币”原则选拔，以确定是否把新增元素提升为上一层的关键节点，并且逐层进行。

ⅱ.__________________。删除时按照查找时的层次从上往下依次进行，每当找到对应的元素，就删除当前层的关键节点，直到最底层的原链表。

(3)其他数据组织与处理方式

①采用_______________代替传统的磁盘数据库来组织、处理海量的数据。;②内存数据库进行数据处理的特点

ⅰ.减少对_______________。

内存数据库通过对磁盘的访问，可将数据处理速度提高10～1000倍。

ⅱ.对数据进行____________。

内存数据库对所需要处理的数据重新进行组织，并进行数据分级，再在处理器缓存中进行分级存储，进一步提升数据的存取效率。

ⅲ.采用________________________来组织、存储数据。

内存数据库将数据在内存中进行重新组织、存储，进行新的体系结构设计，用更快速的算法来处理数据。;;例1大数据背景下的数据组织和存储方式，通常采用的技术是();;;;;;A.跳跃表有很多层组成

B.最底层的链表包含所有元素

C.每个节点只有一个指针，指向同一链表中的下一个元素

D.每一层都是一个有序的链表，默认是升序;A.处理的数据保存在内存中并直接操作

B.增加对磁盘的数据读写

C.对数据进行分级，并在处理器缓存中存??

D.采用改进后的数据结构来组织、存储数据，如跳跃表、平衡树;4.有一链表如图所示：;;A.分布式存储系统需要使用多台服务器共同存储数据

B.分布式存储系统需要多台服务器同时工作

C.分布式存储系统中的多台服务器通过网络进行连接

D.在有服务器出现故障的情况下分布式存储系统将不可用;2.使用数组来组织并存储数据时，使用二分查找算法在一个有序序列中查找新增元素的插入位置，其时间复杂度为()

A.O(1) B.O(n) C.O(log2n) D.O(n2);3.使用链表来组织并存储数据时，要在链表中查找新元素的插入位置，其时间复杂度为()

A.O(1) B.O(n) C.O(log2n) D.O(n2);A.跳跃表是一种特殊的有序链表

B.跳跃表是由多层有序链表组合而成的，最底一层的链表保存了所有的数据

C.相邻的两层链表中元素相同的节点之间存在引用关系

D.使用跳跃表不仅提高了查询效率，同时也节省了存储空间;5.有如图所示跳跃表：;6.有如下图所示跳跃表：;7.有如下图所示的跳跃表：;;8.跳跃表是一种立足链表，借鉴二分查找的思想而形成的数据结构。能否立足有序数组，借鉴链表的思想构造一种新的数据结构来解决上述问题？

___________________________________________________________________;9.在组织、处理大数据时，可采用内存数据库与磁盘数据库，请从处理速度和安全性两方面说明内存数据与传统的磁盘数据库相比存在哪些优势和不足。

(1)内存数据库的优势：________________________________________

______________________________________________________________________________________________________________________________________(2)内存数据库的不足：_________________________________________

_________________________________________________________________________________________________________