资源简介

(共32张PPT)
课时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 基于链表的数据结构，在数据查找时效率较低，下列方法不能提高查找效率的是(　　)
解析　增加链表尾指针，当插入新元素的位置靠近尾部时，会提高查找效率，但平均效率不会提高，因此，答案为D。
D
A.减少查找插入位置过程中的比较次数
B.借鉴二分查找算法的思想
C.利用有序性进行跨区间、跳跃性比较
D.增加链表尾指针，从后往前查找插入位置
例4 有如下跳跃表：
解析　本题主要考查的是跳跃表。该跳跃表中增设了关键节点，插入新元素时，只要让插入元素依次与关键节点比较，即元素7依次与关键节点2、5、8比较，因此，共比较3次就找到插入位置，答案为B。
B
若要原链表中插入元素7，则数据元素需要比较的次数为(　　)
A.1次 B.3次 C.4次 D.5次
随堂检测
3
1.使用链表来组织并存储数据时，在链表中插入一个新数据元素的时间复杂度为(　　)
A.O(1) B.O(n) C.O(log2n) D.O(n2)
A
解析　本题主要考查的是在链表中的插入元素的时间复杂度。在链表中插入一个新数据元素时，只需要改变两个指针的指向即可完成操作，因此其时间复杂度为O(1)，因此，答案为A。
A.跳跃表有很多层组成
B.最底层的链表包含所有元素
C.每个节点只有一个指针，指向同一链表中的下一个元素
D.每一层都是一个有序的链表，默认是升序
C
解析　跳跃表中的每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素，因此，答案为C。
A.处理的数据保存在内存中并直接操作
B.增加对磁盘的数据读写
C.对数据进行分级，并在处理器缓存中存储
D.采用改进后的数据结构来组织、存储数据，如跳跃表、平衡树
B
解析　因为磁盘的数据读写速度较慢，因此应减少对磁盘的访问，答案为B。
4.有一链表如图所示：
D
解析　从第1个节点开始，依次与1、2、5、8、10进行比较，最终确定插入位置，因此比较次数为5次，答案为D。
4
巩固与提升
基础巩固
能力提升
A.分布式存储系统需要使用多台服务器共同存储数据
B.分布式存储系统需要多台服务器同时工作
C.分布式存储系统中的多台服务器通过网络进行连接
D.在有服务器出现故障的情况下分布式存储系统将不可用
D
解析　本题主要考查的是分布式存储系统。分布式存储系统需要使用多台服务器共同存储数据，但随着服务器数量的增加，服务器出现故障的概率也会不断增加。为了保证在有服务器出现故障的情况下系统仍然可用，分布式存储系统一般采用把一个数据分成多份存储在不同的服务器中的方法来解决，因此，在有服务器出现故障的情况下分布式存储系统仍将可用，答案为D。
2.使用数组来组织并存储数据时，使用二分查找算法在一个有序序列中查找新增元素的插入位置，其时间复杂度为(　　)
A.O(1) B.O(n) C.O(log2n) D.O(n2)
C
解析　本题主要考查二分查找算法的时间复杂度。使用二分查找算法查找某个位置的时间复杂度为O(log2n)，因此，答案为C。
3.使用链表来组织并存储数据时，要在链表中查找新元素的插入位置，其时间复杂度为(　　)
A.O(1) B.O(n) C.O(log2n) D.O(n2)
B
解析　本题主要考查的是在链表中的进行数据查找的时间复杂度。在链表中查找数据或数据位置时，需要从链表的一端依次遍历查找，因此其时间复杂度为O(n)，因此，答案为B。
A.跳跃表是一种特殊的有序链表
B.跳跃表是由多层有序链表组合而成的，最底一层的链表保存了所有的数据
C.相邻的两层链表中元素相同的节点之间存在引用关系
D.使用跳跃表不仅提高了查询效率，同时也节省了存储空间
D
解析　本题主要考查的是跳跃表的特点。使用跳跃表的目的在于提高了查询效率，但同时也增加一定的存储空间，因此答案为D。
5.有如图所示跳跃表：
C
解析　本题主要考查的是跳跃表的插入操作。要在原链表中插入元素12，关键是要找到插入的位置，通过与关键节点1、5、10、15的比较，可确定插入的位置，因此比较次数为4次，答案为C。
若要在原链表中插入元素12，需比较的次数为(　　)
A.1次 B.3次 C.4次 D.5次
6.有如下图所示跳跃表：
C
解析　本题主要考查的是在跳跃中查找数据元素。首先从二级索引中经过2次比较确定一个大致区间，然后通过对应关系到达一级索引，最终到达原链表中找到元素27，因此共查找次数为3次，答案为C。
若要在原链表中查找元素27，则查找次数为(　　)
A.1次 B.2次 C.3次 D.4次
7.有如下图所示的跳跃表：
请画出删除元素6后的链表状态。
_______________________________________________________________________________________________________________________________________________________________________________________________________________
答案　删除元素6后的链表状态为：
解析　本题主要考查的是删除跳跃表中的关键节点。当原链表中的数据元素被删除时，各级索引中的关键节点也需要随之删除，删除时按照查找时的层次从上往下依次进行，每当找到对应的元素，就删除当前层的关键节点，直到最底层的原链表。
8.跳跃表是一种立足链表，借鉴二分查找的思想而形成的数据结构。能否立足有序数组，借鉴链表的思想构造一种新的数据结构来解决上述问题？
___________________________________________________________________
9.在组织、处理大数据时，可采用内存数据库与磁盘数据库，请从处理速度和安全性两方面说明内存数据与传统的磁盘数据库相比存在哪些优势和不足。
(1)内存数据库的优势：________________________________________
______________________________________________________________________________________________________________________________________ (2)内存数据库的不足：_________________________________________
______________________________________________________________________________________________________________________________________
答案　(1)内存数据库的优势：内存数据库是将需要处理的数据保存在内存中并直接操作的数据库，内存的读写速度比磁盘高出几个数量级，因此内存数据库在数据的输入和输出上极大地提高了系统的性能。内存数据库数据处理速度比传统数据库的数据处理速度一般都在10倍以上。
(2)内存数据库的不足：内存在系统中是稀缺的资源，因此内存数据库的容量大小受物理内存的限制，通常只有热点或者高频数据进行处理，而不是全部数据。安全性是内存数据库最大的问题，电脑一旦断电或重启，内存中的信息将会丢失，因此在使用内存数据库时，通常需要提前对内存上的数据采取一些保护机制，比如备份，记录日志，热备或集群，与磁盘数据库同步等方式。课时1　实时查询系统中数据的组织
课时目标
1.通过典型案例的剖析，了解数据结构设计的迭代思想。2.通过典型案例的剖析，了解大规模数据的典型数据组织与处理方式。
1.实时查询系统中的数据业务特点
(1)大数据背景下的数据组织和存储方式采用________存储系统。
(2)分布式存储系统
分布式存储系统利用分布在不同____________的服务器来分担系统存储任务，既能提高数据存储的________，又能提升系统数据访问的________，同时也具有较好的____________。
(3)实时查询系统中的数据业务特点
①能实现上千个请求的____________。
②支持后续信息的________。
(4)解决频繁访问数据库的方法
为了减轻有磁盘数据库访问的负担，采用先将数据库中的信息读取出来并保存在____________中，大大提高了数据读取的速度。
2.实时查询系统中的数据结构和算法设计
(1)基于数据间线性关系的数据结构设计
读取数据库中的数据并保存到内存中，可采用数组或链表结构来组织和存储。使用数组和链表的方式进行数据查找和插入的特点如下表所示。
数据结构 查找 插入
______ 采用二分查找，时间复杂度为O(log2n)，速度快 数据移动较多，时间复杂度O(n)，速度较慢
______ 需从头指针依次遍历，时间复杂度为O(n)，速度较慢 时间复杂度为O(1)，速度较快
(2)基于链表的数据结构和算法优化
①优化方法
ⅰ.减少查找插入位置过程中的比较次数
ⅱ.借鉴二分查找算法的思想
②跳跃表
跳跃表简称跳表，是一种立足________，借鉴____________的思想而形成的数据结构。跳跃表是在原有的有序链表上增加了多级索引，通过索引来实现快速查询。 “跳跃表”以空间换时间，时间复杂度为O(log2n)。
缺点：维护成本高，增加删除都需要更新索引。
解决方法：
ⅰ.______________。基于“抛硬币”原则选拔，以确定是否把新增元素提升为上一层的关键节点，并且逐层进行。
ⅱ.________________。删除时按照查找时的层次从上往下依次进行，每当找到对应的元素，就删除当前层的关键节点，直到最底层的原链表。
(3)其他数据组织与处理方式
①采用______________代替传统的磁盘数据库来组织、处理海量的数据。
②内存数据库进行数据处理的特点
ⅰ.减少对____________。
内存数据库通过对磁盘的访问，可将数据处理速度提高10～1000倍。
ⅱ.对数据进行________。
内存数据库对所需要处理的数据重新进行组织，并进行数据分级，再在处理器缓存中进行分级存储，进一步提升数据的存取效率。
ⅲ.采用________________来组织、存储数据。
内存数据库将数据在内存中进行重新组织、存储，进行新的体系结构设计，用更快速的算法来处理数据。
例1 大数据背景下的数据组织和存储方式，通常采用的技术是(　　)
A.传统存储系统 B.云存储系统
C.分布式存储系统 D.集中式存储系统
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
例2 使用数组来组织并存储数据时，将一个新元素插入到数组中的某个位置的时间复杂度为(　　)
A.O(1) B.O(n) C.O(log2n) D.O(n2)
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
例3 基于链表的数据结构，在数据查找时效率较低，下列方法不能提高查找效率的是(　　)
A.减少查找插入位置过程中的比较次数
B.借鉴二分查找算法的思想
C.利用有序性进行跨区间、跳跃性比较
D.增加链表尾指针，从后往前查找插入位置
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
例4 有如下跳跃表：
若要原链表中插入元素7，则数据元素需要比较的次数为(　　)
A.1次 B.3次 C.4次 D.5次
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　
1.使用链表来组织并存储数据时，在链表中插入一个新数据元素的时间复杂度为(　　)
A.O(1) B.O(n) C.O(log2n) D.O(n2)
2.下列有关跳跃表的说法中，错误的是(　　)
A.跳跃表有很多层组成
B.最底层的链表包含所有元素
C.每个节点只有一个指针，指向同一链表中的下一个元素
D.每一层都是一个有序的链表，默认是升序
3.下列方法中，不能有效提升内存数据库的数据处理性能的是(　　)
A.处理的数据保存在内存中并直接操作
B.增加对磁盘的数据读写
C.对数据进行分级，并在处理器缓存中存储
D.采用改进后的数据结构来组织、存储数据，如跳跃表、平衡树
4.有一链表如图所示：
→→→→→→→
要在链表中插入元素9，则需要进行的数据比较次数为(　　)
A.1次 B.3次 C.4次 D.5次
课时1　实时查询系统中数据的组织
知识梳理
1.(1)分布式　(2)物理位置　安全性　速度　可扩展性　(3)①实时响应　②更改　(4)内存
2.(1)数组　链表　(2)②链表　二分查找　ⅰ.增设关键节点　ⅱ.删除关键节点　(3)①内存数据库　②ⅰ.磁盘的访问　ⅱ.分级存储
ⅲ.改进后的数据结构
例题精析
例1　C　[本题主要考查的是分布式存储系统。大数据背景下的数据组织和存储方式采用的是分布式存储系统，分布式存储系统具有优秀的可扩展能力，在性能、维护性和容灾性等方面也具有不同程度的优势。]
例2　B　[本题主要考查的是在数组中插入元素的时间复杂度。在数组中插入一个新数据时，须先将插入位置上及后面的元素往后移动一位，为新元素空出位置，因此时间复杂度为O(n)，答案为B。]
例3　D　[增加链表尾指针，当插入新元素的位置靠近尾部时，会提高查找效率，但平均效率不会提高，因此，答案为D。]
例4　B　[本题主要考查的是跳跃表。该跳跃表中增设了关键节点，插入新元素时，只要让插入元素依次与关键节点比较，即元素7依次与关键节点2、5、8比较，因此，共比较3次就找到插入位置，答案为B。]
随堂检测
1.A　[本题主要考查的是在链表中的插入元素的时间复杂度。在链表中插入一个新数据元素时，只需要改变两个指针的指向即可完成操作，因此其时间复杂度为O(1)，因此，答案为A。]
2.C　[跳跃表中的每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素，因此，答案为C。]
3.B　[因为磁盘的数据读写速度较慢，因此应减少对磁盘的访问，答案为B。]
4.D　[从第1个节点开始，依次与1、2、5、8、10进行比较，最终确定插入位置，因此比较次数为5次，答案为D。]

展开更多......

收起↑