资源简介

(共15张PPT)
一、 实时查询系统中数据的组织
信息技术 选择性必修1 数据与数据结构
第六章　大数据时代数据的组织
知识过关
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. 该系统需满足“即点即现”的查询要求
【解析】 实时查询系统采用分布式存储技术,将数据保存在不同的服务器中,其业务特殊性之一是支持后续商品信息的更改,将修改信息体现在最新的查询结果中,一般从内存中提取查询的结果,满足“即点即现”的要求,D正确。
D
【例2】 下列关于实时查询系统中数据结构的说法,错. 误. 的是(　　)
A. 商品排序时具备线性特征,可以采用数组存储商品数据
B. 链表在商品维护阶段中的查询效率比数组高
C. 相同节点数量的跳跃表,其索引层的层数可能不同
D. 二叉排序树可以用来组织和存储系统中的数据
【解析】 数组和链表属于线性结构,链表的插入和删除效率比数组高,但查询效率低,B符合题意。
B
【例3】 若原始链表有64个有序节点,则对应跳跃表最多创建的索引级数为 (　　)
A. 3 B. 4
C. 5 D. 无法确定
【解析】 原始链表有64个节点,但每层索引的关键节点是从下层节点中随机产生的,因此无法确定有几层索引,D正确。
D
自我检测
1. 下列业务中,不. 属. 于. 实时查询系统的数据业务的是(　　)
A. 移动话费与流量查询业务
B. 某购物网站按“销量”排序的查询业务
C. “XX学校高三期中考试.xlsx”文件中的个人成绩查询
D. 某快递网站按“快递编号”查询快递状态业务
【解析】 此文件属于静态数据集,在文件中查询个人成绩一次只能执行一个查询操作,因此不属于实时查询系统的数据业务,C符合题意。
C
2. 下列措施中,不. 能. 提升实时查询系统的查询效率的是(　　)
A. 采用分布式存储技术存储海量数据
B. 增加计算机硬盘的容量
C. 将重要数据读取并保留在内存中
D. 构造切合实际需求的数据结构组织数据
【解析】 实时查询系统将数据保存在内存中从而提升查询效率,减少对磁盘的访问,因此增加硬盘容量无法提高查询效率,B符合题意。
B
3. 下列不. 属. 于. 线性关系的数据结构设计是(　　)
A. 数组 B. 链表
C. 跳跃表 D. 二叉排序树
【解析】 二叉排序树不属于线性关系的数据结构,D符合题意。
D
4. 若某跳跃表如图所示,该跳跃表的二级索引包含的节点可能是 (　　)
A. d B. e g
C. d f g D. e f m p
【解析】 二级索引包含的节点是从一级索引随机产生的,因此必然包含在一级索引中,e、g节点并不在一级索引中,A符合题意。
A一、 实时查询系统中数据的组织
1. 实时查询系统中的数据业务特点
(1)大数据背景下的数据组织和存储方式采用分布式存储系统。
(2)分布式存储系统。
分布式存储系统利用分布在不同物理位置的服务器来分担系统存储任务,既能提高数据存储的安全性,又能提升系统数据访问的速度,同时也具有较好的可扩展性。
(3)实时查询系统中的数据业务特点。
①能实现上千个请求的实时响应。
②支持后续信息的更改。
(4)解决频繁访问数据库的方法。
为了减轻磁盘数据库访问的负担,采用先将数据库中的商品信息读取出来并保存在内存中,大大提高了数据读取的速度。
2. 实时查询系统中的数据结构和算法设计
(1)基于数据间线性关系的数据结构设计。
读取数据库中的数据并保存到内存中,可采用数组或链表结构来组织和存储。使用数组和链表的方式进行数据查找和插入的特点如下表所示。
数据结构 查找 插入
数组 采用二分查找,时间复杂度为O(log2n),速度快 数据移动较多,时间复杂度为O(n),速度较慢
链表 需从头指针依次遍历,时间复杂度为O(n),速度较慢 时间复杂度为O(1),速度较快
(2)基于链表的数据结构和算法优化。
①优化方法。
ⅰ.减少查找插入位置过程中的比较次数。
ⅱ.借鉴二分查找算法的思想。
②跳跃表。
跳跃表简称跳表,是一种立足于链表,借鉴二分查找的思想而形成的数据结构。跳跃表是在原有的有序链表上增加了多级索引,通过索引来实现快速查询。“跳跃表”以空间换时间,时间复杂度为O(log2n)。
缺点:维护成本高,增加和删除都需要更新索引。
解决方法:
ⅰ.增设关键节点。基于“抛硬币”原则选拔,以确定是否把新增元素提升为上一层的关键节点,并且逐层进行。
ⅱ.删除关键节点。删除时按照查找时的层次从上往下依次进行,每当找到对应的元素,就删除当前层的关键节点,直到最底层的原链表。
(3)其他数据组织与处理方式。
①采用内存数据库代替传统的磁盘数据库来组织、处理海量的数据。
②内存数据库进行数据处理的特点。
ⅰ.减少对磁盘的访问。
内存数据库通过对磁盘的访问,可将数据处理速度提高10~1000倍。
ⅱ.对数据进行分级存储。
内存数据库对所需要处理的数据重新进行组织并进行数据分级,再在处理器缓存中进行分级存储,进一步提升数据的存取效率。
ⅲ.采用改进后的数据结构来组织、存储数据。
内存数据库将数据在内存中进行重新组织、存储,进行新的体系结构设计,用更快速的算法来处理数据。
【例1】 下列关于实时查询系统的说法,正确的是(　D　)
A. 能使用单个服务器和数据库对系统中的全部数据进行组织、存储和处理
B. 商品的修改信息不需要体现在最新的查询结果中
C. 一般从磁盘数据库中提取查询业务的结果
D. 该系统需满足“即点即现”的查询要求
【解析】 实时查询系统采用分布式存储技术,将数据保存在不同的服务器中,其业务特殊性之一是支持后续商品信息的更改,将修改信息体现在最新的查询结果中,一般从内存中提取查询的结果,满足“即点即现”的要求,D正确。
【例2】 下列关于实时查询系统中数据结构的说法,错误的是(　B　)
A. 商品排序时具备线性特征,可以采用数组存储商品数据
B. 链表在商品维护阶段中的查询效率比数组高
C. 相同节点数量的跳跃表,其索引层的层数可能不同
D. 二叉排序树可以用来组织和存储系统中的数据
【解析】 数组和链表属于线性结构,链表的插入和删除效率比数组高,但查询效率低,B符合题意。
【例3】 若原始链表有64个有序节点,则对应跳跃表最多创建的索引级数为 (　D　)
A. 3 B. 4
C. 5 D. 无法确定
【解析】 原始链表有64个节点,但每层索引的关键节点是从下层节点中随机产生的,因此无法确定有几层索引,D正确。
1. 下列业务中,不属于实时查询系统的数据业务的是(　C　)
A. 移动话费与流量查询业务
B. 某购物网站按“销量”排序的查询业务
C. “XX学校高三期中考试.xlsx”文件中的个人成绩查询
D. 某快递网站按“快递编号”查询快递状态业务
【解析】 此文件属于静态数据集,在文件中查询个人成绩一次只能执行一个查询操作,因此不属于实时查询系统的数据业务,C符合题意。
2. 下列措施中,不能提升实时查询系统的查询效率的是(　B　)
A. 采用分布式存储技术存储海量数据
B. 增加计算机硬盘的容量
C. 将重要数据读取并保留在内存中
D. 构造切合实际需求的数据结构组织数据
【解析】 实时查询系统将数据保存在内存中从而提升查询效率,减少对磁盘的访问,因此增加硬盘容量无法提高查询效率,B符合题意。
3. 下列不属于线性关系的数据结构设计是(　D　)
A. 数组 B. 链表
C. 跳跃表 D. 二叉排序树
【解析】 二叉排序树不属于线性关系的数据结构,D符合题意。
4. 若某跳跃表如图所示,该跳跃表的二级索引包含的节点可能是 (　A　)
A. d B. e g
C. d f g D. e f m p
【解析】 二级索引包含的节点是从一级索引随机产生的,因此必然包含在一级索引中,e、g节点并不在一级索引中,A符合题意。

展开更多......

收起↑