第六章 大数据时代数据的组织（复习课件）信息技术浙教版2019选择性必修1

复习课件 第6章 大数据时代数据的组织 浙教版（2019） 选修一 实时查询系统中数据的组织 01 POI数据的组织与应用 02 复习内容总览 实时查询系统中 数据的组织 PART 01 第1节 实时查询系统中数据的组织 知识结构 第1节 实时查询系统中数据的组织 知识点一 实时查询系统的两个特殊性： 1 2 能实现上千个请求的实时响应 支持后续商品信息的更改 1 2 用某种数据结构组织并存储数据： ※能体现数据间的逻辑关系 ※能为后续查询提供算法支持 第1节 实时查询系统中数据的组织 知识点二 基于数据间线性关系的数据结构设计 1 数组 原数据(商品名称，人气，销量，信用，价格) 数据2：按销量排序 数据3：按信用排序 数据4：按价格排序 数据1：按人气排序 数据5：按综合排序 分类 存储 链表 在数组中插入新元素时引起的数据移动低效的问题 链表 数组 第1节 实时查询系统中数据的组织 知识点二 2 基于链表的数据结构和算法优化设计 减少查找插入位置过程中的比较次数 1 链表结构数据主要消耗在插入位置的查找中，可减少查找过程中的数据两两比较的次数来优化数据结构。 借鉴二分查找算法的思想 2 确定比较的关键节点 数据进行有序化处理 （1） （2） 第1节 实时查询系统中数据的组织 知识点二 数组 链表 跳跃表 一个切合实际的数据结构和算法不是一蹴而就的，而是根据问题中数据及其关系的特点，通过迭代逐步优化得到的。 第1节 实时查询系统中数据的组织 知识点三 单纯采用传统的磁盘数据库来组织、处理海量的数据，其固有的数据组织、存取、处理等模式无法适应当今很多数据业务对实时数据管理和查询的需求。于是，人们针对磁盘数据库存在的瓶颈，发明了内存数据库，并于1994年推出了第一个商业化的、实际应用的内存数据库。 推出内存数据库 采用改进后的数据结构来组织、存储数据 AVL树、Sorted-set技术 减少对磁盘的访问 1 对数据进行分级存储 2 3 第1节 实时查询系统中数据的组织 提升练习 1.某算法的时间复杂度是〇(n),表明该算法( )。 A.问题规模是n B.问题规模与n成正比 C.执行时间等于n D.执行时间与n成正比 D 解析 算法的时间复杂度是〇(n),这是设定问题规模为n的分析结果,所以A、B都不对;它也不表明执行时间等于n,它只表明算法的执行时间T(n)≤cXn(c为比例常数)。有的算法,如nXn矩阵的转置,时间复杂度为〇(n),不表明问题规模是n。 第1节 实时查询系统中数据的组织 提升练习 2.跳跃表”是立足链表，是借鉴二分思想形成的数据结构。能否立足数组，借鉴链表的思想构造一种新的数据结构来解决数组数据移动的低效问题？ 能，有序数组在查找数据方面的效率较高,但在插入新数据的效率较低,因为新数据后面的数据元素需要连续后移,因此需要进行优化。将原来一个数组中的数据均匀分解存储到k个数组中,这样就将原来O(n)的移动复杂度降为O(n/k)。 解析 将原来一个数组中的数据均匀地分解存储到k个数组中，这样就将原来(𝑛)的移动复杂度降为(n/k)，虽然数量级没变，但至少是原来的k倍速度 第1节 实时查询系统中数据的组织 提升练习 3.若数据库中有10万条记录以链表形式有序存放，先要在原链表基础上增设关键节点创建索引，若以二分的形式创建每一级索引，则最多需要创建索引的级数是（ ） A.8 B.17 C.100 D.1000 B 解析 二分查找最多的查找次数为log2n+1,答案为 B。 POI数据的组织与应用 PART 02 第2节 POI数据的组织与应用 知识结构 第2节 POI数据的组织与应用 知识点一 概念 POI是“Point of Interest” 的 缩 写， 可 以翻译成“兴趣点”，有些时候也叫作“Point of Information”，即“信息点”。电子地图上一般用气泡图标来表示POI。 应用 POI数据在社会各个领域都得到了广泛的应用。 第2节 POI数据的组织与应用 知识点二 POI数据一般以表记录或点状数据集的形式存在，如以表结构形式储存于Oracle的大型数据库中。 数据结构主要包含下列数据 唯一标识号 点的POI分类编码 POI名称 点要素属于的矩形分幅的网格号 POI地址 POI电话 POI的经纬度 坐标 第2节 POI数据的组织与应用 知识点二 提供了一种超大规模、高可靠性、高可扩展性的存储及计算海量数据的框架，可降低成本 基于HBase的存储可靠性强、检索性能高、存储列可按需增加的特点存储地理信息专题数据 基于HDFS文件系统的高容错性和高吞吐量特点存储空间影像数据 基于MapReduce的计算能力对地理信息中的各种数据进行搭建，对地理信息专题数据进行信息提取，提取有效信息 Hadoop 1 3 2 4 第2节 POI数据的组织与应用 知识点二 包含空间对象的概要信息，如：标识、外接矩形、指针 使空间操作快速访问对象，缩短查询时间 基于树结构 基于网格划分 POI数据的组织主要涉及空间索引问题，空间索引是指依据空间对象的位置和形状或者空间对象之间的某种空间关系，按一定的顺序排列的一种数据结构。 考虑到POI数据本身为点信息，一个数据仅可能出现在一个索引位置中，因此经常使用网格空间索引来对POI建立空间索引。 第2节 POI数据的组织与应用 知识点二 网格空间索引 将一副地图的地理范围均等划分为M行N列的二维空间数据，得到M×N个小矩形网格区域。 判断哪些信息点落在矩形框中只需对A,B,C,D,E运算即可 ※不建立空间索引，所有POI遍历一遍 ※建立索引使得查询次数下降很多 每个网格索引为一个索引项 网格示意图 第2节 POI数据的组织与应用 知识点三 POI数据操作 1 连接POI数据库，将POI数据写入索引数据库。 根据关键字进行查询，存储符合条件的记录，获得结果集。 增加了对地理坐标优化的空间索引算法 1 2 3 第2节 POI数据的组织与应用 知识点三 01 R树 K-D树 02 03 四叉树 高效查找临近点 01 存在数据冗余 不稳定的查改效率 02 缺点 抛开时间效率、空间效率以及算法复杂度等因素，用了这些数据结构也就意味着放弃了使用现成强大的数据库而需要自己编写数据查改系统。 第2节 POI数据的组织与应用 知识点三 二维的信息转化为一维的数据 用于空间检索 用于POI数据查询的算法 良好的稳定性和拓展性 GeoHash 算法 GeoHash算法：二维-->一维 能够广泛引用与空间检索，尤其是POI数据查询的算法 第2节 POI数据的组织与应用 提升练习 1.POI数据的更新通常涉及哪些方面？（ ） A. 增加新的POI B. 删除过时的POI C. 修改现有POI的信息 D. 以上全部 解析 [解析]POI数据的更新可能涉及增加新的POI、删除过时的POI以及修改现有POI的信息等多个方面。 D 第2节 POI数据的组织与应用 提升练习 2.下列关于POI数据的组织和表示的说法,正确的是( ) A.Hadoop提供超大规模、高可靠性、高可扩展性的存储及计算海量数据的框架 B.采用Hadoop作为地理信息存储与计算的基础框架,基于MapReduce存储空间影像数据 C.POI空间索引的建立一般使用基于树结构的空间索引技术 D.空间索引是一种计算POI数据的索引算法 解析 [解析]基于MapReduce的计算能力对地理信息中的各种数据进行搭建,对地理信息专题数据进行信息提取,基于HDFS文件系统的高容错性和高吞吐量特点存储空间影像数据;经常使用网格空间索引对POI建立空间索引;空间索引是指依据空间对象的位置和形状或者空间对象之间的某种空间关系,按一定的顺序排列的一种数据结构。 A 第2节 POI数据的组织与应用 提升练习 3.以下关于索引的正确叙述是( ) A.使用索引可以提高数据查询速度和数据更新速度 B.使用索引可以提高数据查询速度,但会降低数据更新速度 C.使用索引可以提高数据查询速度,对数据更新速度没有影响 D.使用索引对数据查询速度和数据更新速度均没有影响 解析 [解析]使用索引可以提高数据查询速度和数据更新速度B.使用索引可以提高数据查询速度，但会降低数据更新速度C.使用索引可以提高数据查询速度，对数据更新速度没有影响D.使用索引对数据查询速度和数据更新速度均没有影响；故选A。 A 第6章 大数据时代数据的组织 浙教版（2019） 选修一 谢谢观看 $$