資料庫原理
- 2020 年 10 月 21 日
- 筆記
記錄物理存儲
定長記錄
變長記錄
多記錄存儲
物理鄰接存儲
指針連接存儲
大欄位存儲（BLOBS）
文件組織方式
- 堆文件
- 順序文件
- 搜索快
- 插入刪除慢
- 散列文件
- 插入刪除快
- 存取快
- 不需要為存儲索引
- 記錄隨機
- 不能排序
- 有可能導致桶傾斜
- 聚簇文件
- 把多個表物理存儲在一起
- 提高多表關聯查詢
- 降低單表查詢效率
- 按列存儲
- 提高提取單列的效率
- 數據壓縮更好
索引
聚集索引
索引的順序與數據文件的順序一致，例如mysql的主鍵索引，一般一個表只有一個聚集索引
- 當記錄的物理位置發生變化，索引文件需要同步變化
輔助索引
索引的順序與數據文件的順序不一致，索引的值為主鍵，需要通過二級查詢才能到達記錄
- 當記錄的物理位置發生變化，索引文件不需要變化
稠密索引
為每個鍵建立索引
稀疏索引
在順序文件中，只為每個塊建立一個索引鍵
有序索引
索引是按序排列的，例如B+樹索引
散列索引
索引是無序的，通過hash來訪問數據
靜態散列
動態散列
- 可擴展散列
-
線性散列
index=hash(key)%n，當發生衝突時，index++
-
多段散列
多級索引
使用稠密和稀疏索引建立多級索引
查詢與優化
查詢代價的度量
響應時間 = 磁碟存儲時間+CPU運算時間+數據傳輸時間
對於本地大型資料庫一般只考慮磁碟存取時間
查詢處理過程
- SQL語句
- 語法分析
- 生成邏輯查詢
- 優化邏輯查詢
- 創建並生成物理查詢
-
查詢執行引擎
-
查詢結果
關係查詢演算法
選擇/投影/連接
- 投影：select 子句
- 選擇：where子句
- 連接：join子句
查詢演算法
- 基於排序的演算法
- 基於散列的演算法
- 基於索引的演算法
- 一趟或多趟演算法
一趟排序演算法
實現的演算法包括並，交，差，消除重複元組
如果記憶體可以至少容納一個表的數據，可以把一個表的數據全部載入在記憶體，然後對鍵進行排序，然後通過掃描第二表表，一趟把結果計算出來
多趟排序演算法
在兩個表的數據都非常非常大，此時則需要先用歸併演算法得出兩個表的排序記錄，然後再在記憶體堆兩個排序表進行並交差等運算，運算的過程中設計多次的磁碟讀入和寫出
多趟散列演算法
- 為每個表建立k個桶
- 掃描每個表並發記錄hash到k個桶
- 在記憶體中載入兩個表的第i個桶，進行並交差運算
- 如果第i個桶的數據量大於記憶體可以裝載的數量，則需要對第i個進行二次hash，直到記憶體可以裝載為止
基於索引的演算法
- 遍歷第一個表
- 通過第一個表的鍵直接通過索引查詢第二個表
- 在記憶體中進行並交叉運算
運算過程方式
實體化方法
每次運算的中間結果重新寫回磁碟，下一個運算再次從磁碟讀取中間結果並進行再次運算，直到得出結果
- 非常穩定安全
- 慢
流水式方法
每次運算的中間結果保存在記憶體，下次運算直接從記憶體獲得中間結果並進行再次運算，直到得出結果
- 快
- 不安全，有可能記憶體無法達到要求，發生記憶體溢出
查詢優化
- 通過關係運算的等價變換簡化邏輯查詢
- 通過選擇運算下移而減少查詢代價
- 通過對多個方案的估量，選擇一種物理查詢，確定每個查詢子句是否使用索引查詢還是線性查詢，是否使用歸併
故障恢復
-
錯誤的數據輸入
例如用戶錯誤數據類型，效率低的sql
需要對客戶端進行限制，並制定策略檢測和禁止某些危險行為
-
系統錯誤
由於掉電，軟體錯誤造成記憶體中數據丟失或者錯誤
通過資料庫的恢復機制，從日誌和事務中對數據進行恢復
-
介質故障
由於磁碟局部故障，例如磁頭損壞，扇區損壞
通過存儲的奇偶校驗或者使用RAID技術
-
災難性故障
發生不可逆轉的災難，導致數據據介質完全損壞，無法對介質進行任何的恢復
通過多地即時備份
事務
特定ACID
-
Atomicity 原子性
事務是一個不可分割的單元，要麼全部成功，要麼全部失敗
-
Consistency 一致性
事務前後數據的完整性必須保證業務的一致性
-
Isolation 隔離性
多個事務在並發處理時，互相隔離
-
Durability 持久性
事務一旦提交，它對數據的修改是永久的，即時此時發生資料庫發生系統故障，也不應該對此有任何影響
日誌
SQL執行過程
- 寫入日誌
- 執行SQL
日誌記錄的資訊
- 事務開始
- 事務成功提交
- 事務提交失敗
- 數據表更： 事務ID update A oldValue newValue
- 檢查點
undo日誌
規則
- 寫日誌到磁碟
- 更新數據到磁碟
- 把Commit T寫入日誌
恢復機制
從後往前找日誌，把沒有Commit T的事務進行撤銷
檢查點
檢查點包括開始部分和結束部分
開始節點對目前正在活動的事務IdList進行記錄
如果資料庫檢查到所有的IdList都已經完成，則列印一個結束檢查點
- 如果從後往前遍歷第一個遇到檢查點的開始，則找上一個檢查點的開始的位置開始遍歷
- 如果從後往前遍歷第一個遇到檢查點的結束，則找此檢查點的開始位置開始遍歷
- 上一個檢查點之前的事務是已經寫入磁碟並進行了撤銷
- 掃描此檢查點之後的事務，對沒有提交的事務進行撤銷
- 事務有可能跨越多個檢查點，此時需要再往前遍歷
缺點
頻繁將數據更新到磁碟，導致性能不高
redo日誌
規則
- 先記錄數據更新日誌
- 寫入Commit T
- 後把數據一次性從記憶體寫入磁碟
恢復機制
重做已經提交的事務
檢查點
與undo類似，只是把撤銷改成重做
事務並發
問題
- 數據丟失
- 臟讀，讀到了未提交的數據
- 幻讀，同一個事務兩次讀同一個變數，是不一樣的值
調度
串列調度
兩個事務，按照順序一個接一個的執行
可串列化調度
兩個事務，通過指令穿插的方式執行，執行的結果與串列執行的結果一致
衝突可串列化調度
不可串列化調度
在某個事務的一個並髮結果與串列化調度的結果不一致
鎖
保證可串列化的預防型策略
- 共享鎖：讀鎖S
- 排它鎖：寫鎖X
加鎖產生的問題
- 在事務內隨意的解鎖，會導致不可串列化調度
- 兩個事務加鎖順序不對，導致死鎖
- 多個事務不斷的加讀鎖，導致先加寫鎖的事務餓死
兩階段鎖協議
- 增長階段：事務獲得鎖，而不能解鎖
- 縮減階段：事務解鎖，而不能獲得鎖
嚴格兩階段鎖
在提交前釋放鎖
遵循兩階段鎖的並發控制演算法是衝突可串列化調度。但仍然存在死鎖和級聯回滾的發生。
強兩階段鎖
在提交之前不允許釋放任何鎖
可以避免級聯回滾，但依然存在死鎖
多粒度鎖
- 顯式加鎖：對元組單獨加鎖時，為顯式加鎖
- 隱式加鎖：對元組加鎖時，會同時對它的所有祖先加意向鎖
意向鎖
- IS鎖：當後代顯式加S鎖時，對此節點加意向讀鎖
- IX鎖：當後代顯式加X鎖時，對此節點加意向寫鎖
- SIX鎖：對該節點加S鎖，並加IX鎖
可串列化多粒度鎖協議
- 加鎖時遵循上面的矩陣
- 從根節點由上往下加鎖
- 遵循兩階段鎖協議
- 由下往上解鎖
死鎖
- 對鎖進行排序，再加鎖
- 死鎖檢測，系統定時加測是否存在T1->T2->T1這樣的依賴環，並根據策略回滾環中的其中一些事務，來打破死鎖等待的局面
- 搶佔與回滾技術：對事務賦予一個時間戳，如果事務回滾，則重啟該事務，並保持原有時間戳，通過比較兩個事務的時間錯的大小，來決定回滾哪個事務
- 超時機制：為每個事務定義一個等待超時時間，超時則回滾
選擇事務回滾的策略：
- 選擇代價最小的事務
- 為了防止餓死，將回滾次數考慮到代價中
- 鎖的協議開銷大，並發提升有限
基於時間戳的調度協議
保證可串列化的預防型策略
- TS(T)：事務開始執行的時間戳
- W(Q)：在Q數據項上，寫入的事務最大的時間戳
- R(Q)：在Q數據項上，讀取的事務最大的時間戳
執行協議
-
T執行Read(Q)
if TS(T) < W(Q)，回退
if TS(T) > W(Q)，執行，並更新R(Q) = (TS(T), R(Q))
-
T執行Write(Q)
if TS(T) < R(Q)，回退
If TS(T) < W(Q)，回退（可以優化成忽略T對Q的寫，並繼續執行來提高並行度）
否則執行，並更新W(Q) = TS(T)
-
T回退，並賦予新的時間戳，重新執行
基於有效性檢驗的調度協議
保證可串列化的診治型策略
- 讀階段：讀數據並保存在局部變數，並在局部變數中更新數據
- 有效性檢查階段：檢查如果把局部變數更新到資料庫中而不違背可串列性
- 寫階段：把數據更新到資料庫
協議的術語
- start(T)：T開始執行的時間
- validation(T)：完成有效性檢查的時間
- Finish(T)：完成寫的時間
- RS(T)：讀數據項的集合
- WS(T)：寫數據項的集合
有效性檢查失敗情況
- 場景1
- U比T先開始
- RS(T)和WS(U)有交集
- U先確認
- T校驗失敗
- 場景2
- U比T先執行
- T寫入X
- U寫入X
- U先確認
- T校驗失敗
規則
對於T和先於它執行的U滿足以下某一條件，則U和T可串列化
- finish(U)<start(T)
- WS(U)與RS(T)無交集，finish(U)<validation(T)
- WS(T)與RS(T)無交集，WS(U)與WS(T)無交集，validation(U)<validation(T)
事務隔離性級別
嚴格執行隔離會嚴重降低吞吐量，因此需要系統根據應用靈活設置隔離級別
- 可串列化
- 可重複度
- 讀已提交
- 讀未提交
