資源簡介

(共32張PPT)
課時1　實時查詢系統中數據的組織
第六章　大數據時代數據的組織
1.通過典型案例的剖析，了解數據結構設計的迭代思想。2.通過典型案例的剖析，了解大規模數據的典型數據組織與處理方式。
目 錄
CONTENTS
知識梳理
01
例題精析
02
隨堂檢測
03
鞏固與提升
04
知識梳理
1
1.實時查詢系統中的數據業務特點
(1)大數據背景下的數據組織和存儲方式采用_________存儲系統。
(2)分布式存儲系統
分布式存儲系統利用分布在不同____________的服務器來分擔系統存儲任務，既能提高數據存儲的_________，又能提升系統數據訪問的______，同時也具有較好的____________。
分布式
物理位置
安全性
速度
可擴展性
(3)實時查詢系統中的數據業務特點
①能實現上千個請求的____________。
②支持后續信息的______。
實時響應
更改
(4)解決頻繁訪問數據庫的方法
為了減輕有磁盤數據庫訪問的負擔，采用先將數據庫中的信息讀取出來并保存在______中，大大提高了數據讀取的速度。
內存
2.實時查詢系統中的數據結構和算法設計
(1)基于數據間線性關系的數據結構設計
讀取數據庫中的數據并保存到內存中，可采用數組或鏈表結構來組織和存儲。使用數組和鏈表的方式進行數據查找和插入的特點如下表所示。
數據結構 查找 插入
______ 采用二分查找，時間復雜度為O(log2n)，速度快 數據移動較多，時間復雜度O(n)，速度較慢
______ 需從頭指針依次遍歷，時間復雜度為O(n)，速度較慢 時間復雜度為O(1)，速度較快
數組
鏈表
(2)基于鏈表的數據結構和算法優化
①優化方法
ⅰ.減少查找插入位置過程中的比較次數
ⅱ.借鑒二分查找算法的思想
②跳躍表
跳躍表簡稱跳表，是一種立足______，借鑒____________的思想而形成的數據結構。跳躍表是在原有的有序鏈表上增加了多級索引，通過索引來實現快速查詢。 “跳躍表”以空間換時間，時間復雜度為O(log2n)。
缺點：維護成本高，增加刪除都需要更新索引。
鏈表
二分查找
解決方法：
ⅰ.__________________。基于“拋硬幣”原則選拔，以確定是否把新增元素提升為上一層的關鍵節點，并且逐層進行。
ⅱ.__________________。刪除時按照查找時的層次從上往下依次進行，每當找到對應的元素，就刪除當前層的關鍵節點，直到最底層的原鏈表。
(3)其他數據組織與處理方式
①采用_______________代替傳統的磁盤數據庫來組織、處理海量的數據。
增設關鍵節點
刪除關鍵節點
內存數據庫
②內存數據庫進行數據處理的特點
ⅰ.減少對_______________。
內存數據庫通過對磁盤的訪問，可將數據處理速度提高10～1000倍。
ⅱ.對數據進行____________。
內存數據庫對所需要處理的數據重新進行組織，并進行數據分級，再在處理器緩存中進行分級存儲，進一步提升數據的存取效率。
ⅲ.采用________________________來組織、存儲數據。
內存數據庫將數據在內存中進行重新組織、存儲，進行新的體系結構設計，用更快速的算法來處理數據。
磁盤的訪問
分級存儲
改進后的數據結構
例題精析
2
例1 大數據背景下的數據組織和存儲方式，通常采用的技術是(　　)
C
解析　本題主要考查的是分布式存儲系統。大數據背景下的數據組織和存儲方式采用的是分布式存儲系統，分布式存儲系統具有優秀的可擴展能力，在性能、維護性和容災性等方面也具有不同程度的優勢。
A.傳統存儲系統 B.云存儲系統
C.分布式存儲系統 D.集中式存儲系統
例2 使用數組來組織并存儲數據時，將一個新元素插入到數組中的某個位置的時間復雜度為(　　)
A.O(1) B.O(n) C.O(log2n) D.O(n2)
解析　本題主要考查的是在數組中插入元素的時間復雜度。在數組中插入一個新數據時，須先將插入位置上及后面的元素往后移動一位，為新元素空出位置，因此時間復雜度為O(n)，答案為B。
B
例3 基于鏈表的數據結構，在數據查找時效率較低，下列方法不能提高查找效率的是(　　)
解析　增加鏈表尾指針，當插入新元素的位置靠近尾部時，會提高查找效率，但平均效率不會提高，因此，答案為D。
D
A.減少查找插入位置過程中的比較次數
B.借鑒二分查找算法的思想
C.利用有序性進行跨區間、跳躍性比較
D.增加鏈表尾指針，從后往前查找插入位置
例4 有如下跳躍表：
解析　本題主要考查的是跳躍表。該跳躍表中增設了關鍵節點，插入新元素時，只要讓插入元素依次與關鍵節點比較，即元素7依次與關鍵節點2、5、8比較，因此，共比較3次就找到插入位置，答案為B。
B
若要原鏈表中插入元素7，則數據元素需要比較的次數為(　　)
A.1次 B.3次 C.4次 D.5次
隨堂檢測
3
1.使用鏈表來組織并存儲數據時，在鏈表中插入一個新數據元素的時間復雜度為(　　)
A.O(1) B.O(n) C.O(log2n) D.O(n2)
A
解析　本題主要考查的是在鏈表中的插入元素的時間復雜度。在鏈表中插入一個新數據元素時，只需要改變兩個指針的指向即可完成操作，因此其時間復雜度為O(1)，因此，答案為A。
A.跳躍表有很多層組成
B.最底層的鏈表包含所有元素
C.每個節點只有一個指針，指向同一鏈表中的下一個元素
D.每一層都是一個有序的鏈表，默認是升序
C
解析　跳躍表中的每個節點包含兩個指針，一個指向同一鏈表中的下一個元素，一個指向下面一層的元素，因此，答案為C。
A.處理的數據保存在內存中并直接操作
B.增加對磁盤的數據讀寫
C.對數據進行分級，并在處理器緩存中存儲
D.采用改進后的數據結構來組織、存儲數據，如跳躍表、平衡樹
B
解析　因為磁盤的數據讀寫速度較慢，因此應減少對磁盤的訪問，答案為B。
4.有一鏈表如圖所示：
D
解析　從第1個節點開始，依次與1、2、5、8、10進行比較，最終確定插入位置，因此比較次數為5次，答案為D。
4
鞏固與提升
基礎鞏固
能力提升
A.分布式存儲系統需要使用多臺服務器共同存儲數據
B.分布式存儲系統需要多臺服務器同時工作
C.分布式存儲系統中的多臺服務器通過網絡進行連接
D.在有服務器出現故障的情況下分布式存儲系統將不可用
D
解析　本題主要考查的是分布式存儲系統。分布式存儲系統需要使用多臺服務器共同存儲數據，但隨著服務器數量的增加，服務器出現故障的概率也會不斷增加。為了保證在有服務器出現故障的情況下系統仍然可用，分布式存儲系統一般采用把一個數據分成多份存儲在不同的服務器中的方法來解決，因此，在有服務器出現故障的情況下分布式存儲系統仍將可用，答案為D。
2.使用數組來組織并存儲數據時，使用二分查找算法在一個有序序列中查找新增元素的插入位置，其時間復雜度為(　　)
A.O(1) B.O(n) C.O(log2n) D.O(n2)
C
解析　本題主要考查二分查找算法的時間復雜度。使用二分查找算法查找某個位置的時間復雜度為O(log2n)，因此，答案為C。
3.使用鏈表來組織并存儲數據時，要在鏈表中查找新元素的插入位置，其時間復雜度為(　　)
A.O(1) B.O(n) C.O(log2n) D.O(n2)
B
解析　本題主要考查的是在鏈表中的進行數據查找的時間復雜度。在鏈表中查找數據或數據位置時，需要從鏈表的一端依次遍歷查找，因此其時間復雜度為O(n)，因此，答案為B。
A.跳躍表是一種特殊的有序鏈表
B.跳躍表是由多層有序鏈表組合而成的，最底一層的鏈表保存了所有的數據
C.相鄰的兩層鏈表中元素相同的節點之間存在引用關系
D.使用跳躍表不僅提高了查詢效率，同時也節省了存儲空間
D
解析　本題主要考查的是跳躍表的特點。使用跳躍表的目的在于提高了查詢效率，但同時也增加一定的存儲空間，因此答案為D。
5.有如圖所示跳躍表：
C
解析　本題主要考查的是跳躍表的插入操作。要在原鏈表中插入元素12，關鍵是要找到插入的位置，通過與關鍵節點1、5、10、15的比較，可確定插入的位置，因此比較次數為4次，答案為C。
若要在原鏈表中插入元素12，需比較的次數為(　　)
A.1次 B.3次 C.4次 D.5次
6.有如下圖所示跳躍表：
C
解析　本題主要考查的是在跳躍中查找數據元素。首先從二級索引中經過2次比較確定一個大致區間，然后通過對應關系到達一級索引，最終到達原鏈表中找到元素27，因此共查找次數為3次，答案為C。
若要在原鏈表中查找元素27，則查找次數為(　　)
A.1次 B.2次 C.3次 D.4次
7.有如下圖所示的跳躍表：
請畫出刪除元素6后的鏈表狀態。
_______________________________________________________________________________________________________________________________________________________________________________________________________________
答案　刪除元素6后的鏈表狀態為：
解析　本題主要考查的是刪除跳躍表中的關鍵節點。當原鏈表中的數據元素被刪除時，各級索引中的關鍵節點也需要隨之刪除，刪除時按照查找時的層次從上往下依次進行，每當找到對應的元素，就刪除當前層的關鍵節點，直到最底層的原鏈表。
8.跳躍表是一種立足鏈表，借鑒二分查找的思想而形成的數據結構。能否立足有序數組，借鑒鏈表的思想構造一種新的數據結構來解決上述問題？
___________________________________________________________________
9.在組織、處理大數據時，可采用內存數據庫與磁盤數據庫，請從處理速度和安全性兩方面說明內存數據與傳統的磁盤數據庫相比存在哪些優勢和不足。
(1)內存數據庫的優勢：________________________________________
______________________________________________________________________________________________________________________________________ (2)內存數據庫的不足：_________________________________________
______________________________________________________________________________________________________________________________________
答案　(1)內存數據庫的優勢：內存數據庫是將需要處理的數據保存在內存中并直接操作的數據庫，內存的讀寫速度比磁盤高出幾個數量級，因此內存數據庫在數據的輸入和輸出上極大地提高了系統的性能。內存數據庫數據處理速度比傳統數據庫的數據處理速度一般都在10倍以上。
(2)內存數據庫的不足：內存在系統中是稀缺的資源，因此內存數據庫的容量大小受物理內存的限制，通常只有熱點或者高頻數據進行處理，而不是全部數據。安全性是內存數據庫最大的問題，電腦一旦斷電或重啟，內存中的信息將會丟失，因此在使用內存數據庫時，通常需要提前對內存上的數據采取一些保護機制，比如備份，記錄日志，熱備或集群，與磁盤數據庫同步等方式。課時1　實時查詢系統中數據的組織
課時目標
1.通過典型案例的剖析，了解數據結構設計的迭代思想。2.通過典型案例的剖析，了解大規模數據的典型數據組織與處理方式。
1.實時查詢系統中的數據業務特點
(1)大數據背景下的數據組織和存儲方式采用________存儲系統。
(2)分布式存儲系統
分布式存儲系統利用分布在不同____________的服務器來分擔系統存儲任務，既能提高數據存儲的________，又能提升系統數據訪問的________，同時也具有較好的____________。
(3)實時查詢系統中的數據業務特點
①能實現上千個請求的____________。
②支持后續信息的________。
(4)解決頻繁訪問數據庫的方法
為了減輕有磁盤數據庫訪問的負擔，采用先將數據庫中的信息讀取出來并保存在____________中，大大提高了數據讀取的速度。
2.實時查詢系統中的數據結構和算法設計
(1)基于數據間線性關系的數據結構設計
讀取數據庫中的數據并保存到內存中，可采用數組或鏈表結構來組織和存儲。使用數組和鏈表的方式進行數據查找和插入的特點如下表所示。
數據結構 查找 插入
______ 采用二分查找，時間復雜度為O(log2n)，速度快 數據移動較多，時間復雜度O(n)，速度較慢
______ 需從頭指針依次遍歷，時間復雜度為O(n)，速度較慢 時間復雜度為O(1)，速度較快
(2)基于鏈表的數據結構和算法優化
①優化方法
ⅰ.減少查找插入位置過程中的比較次數
ⅱ.借鑒二分查找算法的思想
②跳躍表
跳躍表簡稱跳表，是一種立足________，借鑒____________的思想而形成的數據結構。跳躍表是在原有的有序鏈表上增加了多級索引，通過索引來實現快速查詢。 “跳躍表”以空間換時間，時間復雜度為O(log2n)。
缺點：維護成本高，增加刪除都需要更新索引。
解決方法：
ⅰ.______________?；凇皰佊矌拧痹瓌t選拔，以確定是否把新增元素提升為上一層的關鍵節點，并且逐層進行。
ⅱ.________________。刪除時按照查找時的層次從上往下依次進行，每當找到對應的元素，就刪除當前層的關鍵節點，直到最底層的原鏈表。
(3)其他數據組織與處理方式
①采用______________代替傳統的磁盤數據庫來組織、處理海量的數據。
②內存數據庫進行數據處理的特點
ⅰ.減少對____________。
內存數據庫通過對磁盤的訪問，可將數據處理速度提高10～1000倍。
ⅱ.對數據進行________。
內存數據庫對所需要處理的數據重新進行組織，并進行數據分級，再在處理器緩存中進行分級存儲，進一步提升數據的存取效率。
ⅲ.采用________________來組織、存儲數據。
內存數據庫將數據在內存中進行重新組織、存儲，進行新的體系結構設計，用更快速的算法來處理數據。
例1 大數據背景下的數據組織和存儲方式，通常采用的技術是(　　)
A.傳統存儲系統 B.云存儲系統
C.分布式存儲系統 D.集中式存儲系統
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
例2 使用數組來組織并存儲數據時，將一個新元素插入到數組中的某個位置的時間復雜度為(　　)
A.O(1) B.O(n) C.O(log2n) D.O(n2)
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
例3 基于鏈表的數據結構，在數據查找時效率較低，下列方法不能提高查找效率的是(　　)
A.減少查找插入位置過程中的比較次數
B.借鑒二分查找算法的思想
C.利用有序性進行跨區間、跳躍性比較
D.增加鏈表尾指針，從后往前查找插入位置
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
例4 有如下跳躍表：
若要原鏈表中插入元素7，則數據元素需要比較的次數為(　　)
A.1次 B.3次 C.4次 D.5次
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　
1.使用鏈表來組織并存儲數據時，在鏈表中插入一個新數據元素的時間復雜度為(　　)
A.O(1) B.O(n) C.O(log2n) D.O(n2)
2.下列有關跳躍表的說法中，錯誤的是(　　)
A.跳躍表有很多層組成
B.最底層的鏈表包含所有元素
C.每個節點只有一個指針，指向同一鏈表中的下一個元素
D.每一層都是一個有序的鏈表，默認是升序
3.下列方法中，不能有效提升內存數據庫的數據處理性能的是(　　)
A.處理的數據保存在內存中并直接操作
B.增加對磁盤的數據讀寫
C.對數據進行分級，并在處理器緩存中存儲
D.采用改進后的數據結構來組織、存儲數據，如跳躍表、平衡樹
4.有一鏈表如圖所示：
→→→→→→→
要在鏈表中插入元素9，則需要進行的數據比較次數為(　　)
A.1次 B.3次 C.4次 D.5次
課時1　實時查詢系統中數據的組織
知識梳理
1.(1)分布式　(2)物理位置　安全性　速度　可擴展性　(3)①實時響應?、诟摹?4)內存
2.(1)數組　鏈表　(2)②鏈表　二分查找　ⅰ.增設關鍵節點?、?刪除關鍵節點　(3)①內存數據庫?、冖?磁盤的訪問?、?分級存儲
ⅲ.改進后的數據結構
例題精析
例1　C　[本題主要考查的是分布式存儲系統。大數據背景下的數據組織和存儲方式采用的是分布式存儲系統，分布式存儲系統具有優秀的可擴展能力，在性能、維護性和容災性等方面也具有不同程度的優勢。]
例2　B　[本題主要考查的是在數組中插入元素的時間復雜度。在數組中插入一個新數據時，須先將插入位置上及后面的元素往后移動一位，為新元素空出位置，因此時間復雜度為O(n)，答案為B。]
例3　D　[增加鏈表尾指針，當插入新元素的位置靠近尾部時，會提高查找效率，但平均效率不會提高，因此，答案為D。]
例4　B　[本題主要考查的是跳躍表。該跳躍表中增設了關鍵節點，插入新元素時，只要讓插入元素依次與關鍵節點比較，即元素7依次與關鍵節點2、5、8比較，因此，共比較3次就找到插入位置，答案為B。]
隨堂檢測
1.A　[本題主要考查的是在鏈表中的插入元素的時間復雜度。在鏈表中插入一個新數據元素時，只需要改變兩個指針的指向即可完成操作，因此其時間復雜度為O(1)，因此，答案為A。]
2.C　[跳躍表中的每個節點包含兩個指針，一個指向同一鏈表中的下一個元素，一個指向下面一層的元素，因此，答案為C。]
3.B　[因為磁盤的數據讀寫速度較慢，因此應減少對磁盤的訪問，答案為B。]
4.D　[從第1個節點開始，依次與1、2、5、8、10進行比較，最終確定插入位置，因此比較次數為5次，答案為D。]

展開更多......

收起↑