资源简介

(共21张PPT)
6.1实时查询系统中数据的组织
一、情境导入
网购平台购物，如何查询和选择商品？
思考：小陈同学在该平台查询信息的方式和特点？
（1）能实现上千个请求的实时响应
网站应能做到“即点即现”，即当某用户选择一种查询方式后，系统能马上呈现结果，而且同一时刻可能有上千名用户提出了查询请求。
二、实时查询系统中的数据业务特点
（2）支持后续商品信息的更改
当用户选择了某种查询后，可能马上又有另一名用户提出其他方式的查询请求，而此时恰好网站中更改了某个商品的属性，也或者是删除、增加了商品，那么这个修改信息应该体现在最新的查询结果中。
三、实时查询系统中的数据结构和算法设计
数组
链表
三、实时查询系统中的数据结构和算法设计
1、数组
原数据（商品名称，人气，销量，信用，价格）
数据1
（按人气排序）
数据2
（按销量排序）
数据3
（按信用排序）
数据4
（按价格排序）
分类存储
三、实时查询系统中的数据结构和算法设计
1、数组
索引 0 1 2 3 4 5 6 7 8 9
元素 1 3 4 5 6
（1）有数组如下，若要插入数字7，使数组仍然有序，该如何操作？
8
9
12
15
7
▲请同学们小组讨论并完成学生任务单中的“学习任务一”(1)(2)(3)。
三、实时查询系统中的数据结构和算法设计
1、数组
（2）程序实现：
a=[1,3,4,5,6,8,9,12,15,0] #0表示该位置未存储元素
num=int(input("输入需要插入的数据："))
for i in range(len(a)):
if a[i]>num:
for j in range(len(a)-1,i-1,-1):
_____①_______
____②_______
break
else:
a [-1]=num
print(a)
a[j]=a [j-1]
a [i]=num
三、实时查询系统中的数据结构和算法设计
1、数组
（3）思考：如果数据量较多时，我们可以采用什么方法来查找位置？
二分查找
时间复杂度：O(log2n)
索引 0 1 2 3 4 5 6 7 8
元素 1 3 4 5 6 8 9 12 15
i
j
m
m
m
i
j
j
三、实时查询系统中的数据结构和算法设计
2、链表
12
15
22
29
46
35
（1）有链表如下，若要插入数字26，使链表仍然有序，该如何操作？
head
26
▲请同学们小组讨论并完成学生任务单中的“学习任务二”(1)(2)(3)。
三、实时查询系统中的数据结构和算法设计
2、链表
（2）程序实现：
a=[[12,1],[15,2],[22,3],[29,4],[35,5],[46,-1]]
num=int(input("输入需要插入的数据："))
head=0
p=head
if numa.append([num,head])
_____①______
else:
while num>a[p][0]and p!=-1:
q=p
p=a[p][1]
a.append([num,p])
______②______
p=head
while a[p][1]!=-1:
print(a[p][0],end='->')
_____③_______
print(a[p][0])
head=len(a)-1
a[q][1]=len(a)-1
p=a[p][1]
三、实时查询系统中的数据结构和算法设计
2、链表
（3）思考：请同学们讨论交流，分析数组与链表各自的优势和劣势。
优势 劣势
数组
链表
利用二分查找
时间复杂度：O(log2n)
查找速度比较快
插入位置之后的所有元素都必须往后移位，时间复杂度较大：O(n)
插入新元素效率高，时间复杂度仅为O(1)
查找时必须从头节点开始依次遍历，时间复杂度为O(n)
四、基于链表的数据结构和算法优化
思路：
（1）减少查找插入位置过程中的比较次数
（2）借鉴二分查找算法的思想
二分查找算法之所以效率较高，首先是因为数据是有序的，其次是利用有序性进行跨区间、跳跃性的比较，从而避免低效的逐个依次比较。
跳跃表
四、基于链表的数据结构和算法优化
跳跃表
1
3
4
10
13
18
20
原链表
抛硬币
关键节点
一级索引
1
4
13
20
四、基于链表的数据结构和算法优化
跳跃表
1
3
4
10
13
18
20
原链表
抛硬币
关键节点
一级索引
1
4
13
20
二级索引
1
13
时间复杂度为： O(log2n)
四、基于链表的数据结构和算法优化
跳跃表------增设关键节点
1
3
4
10
13
18
20
原链表
一级索引
1
4
13
20
二级索引
1
13
24
24
四、基于链表的数据结构和算法优化
跳跃表------删除关键节点
1
3
4
10
13
18
20
原链表
一级索引
1
4
13
20
二级索引
1
13
24
24
四、基于链表的数据结构和算法优化
跳跃表------删除关键节点
1
3
4
10
18
20
原链表
一级索引
1
4
20
24
24
数组
链表
跳跃表
四、基于链表的数据结构和算法优化
迭代
五、其他数据组织与处理方式
内存数据库
从以下几个方面来提升数据的处理能力：
1、减少对磁盘的访问
2、对数据进行分级存储
3、采用改进后的数据结构来组织、存储数据
AVL树
Sorted-set
六、小结与拓展
除了本节课提到的几种数据结构，是否还有其他的数据结构来解决数据的组织与存储问题呢？请同学们课后讨论交流。如果有，请简要描述该数据结构组织数据并处理的算法，并尝试分析用该数据结构解决问题的时间复杂度。
课
外
拓
展

展开更多......

收起↑