资源简介

(共25张PPT)
课时42 大数据时代数据的组织
一、实时查询系统中的数据业务特点
1.实时查询数据业务的特点。
（1）能实现上千个请求的　　　　响应。
（2）支持后续数据信息的　　　　。
2.实时查询业务带来的问题及解决方案。
实时
更改
存在问题 解决方案
单个服务器和数据库的数据组织与存储方式，无论从存储容量还是处理速度上都不能满足实时查询系统实际应用的需求 分布式存储系统：利用分布在不同　　　　位置的服务器来分担系统存储任务，既能提高数据存储的安全性，又能提升系统数据访问的速度，同时也具有较好的可扩展性
在大量请求涌入的情况下，系统需频繁地读取计算机硬盘并访问数据库，不仅会在负担过大时导致系统崩溃，还会因过长的等待时间而导致用户的流失 事先将数据库中的信息读取出来并保存在　　　　中，使用户的查询直接面对内存进行，大大提高读取速度
物理
内存
1. 时间复杂度：指算法中包含简单操作的次数，用来度量一个算法在计算机上运行所花费的时间。
2.基于数据间线性关系的数据结构设计。
二、实时查询系统中的数据结构和算法设计
数据结构 数组 链表
优势 ①能比较直接地表示数据之间按照某种属性呈现的有序线性关系 ②在一个有序序列中　　　　新增元素的插入位置，可以采用二分查找算法，时间复杂度为O(log2n) （n表示数组元素的总个数），速度比较快 在链表中新元素　　　　的时间复杂度为O(1)，大大优于采用数组时O(n)的线性复杂度
劣势 新数据的插入操作比较复杂，首先要查找到可以插入的位置x，再将位置x及之后的所有元素往后移一位，才能实现将新元素插入到位置x，时间复杂度为O(n) 在进行数据查找时，需要从链表的一端依次遍历查找，时间复杂度为O(n)，相较数组更高
查找
插入
3.基于链表的数据结构和算法优化设计（跳跃表）。
（1）减少查找插入位置过程中的比较次数。
（2）借鉴二分查找的思想。对有序数据进行跨区间、
跳跃性的比较，从而避免低效的逐个依次比较。
①首先将数据进行　　　　处理，然后确定比较的关键
节点，再将新元素与关键节点进行比较，如果二者相等，
则插入位置查找成功；否则根据序列的有序性，确定新
元素的插入位置在序列的前半部分还是后半部分，以此
缩小数据的查找范围。
②增设关键节点后的查找速度是原来的 2倍，原链表中
每个节点被作为上一层关键节点的概率是二分之一，所
以原链表的一半节点会出现在关键节点中。
有序化
③分级索引，关键节点起到一个　　　　的作用。例如，为一个有序链表设定二级索引，要在该链表中查找数据 4，则可以先在二级索引中确定位置在 1~5 之间，进入一级索引，确定位置在 3~5 之间，最后在原链表中找到节点 4。
索引表
（3）关键节点的增加和删除。由于数据序列在不断地动态变化，关键节点也要随之不断地更新。在数据　　　　时增设关键节点，在数据　　　　时删除关键节点。
①增设关键节点：基于“　　　　”原则，逐层进行。
②删除关键节点：删除时按照查找时的层次从上往下依次进行，每当找到对应的元素，就删除当前层的关键节点，直到最底层的　　　　。
增加
减少
抛硬币
原链表
③操作图示。
1. 产生背景：传统的磁盘数据库无法适应当今很多数据业务对实时查询数据管理和查询的需求。人们针对这样的瓶颈，发明了内存数据库，就是将需要处理的数据保存在内存中并直接操作的数据库。
三、其他数据组织与处理的方式
2.内存数据库性能的提升。
内容 含义 优势
减少对磁盘的访问 内存的数据读写速度比 　　　　要高出几个数量级 ①在数据的输入和输出上极大地提高了系统的性能
②可以将数据处理速度提高至少10倍
对数据进行 　　　　存储 对所有需要处理的数据进行重新组织，并根据应用需要将数据分级，再在处理器缓存中分级存储 由于处理器缓存速度高于内存，因此进一步提升了数据的存取效率
采用改进后的数据结构来组织、存储数据 将全部数据在内存中进行重新组织、存储，进行新的体系结构设计，用更快速的算法来处理数据，并运用支持快速算法的数据结构来组织数据 提高查找速度，例如Redis数据库运用的Sorted-set有序集合技术正是对跳跃表的改进和应用
磁盘
分级
1.POI数据的概念。
（1）POI（兴趣点或信息点），在电子地图上一般用　　　　图标来表示。对于一个地理信息系统来说，POI的数量在一定程度上代表着整个系统的价值。
（2）POI 作为可以在电子地图中查询到的信息点要素，它描述了　　　　实体或者区域的空间位置、名称地址等信息。衡量 POI数据价值的指标有：空间位置的准确性和覆盖率、空间位置的数量。
2.POI数据的组织与表示。
（1）POI 数据一般以　　　　或点状数据集的形式存在。
（2）POI数据的组织主要涉及空间索引问题。
①空间索引的概念：是指依据空间对象的位置和形状或者空间对象之间的某种空间关系，按一定的顺序排列的一种数据结构。
②空间索引的功能：使空间操作快速访问对象，缩短空间查询时间，从而提高效率。③空间索引技术的分类：基于树结构、基于　　　　划分等。
（3）网格索引的空间索引技术：将一幅地图的地理范围规则地划分为二维空间数据，得到 M×N 个小矩形网格区域，每一个网格区域为一个　　　　，可以大大减小检索空间。
四、POI数据的组织和应用
气泡
空间
表记录
网格
索引项
存储方式 数据库 R树、K-D树、四叉树
优点 使用二分查找或B树查找，可以根据某个点的坐标在海量的数据点中找到该坐标所在的区域或者最接近的点 高效地查找临近点
缺点 对于用经纬度来确定的坐标值，不方便直接使用二分法进行查找，而使用数据库的B树索引和Hash索引，并不能提高查找效率 ①数据冗余、不稳定的查改效率
②意味着放弃了使用现成强大的数据库而需要自己编写数据查改系统
优化措施 现在的主流数据库都增加了对地理坐标优化的空间索引算法 GeoHash算法
3.POI数据处理中的数据结构与算法分析。
（1）POI传统处理方式及算法。
（2）优化后的算法——GeoHash。
①GeoHash 算法能够把一个　　　　的信息转换为一维的数据直接存储到数据库中以便快速的查找。
②GeoHash 算法的目的是为地球上的每一个点（根据经纬度）确定一条短的 URL 作为
　　　　。
③GeoHash 算法把一个坐标点映射到一个字符串上，每一个字符串代表的就是一个以经纬度划分的矩形区域。每一个区域又可以继续划分为许多个子区域，每个子区域的 GeoHash 值都是在其　　　　拓展一个字符，以此形成一个层次分明的结构。
④越高级的 GeoHash 值越短，表示的范围越　　　　，越低级的 GeoHash 值越长，
表示的区域越　　　　。
二维
唯一的标识
父区域后面
大
小
典例 1 某个网站的首页如图所示，该网站能够实现商品的检索、筛选以及商品信息的更改，并且响应速度快。下列关于该网站系统的说法，不正确的是 （　　）
A.该网站虽然用户量庞大，但对每一位用户的请求都能做到实时响应
B.该网站采用分布式存储技术，将数据分别保存在不同的服务器中
C.用户对商品的检索和查询一般面对该系统的数据库进行
D.在该系统中更改商品信息之后还能再进行后续的修改
C
√
题型导向一　实时查询系统中数据的组织
胜券点拨1
明考向 本题主要考查实时查询系统中的数据业务特点
审关键 实时查询系统中的数据业务特点
考场思维快闪 A 实时查询系统能实现上千请求的实时响应
B 采用分布式存储技术，将所有数据分别保存在不同的服务器中，需要时从中提取并进行合并，就可以满足海量数据的存储与处理需求
C 实时查询系统一般将数据信息先保存在内存中，使用户的查询直接面对内存进行
D 实时查询系统支持后续商品信息的更改
典例 2 下列关于跳跃表的说法，正确的是（　　）
A.跳跃表相对于普通链表能够提高数据的查找效率
B.跳跃表最多能提取三级索引
C.跳跃表的关键节点数量越多，查找效率越高
D.跳跃表中的关键节点在设定后不发生改变
A
√
胜券点拨2
明考向 本题主要考查跳跃表的相关知识
审关键 跳跃表的作用、索引、关键节点
考场思维快闪 A 借鉴二分查找算法的思想在原链表中增设关键节点，可以大大提高数据的查找速度
B 跳跃表的索引根据实际需求提取，若待查找的数据量大，可以增设三级、四级或更多的索引
C 跳跃表的关键节点数量一般是原链表的一半，过多并不会提高查找效率
D 跳跃表中的关键节点会随着原链表中数据的变化而发生改变
典例 3 下列关于内存数据库的说法，不正确的是 （　　）
A.在数据的输入和输出上极大地提高了系统的性能
B.内存数据库就是将需要处理的数据保存在内存中并直接操作的数据库
C.内存数据库不对数据原有的数据结构进行修改，保留原有数据的真实性
D.内存数据库的数据可以在处理缓存器中分级存储
C
√
胜券点拨3
明考向 本题主要考查内存数据库的相关知识
审关键 内存数据库的作用
考场思维快闪 A 内存的数据读写速度比磁盘高出好几个数量级，在数据的输入和输出上极大地提高了系统的性能
B 内存数据库即是将需要处理的数据保存在内存中并直接操作的数据库
C 内存可以将全部数据在内存中进行重新组织、存储，进行新的体系结构设计
D 内存数据库首先根据应用需要对数据分级，再在处理器缓存中进行分级存储。处理器缓存速度高于内存，进一步提升数据的存取效率
典例 4 使用地图软件在某区域搜索“景区”后，显示的部分界面如图所示，下列说法正确的是（　　）
A.该图所示的 POI 显示的信息有名称、地址、经纬度
B.该地图可能使用的是 GeoHash 算法
C.该系统无法对地理位置信息进行修改
D.若放大该区域，则显示的信息会变少
B
√
题型导向二　POI数据的组织与应用
胜券点拨4
明考向 本题主要考查POI数据相关知识
审关键 POI数据的内容、组织、表示和算法
考场思维快闪 A 图中只显示了空间实体的名称
B GeoHash算法在POI数据的处理中有广泛的应用
C 该系统属于实时查询系统，能够支持后续信息的更改
D POI数据采用的GeoHash算法，是一个层次鲜明的结构，放大该区域，会显示该区域下的子区域中的POI数据
特点 要求 解决思路
实现上千个请求的实时响应 海量数据的存储 分布式存储技术、内存数据库
数据的频繁读取，磁盘数据库的频繁访问，对读取速度的要求较高 事先将数据库中的数据读取出来并保存在内存中，用户的查询直接面对内存进行
海量数据的处理 数据的组织方式（数组、链表）
支持后续数据信息的更改 数据的组织既要体现数据之间的逻辑关系，又能为后续的查询提供算法上的支持 ①数组：体现逻辑关系，数据查询效率高，但是数据的插入与删除效率低
②链表：数据的插入与删除效率相对高，但是数据的查询效率低（相对于数组整体复杂度有所下降）
优化数据结构及算法 借鉴二分查找算法优化链表得到跳跃表
通法一　理解实时查询系统的特点
操作 具体过程
跳跃表的建立 首先将数据进行有序化处理，像二分查找一样确定比较的关键节点，原链表中每个节点被作为上一层关键节点的概率是二分之一
跳跃表中数据的查找 根据新元素与关键节点的比较结果来高效地取舍剩余的查找区间
关键节点的增设 对新增元素基于“抛硬币”原则的选拔，以确定是否把新增元素提升为上一层的关键节点，并且逐层进行
关键节点的删除 按照查找时的层次依次进行，从上层索引开始，向下逐层查找、删除节点，直到原链表
通法二　跳跃表的数据操作
一、实时查询系统中数据的组织
1.下列不属于实时查询系统的是 （　　）
A.政务网站上的政民互动板块可以筛选相关的问题以及问题更新动态
B.网上购物时可以筛选指定价格区间的产品
C.Excel 中的数据筛查可以根据不同条件查找及显示相关的数据
D.在出行 App 上挑选合适的飞机航班并查看剩余席位
C
√
Excel 上的查找筛选功能没有“上千个请求的实时响应”的特征，不属于实时查询系统。
二、POI数据的组织与应用
2.下列关于 POI 数据的组织和表示的说法，正确的是 （　　）
A.Hadoop 提供超大规模、高可靠性、高可扩展性的存储及计算海量数据的框架
B.采用 Hadoop 作为地理信息存储与计算的基础框架，基于 MapReduce 存储空间
影像数据
C.POI 空间索引的建立一般使用基于树结构的空间索引技术
D.空间索引是一种计算 POI数据的索引算法
A
√
基于 MapReduce 的计算能力对地理信息中的各种数据进行搭建，对地理信息专题数据进行信息提取，基于 HDFS 文件系统的高容错性和高吞吐量特点存储空间影像数据。经常使用网格空间索引对 POI 建立空间索引。空间索引是指依据空间对象的位置和形状或者空间对象之间的某种空间关系，按一定的顺序排列的一种数据结构。
3.下列关于内存数据库的说法，不正确的是 （　　）
A.处理的数据保存在内存中并进行操作，可提升内存数据库性能
B.减少对内存数据库的访问，增加对磁盘的数据读写，能有效提高数据处理速度
C.在处理器缓存中将数据分级存储，可以提升数据的存取效率
D.可以采用跳跃表、平衡树等数据结构来组织、存储数据
B
√
磁盘的数据读写速度较慢，因此应减少对磁盘的访问。
4.下列关于空间索引技术的说法，不正确的是（　　）
A.可以描述空间实体的概要信息
B.空间索引中不包含空间对象的标识
C.可以缩短空间查询时间，提高索引 POI数据的效率
D.可以使空间操作快速访问对象
B
√
空间索引中包含空间对象的概要信息，其中就包括空间对象实体的标识。
5.下列关于 POI 数据处理中的数据存储与查询算法的说法，正确的是 （　　）
A.对于用经纬度表示的坐标值，使用二分查找算法能够找到某个数据的临近点
B.K-D 树存储 POI数据具有稳定的查改效率
C.若使用 R 树存储 POI 数据，可以高效地查找临近点
D.GeoHash 算法中，GeoHash 值越长，表示的区域越大
C
√
对于用经纬度来确定的坐标值，不方便直接使用二分查找。 K-D 树结构存在数据冗余、不稳定的查改效率等缺点。GeoHash 算法中，GeoHash 值越长，表示的区域越小。
6.有如图所示的链表，为其建立两级索引的跳跃表，请根据该跳跃表回答下列问题。
（1）若向链表中插入新的数据元素 21，则跳跃表相比于原链表减少的比较次数是
　　　　　　　　（单选，填字母：A.1 / B.2 / C.3 / D.0）。
（2）若要删除原链表中的元素 17，则最终跳跃表的状态是　　　　　　　（单选，填字母）。
A.删除索引及原链表中的元素 17，保留所有索引
B.删除索引及原链表中的元素 17，仅保留一级索引
C.删除原链表中的元素 17，所有索引保持不变
D.删除所有索引中的元素 17，原链表保持不变
B
（1）插入数据元素 21，原链表需要从 3 开始，比较到 26，比较次数是 6 次，跳跃表中首先在二级索引比较 3、17，之后在一级索引比较 33，最后在原链表中比较 26，比较次数是 4。 （2）删除跳跃表中的关键节点需要逐层删除直至原链表，二级索引中只剩一个数据，没有存在的意义，故只保留一级索引。
B

展开更多......

收起↑