资源简介

(共30张PPT)
6.1 实时查询系统中数据的组织
学习目标：
感受数据结构设计过程中的迭代思想。
了解实时查询系统中的数据业务特点。
了解数据业务中，数据进行分类、整理等组织工作的必要性。
引入
引入
操作与体验：
打开天猫购物商城，解决以下问题：
要购买一本有关信息技术的书籍，预算在30元以内？
想要知道目前哪本信息技术书籍最畅销？
想要知道哪个店铺的好评率最高？
引入
实时查询系统数据业务特点：
①能实现上千个请求的实时响应。“即点即现”
②支持后续商品信息的更改。
更改信息、删除商品、增加商品应体现在最新的查询结果中
实时查询系统的两个特殊性：
实时查询系统数据业务特点：
计算机硬盘
数据库
内存
访问
保存
系统崩溃
用户流失
提高读取速度
实时查询系统数据业务特点：
用某种数据结构组织并存储数据：
能体现数据间的逻辑关系
能为后续查询提供算法支持
实时查询系统数据结构和算法设计：
1.基于数据间线性关系的数据结构设计
（1）数组
数据读取到数组后，先按各属性（销量、信用、价格等）进行排序并分类存储。
体现商品间的有序线性关系
基于数组的算法设计：
查询过程中涉及的主要操作：
数据插入
数据查找
例如：新增商品时，需要插入一个新数据并维持数组元素继续有序。
基于数组的算法设计：
查询过程中涉及的主要操作：
数据插入
数据查找
二分查找
插入位置x到n中的元素均后移一位
上千名用户提出请求时，时效性较差
实时查询系统数据结构和算法设计：
整体复杂度有所下降，但还是达不到现实的需求。
（2）链表
数据查找过程：
数据插入过程：
需从链表的一端依次遍历
问题与讨论：
除了数组和链表，是否还有其他的数据结构来组织并存储数据？
非线性数据：
树结构
实时查询系统数据结构和算法设计：
只在查找过程低效
（2）链表
数据查找过程：
数据插入过程：
需从链表的一端依次遍历
实时查询系统数据结构和算法设计：
2.基于链表的数据结构和算法优化设计
（1）减少查找插入位置过程中的比较次数
链表结构数据主要消耗在插入位置的查找中，可减少查找过程中的数据两两比较的次数来优化数据结构。
（2）借鉴二分查找算法的思想
①数据进行有序化处理
②确定比较的关键节点
基于链表的数据结构和算法优化设计：
关键节点：对每个节点采用抛硬币的方法确定是否放在关键节点中
1
3
4
10
13
15
20
1
原链表
4
10
15
关键节点
基于链表的数据结构和算法优化设计：
1
3
4
10
13
15
20
1
原链表
4
10
15
关键节点
抛硬币的次数越多，其正反的概率越趋向于
6
例如：查找元素6
分别与1,3,4,10比较
分别与1, 4,10比较
基于链表的数据结构和算法优化设计：
1
3
4
10
13
15
20
1
原链表
4
10
15
关键节点
从整体效率分析：增设关键节点后，查找速度是原来的2倍
6
例如：查找元素6
分别与1,3,4,10比较
分别与1, 4,10比较
索引表
基于链表的数据结构和算法优化设计：
1
3
4
10
13
15
20
1
原链表
4
10
15
一级索引
1
建立二级索引
10
二级索引
基于链表的数据结构和算法优化设计：
1
3
4
10
13
15
20
1
原链表
4
10
15
一级索引
1
插入数据元素6
10
二级索引
原一级索引的比较次数减少一半，数据多，还可增设三、四级索引
总体来说,通过对链表改进可实现
基于链表的数据结构和算法优化设计：
数据增加时，增设关键节点
实时查询系统中，数据不断发生变化，需对关键节点进行动态调整：
数据减少时，删除关键节点
基于链表的数据结构和算法优化设计：
1
3
4
10
13
15
20
1
原链表
4
10
15
一级索引
1
①增设关键节点。例如：增加数据元素24。
10
二级索引
24
24
“抛硬币”为负则不需要提升；为正，把节点24提升到上一层索引
基于链表的数据结构和算法优化设计：
1
3
4
10
13
15
20
1
原链表
4
10
15
一级索引
1
②删除关键节点。
10
二级索引
24
24
从顶层索引开始查找并删除，直到最底层的原链表
删除二级索引中剩余的1个关键节点
跳跃表
例如：删除元素10
实时查询系统数据结构和算法设计：
数组
一个切合实际的数据结构和算法不是一蹴而就的，而是根据问题中数据及其关系的特点，通过迭代逐步优化得到的
链表
跳跃表
问题与讨论：
“跳跃表”是立足链表，是借鉴二分思想形成的数据结构。能否立足数组，借鉴链表的思想构造一种新的数据结构来解决数组数据移动的低效问题？
参考方向：将原来一个数组中的数据均匀地分解存储到k个数组中，这样就将原来 ( )的移动复杂度降为 (n/k)，虽然数量级没变，但至少是原来的k倍速度
其他数据组织与处理方式：
1.减少对磁盘的访问
2.对数据进行分级存储
3.采用改进后的数据结构来组织、存储数据
推出内存数据库
AVL树、Sorted-set技术
课堂小结
实时查询系统中数据的组织
实时查询系统中的数据业务特点
实时查询系统中的数据结构和算法设计
其他数据组织与处理方式
学习评价
对自己的表现进行客观的评价，并思考后续完善的方向。（3=优秀，2=一般，1=仍需加油）
评分项 自我评价
能说出实时查询系统中的数据业务特点 3 2 1
能说出大数据处理过程中常见的数据组织与处理方式 3 2 1
能形成数据分类、整理等组织工作的意识 3 2 1
知道提升数据处理性能的研究方向 3 2 1
能模拟得出链表的关键节点及结合链表的二分查找过程 3 2 1
课后作业
1.若数据库中有10万条记录以链表形式有序存放，先要在原链表基础上增设关键节点创建索引，若以二分的形式创建每一级索引，则最多需要创建索引的级数是（ ）
A.8 B.17 C.100 D.1000
2.若使用跳跃表查询，则对于下图所示的链表：
假如要查找元素9，则需要从头结点开始遍历____次才能找到
B
8
课后作业
由于元素的有序性，可以通过增加一些路径（索引）来加快查找速度
通过这种方法，我们只需要遍历元素________________，共遍历____次就可以找到数字9
还可以增加二级索引
通过这种方法，我们只需要遍历元素________________，共遍历____次就可以找到数字9
一级索引
一级索引
二级索引
0-2-6-8-10-9
6
0-6-8-10-9
5

展开更多......

收起↑