第一章：DBMS系統(tǒng)概述

1

數(shù)據(jù)庫管理系統(tǒng)將滿足：

• 用戶使用專門的數(shù)據(jù)定義語言來創(chuàng)建新的數(shù)據(jù)庫并指定其模式（數(shù)據(jù)的邏輯結(jié)構(gòu)）
• 用戶使用適當?shù)恼Z言查詢數(shù)據(jù)
• 大量的數(shù)據(jù)長期地進行存儲
• 數(shù)據(jù)具有持久性，從故障、多種類型的錯誤或者故意濫用中進行恢復。
• 多個用戶同時對數(shù)據(jù)進行訪問，孤立性，原子性

關(guān)系數(shù)據(jù)庫系統(tǒng)：關(guān)系數(shù)據(jù)庫的程序員并不需要關(guān)心存儲結(jié)構(gòu)。查詢可以用很高級的語言來表達，這樣可以極大地提高數(shù)據(jù)庫程序員的效率。

數(shù)據(jù)操縱語言(DML)
查詢響應

1. 查詢編譯器對查詢進行分析和優(yōu)化，得到的查詢計劃傳給執(zhí)行引擎。
2. 執(zhí)行引擎向資源管理器發(fā)出一系列對小的數(shù)據(jù)單元（通常是記錄或關(guān)系的元組(tuple))的請求。
3. 查找數(shù)據(jù)的請求被傳送給緩沖區(qū)管理器。從持久地存儲數(shù)據(jù)的輔助存儲器（磁盤）中將數(shù)據(jù)的適當部分取到主存的緩沖區(qū)中。
4. 緩沖區(qū)管理器和存儲管理器進行通信，以從磁盤獲取數(shù)據(jù)，存儲管理器的任務是控制數(shù)據(jù)在磁盤上的放置和在磁盤與主存之間的移動。

事務處理：
孤立地執(zhí)行的單位，一個或多個數(shù)據(jù)庫操作組成一組，稱作事務
1. 并發(fā)控制管理器或調(diào)度器，它負責保證事務的原子性和孤立性。
2. 日志和恢復管理器，它負責事務的待久性。

第二章：輔助存儲管理

加速數(shù)據(jù)庫操作的關(guān)鍵技術(shù)是安排好數(shù)據(jù)， 使得當某一個磁盤塊中有數(shù) 據(jù)被訪問時， 大約在同時很有可能該塊上的其他數(shù)據(jù)也需要被訪問。
數(shù)據(jù)庫中的任何修改都不能認為是最終有效的，直到該修改被存儲到非易失性的輔助存儲器中。

倘若一部分磁化層被以某種方式損壞，那么那些包含這個部分的整個扇 區(qū)也不能再使用。

加速對輔助存儲器的訪問

1/0開銷的主導地位：塊訪問（磁盤1/0)次數(shù)就是算法所需要的時間的近似值， 而且應該被最小化。

1. 將要一起訪問的塊放在同一柱面上，這樣我們可以經(jīng)常避免尋道時間，也可能避免旋轉(zhuǎn)延遲。
2. 將數(shù)據(jù)分隔存儲在幾個相對較小的磁盤上而不是放在一個大磁盤上。讓更多的磁頭組設備分別去訪問磁盤塊可增加在單位時間內(nèi)的磁盤塊訪問數(shù)量。
3. "鏡像“磁盤一把兩個或者更多的數(shù)據(jù)副本放在不同的磁盤上。該策略除了可以保存數(shù) 據(jù)以備某個磁盤可能壞掉，如同將數(shù)據(jù)分隔存儲幾個磁盤上，可以讓我們一次訪問多個磁盤塊。（加快讀取速度，不能加快存儲速度）
4. 在操作系統(tǒng)、DBMS或磁盤控制器中，使用磁盤調(diào)度算法選擇讀寫所請求的塊的順序。
5. 預先將預期被訪問的磁盤塊取到主存儲器中。

磁盤故障

分為間斷性故障和介質(zhì)損壞以及磁盤崩潰

間斷性故障

磁盤塊的正確內(nèi)容沒有被傳送到磁盤控制器中。
判斷：（校驗和）。 每個扇區(qū)有若干個附加位，稱為校驗和 (checksum)

奇偶校驗：單位/多位

關(guān)千大規(guī)模的錯誤，任何一個奇偶位將 檢測出錯誤的可能性是50%, 8位都檢測不 出錯誤的機會僅僅是1/2^8
如果我們用n個獨立位作為校驗碼，漏掉一個錯誤的機會僅為1/2^n

穩(wěn)定存儲的策略：

   穩(wěn)定存儲策略是一種數(shù)據(jù)冗余技術(shù)，用于提高數(shù)據(jù)存儲的可靠性和容錯能力。比如在寫時發(fā)生故障，寫的數(shù)據(jù)丟失，同時原數(shù)據(jù)也遭到破壞。

1. 成對的扇區(qū)：數(shù)據(jù)被存儲在成對的扇區(qū)中，每對扇區(qū)包含相同的數(shù)據(jù)內(nèi)容X。這些扇區(qū)被稱為“左”拷貝XL和“右”拷貝XR。
2. 奇偶校驗：每個拷貝使用額外的奇偶校驗位來增強數(shù)據(jù)的完整性。
3. 寫策略：

• 步驟1：首先將數(shù)據(jù)X寫入XL。如果寫入過程中奇偶校驗位正確，認為寫入成功；否則，需要重新寫入，直到成功或確定存在介質(zhì)故障。
• 步驟2：如果XL寫入成功，對XR重復步驟1的操作。

4. 介質(zhì)故障處理：如果在多次嘗試后，數(shù)據(jù)仍然無法寫入某個扇區(qū)，可以認為該扇區(qū)存在介質(zhì)故障。此時，應使用備用扇區(qū)來代替故障扇區(qū)。
5. 讀策略：

• 交替嘗試讀取XL和XR，直到獲得一個“好”的值，即奇偶校驗位正確的值。
• 如果在預設的嘗試次數(shù)內(nèi)無法獲得好值，可以認為數(shù)據(jù)X是不可讀的。

6. 容錯能力：通過成對存儲和奇偶校驗，該策略能夠容忍單個扇區(qū)的故障，同時保持數(shù)據(jù)的完整性。
   

穩(wěn)定存儲的錯誤處理

1. 寫故障：
   • 在寫入數(shù)據(jù)X的過程中，如果發(fā)生系統(tǒng)故障（如電源斷電），可能導致X在主存中丟失，同時正在寫入的X的拷貝也可能被破壞。
   • 系統(tǒng)恢復后，我們可以通過測試XL和XR的狀態(tài)來確定X的值?？赡艿那闆r包括：

a) 寫XL時發(fā)生故障：

• 如果故障發(fā)生在寫入XL的過程中，我們將發(fā)現(xiàn)XL的狀態(tài)是“壞”。
• 由于我們從未寫入XR，它的狀態(tài)將是“好”（除非XR同時發(fā)生介質(zhì)故障，這種情況可能性很小）。
• 這樣我們可以從XR讀取X的舊值，并可以將XR復制到XL，以修復XL的故障。

b) 寫XR后發(fā)生故障：

• 如果故障發(fā)生在寫入XR之后，我們預計XR將有狀態(tài)“好”，并且我們可以從XR讀取X的新值。
• 由于XL可能包含部分新值和部分舊值，我們需要將XR復制到XL中，以確保兩個扇區(qū)的數(shù)據(jù)一致性。
  

冗余技術(shù)

將多個物理磁盤驅(qū)動器組合成一個或多個邏輯單元，以提高數(shù)據(jù)存儲性能和提供容錯能力的技術(shù)。

RAID1

一個數(shù)據(jù)盤，一個冗余盤。

RAID4（奇偶塊）

多個數(shù)據(jù)盤，一個冗余盤

讀操作：

• 從數(shù)據(jù)盤讀取數(shù)據(jù)塊與從冗余盤讀取數(shù)據(jù)塊在操作上沒有區(qū)別。
• 讀操作可以直接從任何一個數(shù)據(jù)盤進行，因為所有數(shù)據(jù)盤上的數(shù)據(jù)塊內(nèi)容是一致的。
  

寫操作：

• 當向數(shù)據(jù)盤寫入一個新的數(shù)據(jù)塊時，不僅需要更改該數(shù)據(jù)盤上的塊，還需要更新冗余盤上相應的奇偶校驗塊，以保持數(shù)據(jù)的奇偶校驗一致性。
  

樸素的寫方法：

• 讀取所有n個數(shù)據(jù)盤上相應的數(shù)據(jù)塊。
• 將這些數(shù)據(jù)塊進行模2加法以計算新的奇偶校驗值。
• 重寫冗余盤上的塊以反映新的奇偶校驗信息。
• 這種方法涉及n-1次數(shù)據(jù)盤的讀操作，1次數(shù)據(jù)盤的寫操作，以及1次冗余盤的寫操作，總共是n+1次磁盤操作。
  

改進的寫方法：

• 只關(guān)注正在被重寫的數(shù)據(jù)塊i的舊版本和新版本。
• 通過取舊版本和新版本的模2加法，確定哪些位發(fā)生了變化（從0變?yōu)?或從1變?yōu)?）。
• 由于變化總是使1的總數(shù)從一個偶數(shù)變?yōu)橐粋€奇數(shù)，只需更改冗余塊中相應位置的位，即可恢復奇偶校驗的一致性。
• 這種方法減少了磁盤操作次數(shù)，提高了寫操作的效率。
  

寫操作的步驟：

1. 讀取要被改變的數(shù)據(jù)盤上的舊數(shù)據(jù)塊。
2. 讀取冗余盤上相應的奇偶校驗塊。
3. 將新數(shù)據(jù)塊寫入數(shù)據(jù)盤。
4. 根據(jù)新舊數(shù)據(jù)塊的模2加法結(jié)果，重新計算并寫入冗余盤的相應塊。

RAID 4級別能夠在單個數(shù)據(jù)盤發(fā)生故障時保護數(shù)據(jù)不丟失，并且通過奇偶校驗機制實現(xiàn)數(shù)據(jù)的恢復。然而，每次寫操作都需要更新奇偶校驗信息。

RAID5

• 旨在解決RAID 4中的寫入瓶頸問題。
• RAID 5是為了提高寫入性能而設計的，它通過分布式奇偶校驗來平衡各個磁盤的讀寫負載。
• 在RAID 4中，所有的寫操作都需要訪問一個專用的冗余磁盤來更新奇偶校驗信息，這成為系統(tǒng)的瓶頸。
• RAID 5使用分布式奇偶校驗，即奇偶校驗信息不是存儲在一個專用的冗余磁盤上，而是分散存儲在所有磁盤上。
• 在RAID 5中，寫操作不需要總是訪問同一個磁盤，而是根據(jù)數(shù)據(jù)塊的位置動態(tài)選擇奇偶校驗磁盤，從而提高了寫入性能。
  

多個盤崩潰時的處理（RAID6）

海明碼：于檢測和糾正單個位的錯誤（在某些情況下，可以檢測兩個錯誤并糾正一個）
【官方雙語】漢明碼Pa■t1，如何克服噪■_嗶哩嗶哩_bilibili
【官方雙語】漢明碼part2，優(yōu)雅的全貌_嗶哩嗶哩_bilibili

1.盤5的位是盤1、2、3 相應位的模2和。
2.盤6的位是盤1、2、4相應位的模2和。
3.盤7的位是盤1、3、4相應位的模2和。
讀
從任何一個數(shù)據(jù)盤中正常地讀數(shù)據(jù)。冗余盤可以不予理睬。
寫
為了寫某個數(shù)據(jù)盤的一個塊，我們要求那個塊的新版與舊版的模2和。得出的結(jié)果與對應的冗余塊進行模2和更新。

2.6 指針混寫：

處理數(shù)據(jù)項在不同存儲層次（如主存儲器和二級存儲器）之間的移動時的指針地址轉(zhuǎn)換問題
指針混寫是塊從第二級存儲器移到內(nèi)存中時，將數(shù)據(jù)庫地址空間轉(zhuǎn)換為虛擬地址空間。

自動混寫

優(yōu)點：
高效性：一旦塊被加載到內(nèi)存，所有可識別的指針立即被混寫，減少了后續(xù)操作中查找和混寫指針的延遲。
簡化編程：開發(fā)者無需擔心指針的混寫和解混寫，DBMS自動處理。
缺點：
資源浪費：如果某些混寫的指針從未被訪問，則混寫這些指針的時間和資源就被浪費了。
復雜性：需要復雜的機制來識別和定位塊內(nèi)的所有指針，可能涉及模式識別或額外的數(shù)據(jù)結(jié)構(gòu)。

按需混寫

優(yōu)點：
資源節(jié)約：只在指針被實際使用時才進行混寫，避免了不必要的混寫操作。
靈活性：可以根據(jù)訪問模式動態(tài)調(diào)整混寫策略。
缺點：
延遲：首次訪問未混寫的指針時會有額外的混寫開銷。
編程復雜性：開發(fā)者需要更仔細地管理指針的混寫狀態(tài)，確保在需要時能夠正確混寫。

不混寫

優(yōu)點：
簡單性：無需實現(xiàn)復雜的混寫和解混寫邏輯。
靈活性：指針始終以數(shù)據(jù)庫地址形式存在，便于處理和跟蹤。
缺點：
性能下降：每次訪問數(shù)據(jù)庫地址時都需要通過轉(zhuǎn)換表查找對應的內(nèi)存地址，增加了訪問延遲。
內(nèi)存管理限制：數(shù)據(jù)塊無法像混寫時那樣被有效地固定在內(nèi)存中。
混寫的程序控制
優(yōu)點：
靈活性：開發(fā)者可以根據(jù)具體的應用場景和需求來控制混寫行為。
性能優(yōu)化：對于頻繁訪問的數(shù)據(jù)塊，可以顯式地進行混寫以提高性能。
缺點：
編程復雜性：需要開發(fā)者對應用的訪問模式有深入的了解，并編寫額外的代碼來控制混寫行為。
錯誤風險：不恰當?shù)幕鞂懣刂瓶赡軐е滦阅芟陆祷蛸Y源浪費。

塊返回磁盤

轉(zhuǎn)換表（Translation Table）存儲了內(nèi)存地址（memAddr）和數(shù)據(jù)庫地址（dbAddr）之間的映射關(guān)系。這種映射允許系統(tǒng)在需要時將內(nèi)存中的地址轉(zhuǎn)換回它們在數(shù)據(jù)庫（即磁盤）上的原始地址，或者在數(shù)據(jù)從磁盤加載到內(nèi)存時執(zhí)行相反的轉(zhuǎn)換。
為了加速查詢過程，通常在轉(zhuǎn)換表上建立索引。

索引
常見的索引結(jié)構(gòu)包括散列表（Hash Table）、B樹（B-Tree）或平衡樹（如AVL樹、紅黑樹）等。
_散列表_在提供快速查找方面具有優(yōu)勢，特別是對于等長鍵的查找。然而，散列表在處理鍵的刪除和重新插入時可能會遇到性能問題，尤其是當發(fā)生哈希沖突時。
_B樹和類似的平衡樹結(jié)構(gòu)_則更適合于需要支持范圍查詢和頻繁更新的場景。它們通過保持樹的平衡來確保查詢、插入和刪除操作的時間復雜度保持在對數(shù)級別。

被釘住的記錄和塊

如果內(nèi)存中一個塊當前不能安全地被寫回磁盤，稱它為被釘住的。
內(nèi)存中B1有一個混寫指針，指向B2。B2移回磁盤時，B1的指針成為懸掛指針，我們稱B2是被釘住的。
我們需要解混寫指向B2的所有指針。因此，對每一個有數(shù)據(jù)項在內(nèi)存中的數(shù)據(jù)庫地址，轉(zhuǎn)換表必須記錄指向內(nèi)存中存在那個數(shù)據(jù)項的混寫指針的位置。
為了解決懸掛指針的問題，系統(tǒng)需要維護一個轉(zhuǎn)換表。這個表記錄了每個在內(nèi)存中有數(shù)據(jù)項的數(shù)據(jù)庫地址，以及指向這些數(shù)據(jù)項的混寫指針在內(nèi)存中的位置。當某個內(nèi)存塊（如B2）需要被寫回到磁盤時，系統(tǒng)會使用這個轉(zhuǎn)換表來找到所有指向該內(nèi)存塊的混寫指針，并將它們更新為新的有效值（如果B2的數(shù)據(jù)在磁盤上有了新的位置）或刪除它們（如果B2的數(shù)據(jù)不再需要被引用）。

在轉(zhuǎn)換表中使用附加鏈表

在這種方法中，轉(zhuǎn)換表不僅僅存儲數(shù)據(jù)庫地址到內(nèi)存地址的映射，還附加了一個鏈表來跟蹤所有引用該內(nèi)存地址的混寫指針。這個鏈表實際上是附加在轉(zhuǎn)換表中與特定內(nèi)存地址相關(guān)聯(lián)的表項上的。
當需要將一個內(nèi)存塊（如B2）寫回磁盤時，系統(tǒng)會查找轉(zhuǎn)換表中B2的內(nèi)存地址（memAddr）對應的條目。然后，它會遍歷附加在該條目上的鏈表，找到并更新或刪除所有引用B2的混寫指針。

在指針自身空間中創(chuàng)建鏈表

這種方法假設內(nèi)存地址（或指針大小）比數(shù)據(jù)庫地址短得多，因此有足夠的空間在指針本身內(nèi)部來存儲額外的信息。
每個指針不再僅僅是一個內(nèi)存地址，而是被擴展為一個結(jié)構(gòu)體，包含至少兩個部分：
a)被混寫的指針（或數(shù)據(jù)庫地址）：指向?qū)嶋H數(shù)據(jù)的原始數(shù)據(jù)庫地址。
b)鏈表指針：指向一個鏈表節(jié)點，該節(jié)點是包含所有引用該指針的混寫指針出現(xiàn)的鏈表的一部分。
鏈表內(nèi)容：每個鏈表節(jié)點包含對另一個混寫指針（實際上是另一個擴展的指針結(jié)構(gòu)體）的引用，這些混寫指針都指向同一個內(nèi)存地址。

2.7 變長數(shù)據(jù)和記錄

2.7.1 具有變長字段的記錄

將所有定長字段放在變長字段之前，然后我們在記錄首部寫人以下信息:
1.記錄長度。
2.指向所有除第一個之外的變長字段起始處(即偏移量)的指針(我們知道第一個變長字段就緊跟在定長字段之后)。

2.7.2 具有重復字段的記錄

方法一：

將字段F的每次出現(xiàn)放在一起，在記錄首部放一個指針，讓它指向字段F出現(xiàn)的第一個位置。
我們可用以下方法找到字段F出現(xiàn)的所有位置:令字段F的一次出現(xiàn)占用的字節(jié)數(shù)為L，然后在字段F的偏移量上加上L的所有整數(shù)倍數(shù)，從0開始而后L、2L、3L，依此類推。最后，我們到達F后面的字段的偏移量或記錄末尾，至此停止。

方法二：

另一種表示方法是保持記錄定長，而將變長部分(無論它是變長字段，還是重復次數(shù)不確定的字段)放在另一個塊上。在記錄本身中我們存儲:
1.指向每一個重復字段開始處的指針。
2.重復次數(shù)或者重復結(jié)束處。
優(yōu)點：
保持記錄定長?？梢愿行У貙τ涗涍M行搜索，使塊首部的開銷最少，記錄能很容易地在塊內(nèi)或塊間移動。
缺點：
另一方面，將變長部分存儲在另一個塊中增加了為檢査一條記錄的所有部分而進行的磁盤 //0 數(shù)目。

2.7.4 不能裝入一個塊中的記錄

如果記錄能跨塊，則每一條記錄和記錄片段需要一些額外的首部信息:
1.每一條記錄或片段首部必須包含一個二進制位，指明它是否為一個片段。
2.如果它是一個片段，則它需要幾個二進制位，指明它是否為它所屬的記錄的第一個或最后一個片段。
3.如果對同一條記錄有下一個和/或前一個片段，則片段需要指向這樣一些其他片段的指針。
記錄片段2-a的首部包含一個指明它是片段的標記，一個指明它是記錄的第一個片段的標記和一個指向下一個片段2-b的指針。
同樣，2-b首部指明它是記錄的最后一個片段，且有一個指向前一個片段2a的反向指針。

2.7.5 BLOB（大數(shù)據(jù)量存儲）

連續(xù)存儲： 理想情況下，BLOB數(shù)據(jù)應該連續(xù)存儲在磁盤上，以減少磁頭移動的次數(shù)，從而提高數(shù)據(jù)讀取效率。然而，隨著BLOB數(shù)據(jù)量的增加，找到足夠大的連續(xù)空間可能會變得困難。
鏈表存儲： 當無法找到足夠的連續(xù)空間時，BLOB數(shù)據(jù)可能被分割并存儲在磁盤的多個不連續(xù)塊中，這些塊通過鏈表連接起來。這種方式雖然解決了空間分配的問題，但可能會增加數(shù)據(jù)檢索時的磁盤I/O操作次數(shù)，降低性能。
多磁盤存儲： 對于非常大的BLOB數(shù)據(jù)，可以考慮將其分布在多個磁盤上。這樣，當進行數(shù)據(jù)檢索時，可以并行地從多個磁盤讀取數(shù)據(jù)塊，顯著提高讀取速度。這種方法特別適用于需要實時處理大量數(shù)據(jù)的場景，如視頻流服務。
按需傳輸： 數(shù)據(jù)庫系統(tǒng)可以根據(jù)客戶端的播放速度實時地傳輸BLOB數(shù)據(jù)塊，而無需等待整個文件完全加載。這種方式極大地減少了延遲，提高了用戶體驗。

2.7.6列存儲

列存儲（Column-Oriented Storage）是一種數(shù)據(jù)庫存儲技術(shù)，與傳統(tǒng)的行存儲（Row-Oriented Storage）方式相對。在列存儲中，數(shù)據(jù)庫表中的數(shù)據(jù)不是按行存儲，而是按列存儲。
列存儲的優(yōu)勢：
數(shù)據(jù)壓縮： 由于同一列中的數(shù)據(jù)通常具有相似的數(shù)據(jù)類型和值域，因此可以實現(xiàn)高效的數(shù)據(jù)壓縮。例如，在性別（gender）列中，如果只有“男”和“女”兩種值，則可以使用非常少的位來表示每個值，從而大大減少存儲需求。
更快的查詢速度： 當查詢只涉及表中的少數(shù)幾列時，列存儲數(shù)據(jù)庫可以只讀取這些列的數(shù)據(jù)，而無需讀取整行數(shù)據(jù)。這減少了I/O操作的數(shù)量，從而提高了查詢速度。
更好的緩存利用率： 由于相同列的數(shù)據(jù)在物理上連續(xù)存儲，因此它們更有可能被緩存在一起。這提高了緩存的利用率，因為一旦某個列的數(shù)據(jù)被讀入緩存，后續(xù)對該列的查詢就可以直接從緩存中獲取數(shù)據(jù)。
更高效的聚合操作： 列存儲特別適合于執(zhí)行聚合操作（如SUM、AVG、COUNT等），因為相同列的數(shù)據(jù)已經(jīng)聚集在一起，可以直接進行計算而無需跨行訪問。

2.8 記錄的修改

2.8.1 插入

定位塊->檢查空間->空間足夠->滑動記錄->更新偏移量表->插入新記錄->添加新指針(可以通過偏移量表來訪問它了)

塊空間不夠插入新數(shù)據(jù)

1. 在“鄰近塊”中找空間

步驟：
找到邏輯上或物理上緊隨塊B的下一個塊（如塊B’）。
檢查塊B’是否有足夠的空間。
如果有，將塊B中最后一個記錄（或幾個記錄）移動到塊B’的開始位置，為新記錄騰出空間。
更新塊B和塊B’的偏移量表（如果使用）和任何必要的索引。
將新記錄插入到塊B的適當位置。
這種方法的好處是保持了記錄的物理順序，減少了數(shù)據(jù)碎片，但可能需要移動大量數(shù)據(jù)以騰出空間。

2. 創(chuàng)建一個溢出塊

當在鄰近塊中找不到足夠的空間時，或者為了優(yōu)化性能而減少數(shù)據(jù)移動，可以創(chuàng)建一個溢出塊來存儲那些在當前塊中無法容納的額外記錄。
步驟：
當塊B沒有足夠的空間時，創(chuàng)建一個新的溢出塊。
在塊B的首部（或某個預定義的位置）添加一個指針，指向這個溢出塊。
將原本應該插入到塊B但由于空間不足而無法存儲的記錄放入溢出塊中。
優(yōu)點：減少了因插入操作而需要移動的數(shù)據(jù)量
缺點：可能會增加查詢操作的復雜性，因為查詢可能需要遍歷多個溢出塊來找到所需的記錄。此外，過多的溢出塊還可能導致性能下降，因為需要讀取更多的磁盤塊來完成查詢。

2.8.2 刪除

刪除記錄并回收空間
如果記錄可以滑動，那么在刪除一條記錄后，可以將塊中的其他記錄向前滑動以填補被刪除記錄留下的空白。這樣可以使塊內(nèi)的空間更加緊湊，減少碎片。在使用偏移量表的情況下，刪除記錄后需要更新偏移量表中的指針。
如果記錄不能滑動，在塊首部維護一個可用空間列表。這個列表記錄了塊中所有可用的空間區(qū)域及其大小。當刪除一條記錄時，將該記錄所占用的空間區(qū)域添加到可用空間列表中。當需要插入新記錄時，可以從這個列表中查找合適的空間區(qū)域。

第三章：索引結(jié)構(gòu)

3.1 索引基礎(chǔ)結(jié)構(gòu)

索引：它以一個或多個字段的值為輸人并能快速地找出具有該值的記錄。
索引使我們只需查看所有可能記錄中的一小部分就能找到所需記錄。建立索引的字段(組合)稱為查找鍵。
稠密索引：為數(shù)據(jù)文件中的每個記錄都創(chuàng)建一個索引項。這種索引方式提供了最精確的位置信息，但會占用更多的存儲空間。
稀疏索引：不是為數(shù)據(jù)文件中的每個記錄都創(chuàng)建索引項，而是選擇性地為某些記錄（如每個數(shù)據(jù)塊的首個記錄）創(chuàng)建索引項。稀疏索引減少了索引文件的大小，但可能需要在檢索時執(zhí)行額外的步驟來定位具體的數(shù)據(jù)記錄。
主索引：也稱為聚集索引，它決定了數(shù)據(jù)文件中記錄的物理存儲順序。主索引能夠直接定位到數(shù)據(jù)文件中的記錄位置，因此查詢效率很高。在數(shù)據(jù)庫中，通常會在主鍵上建立主索引。
輔助索引（非聚集索引）：不決定數(shù)據(jù)記錄的物理存儲順序，僅提供查找鍵與數(shù)據(jù)記錄之間的邏輯關(guān)聯(lián)。輔助索引通常用于非主鍵列，以提高基于這些列的查詢效率。
順序文件：順序文件是對關(guān)系中的元組按主鍵進行排序而生成的文件。關(guān)系中的元組按照這個次序分布在多個數(shù)據(jù)塊中。

3.1.2 稠密索引

如果記錄是排好序的，我們就可以在記錄上建立稠密索引
它是這樣一系列存儲塊:塊中只存放記錄的鍵以及指向記錄本身的指針
存儲索引文件比存儲數(shù)據(jù)文件所需存儲塊要少得多。通過使用索引文件，我們每次査詢只用一次 I/0操作就能找到給定鍵值的記錄。

查找索引更快
1.索引塊數(shù)量通常比數(shù)據(jù)塊數(shù)量少。

索引塊數(shù)量通常比數(shù)據(jù)塊數(shù)量少的原因主要基于以下幾點：
鍵與記錄大小的差異：在數(shù)據(jù)庫中，一個記錄（record）通常包含多個字段，如姓名、地址、電話號碼等，這些字段合起來可能占用相當多的存儲空間。相比之下，索引中存儲的僅僅是鍵（key）以及指向記錄的指針（或地址）。鍵通常是記錄中的一個或幾個字段，因此其大小遠小于整個記錄。由于索引塊中只存儲鍵和指針，所以每個索引塊能夠存儲的索引項（即鍵和指針的組合）數(shù)量相對較多。
壓縮性：由于索引中的鍵通常是按順序存儲的，這允許數(shù)據(jù)在物理存儲上更加緊湊。此外，如果鍵的類型是固定的（如整數(shù)或固定長度的字符串），那么索引塊中的空間可以得到更有效的利用，因為不需要為每個鍵動態(tài)分配空間。
索引的稀疏性：索引不需要為數(shù)據(jù)集中的每個記錄都創(chuàng)建一個索引項。特別是在面對大量數(shù)據(jù)時，完全索引（即每個記錄都有一個索引項）可能會非常龐大且效率低下。相反，索引可以設計為稀疏的，即只在關(guān)鍵位置（如數(shù)據(jù)塊的起始處或特定間隔）創(chuàng)建索引項。這樣，索引文件就會比完全索引要小得多。
多層索引結(jié)構(gòu)：對于非常大的數(shù)據(jù)集，通常會采用多層索引結(jié)構(gòu)（如B樹、B+樹等）。在這些結(jié)構(gòu)中，最底層的索引塊（葉子節(jié)點）直接指向數(shù)據(jù)記錄，而更高層的索引塊則指向下一層的索引塊。這種多層結(jié)構(gòu)進一步減少了頂層索引塊的數(shù)量，因為每個上層索引塊能夠覆蓋多個下層索引塊或數(shù)據(jù)塊。

2.由于鍵被排序，我們可以使用二分查找法來查找K。若有幾個索引塊，我們只需查找log2^n 個塊。
3.索引文件可能足夠小，以至可以永久地存放在主存緩沖區(qū)中。要是這樣的話，查找鍵K時就只涉及主存訪問而不需執(zhí)行 I/0 操作。

3.1.3 稀疏索引

稀疏索引只為數(shù)據(jù)文件的每個存儲塊設一個鍵-指針對，它比稠密索引節(jié)省了更多的存儲空間，但查找給定值的記錄需更多的時間。
只有當數(shù)據(jù)文件是按照某個查找鍵排序時，在該查找鍵上建立的稀疏索引才能被使用，而稠密索引則可以應用在任何的査找鍵。

3.1.4 多級索引

3.1.5 輔助索引

有一個書架，上面放了很多書。這些書是按照某種順序（比如書名的字母順序）排列的，這個順序就是書的主索引，類似于數(shù)據(jù)庫中的聚簇索引。你按照這個順序找書會很快，因為書是按照這個順序擺放的。
但是，有時候你可能不想按照書名來找書，而是想按照作者名、出版年份或者書的主題來找。這時候，如果書架上沒有額外的標記或指示來幫助你快速找到這些書，你就會很費勁。
在數(shù)據(jù)庫中，這就是輔助索引的作用。輔助索引就像是書架上的標簽或指示牌，它們告訴你：“如果你想找作者名是XXX的書，可以去看這里；如果你想找出版年份是YYYY的書，可以去看那里?！?br /> 具體來說，輔助索引在數(shù)據(jù)庫中是一個額外的數(shù)據(jù)結(jié)構(gòu)，它存儲了表中某些列的值（比如作者名、出版年份等）以及這些值對應的行在表中的位置（通常是一個指向主鍵的指針，因為主鍵能夠唯一標識表中的每一行）。
當你根據(jù)非主鍵列（比如作者名）來查詢數(shù)據(jù)時，數(shù)據(jù)庫會使用輔助索引來快速定位到這些列的值對應的行。首先，數(shù)據(jù)庫在輔助索引中查找你指定的值（比如作者名），找到后，它會獲取到對應的行位置（比如主鍵值），然后再根據(jù)這個位置去聚簇索引中找到完整的行數(shù)據(jù)。
需要注意的是，雖然輔助索引可以提高查詢效率，但它們也會占用額外的存儲空間，并且在數(shù)據(jù)發(fā)生變化（如插入、刪除、更新）時，數(shù)據(jù)庫需要同時更新輔助索引，這可能會增加額外的維護成本。

**輔助索引總是稠密索引：**輔助索引的索引項與字段值的數(shù)量是相對應的，呈現(xiàn)出一種“稠密”的狀態(tài)。如果輔助索引是稀疏的，即只為字段的某些值建立索引項，那么就無法保證快速定位到所有相關(guān)的記錄。

3.1.7 輔助索引中的間接

每個查找鍵K有一個鍵-指針對，指針指向一個桶文件，該文件中存放K的桶。從這個位置開始，直到索引指向的下一個位置，其間指針指向索引鍵值為K的所有記錄。


輔助索引上使用間接層也有一個重要的好處:我們通常可以在不訪問數(shù)據(jù)文件記錄的前提下利用桶的指針來幫助回答一些查詢。特別是，當查詢有多個條件，而每個條件都有一個可用的輔助索引時，我們可以通過在主存中將指針集合求交來找到滿足所有條件的指針，然后只需要檢索交集中指針指向的記錄。這樣我們就節(jié)省了檢索滿足部分條件而非所有條件的記錄所需的 I/0開銷。
輔助索引求交集：

3.1.8 文檔檢索和倒排索引

傳統(tǒng)的數(shù)據(jù)庫索引：該索引的鍵是文檔ID，而值是文檔中出現(xiàn)的詞（或詞頻、位置等信息）。然
**倒排索引：**索引的鍵是文檔中出現(xiàn)的詞（或稱為“詞條”），而值則是包含該詞的文檔ID列表（或稱為“文檔集合”）。這樣，當我們想要查找包含某個特定詞的文檔時，就可以直接通過該詞作為鍵來查找對應的文檔ID列表，而無需遍歷所有文檔的索引項。
文檔檢索：

• 一個文檔可被看成是關(guān)系 Doc的元組。這個關(guān)系有很多的屬性，每個屬性對應于文檔可能出現(xiàn)的一個詞。每個屬性都是布爾型的–表明該詞在該文檔出現(xiàn)還是沒有出現(xiàn)。因此，這一關(guān)系模式可以被看作:

   Doc(hasCat，hasDog,...)<br />       其中 hasCat 取值為真當且僅當該文檔中至少出現(xiàn)一次“cat"這個詞。
  

• 關(guān)系 Doc 的每個屬性上都建有輔助索引。不過，我們不必費心為屬性值為FALSE的元組建索引項;相反，索引只會將我們帶到出現(xiàn)該詞的那些文檔。也就是說，索引中只有查找鍵值為 TRUE的索引項。

• 我們不是給每個屬性(即每個詞)建立一個單獨的索引，而是把所有的索引合成一個，稱為倒排索引。這個索引使用間接桶來提高空間利用率，正如3.1.7節(jié)中討論的那樣。

桶文件中指針可以是:
1.指向文檔本身的指針。
2.指向詞的一個出現(xiàn)的指針。在這種情況下，指針可以是由文檔的第一個塊和一個表示該詞在文檔中出現(xiàn)次數(shù)的整數(shù)構(gòu)成的對。

當我們使用指針“桶”指向每個詞的多次出現(xiàn)的時候，我們可能就會想擴展這個想法，使桶數(shù)組包含更多有關(guān)詞的出現(xiàn)的信息。這樣，桶文件本身就成了有重要結(jié)構(gòu)的記錄集合。

3.2 B-樹

B-樹能自動地保持與數(shù)據(jù)文件大小相適應的索引層次。
對所使用的存儲塊空間進行管理，使每個塊的充滿程度在半滿與全滿之間。

3.2.1 B-樹的結(jié)構(gòu)

一顆m階的B樹定義如下：
1）每個結(jié)點最多有m-1個關(guān)鍵字。
2）根結(jié)點最少可以只有1個關(guān)鍵字。
3）非根結(jié)點至少有Math.ceil(m/2)-1個關(guān)鍵字。（（m/2）向上取整減去1）
4）每個結(jié)點中的關(guān)鍵字都按照從小到大的順序排列，每個關(guān)鍵字的左子樹中的所有關(guān)鍵字都小于它，而右子樹中的所有關(guān)鍵字都大于它。
5）所有葉子結(jié)點都位于同一層，或者說根結(jié)點到每個葉子結(jié)點的長度都相同。

3.2.2 B-樹的應用

B-樹是用來建立索引的一種強有力的工具。它的葉結(jié)點上指向記錄的一系列指針可以起到任何一種索引文件中指針序列的作用。

3.2.5 B-樹的插入

1、插入一個元素時，首先在B樹中是否存在，如果不存在，即比較大小尋找插入位置，在葉子結(jié)點處結(jié)束，然后在葉子結(jié)點中插入該新的元素
2、如果葉子結(jié)點空間足夠，這里需要向右移動該葉子結(jié)點中大于新插入關(guān)鍵字的元素，如果空間滿了以致沒有足夠的空間去添加新的元素，則將該結(jié)點進行“分裂”，將一半數(shù)量的關(guān)鍵字元素分裂到新的其相鄰右結(jié)點中，中間關(guān)鍵字元素上移到父結(jié)點中（當然，如果父結(jié)點空間滿了，也同樣需要“分裂”操作）
3、當結(jié)點中關(guān)鍵元素向右移動了，相關(guān)的指針也需要向右移。如果在根結(jié)點插入新元素，空間滿了，則進行分裂操作，這樣原來的根結(jié)點中的中間關(guān)鍵字元素向上移動到新的根結(jié)點中，因此導致樹的高度增加一層。

3.2.6 B-樹的刪除

1）如果當前需要刪除的key位于非葉子結(jié)點上，則用后繼key（這里的后繼key均指后繼記錄的意思）覆蓋要刪除的key，然后在后繼key所在的子支中刪除該后繼key。此時后繼key一定位于葉子結(jié)點上，這個過程和二叉搜索樹刪除結(jié)點的方式類似。刪除這個記錄后執(zhí)行第2步
2）該結(jié)點key個數(shù)大于等于Math.ceil(m/2)-1，結(jié)束刪除操作，否則執(zhí)行第3步。
3）如果兄弟結(jié)點key個數(shù)小于Math.ceil(m/2)-1，則父結(jié)點中的key下移到該結(jié)點，兄弟結(jié)點中的一個key上移，刪除操作結(jié)束。
否則，將父結(jié)點中的key下移與當前結(jié)點及它的兄弟結(jié)點中的key合并，形成一個新的結(jié)點。原父結(jié)點中的key的兩個孩子指針就變成了一個孩子指針，指向這個新結(jié)點。然后當前結(jié)點的指針指向父結(jié)點，重復上第2步。
有些結(jié)點它可能即有左兄弟，又有右兄弟，那么我們?nèi)我膺x擇一個兄弟結(jié)點進行操作即可。

刪除27。從上圖可知27位于非葉子結(jié)點中，所以用27的后繼替換它。從圖中可以看出，27的后繼為28，我們用28替換27，然后在28（原27）的右孩子結(jié)點中刪除28。刪除后的結(jié)果如下圖所示。

刪除后發(fā)現(xiàn)，當前葉子結(jié)點的記錄的個數(shù)小于2，而它的兄弟結(jié)點中有3個記錄（當前結(jié)點還有一個右兄弟，選擇右兄弟就會出現(xiàn)合并結(jié)點的情況，不論選哪一個都行，只是最后B樹的形態(tài)會不一樣而已），我們可以從兄弟結(jié)點中借取一個key。所以父結(jié)點中的28下移，兄弟結(jié)點中的26上移,刪除結(jié)束。結(jié)果如下圖所示。

3.2.7 B-樹的效率

B-樹的效率：磁盤I/O次數(shù)、樹的層數(shù)、節(jié)點的分裂與合并、以及針對查找、插入和刪除操作的優(yōu)化。
磁盤I/O次數(shù)
B-樹的主要優(yōu)勢之一是它減少了磁盤I/O次數(shù)，這是因為它通過保持樹的高度盡可能低來實現(xiàn)。在B-樹中，每個節(jié)點可以包含多個鍵和子指針，這允許樹在保持相同數(shù)量元素的情況下具有更少的層數(shù)。對于大多數(shù)數(shù)據(jù)庫和文件系統(tǒng)應用，三層B-樹足以滿足需求，因為節(jié)點容量（如每塊340個鍵-指針對）可以非常大，這取決于塊的大小和鍵的大小。
樹的層數(shù)
B-樹的層數(shù)決定了查找記錄所需的最大磁盤I/O次數(shù)。在三層B-樹中，最多需要三次磁盤I/O（從根到葉節(jié)點，加上一次讀取數(shù)據(jù)記錄本身）。然而，通過緩存技術(shù)（如將根節(jié)點或某些中間節(jié)點常駐內(nèi)存），這個次數(shù)可以進一步減少。例如，如果根節(jié)點被緩存，那么查找將只需要兩次磁盤I/O。
節(jié)點的分裂與合并
在B-樹中，節(jié)點的分裂和合并是罕見的，特別是當節(jié)點容量足夠大時。當節(jié)點需要分裂時，大多數(shù)操作都局限于葉節(jié)點，這減少了對樹結(jié)構(gòu)整體的影響。此外，分裂和合并操作通常只涉及兩個節(jié)點（一個要被分裂的節(jié)點和一個新的或已有的節(jié)點）以及它們的父節(jié)點，這進一步限制了操作的復雜性。
插入和刪除
插入和刪除操作可能需要額外的磁盤I/O來更新數(shù)據(jù)記錄和索引本身。然而，通過適當?shù)鼐S護B-樹的平衡（如通過旋轉(zhuǎn)和重新分布節(jié)點中的鍵），可以最小化這些操作的影響。在某些實現(xiàn)中，如果刪除操作導致節(jié)點中的鍵數(shù)低于最小要求，但預計該節(jié)點很快會再次填滿，那么可能不對該節(jié)點進行合并或重新分配鍵，而是簡單地留下該節(jié)點。
刪除標記
在處理刪除操作時，一種常見的策略是使用“刪除標記”而不是實際從B-樹中刪除條目。這樣做的好處是，即使記錄已從數(shù)據(jù)庫中刪除，B-樹索引仍然可以保留對該記錄的引用（盡管它已被標記為刪除）。這有助于維護索引的完整性，并允許通過B-樹索引查詢已刪除記錄的狀態(tài)（例如，檢查記錄是否已被刪除）。

3.3 散列表

散列函數(shù)：散列函數(shù) ( h ) 接受一個查找鍵（Key）作為輸入，并計算出一個介于 0 到 ( B-1 ) 之間的整數(shù)，其中 ( B ) 是桶（Bucket）的數(shù)目。
桶：桶是散列表中用于存儲數(shù)據(jù)的單元。每個桶可以存儲多個數(shù)據(jù)項，通常使用鏈表來實現(xiàn)。桶數(shù)組是一個序號從 0 到 ( B-1 ) 的數(shù)組，每個數(shù)組元素對應一個桶。
存儲：當需要存儲一個記錄時，首先計算其查找鍵 ( K ) 的散列值 ( h(K) )。然后將該記錄鏈接到桶號為 ( h(K) ) 的桶表中。

3.3.1 輔存散列表

有的散列表包含大量記錄，記錄如此之多，以至于它們主要存放在輔助存儲器上，這樣的散列表在一些細小而重要的方面與主存中的散列表存在區(qū)別

3.3.2 散列表的插入

查找鍵為K的新記錄需要被插入時，計算h(K)。
如果桶號為h(K)的桶還有空間，我們就把該記錄存放到此桶的存儲塊中。
其存儲塊沒有空間時存儲到塊鏈上的某個溢出塊中
如果桶的所有存儲塊都沒有空間:我們就增加一個新的溢出塊到該桶的鏈上。

3.3.5 可擴展散列表

它在簡單的靜態(tài)散列表結(jié)構(gòu)上主要增加了:
1.為桶引人了一個間接層，即用一個指向塊的指針數(shù)組來表示桶，而不是用數(shù)據(jù)塊本身組
成的數(shù)組來表示桶。
2.指針數(shù)組能增長，它的長度總是2的冪，因而數(shù)組每增長一次，桶的數(shù)目就翻倍。
3.并非每個桶都有一個數(shù)據(jù)塊;如果某些桶中的所有記錄可以放在一個塊中，那么
這些桶可能共享一個塊。
4.散列函數(shù)h為每個鍵計算出一個K位二進制序列，該K足夠大，比如32。但是，桶的數(shù)目總是使用從序列第一位或最后一位算起的若干位，此位數(shù)小于K，比如說是i位。也就是說，當i是使用的位數(shù)時，桶數(shù)組將有2^i個項。

3.3.6 可擴展散列表的插入
計算哈希值：首先，計算要插入的鍵的哈希值 h(K)。
定位桶數(shù)組項：使用哈希值 h(K) 的前 i 位來確定桶數(shù)組中的項。這里的 i 是當前用于索引桶數(shù)組的全局位數(shù)（global bit position）。
檢查存儲塊空間：如果找到的存儲塊（B）有足夠的空間來存放新記錄，則直接插入新記錄。
如果存儲塊已滿（即沒有空間），則需要進行分裂或桶數(shù)組擴展。
處理存儲塊滿的情況：
如果 j < i：

將存儲塊 B 分裂成兩個新的存儲塊。
根據(jù)新記錄的哈希值的第 (j+1) 位來決定其歸屬的存儲塊（0 或 1）。
更新存儲塊的小方塊中的位數(shù)為 (j+1)，表示現(xiàn)在使用更多的位來確定存儲塊的成員資格。
調(diào)整桶數(shù)組中的指針，根據(jù)新記錄的哈希值的第 (j+1) 位來指向正確的存儲塊。
如果分裂后仍然有存儲塊過滿，則繼續(xù)以更高的 j 值重復分裂過程。

如果 j = i：

桶數(shù)組的長度翻倍，并創(chuàng)建一個新的桶數(shù)組。
對于舊桶數(shù)組中的每個項 w，在新桶數(shù)組中創(chuàng)建兩個項 u0 和 u1（分別通過在 w 后面添加 0 和 1 來獲得）。這兩個新項都指向原 w 項指向的存儲塊。
然后，像 j < i 的情況一樣，分裂過滿的存儲塊。

3.3.7 線性散列表

可擴展散列缺點：
1.當桶數(shù)組需要翻倍時，要花費很長的時間。
2.當桶數(shù)翻倍后，它在主存中可能就裝不下了，或者把其他的一些我們需要保存在主存的數(shù)據(jù)擠出去。其結(jié)果是，一個運行良好的系統(tǒng)可能突然之間每個操作所需磁盤I/O開始大增。
3.如果每塊的記錄數(shù)很少，那么很有可能某一塊的分裂比在邏輯上講需要分裂的時間提前許多。
線性散列解決其缺點

• 桶數(shù)n的選擇總是使存儲塊的平均記錄數(shù)保持與存儲塊所能容納的記錄總數(shù)成一個固定的比例，如 80%。
• 由于存儲塊并不總是可以分裂，所以允許有溢出塊，盡管每個桶的平均溢出塊數(shù)遠小于1。
• 用來作桶數(shù)組項序號的二進制位數(shù)是1og2^n向上取整，其中n是當前的桶數(shù)。這些位總是從散列函數(shù)得到的位序列的右(低位)端開始取。
• 假定散列函數(shù)值的i位正在用來給桶數(shù)組項編號，且有一個鍵值為K的記錄想要插人到編號為 a,…a; 的桶中;即 a,…a 是h(K)的后i位。那么,把 a,a,…a;當作二進制整數(shù)，設它為 m。如果m<n，那么編號為m的桶存在并把記錄存入該桶中。如果 n≤m<2^{i那么m桶還不存在，因此我們把記錄存人桶m-2}(i-1)，也就是當我們把a1(它肯定是1)改為0時對應的桶。
  

3.3.8 線性散列表的插入

確定桶號：
使用哈希函數(shù) h(K) 計算鍵 K 的哈希值。
取 h(K) 序列末尾的 i 位來表示桶號 m。這里，i 是一個與當前散列表容量相關(guān)的參數(shù)，可能基于 n（當前桶的數(shù)量）的某種屬性（如 log2(n) 的整數(shù)部分，但具體取決于實現(xiàn)）。
如果 m < n，則直接將記錄插入到桶 m 中。
如果 m ≥ n，則通過 (m - 2^(i-1)) % n來計算實際的桶號，并插入記錄。
處理溢出：
如果桶已滿，則創(chuàng)建一個新的溢出塊（如鏈表節(jié)點），將新記錄存入該節(jié)點，并將此節(jié)點鏈接到桶的尾部。
動態(tài)擴容和桶分裂：
每次插入后，檢查當前記錄總數(shù)與 n 的比例是否超過了某個閾值 r/n。
如果超過，則增加散列表的容量（即增加桶的數(shù)量），并可能需要重新組織或分裂某些桶。
如果新增加的桶號的二進制表示為 1aa…a，則分裂桶號為 0aa…a 的桶。這通常意味著根據(jù)記錄的后 i 位值（特別是從右數(shù)起的第 i 位）來重新分配記錄到兩個桶中。
i 值的調(diào)整：
當 n 超過 2^i 時，i+1。

3.4 多維索引

3.4.2 利用傳統(tǒng)索引執(zhí)行范圍查詢

在處理二維范圍查詢時，盡管分別為x和y坐標構(gòu)建一維B-樹索引可以高效定位單維度范圍內(nèi)的記錄，但將它們用于二維查詢時效率較低。因為即使每維索引能減少候選記錄數(shù)量，交集操作后仍需訪問大量數(shù)據(jù)塊，導致磁盤I/O成本高昂。因此，在處理多維數(shù)據(jù)時，考慮使用如R樹等多維索引結(jié)構(gòu)以更直接地定位滿足多維查詢條件的記錄，從而提高查詢性能。

3.4.1 多維索引應用

1.部分匹配查詢。我們指定一維或多維上的值并查找在這些維上匹配這些值的所有點。
2.范國查詢。我們給出一維或多維上的范圍并查找在這些范圍內(nèi)點的集合，或者在所表示的是形狀時，查找出部分或全部形狀在該范圍內(nèi)的形狀的集合。
3.最近鄰查詢。我們查找與給定點最近的點。
4.where-am-查詢。已知一個點，我們想知道該點所處的形狀，若存在這樣的形狀的話。一個熟悉的例子是當你點擊鼠標時，系統(tǒng)決定你點擊的是哪個顯示元素。

3.4.2傳統(tǒng)索引進行范圍查詢

首先我們通過x的B-樹索引得到在x范圍內(nèi)的所有記錄的指針。然后，我們通過y的B-樹索引得到在y范圍內(nèi)的所有記錄的指針。最后求出這些指針的交集。I/O次數(shù)多。

3.5 多維數(shù)據(jù)的散列結(jié)構(gòu)

3.5.1 網(wǎng)格文件

網(wǎng)格文件（Grid File）是一種用于多維數(shù)據(jù)索引的高效數(shù)據(jù)結(jié)構(gòu)，它通過在各維度上劃分空間為網(wǎng)格狀區(qū)域，顯著提升了多維數(shù)據(jù)查詢的性能。這種劃分允許將數(shù)據(jù)集劃分為多個子空間（或“條狀”），其中每個子空間由網(wǎng)格線界定，且網(wǎng)格線的數(shù)量和間隔在不同維度上可靈活設置，甚至在同一維度內(nèi)也可不同，從而實現(xiàn)了對多維數(shù)據(jù)的高效索引和查詢處理。

3.5.2 網(wǎng)格文件的查找

空間劃分成的每一個區(qū)域可以被看成是散列表的一個桶，落人該區(qū)域的每個點的記錄都存放在屬于該桶的塊中。如有必要，溢出塊可以用來增加桶的大小。
與傳統(tǒng)散列表中使用的一維桶數(shù)組不同，網(wǎng)格文件使用的桶數(shù)組的維數(shù)與數(shù)據(jù)文件的維數(shù)一樣。

3.5.3 網(wǎng)格文件的插入

我們遵循查找記錄的過程并把新記錄放到查找到的桶中。如果在該桶中的塊有空間，那就不需要做更多的事。如果在桶中沒有空間，通常有兩種方法解決這個問題:
1.按需要給桶增加溢出塊。
2.通過增加或移動網(wǎng)格線來重組結(jié)構(gòu)。這種方法類似于3.3節(jié)討論的動態(tài)散列技術(shù)，但這里還有別的問題，因為在一個維上桶的內(nèi)容是相互關(guān)聯(lián)的。也就是說，增加一條網(wǎng)格線將分裂沿該線的所有桶。因此，要選擇一條對所有桶都最優(yōu)的網(wǎng)格線也許是不可能的。例如，要是一個太大，我們也許不知是該選擇對維分裂還是對點分裂，并且不會造成許多的空桶或使某些桶太滿。

3.6 多維數(shù)據(jù)的樹結(jié)構(gòu)

1.多鍵索引。
2. kd-樹。
3.四叉樹。
4.R-樹。
前三種用于點集。R-樹通常用來表示區(qū)域的集合，它也可用來表示點集。

3.6.1 多鍵索引

假若我們有幾個屬性來表示我們的數(shù)據(jù)點的維，并且我們想在這些點上支持范圍查詢或最近鄰查詢。用來訪問這些點的一個簡單的樹模式是索引的索引，或者用更一般的話來說，是一棵樹，它的每一層的結(jié)點都是一個屬性的索引。
這種想法如圖 所示，這是兩個屬性的情況,“樹根”是兩個屬性中第一個屬性的索引，它可以是任何類型的常規(guī)索引，如B-樹或散列表。該索引把每一個索引鍵值–即第一個屬性的值–同指向另一個索引的指針相關(guān)聯(lián)。如果V是第一個屬性的一個值，那么通過鍵值V和它的指針找到的索引是一個指向這些點集的索引，這些點的第一個屬性值是V而第二個屬性為任意值。

3.6.3 kd-樹

kd-樹(k維搜索樹)是把二叉搜索樹推廣到多維數(shù)據(jù)的一種主存數(shù)據(jù)結(jié)構(gòu)。我們將先介紹這種思想，然后討論怎樣使這種思想適合存儲的塊模型。kd-樹是一個二叉樹，它的內(nèi)部結(jié)點有一個相關(guān)聯(lián)的屬性a和一個值V，它將數(shù)據(jù)點集分成兩個部分:a值小于V的部分和a值大于等于V的部分。由于所有維的屬性在層間交替出現(xiàn)，所以樹的不同層上的屬性是不同的。在一般的 kd-樹中，數(shù)據(jù)點被存放在結(jié)點內(nèi)，就像在二叉搜索樹中一樣。不過我們在開始引人這個思想時做了兩個修改，以便獲得塊模式的有限益處:
1.內(nèi)部結(jié)點只有一個屬性，該屬性的一個劃分值和指向左、右子樹的指針。
2.葉結(jié)點是塊，塊空間中存放著盡可能多的記錄。

在kd-樹中查找一個所有維都給定值的元組類似于在二叉搜索樹中查找一個值。從根節(jié)點開始，根據(jù)當前節(jié)點的劃分維度和查詢點的對應維度值決定是向左子樹還是向右子樹遞歸查找，直到達到葉節(jié)點。如果葉節(jié)點中包含查詢點，則查找成功；否則，查找失敗。

3.6.4 kd-樹的操作

插入操作
1. 查找過程：首先，執(zhí)行一個類似于查找的過程，以確定新數(shù)據(jù)點應該插入的位置。這將引導我們到一個葉節(jié)點。
2. 空間檢查：如果葉節(jié)點的塊中還有空間（即未達到最大容量限制），則直接將新數(shù)據(jù)點放入該塊中。
3. 分裂操作：如果葉節(jié)點的塊已滿，則需要進行分裂操作。選擇當前節(jié)點的劃分維度作為分裂維度，并根據(jù)該維度上的中位數(shù)（或其他合適的值）將節(jié)點中的點分為兩部分，創(chuàng)建兩個新的子節(jié)點。
4. 創(chuàng)建新節(jié)點：然后，創(chuàng)建一個新的內(nèi)部節(jié)點，其左右子節(jié)點指向這兩個新創(chuàng)建的子節(jié)點，并設置該內(nèi)部節(jié)點的劃分值為分裂時使用的值。
范圍查詢
在范圍查詢中，我們可能需要根據(jù)多個維度上的范圍來查找數(shù)據(jù)點。例如，查找年齡在35到55之間且薪水在8100K至200K之間的所有點。
1. 從根節(jié)點開始：根據(jù)根節(jié)點的劃分維度（假設是薪水）和查詢范圍，確定是否進入左子樹、右子樹或兩者都進入。
2. 遞歸查詢：在每個子節(jié)點上重復上述過程，根據(jù)當前節(jié)點的劃分維度和查詢范圍來決定搜索路徑。
3. 收集結(jié)果：當達到葉節(jié)點時，檢查該節(jié)點中的點是否滿足查詢條件，并將滿足條件的點添加到結(jié)果集中。
4. 回溯：在回溯過程中，繼續(xù)檢查其他可能包含滿足條件點的子樹。

3.6.5 使 kd-樹適合輔助存儲器

為了提高kd-樹在輔助存儲器（如磁盤）上的效率，可以通過內(nèi)部結(jié)點的多分支和聚集內(nèi)部結(jié)點到塊這兩種方法來解決長路徑和未用空間的問題。多分支使得內(nèi)部結(jié)點能夠管理更多的鍵和指針，減少樹的高度；而聚集內(nèi)部結(jié)點到塊則通過減少磁盤I/O次數(shù)來優(yōu)化性能，因為一次磁盤訪問可以處理多個內(nèi)部結(jié)點。這兩種方法共同作用，能夠顯著提升kd-樹在處理大規(guī)模數(shù)據(jù)集時的效率。

3.6.7 R-樹

R-樹(區(qū)域樹)是一種利用B-樹的某些本質(zhì)特征來處理多維數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。B-樹的結(jié)點有一個鍵的集合，這些鍵把線分成片段，沿著那條線的每個點僅屬于一個片段，B-樹因此使我們很容易地找到點。如果我們把沿線各處的點表示成B-樹結(jié)點我們就能夠確定點所屬的唯一子結(jié)點，在那里可以找到該點。
而R-樹表示由二維或更高維區(qū)域組成的數(shù)據(jù)，我們把它稱為數(shù)據(jù)區(qū)。R-樹的一個內(nèi)部結(jié)點對應于某個內(nèi)部區(qū)域，或稱“區(qū)域”，它不是普通的數(shù)據(jù)區(qū)。原則上，區(qū)域可以是任何形狀雖然實際上它經(jīng)常為矩形或其他簡單形狀。R-樹的結(jié)點的鍵位置上含有子區(qū)域，它表示結(jié)點的子結(jié)點的內(nèi)容。允許子區(qū)域有部分重疊，盡管我們希望重疊較小。

3.7 位圖索引

二進制的位數(shù)代表總共有多少數(shù)據(jù)，哪個數(shù)據(jù)中包含25，對應位為1。
第2,8個數(shù)據(jù)是25，所以25的向量為：100000001000

第四章：查詢執(zhí)行

查詢編譯預覽

查詢分析（Analysis）
目的：將輸入的查詢語句（如SQL查詢）轉(zhuǎn)換成一種中間表示形式，即分析樹（Parse Tree）或抽象語法樹（AST）。這個樹形結(jié)構(gòu)表示了查詢的語法結(jié)構(gòu)，但尚未考慮查詢的邏輯或物理執(zhí)行方式。
過程：詞法分析器（Lexer）將查詢語句分解成一系列的詞法單元（tokens），如關(guān)鍵字、標識符、常量等；然后語法分析器（Parser）根據(jù)這些詞法單元構(gòu)建出分析樹。
查詢重寫（Query Rewriting）
目的：將分析樹轉(zhuǎn)換為初始查詢計劃，這個計劃通常以查詢的代數(shù)表達式（如關(guān)系代數(shù)表達式）的形式表示。之后，這個初始計劃會被進一步優(yōu)化，以產(chǎn)生一個預期執(zhí)行時間更短的等價查詢計劃。
過程：
邏輯優(yōu)化：包括規(guī)則如謂詞下推（Pushdown Predicates）、視圖重寫（View Rewriting）、選擇投影合并（Select-Project Merge）等，以減少計算量或避免不必要的數(shù)據(jù)訪問。
等價變換：尋找查詢的代數(shù)等價形式，這些形式可能在執(zhí)行時更高效。
物理計劃生成（Physical Plan Generation）
目的：將邏輯查詢計劃轉(zhuǎn)換為物理查詢計劃，這包括為每個邏輯操作符選擇具體的實現(xiàn)算法（如哈希連接、嵌套循環(huán)連接等），并決定這些操作符的執(zhí)行順序。
過程：
操作符選擇：為每個邏輯操作符（如選擇、投影、連接等）選擇最合適的物理實現(xiàn)算法。
執(zhí)行順序確定：根據(jù)數(shù)據(jù)分布、索引可用性等因素，確定操作符的最佳執(zhí)行順序。
數(shù)據(jù)傳輸策略：決定數(shù)據(jù)如何在操作之間傳輸，包括是否使用流水線（Pipeline）、內(nèi)存緩沖區(qū)或磁盤等。

4.1 物理查詢計劃操作符介紹

4.1.1 掃描表

1. 表掃描（Table Scan）
表掃描是最直接的讀取數(shù)據(jù)方式，它遍歷表中存儲的所有數(shù)據(jù)塊，讀取并檢查每個元組（行）以找出滿足查詢條件的那些。這種方式的效率通常較低，特別是在處理大型表或只有少數(shù)元組滿足查詢條件時。然而，在以下情況下，表掃描可能是必要的或最優(yōu)的：
表中數(shù)據(jù)量很小。
沒有合適的索引可以利用，或者索引的使用成本（如索引維護開銷）超過了直接掃描表的成本。
查詢條件涉及非索引列或復雜計算，使得索引無法有效減少搜索空間。
2. 索引掃描（Index Scan）
索引掃描利用索引來快速定位滿足查詢條件的元組。索引是數(shù)據(jù)庫管理系統(tǒng)用于提高數(shù)據(jù)檢索效率的數(shù)據(jù)結(jié)構(gòu)，它存儲了表中某些列（或列的組合）的值以及這些值對應的元組在表中的位置信息。通過索引，數(shù)據(jù)庫系統(tǒng)可以快速縮小搜索范圍，只檢查那些可能包含所需數(shù)據(jù)的塊或頁。索引掃描可以分為幾種類型：
全索引掃描：遍歷索引中的所有條目，但這通常比表掃描要快，因為索引通常比表小得多。
范圍索引掃描：在索引中查找一個范圍內(nèi)的條目。
唯一索引掃描：當索引是唯一的，并且查詢條件精確匹配索引中的一個值時，這種掃描非常高效。
索引掃描的優(yōu)勢在于其速度，尤其是在處理大型表時。然而，索引并非沒有成本。索引需要額外的存儲空間，并且在數(shù)據(jù)插入、刪除和更新時需要維護，這可能會降低這些操作的性能。

4.1.2 掃描表時的排序

在數(shù)據(jù)庫查詢處理中，排序是一個常見的操作，它可能由查詢中的ORDER BY子句直接觸發(fā)。
使用索引進行排序
如果排序所依據(jù)的屬性（如屬性a）上存在B-樹索引，或者關(guān)系本身就是按照該屬性的索引順序存儲的，那么可以直接通過索引掃描來獲取已經(jīng)排序好的數(shù)據(jù)。這種方法非常高效，因為它避免了額外的排序步驟，直接利用了索引的有序性。
內(nèi)存排序
如果關(guān)系R的大小足夠小，能夠完全裝入內(nèi)存，那么可以先通過表掃描或索引掃描獲取R的所有元組，然后在內(nèi)存中使用排序算法（如快速排序、歸并排序等）對它們進行排序。內(nèi)存排序的優(yōu)點是速度快，但缺點是當數(shù)據(jù)集很大時，可能無法全部裝入內(nèi)存，從而導致溢出到磁盤，影響性能。
多路歸并排序
當關(guān)系R太大，無法全部裝入內(nèi)存時，就需要采用外部排序的方法。多路歸并排序是外部排序的一種常用技術(shù)，它將關(guān)系R分成多個可以裝入內(nèi)存的部分（稱為“塊”或“段”），對每個部分在內(nèi)存中進行排序，然后將排序后的部分寫入到外部存儲（如磁盤）上。最后，使用多路歸并算法將這些排序后的部分合并成一個完整的有序關(guān)系。

4.1.4 衡量代價的參數(shù)

**B：**當描述一個關(guān)系R的大小時，絕大多數(shù)情況下，我們關(guān)心包含R的所有元組所需的塊的數(shù)目。這個塊的數(shù)目表示為B?。
**T：**有時候，我們也需要知道R中的元組的數(shù)目，我們將這個數(shù)量表示為T?。
**V：**最后，我們有時候希望參考出現(xiàn)在關(guān)系的一個列中的不同值的數(shù)目。如果R是一個關(guān)系，它的一個屬性是。那么V(R，a)是R中a對應列上不同值的數(shù)目。

4.1.6 實現(xiàn)物理操作符的迭代器

**1.0pen()。**這個方法啟動獲得元組的過程，但并不獲得元組。
**2.GetNext()。**這個方法返回結(jié)果中的下一個元組
3. Close()



/注意，如果S已消耗完，s.GetNext將會返回 NotFound，對 GetNext 來說這也是正確的動作

4.2 一趟算法

我們怎樣執(zhí)行邏輯查詢計劃中的每個單獨的步驟(例如，連接或選擇)?關(guān)于各種操作符已提出了很多算法，
我們可以將操作符算法按照難度和代價分成三種“等級”:
a)一些方法僅從磁盤讀取一次數(shù)據(jù)，這就是一趟(one-pass)算法。它們通常要求操作的至少一個操作對象能完全裝人內(nèi)存.
b)一些方法處理的數(shù)據(jù)量太大以至于不能裝入可利用的內(nèi)存，但又不是可想象的最大的數(shù)據(jù)集合。這些兩趟算法的特點是首先從磁盤讀一遍數(shù)據(jù)，用某種方式處理，將全部或絕大部分寫回磁盤，然后在第二趟中為了進一步處理，再讀一遍數(shù)據(jù)。
c)某些方法對處理的數(shù)據(jù)量沒有限制。這些方法用三趟或更多趟來完成工作，它們是對兩趟算法的自然的遞歸的推廣。
操作符分為三大類:
1.一次單個元組，一元操作。我們一次可以讀一個塊，使用內(nèi)存緩沖區(qū)，并產(chǎn)生我們的輸出。
2.整個關(guān)系，一元操作。這些單操作對象的操作需要一次從內(nèi)存中看到所有或大部分元組因此，一趟算法局限于大小約為M(內(nèi)存中可用緩沖區(qū)的數(shù)量)或更小的關(guān)系。
3.整個關(guān)系，二元操作。其他所有的操作可以歸為這一類:并、交、差、連接和積的集合形式以及包形式。我們將發(fā)現(xiàn)如果要用一趟算法，那么這類操作中的每一個都要求至少一個操作對象的大小限制在 M 以內(nèi)。

4.2.1一次單個元組操作的一趟算法

我們一次讀取R的一塊到輸人緩沖區(qū)，對每一個元組進行操作,并將選出的元組或投影得到的元組移至輸出緩沖區(qū)。
如果R是聚集的，代價就是B，如果R不是聚集的，代價就是T。

B：包含R的所有元組所需的塊的數(shù)目。這個塊的數(shù)目表示為B?。
T：R中的元組的數(shù)目，我們將這個數(shù)量表示為T?。

4.2.2 整個關(guān)系的一元操作的一趟算法

一元操作（消除重復，分組）
消除重復
一次一個地讀取R的每一塊，但是對每一個元組，我們需要判定:
1.這是我們第一次看到這個元組，這時將它復制到輸出。
2.我們從前見過這個元組，這時不必輸出它。
為支持這個判定，我們需要為見過的每一個元組在內(nèi)存中保存一個備份。用一個內(nèi)存緩沖區(qū)保存R的元組的一個塊，其余的M-1個緩沖區(qū)可以用來保存目前為止我們見過的每個元組的一個副本。

分組

• 對 MIN(a)或MAX(a)聚集來說，分別記錄組內(nèi)迄今為止見到的任意元組在屬性a上的最小或最大值。每當見到組中的一個元組時，如果合適，就改變這個最小值或最大值。
• 對于任意 COUNT聚集來說，為組中見到的每個元組加1。
• 對SUM(a)來說，如果a不為NULL的話，在它的組里掃描到的累加值上增加屬性a的值。
• AVG(a)的情況復雜。我們必須保持兩個累計值:組內(nèi)元組個數(shù)以及這些元組在a上的值的和。二者的計算分別與我們?yōu)镃OUNT和SUM聚集所做的一樣。當R中所有元組都被掃描后，我們計算總和和個數(shù)的商以得到平均值。
  

4.2.3 二元操作的一趟算法（并、交、差、積和連接）

B：包 S：集合
1. 集合并（Union）
操作：合并兩個集合S和R中的所有不重復元素。
實現(xiàn)：將S讀入內(nèi)存并使用查找結(jié)構(gòu)（如哈希表）存儲，然后遍歷R的每一塊，對于R中的每個元素，如果它不在S中，則將其復制到輸出。
2. 集合交（Intersection）
操作：找出同時存在于S和R中的元素。
實現(xiàn)：同樣將S讀入內(nèi)存并使用查找結(jié)構(gòu)，然后遍歷R的每一塊，對于R中的每個元素，如果它也在S中，則將其復制到輸出。
3. 集合差（Difference）
操作：找出存在于S但不在R中的元素（S-R），或存在于R但不在S中的元素（R-S）。
實現(xiàn)：對于S-R，遍歷R并刪除S中與R相同的元素，最后輸出S中剩余的元素。對于R-S，遍歷R并僅輸出不在S中的元素。
4. 包交（Bag Intersection）
操作：類似于集合交，但保留元素出現(xiàn)的次數(shù)。
實現(xiàn)：為S中的每個元素維護一個計數(shù)，遍歷R時，如果元素在S中存在且計數(shù)大于0，則輸出該元素并減少計數(shù)。
5. 包差（Bag Difference）
操作：類似于集合差，但保留元素出現(xiàn)的次數(shù)。
實現(xiàn)：對于S-R，遍歷R并減少S中對應元素的計數(shù)，最后輸出計數(shù)大于0的元素及其剩余次數(shù)。對于R-S，遍歷R，如果元素不在S中或S中計數(shù)為0，則輸出元素（可能帶計數(shù)）。
6. 積（Cartesian Product）
操作：將S和R中的每個元素組合起來。
實現(xiàn)：將S讀入內(nèi)存，然后遍歷R的每一塊，將R中的每個元素與S中的每個元素組合后輸出。
7. 自然連接（Natural Join）
操作：基于兩個關(guān)系的公共屬性連接它們。
實現(xiàn)：將S讀入內(nèi)存并使用公共屬性作為查找鍵構(gòu)建查找結(jié)構(gòu)，然后遍歷R的每一塊，對于R中的每個元素，使用查找結(jié)構(gòu)找到S中與之匹配的元素，并輸出連接后的結(jié)果。

4.3 嵌套循環(huán)連接

4.3.1 基于元組的嵌套循環(huán)連接

如果我們不注意關(guān)系R和S的塊的緩沖方法，那么這種算法需要的磁盤I/0可能多達T?T(S)。
當我們可以使用R的連接屬性上的索引來查找與給定的8元組匹配的R元組時，這樣的匹配不必讀取整個關(guān)系R。
執(zhí)行內(nèi)層循環(huán)時，要盡可能多地使用內(nèi)存，以減少磁盤0的數(shù)目。

4.3.3 基于塊的嵌套循環(huán)連接算法

1.對作為操作對象的兩個關(guān)系的訪問均按塊組織。
2.使用盡可能多的內(nèi)存來存儲屬于關(guān)系S的元組，S是外層循環(huán)中的關(guān)系。
第1點確保了當在內(nèi)層循環(huán)中處理關(guān)系R的元組時，我們可以用盡可能少的磁盤I/0來讀取R。
第2點使我們不是將讀到的R的每一個元組與S的一個元組連接，而是與能裝入內(nèi)存的盡可能多的S元組連接。

σ? - 選擇（Selection）π? - 投影（Projection）

??：連接

4.4 基于排序的兩趟算法

4.4.1 兩階段多路歸并排序

兩階段多路歸并排序（TPMMS）是一種針對大數(shù)據(jù)集進行排序的有效方法，特別是在處理無法一次性裝入內(nèi)存的數(shù)據(jù)集時。
第一階段：分割和局部排序
分割：將大數(shù)據(jù)集R分割成多個較小的部分（塊），每個部分大小適中，可以單獨放入內(nèi)存進行排序。
局部排序：使用內(nèi)存中的排序算法（如快速排序、歸并排序等）對每個塊進行排序，并將排序后的結(jié)果寫回到外存（如硬盤）。每個塊排序后形成一個有序的子表。
第二階段：全局歸并
讀取和歸并：從外存中讀取這些有序的子表到內(nèi)存中，并使用多路歸并算法將它們合并成一個大的有序表。
多路歸并：同時處理多個有序子表，每次從所有子表中選出最小（或最大）的元素，并將其放入結(jié)果集中。這個過程中，可能需要多次從外存讀取子表數(shù)據(jù)到內(nèi)存。

4.4.2 利用排序去除重復

第一趟：分割和局部排序
與TPMMS的第一階段相同，
第二趟：去重和歸并
去重：對于每個輸入塊，算法讀取第一個未考慮的元組t，并將其復制到輸出塊中。然后，它檢查輸入塊中剩余的元素，如果發(fā)現(xiàn)有與t相同的元素，則將它們從輸入塊中刪除（或標記為已處理，實際刪除可能不是必需的，具體取決于實現(xiàn)方式）。這樣，每個唯一的元組只會被復制到輸出塊一次。
歸并：由于輸入塊已經(jīng)是有序的，因此可以確保在復制過程中，輸出塊中的元素也是有序的。隨著輸入塊的讀取和去重，算法會不斷地將唯一的元組添加到輸出塊中。
性能分析
磁盤I/O：與TPMMS相同，該算法的總磁盤I/O次數(shù)也是3B?，其中B?是數(shù)據(jù)集的塊數(shù)。這是因為每個塊在第一趟中需要被讀入和寫出一次，在第二趟中可能再次被讀入（用于去重和歸并），并且結(jié)果可能還需要被寫出（盡管在某些情況下，這個結(jié)果可能直接用于后續(xù)處理而不需要寫回磁盤）。

4.4.3 利用排序進行分組和聚集

第一趟：分割、排序和寫入
讀取和排序：將數(shù)據(jù)集R的元組按批次讀取到內(nèi)存中，每次讀取M個塊。使用分組屬性作為排序關(guān)鍵字，對每個內(nèi)存中的塊進行排序。
寫入磁盤：將每個排好序的子表（塊）寫回到磁盤上。這樣，每個子表都是按分組屬性有序的。
第二趟：歸并、分組和聚集
初始化緩沖區(qū)：為每個子表分配一個主存緩沖區(qū)，并將每個子表的第一個塊加載到其對應的緩沖區(qū)中。
查找最小分組：在所有緩沖區(qū)的可用元組中，反復查找排序關(guān)鍵字（即分組屬性）的最小值。這個最小值確定了下一個要處理的分組。
分組和聚集：
準備聚集：為每個新的分組準備一個空白的聚集結(jié)果列表或數(shù)據(jù)結(jié)構(gòu)。
遍歷和累計：遍歷所有緩沖區(qū)中的元組，檢查每個元組的分組屬性是否與當前處理的分組相匹配。如果匹配，則根據(jù)需要對元組中的其他屬性進行聚集操作（如計數(shù)、求和等）。
更新聚集結(jié)果：將每個匹配的元組的貢獻累加到當前分組的聚集結(jié)果中。
替換空緩沖區(qū)：如果一個緩沖區(qū)的所有匹配元組都已處理完畢（即緩沖區(qū)為空或剩余元組不屬于當前分組），則用同一子表中的下一個塊替換它（如果有的話）。
輸出分組和聚集結(jié)果：當不再有排序關(guān)鍵字為當前分組的元組時，輸出一個包含分組屬性和對應聚集值的元組。
重復：重復步驟2-5，直到所有分組都被處理完畢。

4.4.4 基于排序的并算法

第一趟：創(chuàng)建排序子表
將關(guān)系R和S的元組分別讀取到內(nèi)存中，并使用排序關(guān)鍵字（通常是元組本身，因為并集操作不需要特定的排序?qū)傩?#xff09;進行排序。
將排好序的元組塊寫回到磁盤上，形成排序子表。這些子表將用于第二趟的歸并操作。
第二趟：歸并和輸出
為R和S的每個子表分配一個內(nèi)存緩沖區(qū)，并用每個子表的第一塊數(shù)據(jù)初始化這些緩沖區(qū)。
重復地在所有緩沖區(qū)中查找并比較剩余的第一個元組t。將t復制到輸出緩沖區(qū)（或直接輸出到最終結(jié)果中，如果輸出緩沖區(qū)已滿或接近滿），并從所有包含t的緩沖區(qū)中刪除t的副本（在集合的情況下，每個元素至多有兩個副本，分別來自R和S）。
當輸入緩沖區(qū)變空或輸出緩沖區(qū)變滿時，根據(jù)TPMMS算法的策略進行處理：從磁盤上讀取新的塊到輸入緩沖區(qū)，或?qū)⑤敵鼍彌_區(qū)的內(nèi)容寫回磁盤，并清空輸出緩沖區(qū)以繼續(xù)接收新數(shù)據(jù)。

4.4.5 基于排序的交和差算法

集合與包交算法
集合交：當處理到所有緩沖區(qū)中最小的元組t時，如果t同時在關(guān)系R和S的緩沖區(qū)中都存在，則輸出t。
由于是集合操作，不考慮t在R和S中出現(xiàn)的次數(shù)，只關(guān)心是否存在。
包交：對于包交，需要計算t在R和S中出現(xiàn)的最小次數(shù)，并輸出該次數(shù)。
如果t在任一關(guān)系中未出現(xiàn)（即計數(shù)為0），則不輸出t。
集合與包差算法
集合差 R-S：當處理到所有緩沖區(qū)中最小的元組t時，如果t在R的緩沖區(qū)中存在但在S的緩沖區(qū)中不存在，則輸出t。由于是集合操作，不關(guān)心t在R中出現(xiàn)的具體次數(shù)。
包差 R-S：對于包差，需要計算t在R中出現(xiàn)的次數(shù)減去在S中出現(xiàn)的次數(shù)，并輸出該差值。如果差值小于或等于0（即t在S中出現(xiàn)的次數(shù)至少等于在R中出現(xiàn)的次數(shù)），則不輸出t。當處理一個塊且該塊中所有剩余的元組都是t時，需要繼續(xù)讀取下一個塊來計算t的準確出現(xiàn)次數(shù)。

4.4.6 基于排序的一個簡單的連接算法

給定兩個要連接的關(guān)系R(X, Y)和S(Y, Z)，其中Y是連接屬性，且有一個大小為M的內(nèi)存塊限制用于緩沖區(qū)。算法的目標是計算這兩個關(guān)系的連接結(jié)果。
1. 排序：
○ 使用Y作為排序關(guān)鍵字，對關(guān)系R和S分別應用2PMMS（兩趟多路歸并排序）算法進行排序。排序后，具有相同Y值的元組在各自的關(guān)系中會相鄰。
2. 歸并和連接：
○ 使用兩個緩沖區(qū)，一個用于存儲R的當前塊，另一個用于存儲S的當前塊。
○ 重復執(zhí)行以下步驟，直到R和S的所有元組都被處理完：
a. 在當前R和S的塊的前端查找連接屬性Y的最小值y。
b. 如果y在另一個關(guān)系的前部沒有出現(xiàn)（即，當前R塊的最小Y值大于當前S塊的最大Y值，或反之），則刪除當前塊中具有排序關(guān)鍵字y的元組（或跳過它們，因為它們無法參與當前連接），并嘗試從磁盤加載下一個塊到相應關(guān)系的緩沖區(qū)中。
c. 如果y在兩個關(guān)系中都出現(xiàn)，則：
■ 從R和S中讀取盡可能多的塊，直到確定每個關(guān)系中都不再有y的副本。在這個過程中，可以使用多達M個緩沖區(qū)來存儲具有相同Y值的元組。
■ 輸出通過連接R和S中具有共同的Y值y的元組所能形成的所有元組。這通常涉及嵌套循環(huán)遍歷具有相同Y值的元組對。
d. 如果一個關(guān)系在內(nèi)存中已沒有未考慮的元組（即，其緩沖區(qū)為空），則重新從磁盤加載該關(guān)系的下一個塊到緩沖區(qū)中。

4.4.8 一種更有效的基于排序的連接

排序階段：
使用連接屬性Y作為排序關(guān)鍵字，分別對關(guān)系R(X, Y)和S(Y, Z)進行排序。
將排序后的數(shù)據(jù)分割成多個子表（或塊），每個子表的大小通常受限于內(nèi)存中的可用緩沖區(qū)大小。這里假設總共有不超過M個子表，每個子表可以被完全加載到內(nèi)存中。
初始化緩沖區(qū)：
為每個子表分配一個緩沖區(qū)（總共不超過M個緩沖區(qū)），并將每個子表的第一塊加載到對應的緩沖區(qū)中。
歸并和連接階段：
重復執(zhí)行以下步驟，直到所有子表都被完全處理：
a. 在所有子表的當前塊中查找具有最小Y值的元組。
b. 一旦找到具有最小Y值y的元組，就識別出關(guān)系R和S中所有具有此Y值的元組。
c. 使用找到的元組進行連接操作，并輸出所有可能的連接結(jié)果。這通常涉及到對兩個關(guān)系中具有相同Y值的元組進行嵌套循環(huán)遍歷。
d. 如果一個子表的當前塊中的所有元組都已被處理，則將該子表的下一個塊從磁盤加載到其對應的緩沖區(qū)中。如果所有塊都已被處理，則可能需要重新排序或合并剩余的子表塊。

4.5 基于散列的兩趟算法

基于散列的算法在處理大數(shù)據(jù)集時提供了一種有效的方法來減少內(nèi)存使用并提高操作效率。這些算法通過選擇適當?shù)纳⒘嘘P(guān)鍵字，將大量數(shù)據(jù)分散到有限數(shù)量的桶（或稱為哈希桶）中，從而允許算法一次處理一個桶或具有相同散列值的一對桶。

4.5.1通過散列劃分關(guān)系

初始化：
設定散列函數(shù)h，該函數(shù)將關(guān)系R中的整個元組t作為輸入，并輸出一個介于0到M-1之間的整數(shù)，表示桶的索引。
準備M個緩沖區(qū)（或磁盤上的塊），每個緩沖區(qū)對應一個桶。注意，實際上只有M-1個桶用于存儲數(shù)據(jù)，而第M個緩沖區(qū)用作臨時存儲，以便在最后一個桶填滿時可以繼續(xù)加載數(shù)據(jù)。
遍歷關(guān)系R：
遍歷關(guān)系R中的每個元組t。使用散列函數(shù)h計算元組t的桶索引h(t)。將元組t復制到對應桶的緩沖區(qū)中。
緩沖區(qū)管理：
如果某個桶的緩沖區(qū)已滿，將該緩沖區(qū)的內(nèi)容寫入磁盤上的相應塊中。
為該桶初始化一個新的緩沖區(qū)，以便繼續(xù)存儲后續(xù)的元組。
處理最后一個桶：
在遍歷完關(guān)系R的所有元組后，最后一個桶（可能包括第M個緩沖區(qū)中暫存的元組）可能并未填滿。如果最后一個桶的緩沖區(qū)不為空，將其內(nèi)容寫入磁盤上的相應塊中。

4.5.2 基于散列的消除重復算法

**散列劃分：**使用散列函數(shù)h將關(guān)系R的元組劃分到M-1個桶中。每個桶與一個緩沖區(qū)或磁盤塊相關(guān)聯(lián)，用于存儲散列到該桶的元組。如果某個桶的緩沖區(qū)滿了，就將其內(nèi)容寫入磁盤上的一個新塊，并為該桶初始化一個新的緩沖區(qū)。
**寫入磁盤：**遍歷完關(guān)系R后，將所有非空桶的緩沖區(qū)內(nèi)容寫入磁盤上的塊中。
**重復消除：**對每個桶中的數(shù)據(jù)進行重復消除。由于每個桶的大小相對較小（假設每個桶都能裝入內(nèi)存），因此可以使用一趟算法（如4.2.2節(jié)中討論的方法）來去除重復元組。
優(yōu)點：
減少了內(nèi)存使用，因為每個桶都可以獨立地裝入內(nèi)存處理。
提高了處理速度，因為可以并行處理多個桶。
適用于大數(shù)據(jù)集，因為可以通過增加桶的數(shù)量來擴展處理能力。

4.5.3 基于散列的分組和聚集算法

**散列劃分：**使用依賴于分組屬性的散列函數(shù)h將關(guān)系R的元組劃分到M-1個桶中。每個桶收集具有相同散列值的元組，這些元組在分組屬性上可能相同或相似。
寫入磁盤：
如果某個桶的緩沖區(qū)滿了，就將其內(nèi)容寫入磁盤上的一個新塊，并為該桶初始化一個新的緩沖區(qū)。最終，所有非空桶的內(nèi)容都需要被寫入磁盤，以便后續(xù)處理。
**分組和聚集：**遍歷每個桶，對每個桶內(nèi)的元組進行分組。由于桶的大小可能較大，但分組是基于散列值的，因此同一分組的所有元組理論上應該都在同一個桶內(nèi)。
對每個分組應用聚集函數(shù)（如求和、平均值、最大值、最小值等）。
合并結(jié)果：
將來自不同桶的聚集結(jié)果合并成一個完整的結(jié)果關(guān)系。這通常不需要額外的磁盤I/O，除非結(jié)果關(guān)系本身太大而無法完全裝入內(nèi)存。

4.5.4 基于散列的并（∪）、交（∩）和差（-）算法

**散列劃分：**使用相同的散列函數(shù)h將關(guān)系R和S的元組分別散列到M-1個桶中。這意味著對于R，我們有桶R?, R?, …, R_{M-1}；對于S，我們有桶S?, S?, …, S_{M-1}。
**寫入磁盤：**如果某個桶的緩沖區(qū)滿了，就將其內(nèi)容寫入磁盤上的一個新塊。最終，所有非空桶的內(nèi)容都需要被寫入磁盤，以便后續(xù)處理。
執(zhí)行集合操作：
并（∪）：對于每個i，計算桶R_i和S_i的并集，并將結(jié)果輸出到結(jié)果關(guān)系的相應桶中。注意，由于使用了相同的散列函數(shù)，任何在兩個關(guān)系中都出現(xiàn)的元組都會被散列到相同的桶中，從而避免了在結(jié)果中引入重復。
交（∩）：對于每個i，計算桶R_i和S_i的交集，并將結(jié)果輸出到結(jié)果關(guān)系的相應桶中。
差（-）：對于每個i，計算桶R_i中但不在S_i中的元組（即R_i - S_i），并將結(jié)果輸出到結(jié)果關(guān)系的相應桶中。注意，如果還需要計算S - R，則需要額外處理。

4.5.5 散列連接算法

為了計算關(guān)系R(X, Y)和S(Y, Z)的連接，我們可以使用基于散列的兩趟算法。這個算法的核心思想是利用連接屬性Y作為散列關(guān)鍵字，將R和S的元組分別散列到多個桶中。然后，對每個對應的桶對執(zhí)行一趟連接操作，最終將所有桶的連接結(jié)果合并起來得到最終的結(jié)果關(guān)系。
**散列劃分：**使用連接屬性Y作為散列關(guān)鍵字，將R和S的元組分別散列到M個桶中。結(jié)果得到桶R_0, R_1, …, R_{M-1}和桶S_0, S_1, …, S_{M-1}。
**寫入磁盤：**將每個桶的內(nèi)容寫入磁盤，以便后續(xù)處理。
**執(zhí)行連接操作：**對每對對應的桶（R_i 和 S_i）執(zhí)行一趟連接操作。由于連接屬性Y被用作散列關(guān)鍵字，因此如果R中的元組t_R能與S中的元組t_S連接，則它們必然位于具有相同i值的桶中。在一趟連接過程中，算法會讀取桶R_i和S_i的內(nèi)容到內(nèi)存中，執(zhí)行連接操作，并將結(jié)果輸出到結(jié)果關(guān)系的相應部分。
**合并結(jié)果：**將來自不同桶的連接結(jié)果合并成一個完整的結(jié)果關(guān)系。這通常涉及讀取每個桶的連接結(jié)果，并將它們組合起來。
**磁盤I/O：**散列連接算法大致需要3(B? + B(S))次磁盤I/O操作，其中B?和B(S)分別是關(guān)系R和S的塊數(shù)。這些操作包括讀取R和S的塊到桶中、將桶寫入磁盤（如果必要）、以及讀取桶對以執(zhí)行連接操作。

4.5.6 節(jié)省一些磁盤 I/O（混合散列連接）

桶的分配與內(nèi)存使用：
假設有兩個關(guān)系R和S，其中S較小。我們創(chuàng)建k個桶，但k的數(shù)量遠小于可用的內(nèi)存M（以塊為單位）。選擇m個桶（m < k）完全保留在內(nèi)存中，以存儲S的元組。這些桶的選擇基于它們預期的大小和內(nèi)存的限制。對于剩下的k-m個桶，每個桶只保留一個塊在內(nèi)存中，其余部分寫入磁盤。
第一趟處理：
當讀取S的元組時，將它們分配到相應的桶中。m個桶完全保留在內(nèi)存中，而k-m個桶的剩余部分寫入磁盤。
當讀取R的元組時，也進行類似的分配。但此時，對于R的每個桶，如果它對應的S桶在內(nèi)存中，則直接進行連接；如果S桶在磁盤上，則將R桶的當前塊寫入內(nèi)存中的臨時空間，以便后續(xù)處理。
第二趟處理：
讀取所有寫入磁盤的桶（包括S和R的桶），并對它們進行連接。重要的是，對于那些在第一趟中已經(jīng)在內(nèi)存中完成連接的S桶和R桶對，不需要在第二趟中再次連接。
節(jié)省磁盤I/O的關(guān)鍵
減少尋道時間和旋轉(zhuǎn)延遲：通過將多個塊連續(xù)寫入磁盤，可以減少磁盤的尋道次數(shù)和旋轉(zhuǎn)延遲，從而提高I/O效率。
避免不必要的讀寫：通過在內(nèi)存中直接連接部分桶，可以避免將這些桶的內(nèi)容寫入磁盤后再讀取的額外I/O
要最大化節(jié)省的磁盤I/O，需要使m/k的比率盡可能大，同時滿足內(nèi)存限制。

基于排序和基于散列的區(qū)別

大小依賴性的差異：
基于散列的算法在處理二元操作時（如比較、合并等），其性能或空間需求通常依賴于兩個操作對象中較小的一個的大小。這是因為散列通常通過映射較小的數(shù)據(jù)元素到固定的桶（或位置）中來工作，避免了直接處理整個數(shù)據(jù)集的大小。
相比之下，基于排序的算法通常需要處理整個數(shù)據(jù)集，或至少是數(shù)據(jù)集的一個顯著部分，其性能往往與數(shù)據(jù)集的總大小直接相關(guān)。
有序輸出的能力：
基于排序的算法天然能夠產(chǎn)生有序的結(jié)果集，這對于需要排序輸出的應用非常重要。排序后的數(shù)據(jù)還可以用于進一步的查詢或分析，如二分查找、范圍查詢等。
基于散列的算法則不直接提供排序功能，其輸出通常是無序的。如果需要排序，則必須額外進行排序操作。
桶大小的限制：
基于散列的算法依賴于固定大小的桶來存儲數(shù)據(jù)。如果數(shù)據(jù)分布不均，可能導致某些桶過載而其他桶空閑，影響性能。此外，桶的數(shù)量通常受限于可用的存儲空間或內(nèi)存大小。
特別是在處理具有少量不同值的場景（如group-by操作中的少量分組）時，桶的利用效率可能較低。
磁盤I/O效率：
在基于排序的算法中，通過合理組織磁盤上的數(shù)據(jù)塊，可以最小化磁盤I/O操作，提高性能。特別是當排序后的數(shù)據(jù)可以連續(xù)存儲在磁盤上時，可以減少磁頭移動和旋轉(zhuǎn)延遲時間。
基于散列的算法在磁盤I/O方面可能不那么高效，除非能夠精心組織桶的存儲位置以減少磁盤訪問時間。
批量讀寫優(yōu)化：
當排序子表的數(shù)量遠小于可用內(nèi)存塊（M）時，基于排序的算法可以通過批量讀寫磁盤塊來減少I/O操作次數(shù)和延遲。
類似地，在基于散列的算法中，如果桶的數(shù)量可以精心選擇以匹配磁盤塊的布局，則可以實現(xiàn)類似的性能優(yōu)化。

4.6 基于索引的算法

通過在關(guān)系的一個或多個屬性上創(chuàng)建索引，可以極大地加速數(shù)據(jù)檢索、選擇和連接等操作。基于索引的算法利用這些索引來快速定位數(shù)據(jù)，從而顯著提高查詢效率。

4.6.1聚簇和非聚簇索引

聚簇（Clustering）
在數(shù)據(jù)庫管理系統(tǒng)中，聚簇通常指的是將表中的數(shù)據(jù)物理地存儲在一起，以便基于某個特定的順序或?qū)傩詠韮?yōu)化查詢性能。當關(guān)系的元組被緊縮到能存儲這些元組的盡可能少的塊中時，我們稱這個關(guān)系是被聚簇的。聚簇可以是基于整個表（即整個關(guān)系）的，也可以是基于表中某個或某些屬性的。
聚簇索引（Clustered Index）
聚簇索引是一種特殊的索引，它不僅定義了表中數(shù)據(jù)的邏輯順序，還決定了數(shù)據(jù)的物理存儲順序。在具有聚簇索引的表中，索引鍵的值決定了數(shù)據(jù)行在磁盤上的物理位置。這意味著，當你通過聚簇索引來查詢數(shù)據(jù)時，數(shù)據(jù)庫可以直接定位到數(shù)據(jù)的物理位置，并快速讀取數(shù)據(jù)。
非聚簇索引（Non-Clustered Index）
與聚簇索引不同，非聚簇索引不定義表中數(shù)據(jù)的物理存儲順序。相反，它提供了一個索引結(jié)構(gòu)，該結(jié)構(gòu)包含索引鍵和指向表中相應數(shù)據(jù)行的指針。這意味著，當你通過非聚簇索引來查詢數(shù)據(jù)時，數(shù)據(jù)庫首先使用索引來快速定位到數(shù)據(jù)行的指針，然后通過該指針訪問實際的數(shù)據(jù)行。

4.6.2 基于索引的選擇

聚簇索引下的選擇操作
當屬性a上的索引是聚簇的時，數(shù)據(jù)本身就是按照索引鍵（即屬性a的值）的順序存儲的。這意味著，如果我們想要選擇所有a=v的元組，我們可以直接通過索引快速定位到這些元組在磁盤上的位置，并讀取它們所在的塊。
然而，實際的磁盤I/O次數(shù)可能會受到幾個因素的影響：
索引不在內(nèi)存中：索引本身可能不完全駐留在內(nèi)存中，因此可能需要從磁盤讀取索引塊。
塊分裂：即使所有滿足條件的元組都可以放入少量的塊中，這些元組也可能因為塊分裂而分布在多個塊中，特別是如果它們不是從塊的開始位置開始的。
塊填充和預留空間：關(guān)系R的塊可能沒有被完全填滿，或者為了未來的插入操作而預留了空間。這會導致需要讀取更多的塊來檢索所有相關(guān)的元組。
整數(shù)取整：如果B?/V(R,a)不是整數(shù)，我們需要向上取整以確保所有相關(guān)的塊都被讀取。
非聚簇索引下的選擇操作
在非聚簇索引的情況下，索引僅僅提供了指向數(shù)據(jù)行指針的列表，而數(shù)據(jù)本身并不是按照索引鍵的順序物理存儲的。因此，當我們通過非聚簇索引查找滿足a=v的元組時，每個匹配的元組都可能位于不同的塊中。這導致我們需要讀取更多的塊來檢索所有相關(guān)的元組，因為索引只能告訴我們每個元組的位置，而不能保證它們會聚集在一起。

4.6.3 使用索引的連接

自然連接 R(X, Y) ? S(Y, Z)
在自然連接中，我們假設兩個關(guān)系R和S分別具有屬性集X和Y的交集，以及各自的額外屬性集（Y對于R，Z對于S）。連接操作基于這些共同的屬性（在這個例子中是Y）來合并元組。
索引的使用
假設S在屬性Y上有一個索引。這個索引可以極大地加速連接過程，因為它允許我們快速定位S中所有與R中當前元組在Y屬性上相匹配的元組。
磁盤I/O數(shù)量的分析
讀取R的元組：
如果R是聚簇的，我們需要讀取B?個塊來獲取R的所有元組。
如果R不是聚簇的，可能需要讀取多達T?個塊（即R中元組的總數(shù)）。
對于R中的每個元組，查找S中的匹配元組：
使用S在Y屬性上的索引，我們可以快速定位到S中所有Y值匹配的元組。
如果索引是非聚簇的，那么對于R中的每個元組，我們平均需要讀取T(S)/V(S,Y)個S的元組（這里V(S,Y)是S中Y屬性不同值的數(shù)量）。因此，總的磁盤I/O次數(shù)大約為T?T(S)/V(S,Y)。
如果索引是聚簇的，那么我們可以直接通過索引訪問到物理上連續(xù)存儲的元組，從而減少磁盤I/O。在這種情況下，我們大約需要T?B(S)/V(S,Y)次磁盤I/O（這里假設每個塊可以容納多個具有相同Y值的元組）。注意，如果B(S)/V(S,Y)小于1，則至少需要一個磁盤I/O來讀取包含至少一個匹配元組的塊。

4.6.4 使用有序索引的連接

當索引以有序形式（如B-樹索引）存在時，我們可以利用這些索引來優(yōu)化連接操作。有序索引允許我們直接按照排序順序遍歷關(guān)系中的元組，而無需顯式地對整個關(guān)系進行排序，從而節(jié)省了大量的計算資源和時間。
Zig-Zag 連接
當兩個關(guān)系R(X, Y)和S(Y, Z)在共同的屬性Y上都擁有有序的索引時，我們可以采用一種高效的連接方法，稱為Zig-Zag連接。這種方法的核心思想是同時遍歷R和S的索引，并比較當前元組的Y值，以找到所有匹配的元組對。
**初始化：**設置兩個指針，一個指向R的索引的起始位置，另一個指向S的索引的起始位置。
**比較與遍歷：**比較兩個指針當前指向的元組的Y值。如果Y值相等，則這兩個元組構(gòu)成一個連接對，輸出它們，并將兩個指針都向前移動。如果R的Y值小于S的Y值，則將R的指針向前移動。如果R的Y值大于S的Y值，則將S的指針向前移動。重復上述步驟，直到至少一個索引被完全遍歷。

4.7 緩沖區(qū)管理

4.7.1 緩沖區(qū)管理結(jié)構(gòu)

1. 直接控制內(nèi)存的緩沖區(qū)管理器
在這種模式下，DBMS的緩沖區(qū)管理器直接管理內(nèi)存中的緩沖區(qū)，負責分配和回收內(nèi)存空間給這些緩沖區(qū)。
2. 使用虛擬內(nèi)存的緩沖區(qū)管理器
DBMS的緩沖區(qū)管理器在虛擬內(nèi)存中分配緩沖區(qū)，而不是直接管理物理內(nèi)存。操作系統(tǒng)負責將虛擬內(nèi)存映射到物理內(nèi)存，并根據(jù)需要在物理內(nèi)存和磁盤的交換空間之間移動數(shù)據(jù)塊。

4.7.2 緩沖區(qū)管理策略

最近最少使用(LRU)
先進先出(FIFO)
“時鐘”算法(第二次機會)

4.8 使用超過兩趟的算法

4.8.1 基于排序的多趟算法

當關(guān)系R的大小（以塊數(shù)B?衡量）可以直接裝入M個內(nèi)存緩沖區(qū)時：
讀取數(shù)據(jù)：將整個關(guān)系R讀入內(nèi)存。
排序：在內(nèi)存中使用任何高效的排序算法（如快速排序、歸并排序等）對R進行排序。
寫回磁盤：將排序后的關(guān)系R寫回到磁盤上。
當關(guān)系R的大小超過了M個內(nèi)存緩沖區(qū)能夠容納的范圍時：
分組：將R的塊分成M個組，即R?, R?, …, R?。
遞歸排序：對每個分組R?（i=1,…,M）遞歸地應用排序算法。這意味著每個分組都會被讀入內(nèi)存、排序，然后寫回磁盤。
合并排序的子表：使用類似于外部歸并排序的方法，將所有M個排序后的子表合并成一個大的有序表。這個步驟可能需要多趟讀寫操作，具體取決于內(nèi)存大小和關(guān)系R的塊數(shù)。
執(zhí)行一元操作
如果需要在排序的同時執(zhí)行一元操作（如去重δ或分組γ），則需要在合并步驟中適當修改算法：
去重（δ）：在合并過程中，僅當遇到新的元組時才將其寫入輸出文件，忽略重復的元組。
分組（γ）：首先按分組屬性對關(guān)系進行排序，然后在合并過程中收集具有相同分組屬性值的元組，并根據(jù)需要進行聚合操作（如求和、平均等）。
執(zhí)行二元操作
對于二元操作（如交、連接等），算法也遵循類似的分而治之策略：
分組和排序：對兩個關(guān)系R和S分別進行分組和排序，生成排序后的子表。
分配緩沖區(qū)：根據(jù)R和S的塊數(shù)（B?和B(S)）按比例分配M個緩沖區(qū)給R和S。
執(zhí)行操作：使用適當?shù)乃惴?#xff08;如嵌套循環(huán)連接、歸并連接等）來合并排序后的子表，并執(zhí)行所需的二元操作。這個步驟可能需要多次從磁盤讀取和寫入數(shù)據(jù)，具體取決于操作類型和緩沖區(qū)大小。

4.8.3 基于散列的多趟算法

一元操作
如果關(guān)系R能夠裝入M個內(nèi)存緩沖區(qū)中（即B? ≤ M），則直接將R讀入內(nèi)存，并在內(nèi)存中執(zhí)行所需的一元操作。如果關(guān)系R太大，無法裝入M個內(nèi)存緩沖區(qū)，則執(zhí)行以下步驟：
散列到桶中：使用散列函數(shù)將關(guān)系R的元組散列到M-1個桶中。
遞歸處理：對每個桶遞歸地執(zhí)行一元操作。
合并結(jié)果：將所有桶的處理結(jié)果合并成一個最終的結(jié)果集。
二元操作
如果有一個關(guān)系（比如R）能夠裝入M-1個內(nèi)存緩沖區(qū)中，而另一個關(guān)系（比如S）可以逐個塊地裝入剩下的第M個緩沖區(qū)，則可以直接在內(nèi)存中執(zhí)行連接操作。具體地，將R讀入內(nèi)存，然后逐個塊地將S讀入第M個緩沖區(qū)，并在內(nèi)存中執(zhí)行連接。
如果兩個關(guān)系都太大，無法同時裝入內(nèi)存，則執(zhí)行以下步驟：
散列到桶中：將兩個關(guān)系R和S分別散列到M-1個桶中。對于每個桶i（i=1,…,M-1），R和S都有一個對應的桶R[i]和S[i]。
遞歸處理：對每個相應的桶對(R[i], S[i])遞歸地執(zhí)行連接操作。注意，這里的遞歸處理與一元操作類似，但操作的是桶對而不是單個關(guān)系。
合并結(jié)果：將所有桶對的連接結(jié)果合并成一個最終的結(jié)果集。這個合并過程可能需要額外的排序和歸并步驟，以確保最終結(jié)果的順序性（如果需要的話）。

第五章 查詢編譯器

5.1 語法分析和預處理

5.1.1 語法分析與語法分析樹

語法分析樹的構(gòu)成
原子：語法分析樹中的葉子節(jié)點，對應于源代碼中的不可再分的基本元素，如關(guān)鍵字、標識符（如變量名、表名、列名）、常量、標點符號（如括號、逗號）、運算符等。這些元素是詞法分析器（Lexer）的輸出，詞法分析器負責將源代碼文本分割成這些基本的詞法單元（Tokens）。
語法類：語法分析樹中的非葉子節(jié)點，代表語法結(jié)構(gòu)中的構(gòu)造塊或“短語”，這些短語由一組原子或更小的語法類通過特定的語法規(guī)則組合而成。這些節(jié)點用于表示語言中的語法結(jié)構(gòu)，如表達式、語句、程序塊等。在表示時，通常會使用尖括號（< >）來標識語法類的名稱，以便于區(qū)分原子和語法類。

：整個查詢的根節(jié)點，表示一個完整的SQL查詢。
：表示一個SELECT語句，可能包括選擇列表、FROM子句、WHERE子句等。
：包含要選擇的列名或表達式的列表，如name, age。
：表示對表中某列的引用，如name和age（盡管在這里它們直接作為原子出現(xiàn)，但在更 復雜的表達式中，它們可能是的實例）。
：表示FROM子句，指定查詢的數(shù)據(jù)來源，如FROM users。
：表示表名，如users。
：表示W(wǎng)HERE子句，包含用于過濾結(jié)果的條件，如WHERE age > 30。
：表示一個條件表達式，如age > 30。這里可以進一步細分，比如表示比較操作，表示值（盡管在這個例子中30被直接視為原子）。

SELECT name, age FROM users WHERE age > 30;該查詢的語法分析樹可能包含以下節(jié)點：
<Query>：根節(jié)點，表示整個查詢。
<SelectList>：包含name和age的列表。
name（原子）
age（原子）
<FromClause>：包含users。
users（原子）
<WhereClause>：包含條件表達式。
<Condition>：表示條件表達式age > 30。
age（原子）
>（原子）
30（原子）

5.1.2 SQL 的一個簡單子集的語法

存在一些“基本”或“終端”語法類（有時也稱為詞法單元或標記），它們不是通過其他語法規(guī)則組合而成的，而是直接對應于源代碼中的基本元素。這些元素在語法分析階段之前就已經(jīng)被詞法分析器識別出來。

通常代表數(shù)據(jù)庫表中的列名。在SQL查詢中，這些列名用于指定要從表中檢索哪些數(shù)據(jù)。在語法分析樹中，的一個實例就是任何當前數(shù)據(jù)庫模式中存在的有效列名。例如，在表employees中，name、age和salary都可能是的實例。

代表數(shù)據(jù)庫中的一個表或視圖。在SQL查詢中，FROM子句后面通常會跟有一個或多個，以指定查詢將要從哪些表中檢索數(shù)據(jù)。同樣，在語法分析樹中，的一個實例就是任何當前數(shù)據(jù)庫模式中存在的有效表名或視圖名。例如，employees、departments和orders都可能是的實例。

在SQL中通常與字符串匹配和搜索相關(guān)，盡管在標準的SQL查詢中直接使用的情況可能不如和那么普遍。但是，在像LIKE這樣的SQL語句中，用于指定要匹配的字符串模式。的一個實例是任何被引號括起來的、符合SQL字符串匹配規(guī)則的字符串。例如，在LIKE語句中，'John%'可能是一個的實例，用于匹配以"John"開頭的任何字符串。

5.1.3預處理器

視圖引用的預處理
當查詢語句中引用的關(guān)系實際上是一個視圖時，預處理器需要將該視圖的定義嵌入到原始查詢中。
語義檢查
確保查詢語句在邏輯上是合理的。包括檢查關(guān)系、屬性、類型和運算符的使用是否滿足數(shù)據(jù)庫規(guī)則。
檢查關(guān)系的使用：
驗證FROM子句中指定的每個關(guān)系（表或視圖）在當前數(shù)據(jù)庫模式中是存在的。
檢查屬性的使用：
確保在SELECT子句、WHERE子句等中引用的每個屬性都屬于當前查詢范圍內(nèi)的一個關(guān)系。
類型的檢查：
驗證每個屬性的使用是否符合其數(shù)據(jù)類型的要求。例如，在WHERE子句中使用LIKE運算符時，比較的兩邊通常應該是字符串或可以隱式轉(zhuǎn)換為字符串的類型。如果使用了不兼容的類型（如將日期類型直接與字符串進行比較），預處理器將需要執(zhí)行類型轉(zhuǎn)換。

5.2 用于改進查詢計劃的代數(shù)定律

本節(jié)列出一些代數(shù)定律，用于將一個表達式樹轉(zhuǎn)換成一個等價的表達式樹，后者可能有更有效的物理查詢計劃。應用這些代數(shù)變換式的結(jié)果是邏輯查詢計劃，它是查詢重寫階段的輸出。
數(shù)據(jù)庫系統(tǒng)之：關(guān)系代數(shù)詳解-超詳細-CSDN博客

選擇（σ）：選擇運算用于從關(guān)系中選擇滿足特定條件的元組。選擇運算的表達式通常表示為σp?，其中p是選擇條件，R是關(guān)系名。
投影（π）：投影運算用于從關(guān)系中選擇指定的屬性列，并刪除重復的元組。投影運算的表達式通常表示為πA?，其中A是屬性列表，R是關(guān)系名。
消除重復（δ）：當δ運算符應用于一個關(guān)系時，它會檢查關(guān)系中的每個元組，并移除所有重復的元組。這意味著在結(jié)果關(guān)系中，每個元組都是唯一的。
笛卡爾積：笛卡爾積是指兩個集合（在數(shù)據(jù)庫操作中，可以理解為兩個表）的所有可能組合。如果表A有M行，表B有N行，那么A和B的笛卡爾積將有M*N行。每一行都是由表A中的一行與表B中的一行組合而成。不考慮表之間的實際關(guān)系，簡單地將一個表中的每一行與另一個表中的每一行進行組合。

自然連接：自然連接是一種特殊的等值連接，它自動根據(jù)兩個表中具有相同名稱的列來連接這兩個表。如果兩個表中存在多個具有相同名稱的列，則這些列都會被用作連接條件。連接后，結(jié)果表中只保留一個公共列，并去除不滿足連接條件的行。根據(jù)兩個表中具有相同名稱的列來連接這兩個表，只保留滿足連接條件的行，并且結(jié)果表中只保留一個公共列。
等值連接（E Inner Join）：
等值連接是基于兩個或多個表中指定列的值相等進行連接的連接操作。與自然連接不同，等值連接需要顯式指定連接條件，即哪些列的值應該相等。連接結(jié)果中包含滿足連接條件的所有行和列，不會自動去除重復的列。
SELECT * FROM 表A INNER JOIN 表B ON 表A.ID = 表B.ID;

5.2.1 交換律與結(jié)合律

交換律
對于某些運算符，其操作數(shù)的順序可以互換而不影響結(jié)果。并集（∪）、交集（∩）和笛卡爾積（×）等運算符滿足交換律。
并集（∪）：對于任意兩個關(guān)系R和S，如果它們有相同的結(jié)構(gòu)（相同的列名），則R ∪ S = S ∪ R。
交集（∩）：對于任意兩個結(jié)構(gòu)相同的關(guān)系R和S，R ∩ S = S ∩ R。
笛卡爾積（×）：雖然笛卡爾積通常用于不同結(jié)構(gòu)的關(guān)系之間，但如果我們考慮兩個關(guān)系R和S（不必有相同的結(jié)構(gòu)），則R × S和S × R的結(jié)果在邏輯上是不同的（因為結(jié)果關(guān)系中的元組順序和屬性排列會不同）。然而，在關(guān)系代數(shù)的上下文中，我們通常只關(guān)注元組的內(nèi)容而不關(guān)注其順序，因此可以認為笛卡爾積在“無序”的意義上滿足交換律。
結(jié)合律
并集（∪）、交集（∩）和笛卡爾積（×）等運算符也滿足結(jié)合律。
并集（∪）：對于任意三個結(jié)構(gòu)相同的關(guān)系R、S和T，(R ∪ S) ∪ T = R ∪ (S ∪ T)。
交集（∩）：(R ∩ S) ∩ T = R ∩ (S ∩ T)。
笛卡爾積（×）：對于任意兩個關(guān)系R和S，以及另一個關(guān)系T（T的結(jié)構(gòu)可以與R和S不同），(R × S) × T 和 R × (S × T) 在邏輯上是不等價的（因為結(jié)果關(guān)系的結(jié)構(gòu)和元組數(shù)會不同）。但是，如果我們考慮將笛卡爾積的結(jié)果視為一個單一的關(guān)系，并僅關(guān)注元組的內(nèi)容（而不考慮其內(nèi)部結(jié)構(gòu)），則可以認為笛卡爾積滿足結(jié)合律。

5.2.2 涉及選擇的定律

“下推選擇”（Pushing Selections Down）是一種重要的優(yōu)化策略，旨在通過重新排列查詢計劃中的操作順序來減少處理的數(shù)據(jù)量，從而提高查詢效率。

下推選擇是指在構(gòu)建查詢執(zhí)行計劃時，將選擇（或稱為過濾）操作盡可能地移動到查詢計劃的早期階段，即靠近數(shù)據(jù)源（如表掃描或索引掃描）的位置。這樣做的目的是減少后續(xù)操作需要處理的數(shù)據(jù)量，從而提高查詢的整體性能。

1.對于并，選擇必須下推到兩個參數(shù)中。

2.對于差，選擇必須下推到第一個參數(shù)，下推到第二個參數(shù)是可選的。


3.對于其他運算符，只要求選擇下推到其中一個參數(shù)。對于連接和積，將選擇下推到兩個參數(shù)是沒有意義的，因為參數(shù)可能有也可能沒有選擇所要求的屬性。即使可以同時下推到兩者該做法也不一定能改進計劃。選擇條件可能依賴于兩個表之間的交互數(shù)據(jù)，而這些數(shù)據(jù)在連接或積操作之前是不可見的。
假設關(guān)系R具有C中要求的全部屬性：

5.2.3 下推選擇

當查詢包含虛視圖時，有時首先將選擇盡可能往樹的上部移是很必要的，然后再把選擇下推到所有可能的分支。

**選擇前置：**原始查詢中的選擇條件（即電影年份為1996年）實際上可以前置到連接操作之前。我們可以先對Movies表進行過濾，只選擇1996年的電影，然后再與StarsIn表進行連接。
**選擇下推：**在將選擇前置后，我們可以將這個選擇條件進一步下推到連接的子節(jié)點上。因為year是Movies表的屬性，也是連接操作需要考慮的屬性，所以我們可以將這個條件分別應用于Movies表和StarsIn表。連接操作只需要處理與1996年電影相關(guān)的StarsIn記錄，從而顯著減少了處理的數(shù)據(jù)量。

5.2.4 涉及投影的定律

投影的下推
當投影操作可以下推到其他操作（如連接、排序等）中時，可以優(yōu)化查詢的執(zhí)行計劃。投影操作只是減少了每個元組的長度，對總處理量的減少作用有限。因此，在選擇和投影都能下推的情況下，優(yōu)先選擇下推選擇操作往往更為有效。
擴展投影
擴展投影是投影操作的一個擴展，它允許在投影的過程中不僅選擇原始關(guān)系中的屬性，還可以計算新的屬性或表達式作為輸出。在擴展投影中，輸出屬性x可能是一個復雜的表達式，該表達式可以包含輸入屬性E中的屬性、常量或函數(shù)運算等。
E->x
輸入屬性：在投影操作中，E中提到的屬性稱為輸入屬性，它們是原始關(guān)系中的屬性，用于計算或選擇輸出屬性。
輸出屬性：在投影或擴展投影中，x是輸出屬性，它可能是原始關(guān)系中的一個屬性，也可能是通過輸入屬性計算得到的新值。
簡單投影：如果投影列表中的屬性只是簡單地選擇原始關(guān)系中的屬性，沒有包含復雜的表達式或更名操作，則稱該投影為簡單投影。

5.2.6 有關(guān)消除重復的定律

5.2.7 涉及分組與聚集的定律

運算符 γ (Gamma): γ 表示聚集運算符，它可以對一組數(shù)據(jù)進行某種形式的聚合操作，比如求和、計數(shù)、平均、最小值或最大值等。
運算符 δ (Delta): 表示去重操作，即從一組數(shù)據(jù)中刪除重復的記錄，只保留唯一的記錄。
運算符 π (Pi): 是一個選擇操作符，用于從一組數(shù)據(jù)中選擇特定的列或?qū)傩浴?br />L（屬性列表）：通常與聚集操作相關(guān)聯(lián)。在聚集函數(shù)的表達式中，“L” 指的是聚集操作所應用的屬性列表。
M（屬性列表）：通常用于投影操作。在關(guān)系代數(shù)中，投影操作（π）用來從關(guān)系中選擇特定的列或?qū)傩?。表示從關(guān)系 R 中選擇屬性列表 M 中的所有屬性。“M” 在聚集操作中的作用是確保在進行聚集之前，關(guān)系中包含所有需要的屬性。
聚集運算符的通用定律: δ(γL?) = γL?，意味著先進行聚集操作，然后去重，與先去重再進行聚集操作的結(jié)果是相同的。這是因為聚集操作本身不關(guān)心數(shù)據(jù)中的重復項。
投影去除無用屬性: γL? = γL(πM?) 表示，在進行聚集操作之前，我們可以選擇性地去除那些在聚集列表 L 中沒有被使用的屬性 M。這是因為這些屬性對于最終的聚集結(jié)果沒有影響。
不受重復影響的聚集: 當聚集列表 L 中只包含 MIN 或/和 MAX 函數(shù)時，我們稱這個聚集操作是不受重復影響的。這是因為 MIN 和 MAX 函數(shù)的結(jié)果是不會因為數(shù)據(jù)中的重復項而改變的。因此，可以有 γL? = γL(δ?)，即無論數(shù)據(jù)是否有重復，最終的聚集結(jié)果都是相同的。
受重復影響的聚集: 與不受重復影響的聚集相反，像 SUM、COUNT、AVG 這樣的聚集函數(shù)，其結(jié)果會受到數(shù)據(jù)中重復項的影響。如果在計算這些聚集之前去除重復項，最終的值可能會不同。

5.3 從語法分析樹到邏輯查詢計劃

第一步：使用關(guān)系代數(shù)運算符替換語法樹
關(guān)系代數(shù)是一組抽象的操作，用于對關(guān)系（即表）進行查詢和修改。這些操作包括選擇（σ）、投影（π）、連接（?）、并（∪）、差（-）、笛卡爾積（×）等。

表引用：直接映射為關(guān)系代數(shù)中的關(guān)系（即表）。
選擇條件：轉(zhuǎn)換為選擇（σ）操作，用于過濾滿足條件的元組。
投影：將SELECT子句中的字段名轉(zhuǎn)換為投影（π）操作，用于選擇特定的屬性。
連接：根據(jù)JOIN條件（如A.dept_id = B.dept_id），轉(zhuǎn)換為連接（?）操作，合并兩個或多個關(guān)系。

第二步：優(yōu)化關(guān)系代數(shù)表達式
在得到邏輯查詢計劃（即關(guān)系代數(shù)表達式）后，下一步是優(yōu)化它以生成更有效的物理查詢計劃。

查詢重寫：通過等價變換（如改變連接順序、合并選擇操作等）來減少計算量。
索引利用：識別并利用索引來加速查詢執(zhí)行。
并行處理：如果可能，將查詢分解為可以并行執(zhí)行的部分。

5.3.1 轉(zhuǎn)換成關(guān)系代數(shù)

您“簡單”SELECT-FROM-WHERE結(jié)構(gòu)轉(zhuǎn)換為關(guān)系代數(shù)表達式的規(guī)則。
處理FROM列表：
將FROM列表中提及的所有關(guān)系（即表）視為關(guān)系代數(shù)中的基本關(guān)系。如果FROM列表中包含了多個表，并且這些表之間需要通過某種方式（如JOIN條件）相關(guān)聯(lián)，則首先計算這些表的笛卡爾積。
處理WHERE條件：
使用選擇（σ）運算符來過濾滿足WHERE子句中條件的元組。將WHERE子句中的條件表達式轉(zhuǎn)換為關(guān)系代數(shù)中的選擇條件。
處理SELECT列表：
使用投影（π）運算符來選擇SELECT列表中指定的屬性。投影運算符作用于經(jīng)過選擇和連接（如果有的話）處理后的關(guān)系上。

5.3.2 從條件中去除子查詢

5.3.3 邏輯查詢計劃的改進

** 選擇條件下推**
選擇條件下推是一種將選擇（過濾）操作盡可能地向查詢計劃樹的底部（即數(shù)據(jù)源）移動的優(yōu)化策略。當查詢中包含多個連接的表時，將選擇條件盡早應用于較小的數(shù)據(jù)集可以減少后續(xù)操作的數(shù)據(jù)量，從而提高查詢效率。對于AND連接的多個條件，可以分別將每個條件下推到樹的相應位置。
投影下推
投影下推是另一種優(yōu)化策略，它將投影（即選擇列）操作盡可能地向查詢計劃樹的底部移動。這有助于減少在數(shù)據(jù)傳輸和處理過程中所需的數(shù)據(jù)量。
重復消除
重復消除是指移除查詢結(jié)果中的重復行。在某些情況下，這個操作可以被移動到查詢計劃樹中更方便的位置，以減少需要處理的數(shù)據(jù)量。
選擇與積的結(jié)合
在某些情況下，可以將選擇條件與下面的連接操作結(jié)合，將等值條件的選擇操作轉(zhuǎn)換為等值連接。這通?？梢蕴岣卟樵兊男?#xff0c;因為等值連接通常可以更有效地利用索引和連接算法。

5.4 運算代價的估計

在將邏輯查詢計劃轉(zhuǎn)換為物理查詢計劃的過程中，有四個方面值得關(guān)注。
1. 滿足結(jié)合律與分配律的運算的次序與分組
結(jié)合律：對于滿足結(jié)合律的運算（如連接、并、交），其操作對象的次序可以改變而不影響最終結(jié)果。在物理計劃中，我們可以重新排列這些運算的次序，以最小化數(shù)據(jù)移動、減少中間結(jié)果的大小或利用系統(tǒng)的并行處理能力。
分配律：在某些情況下，我們可以利用類似分配律的性質(zhì)來優(yōu)化查詢。例如，將選擇（過濾）操作“分配”到連接操作之前，以減少需要連接的數(shù)據(jù)量。
分組：將多個可結(jié)合的運算組合成一個更大的運算單元，可以減少運算符之間的數(shù)據(jù)交換次數(shù)，提高執(zhí)行效率。例如，將多個連接操作組合成一個復合連接操作。
2. 邏輯計劃中每個運算符的算法選擇
在邏輯計劃中，我們定義了要執(zhí)行的運算，但在物理計劃中，我們需要選擇實現(xiàn)這些運算的具體算法。例如，對于連接操作，我們可以選擇嵌套循環(huán)連接、散列連接或排序合并連接等算法。
3. 物理計劃中的其他運算符
掃描：物理計劃需要明確如何從存儲介質(zhì)（如磁盤）中讀取數(shù)據(jù)。這通常涉及掃描操作，可以是全表掃描或索引掃描。
排序：在物理計劃中，排序操作可能是顯式的（如ORDER BY子句）或隱式的（如連接操作前的排序）。排序算法的選擇和數(shù)據(jù)的物理布局都會影響排序操作的效率。
4. 參數(shù)和數(shù)據(jù)的傳輸方式
在物理計劃中，我們需要考慮數(shù)據(jù)如何在不同的運算符之間傳輸。這包括確定中間結(jié)果的存儲位置（如內(nèi)存、磁盤）以及傳輸機制（如迭代器、批量傳輸）。使用磁盤上的中間結(jié)果可以減少內(nèi)存的使用，但會增加I/O成本。使用迭代器可以逐條處理數(shù)據(jù)，減少內(nèi)存占用，但可能增加CPU的開銷。

5.4.1 中間關(guān)系大小的估計

主要關(guān)注查詢執(zhí)行過程中產(chǎn)生的臨時結(jié)果（即中間關(guān)系）的元組數(shù)或數(shù)據(jù)量。這是評估查詢性能的一個重要方面，因為中間關(guān)系的大小直接影響了查詢所需的存儲空間、I/O操作次數(shù)以及后續(xù)運算的復雜度。

5.4.2 投影運算大小的估計

對于關(guān)系 R：
每個元組大小：12（元組頭）+ 4（a）+ 4（b）+ 100（c）= 120字節(jié)。
塊中元組數(shù)：(1024?24)/120=8（向下取整）。
元組總數(shù) T?=10000，因此塊數(shù) B?=10000/8=1250。
對于關(guān)系 S=π + ?（其中 + 表示擴展投影，用 a 與 b 的和替代 a 和 b）：
新的元組結(jié)構(gòu)包括：12（元組頭）+ 4（a+b的和，假設結(jié)果仍為整數(shù)）+ 100（c）= 116字節(jié)。
盡管元組大小略有減少，但由于仍然可以存放8個元組在一個塊中，所以塊數(shù)和元組總數(shù)保持不變：T(S)=10000，B(S)=1250。
對于關(guān)系 U=π a,b ?（即傳統(tǒng)的去除 c 的投影）：
新的元組結(jié)構(gòu)包括：12（元組頭）+ 4（a）+ 4（b）= 20字節(jié)。
由于元組大小顯著減小，現(xiàn)在每個塊可以存放更多的元組：(1024?24)/20=50（向下取整）。
因此，雖然元組總數(shù)仍然是 T(U)=10000，但塊數(shù)大大減少：B(U)=10000/50=200。

5.4.3 選擇運算大小的估計

等值比較：
當查詢條件為某個屬性等于某個常量時（如 S = σA=c?），那么結(jié)果集的大小可以通過 T(S) = T? / V(R, A) 來估計，其中 T? 是表 R 的元組數(shù)，V(R, A) 是屬性 A 的不同取值的數(shù)量。這個假設在屬性值均勻分布時較為準確。
非等值比較：
對于非等值比較（如 S = σA<c? 或 S = σA>c?），由于條件的非確定性，結(jié)果集的估計更加復雜。一種假設是認為滿足條件的元組大約占總元組數(shù)的一半，然而涉及非等值比較的查詢傾向產(chǎn)生更小量的元組因此我們估計： T(S) = T? / 3。
特殊比較：
對于某些特殊的選擇條件，如檢查某個屬性是否非空（A IS NOT NULL），如果大多數(shù)元組都滿足這個條件（即空值較少），則可以假設所有元組都滿足條件，即 T(S) = T??；蛘?#xff0c;更精確地，可以通過 T(S) = T? * (V(R, A) - 1) / V(R, A) 來估計。

5.4.4 連接運算大小的估計

值集的包含：
如果一個屬性Y同時出現(xiàn)在關(guān)系R和S中，且R的Y值集合是S的Y值集合的子集（即V(R,Y) ≤ V(S,Y)），那么R中的每個Y值都會在S中出現(xiàn)。這個假設在Y是S的鍵且是R的外鍵時成立，但在其他情況下可能不成立。
值集的保持：
在進行連接時，非連接屬性（即只出現(xiàn)在一個關(guān)系中的屬性）不會丟失其值集中的任何值。這意味著，如果A是R的屬性但不是S的屬性，那么V(R∞S, A) = V(R, A)。這個假設在大多數(shù)情況下是合理的，但也可能在某些特殊情況下不成立。
概率計算與結(jié)果集大小估計
如果V(R,Y) > V(S,Y)，那么S中每個Y值都會出現(xiàn)在R中，因此s的Y值出現(xiàn)在R中的概率為1，但r和s具有相同Y值的概率為1/V(R,Y)（因為R中有V(R,Y)個可能的Y值）。
如果V(R,Y) < V(S,Y)，則情況相反，r的Y值會出現(xiàn)在S中，r和s具有相同Y值的概率為1/V(S,Y)。
為了統(tǒng)一這兩種情況，我們可以將概率估算為1/max(V(R,Y), V(S,Y))。
基于上述概率，我們可以估算連接結(jié)果集T(R∞S)的大小：T(R∞S)= T?×T(S)/max( V(R,Y),V(S,Y) )

5.4.5 多連接屬性的自然連接

當連接R(X，Y)xS(Y，Z)中的屬性集Y包含多于一個屬性時
R?S的大小估計是通過T?乘以T(S)，對于每一個R與S的公共屬性y，除以V(R，y)與V(S，y)中較大者來計算。
假設我們有兩個關(guān)系R(X, Y)和S(Y, Z)，其中Y是兩個關(guān)系的共同屬性集，并且Y包含多個屬性（y1, y2, …, yn）。我們可以嘗試使用以下方法來近似計算自然連接結(jié)果集的大小：

5.4.6 多個關(guān)系的連接

在考慮多個關(guān)系（表）的自然連接時，特別是當某個屬性A出現(xiàn)在多個關(guān)系中時，我們需要分析這些關(guān)系在連接后如何影響結(jié)果集的大小以及屬性A上值的分布。以下是對您提出的問題的詳細解答：
假設有 k 個關(guān)系 _R_1,_R_2,…,Rk，它們通過自然連接合并成一個新的關(guān)系 S，即 S=R_1?_R_2?…?_Rk。屬性 A 出現(xiàn)在這 k 個關(guān)系中的至少兩個關(guān)系中。
屬性A上值的分布：
假設屬性 A 在 k 個關(guān)系中的值集大小分別為 _u_1,_u_2,…,uk，且已按從小到大的順序排列，即 u_1≤_u_2≤…≤_uk。
值集保持假設：在連接后的關(guān)系 S 中，屬性 A 的值集大小將是這些 ui 中的最小值，即 _u_1。
所選元組在屬性A上相同的概率：
假設首先從具有最小 _u_1 的關(guān)系 _R_1 中選擇一個元組 _t_1，其屬性 A 的值為 a。
對于其他關(guān)系 Ri（其中 i=2,3,…,k），所選元組 ti 在屬性 A 上與 _t_1 相同的概率是 _ui_1（因為 Ri 中有 ui 個不同的 A 值）。
因此，所有 k 個元組在屬性 A 上相同的概率是這些概率的乘積，即 1/_u_1_u_2…uk。
估計連接后的大小：
一個近似的估計方法是：對于每個這樣的屬性 A，從乘積中除以除了 V(Ri,A) 中的最小值（即 _u_1）之外的所有 V(Ri,A) 的較大值的乘積

5.4.7 其他運算大小的估計

并
包的并：結(jié)果的大小正好是參數(shù)關(guān)系大小之和。
集合的并：結(jié)果的大小介于兩參數(shù)大小之和到兩參數(shù)中較大者之間。建議取中間值，如較大者加上較小者的一半。
交
結(jié)果的大小可以從0個元組（無交集時）到兩參數(shù)中較小者（完全重疊時）之間變化。建議取兩極端的平均值，即較小值的一半。
差
當計算 R_?_S 時，結(jié)果中的元組數(shù)可以從 T(R)（S 為空時）到 T(R)?_T_(S)（S 完全包含在 R 中時）之間變化。建議估計值取其平均值：T(R)?_T_(S)/2。
消除重復
如果 R(_a_1,_a_2,…,an) 是一個關(guān)系，則去重后 δ(R) 的大小理論上等于 R 中不同元組的數(shù)量。由于這個統(tǒng)計值通常不可得，需要取近似值。極端情況下，去重后的大小可以是 T(R)（無重復元組時）或1（所有元組都相同時）。另一個上限是可能存在的不同元組的最大數(shù)，即所有 V(R,ai)（i=1,2,…,n）的乘積。然而，這個數(shù)可能遠大于 T(R) 的實際值。一個合理的估計是取 T(R)/2 與所有 V(R,ai) 之積中的較小者。
分組（GROUP BY）與聚集
對于分組操作 γL(R)（其中 L 是分組屬性列表），結(jié)果中的元組數(shù)與分組數(shù)相同。
分組數(shù)的范圍可以從1（所有元組在分組屬性上都相同）到 T(R)（每個元組在分組屬性上都是唯一的）。
與去重類似，可以使用所有 V(R,A)（其中 A 是 L 中的屬性）的乘積作為分組數(shù)的上界。建議的估計值是 T(R)/2 與這個乘積中的較小者。

5.5 基于代價的計劃選擇介紹

5.5.1 大小參數(shù)估計值的獲取

元組數(shù)和不同值數(shù)目的獲取
元組數(shù)（T?）：通過對整個關(guān)系R進行一次掃描，可以簡單地計算出關(guān)系中的元組數(shù)。
不同值數(shù)目（V(R,A)）：通過掃描關(guān)系R并跟蹤每個屬性A的不同值，可以計算出該屬性列的不同值數(shù)目。
塊數(shù)（B?）的估計 : 如果關(guān)系R是聚簇存儲的，那么它所占用的塊數(shù)（B?）可以通過實際使用的塊數(shù)來計數(shù)。如果關(guān)系不是聚簇存儲的，或者需要更粗略的估計，則可以通過將元組數(shù)（T?）除以一個磁盤塊可以容納的R的元組個數(shù)來估算塊數(shù)。
直方圖的計算
等寬直方圖：將屬性值的范圍劃分為等寬的區(qū)間，并計算每個區(qū)間內(nèi)的元組數(shù)。如果遇到新的更小的值，可能需要調(diào)整區(qū)間的邊界。
等高直方圖：基于百分比來劃分區(qū)間，例如列出最小值、比最小值多p%的值、比最小值多2p%的值等，直到最大值。
最頻值直方圖：列出最常見的值及其出現(xiàn)次數(shù)，同時可能包含其他值的分組統(tǒng)計。
基于直方圖的連接大小估計
使用直方圖可以更準確地估計連接操作的結(jié)果大小。特別是當連接屬性的值顯式地出現(xiàn)在兩個關(guān)系的直方圖上時，可以精確地知道結(jié)果中有多少元組將具有該值。

5.5.2 統(tǒng)計量的計算

周期性更新的原因
穩(wěn)定性：數(shù)據(jù)庫中的統(tǒng)計量在短時間內(nèi)通常不會發(fā)生劇烈變化，因此沒有必要頻繁更新。
一致性：即使統(tǒng)計量不是絕對精確的，只要它們被一致地應用于所有查詢計劃，優(yōu)化器仍然能夠進行有效的比較和選擇。
性能考量：頻繁更新統(tǒng)計量會將統(tǒng)計量本身變成數(shù)據(jù)庫中的“熱點”，因為它們會被頻繁讀取和寫入，這會影響數(shù)據(jù)庫的整體性能。
取樣大小：取樣的元組數(shù)量需要根據(jù)統(tǒng)計精度和計算成本之間的平衡來確定。例如，可以選擇關(guān)系R的1%作為樣本。

5.5.4 枚舉物理計劃的方法

選擇最優(yōu)的物理查詢計劃：
**窮盡法：**窮盡法是一種最直接但可能最耗時的方法，它嘗試所有可能的物理計劃組合，并對每個計劃進行代價估計，最終選擇代價最小的計劃。這種方法適用于小型數(shù)據(jù)庫或查詢，但對于大型數(shù)據(jù)庫和復雜查詢來說，其計算量將變得不可接受。
自頂向下與自底向上方法
自頂向下（Top-Down）：從邏輯查詢計劃樹的根部開始，逐級向下考慮每個運算符的可能實現(xiàn)，并計算每種組合的代價。這種方法在每一步都需要評估所有可能的子計劃，并可能導致大量的重復計算。
自底向上（Bottom-Up）：從邏輯查詢樹的葉子節(jié)點（即基本關(guān)系）開始，逐級向上計算每個子表達式的最優(yōu)計劃，并在構(gòu)建較大子表達式的計劃時只考慮較小子表達式的最優(yōu)計劃。這種方法通常與動態(tài)規(guī)劃相結(jié)合，以減少重復計算并提高效率。
**動態(tài)規(guī)劃：**動態(tài)規(guī)劃是自底向上方法的一個變種，它通過保存子問題的解來避免重復計算。對于每個子表達式，動態(tài)規(guī)劃方法只保留其最小代價的計劃，并在構(gòu)建更大子表達式的計劃時利用這些已保存的最優(yōu)解。這種方法雖然不保證總是找到全局最優(yōu)解，但在許多情況下都能獲得很好的結(jié)果。
**Selinger 風格的優(yōu)化：**是對動態(tài)規(guī)劃方法的一種改進。它不僅記錄了每個子表達式的最小代價計劃，還記錄了那些具有較高代價但結(jié)果順序?qū)ι蠈舆\算符有用的計劃。這種方法利用了查詢計劃中的某些特性（如排序、分組和連接屬性），以期望從非最優(yōu)的子表達式計劃中構(gòu)建出整體最優(yōu)的查詢計劃。
啟發(fā)式選擇：基于一系列啟發(fā)式規(guī)則來選擇物理計劃。這些規(guī)則通?；诮?jīng)驗或統(tǒng)計信息，旨在快速找到近似最優(yōu)的查詢計劃。例如，如果連接的一個參數(shù)在連接屬性上有索引，則采用索引連接；如果需要對多個關(guān)系進行并或交操作，則先對最小關(guān)系進行組合等。啟發(fā)式選擇方法通常比窮盡法更快，但可能無法找到全局最優(yōu)解。
**分支界定計劃枚舉：**通過啟發(fā)式方法找到一個好的初始物理計劃，并以此為基準來剪枝搜索空間。在搜索過程中，任何代價高于當前已知最優(yōu)計劃的計劃都將被放棄，因為它們不可能成為更優(yōu)的完整查詢計劃的一部分。這種方法可以顯著減少搜索空間的大小，并提高搜索效率。
爬山法：從一個初始的物理計劃開始，通過不斷地對計劃進行小的修改（如替換運算符的實現(xiàn)方法、重新排序連接等）來尋找代價更低的鄰近計劃。當無法再通過小修改來降低計劃的代價時，算法停止并返回當前的計劃作為最優(yōu)解。這種方法可能陷入局部最優(yōu)解，但通常能夠快速找到一個可接受的解決方案。

5.6連接順序的選擇

5.6.1 連接的左右參數(shù)的意義

**一趟連接：**通常選擇較小的關(guān)系作為左參數(shù)（構(gòu)造用關(guān)系），并將其加載到內(nèi)存中，構(gòu)建成一個哈希表。這個哈希表使得數(shù)據(jù)查找變得非常高效。然后，將較大的關(guān)系（右參數(shù)，探查用關(guān)系）分批讀入內(nèi)存，并將每個元組與哈希表中的元組進行匹配，從而執(zhí)行連接操作。這種策略利用了較小的關(guān)系能夠完全加載到內(nèi)存中并構(gòu)建高效索引的優(yōu)勢。
嵌套循環(huán)連接：左參數(shù)通常被選作外部循環(huán)關(guān)系。這意味著查詢優(yōu)化器會遍歷左參數(shù)中的每一個元組，并將其與右參數(shù)中的所有元組進行比較，以查找匹配項。如果左參數(shù)較小，則外部循環(huán)的開銷相對較小，這有助于提升整體性能。如果左參數(shù)很大，則可能需要考慮其他連接策略。
索引連接：右參數(shù)通常被認為是有索引的關(guān)系。這意味著在連接過程中，查詢優(yōu)化器會利用右參數(shù)的索引來快速定位匹配的元組，而不是遍歷整個關(guān)系。因此，選擇擁有有效索引的關(guān)系作為右參數(shù)可以顯著提高連接操作的效率。索引連接特別適用于當右參數(shù)很大，但可以通過索引快速訪問其特定部分時。

5.6.3 左深連接樹

左深樹

濃密樹

右深樹
左深樹的數(shù)量與所有樹的數(shù)量
對于給定數(shù)目的關(guān)系（即樹葉），所有可能的樹形結(jié)構(gòu)（包括非左深樹和左深樹）的數(shù)量是巨大的，特別是隨著關(guān)系數(shù)量的增加，這個數(shù)量呈指數(shù)級增長。相比之下，左深樹作為這些所有可能樹形結(jié)構(gòu)的一個子集，其數(shù)量雖然也很大，但增長速度要慢得多。這是因為左深樹的結(jié)構(gòu)限制了樹的形狀，使得每個節(jié)點最多只能有一個右子節(jié)點（且該右子節(jié)點可以是另一個連接或關(guān)系），從而減少了可能的組合方式。
左深樹與連接算法的交互
一趟連接：左深樹使得優(yōu)化器能夠選擇較小的關(guān)系作為構(gòu)建哈希表的關(guān)系（即左子樹），而將較大的關(guān)系或連接結(jié)果作為探查的關(guān)系（即右子樹）。這種安排可以最大化哈希表的效率，因為哈希表可以一次性構(gòu)建并用于多個連接操作。
嵌套循環(huán)連接：在嵌套循環(huán)連接中，左深樹允許優(yōu)化器將較小的關(guān)系放在外層循環(huán)（即左子樹），而將較大的關(guān)系或連接結(jié)果放在內(nèi)層循環(huán)（即右子樹）。這樣可以減少內(nèi)層循環(huán)的迭代次數(shù)，從而提高整體連接的效率。
**左深樹中的運算符：**左深樹或右深樹中的樹葉（即基本關(guān)系）不僅可以是簡單的關(guān)系，還可以是包含其他運算符（如選擇、投影）的內(nèi)部節(jié)點。這意味著在構(gòu)建查詢計劃時，優(yōu)化器可以靈活地將這些運算符應用于連接的輸入或輸出，以進一步減少處理的數(shù)據(jù)量并優(yōu)化查詢性能。

5.6.4 通過動態(tài)規(guī)劃來選擇連接順序和分組

1. 定義狀態(tài)和問題
在動態(tài)規(guī)劃中，我們首先定義狀態(tài)。在這個場景下，狀態(tài)可以定義為包含一定數(shù)量表的集合，以及這些表之間可能的連接順序和成本。目標是找到包含所有目標表的一個集合的最優(yōu)連接順序，使得總成本最小。
2. 構(gòu)建代價表
代價表（或稱為DP表）用于存儲中間結(jié)果，即對于每個可能的表集合，其最優(yōu)連接順序及其對應的成本。這個表通常通過歸納法來填充。
基礎(chǔ)情況：對于只包含一個表的集合，其最優(yōu)連接順序就是該表本身，成本為0（因為沒有進行連接）。
歸納步驟：對于包含多個表的集合，我們考慮所有可能的子集劃分，并計算每種劃分下的連接成本。我們選擇成本最小的劃分作為該集合的最優(yōu)連接順序。
3. 考慮左深樹與其他樹形
左深樹：在只考慮左深樹的情況下，連接順序的選擇相對簡單。對于集合R中的k個表，我們嘗試將R劃分為R-i和{i}（其中i是R中的一個表），并計算R-i與i連接的成本。我們選擇成本最小的劃分作為最優(yōu)解。
所有可能的樹形：如果考慮所有可能的樹形，問題變得更加復雜。我們需要考慮所有可能的子集劃分，并計算每種劃分下將子集連接起來的成本。這通常涉及更復雜的成本函數(shù)和更多的計算。
4. 計算成本和表達式
對于每種劃分，我們需要計算兩個主要值：
連接成本：這是將兩個子集連接起來的成本，通常基于它們的大小、索引使用情況、以及可能的公共屬性等因素。
結(jié)果大小：這是連接操作后結(jié)果集的大小，用于后續(xù)連接的成本計算。
5. 表達式構(gòu)建
在找到最優(yōu)連接順序的同時，我們還需要構(gòu)建相應的表達式，這個表達式描述了表之間的連接順序。在左深樹的情況下，表達式就是表的順序；在更一般的情況下，表達式可能包括嵌套的連接操作。
6. 應用到實際查詢
最終，我們得到的代價表和相應的表達式可以被用來優(yōu)化實際的數(shù)據(jù)庫查詢。通過選擇成本最低的連接順序，數(shù)據(jù)庫管理系統(tǒng)可以減少查詢的執(zhí)行時間，提高查詢效率。

5.6.5 帶有更具體的代價函數(shù)的動態(tài)規(guī)劃

僅基于關(guān)系大小來估計連接成本可能會忽略一些重要的實現(xiàn)細節(jié)，如索引的使用、磁盤I/O成本等。為了更準確地估計連接成本，我們可以對動態(tài)規(guī)劃算法進行修改，以納入更具體的代價函數(shù)，如磁盤I/O成本。在動態(tài)規(guī)劃算法中，我們可以修改代價的計算方式，以考慮實際的連接成本。這通常涉及以下幾個方面：
磁盤I/O成本：對于每個關(guān)系，我們需要知道其數(shù)據(jù)在磁盤上的存儲方式（如是否索引），以及訪問這些數(shù)據(jù)所需的磁盤I/O次數(shù)。
連接算法：不同的連接算法（如嵌套循環(huán)連接、排序合并連接、散列連接）具有不同的成本特性。我們需要根據(jù)關(guān)系的特性和可用索引來選擇最合適的連接算法。
中間結(jié)果的大小：連接操作的結(jié)果大小也會影響后續(xù)操作的成本。較大的中間結(jié)果可能需要更多的磁盤空間，并增加后續(xù)操作的I/O成本。
**Selinger風格優(yōu)化：**是一種更全面的查詢優(yōu)化方法，它不僅考慮連接操作的成本，還考慮查詢結(jié)果的排序和存儲順序。這種方法對于生成高效的查詢計劃特別有用，特別是當查詢結(jié)果需要按照特定順序返回給用戶時。在Selinger風格優(yōu)化中，對于每個可能被連接的關(guān)系集合，我們不僅計算連接的最小成本，還考慮生成以幾個“感興趣”的順序中的任意一個順序存儲的關(guān)系的最小成本。這些“感興趣”的順序可能包括：
對后續(xù)排序連接有利的順序：如果查詢計劃中包含排序連接，那么生成已經(jīng)排序的中間結(jié)果可能會減少后續(xù)操作的成本。
用戶期望的輸出順序：如果查詢結(jié)果需要按照特定順序返回給用戶，那么生成符合這一順序的中間結(jié)果可能會減少最終排序的成本。

5.6.6 選擇連接順序的貪婪算法

在數(shù)據(jù)庫查詢優(yōu)化中，特別是在處理多表連接（JOINs）時，選擇最優(yōu)的連接順序?qū)τ谔岣卟樵冃手陵P(guān)重要。當連接的表數(shù)量增多時，可能的連接順序組合呈指數(shù)級增長，這使得窮盡搜索所有可能的連接順序變得不現(xiàn)實。因此，啟發(fā)式算法如貪婪算法成為了一個實用的選擇。
貪婪算法在連接順序選擇中的應用
貪婪算法在選擇連接順序時，遵循局部最優(yōu)原則，即每一步都選擇當前看來最好的選擇，從而希望導致全局最優(yōu)解。
**初始化：**選擇一個或多個基礎(chǔ)表（通常是較小的表或者索引良好的表）作為起始點。初始化一個空的連接樹，這個樹開始時只包含選定的基礎(chǔ)表。
**迭代選擇：**在所有尚未被添加到當前連接樹中的表中，選擇一個表與當前連接樹的根（或某個節(jié)點）進行連接，這個選擇基于某種估計的成本或大小（如基于統(tǒng)計信息的行數(shù)估計）。將選中的表添加到連接樹中，形成新的連接樹結(jié)構(gòu)。

5.7 物理查詢計劃選擇的完成

1. 算法選擇
在邏輯查詢計劃轉(zhuǎn)換為物理查詢計劃的過程中，需要為各個操作選擇合適的算法。
2. 中間結(jié)果的物化和流水操作
物化：物化是指將查詢的中間結(jié)果完全存儲在磁盤上。這種方式在內(nèi)存不足或需要重用中間結(jié)果時非常有用。然而，物化會增加磁盤IO操作，降低查詢效率。
流水操作：流水操作是指在執(zhí)行查詢時，中間結(jié)果只在內(nèi)存中臨時存儲，不保存到磁盤上。這種方式可以減少磁盤IO，但要求系統(tǒng)有足夠的內(nèi)存來支持所有中間結(jié)果的存儲。

5.7.1 選取一個選擇方法

分析不同算法的代價
1. 表掃描算法與過濾器步驟結(jié)合
代價估計：如果R被聚集（Clustered）：B?，其中B?是關(guān)系R的數(shù)據(jù)塊數(shù)量。聚集意味著數(shù)據(jù)在物理存儲上按某個特定屬性（通常是主鍵或索引鍵）的順序排列，但這對于表掃描的代價估計通常不直接影響，因為表掃描仍需檢查所有塊。
如果R沒有被聚集：T?，這里T?可能表示關(guān)系R中所有元組的總數(shù)，但在I/O代價的上下文中，更準確地應該是T?除以每塊能容納的元組數(shù)，但通常簡化為B?，即數(shù)據(jù)塊的數(shù)量，因為I/O操作以塊為單位進行。
2. 利用等值索引掃描
代價估計：如果索引是聚集的：B?/V(R,a)，其中V(R,a)是屬性a在關(guān)系R中的唯一值數(shù)量（或近似值）。聚集索引意味著數(shù)據(jù)本身就是按照索引的順序存儲的，因此可以更快地定位到滿足條件的元組。但代價估計中仍然考慮了整個關(guān)系的數(shù)據(jù)塊數(shù)量，因為即使索引是聚集的，也可能需要遍歷多個塊來找到所有匹配的元組。
如果索引不是聚集的：T?/V(R,a)。非聚集索引不包含數(shù)據(jù)本身，只包含指向數(shù)據(jù)塊的指針，因此需要額外的I/O來檢索實際的數(shù)據(jù)行。但在這個簡化的估計中，我們假設通過索引可以快速定位到包含所需數(shù)據(jù)的塊。
3. 利用不等值索引掃描
如果索引是聚集的：B?/3.9。這個估計試圖反映不等值查詢可能需要檢查比等值查詢更多的塊，因為不等值條件可能匹配多個連續(xù)的數(shù)據(jù)塊。然而，這個數(shù)字3.9是一個高度簡化的假設，實際中可能需要更復雜的模型來準確估計。
如果索引不是聚集的：T?/3。對于非聚集索引，不等值查詢同樣需要額外的I/O來檢索數(shù)據(jù)行，但代價估計的具體數(shù)字取決于索引和數(shù)據(jù)的實際情況。

5.7.3 /4流水操作與物化

流水操作：流水操作是一種更有效的方法，它允許同時交錯進行多個運算，減少了磁盤I/O的需求。在流水操作中，一個運算產(chǎn)生的結(jié)果元組直接傳遞給需要它的運算，而不需要將中間結(jié)果存儲在磁盤上。這種方法通常由迭代器網(wǎng)絡執(zhí)行，迭代器網(wǎng)絡中的迭代器在適當?shù)臅r候互相調(diào)用，實現(xiàn)數(shù)據(jù)的流動。
**一元流水：**一元流水操作是指涉及單個輸入源的操作，如選擇（Selection）和投影（Projection）。在這種操作中，消費者（即需要結(jié)果的查詢部分）通過調(diào)用迭代器的GetNext()方法來請求下一個元組。
**二元流水：**二元運算涉及兩個輸入?yún)?shù)，如連接（Join）或合并（Union）操作。二元運算的結(jié)果也可以進行流水操作。我們使用一個緩沖區(qū)將結(jié)果傳遞給消費者，一次一塊。然而，計算結(jié)果和消費結(jié)果所需的其他緩沖區(qū)數(shù)目是不同的，它們?nèi)Q于結(jié)果的大小以及參數(shù)的大小。我們將使用一個擴展的例子來演示折中和機會。

5.7.7 物理運算的排序

物理查詢計劃樹的分解與執(zhí)行
樹的分解：當查詢計劃以樹的形式表示時，我們可以通過物化（即存儲中間結(jié)果）來分解這棵樹。物化意味著在樹中的某些節(jié)點處，將中間結(jié)果存儲在磁盤上，以便后續(xù)運算使用。這樣做可以將復雜的查詢計劃分解成一系列較小的、更易于管理的子樹。
子樹的執(zhí)行順序：在物化策略下，子樹的執(zhí)行順序通常是按照從下到上、從左到右的前序遍歷順序進行的。這種順序確保了每個子樹在其依賴的子樹完成執(zhí)行后才能開始執(zhí)行，從而保證了數(shù)據(jù)的正確性和完整性。
迭代器網(wǎng)絡與流水操作
對于采用流水操作（也稱為流水線操作）的物理查詢計劃，迭代器網(wǎng)絡是實現(xiàn)這一策略的關(guān)鍵。迭代器網(wǎng)絡由一系列相互連接的迭代器組成，每個迭代器代表查詢計劃中的一個運算。迭代器之間通過調(diào)用GetNext等方法來傳遞數(shù)據(jù)，從而實現(xiàn)了數(shù)據(jù)的直接傳遞和連續(xù)處理，而無需將中間結(jié)果存儲在磁盤上。
迭代器網(wǎng)絡中的事件順序
在迭代器網(wǎng)絡中，事件的順序是由各個迭代器之間的交互和調(diào)用關(guān)系決定的。具體來說，當一個迭代器需要數(shù)據(jù)時，它會調(diào)用其上游迭代器的GetNext方法。這個調(diào)用會觸發(fā)上游迭代器執(zhí)行必要的運算，并將結(jié)果返回給下游迭代器。通過這種方式，整個查詢計劃中的運算被同步地執(zhí)行，而事件的確切順序則是由這些調(diào)用關(guān)系決定的。
查詢優(yōu)化與執(zhí)行代碼生成
基于上述策略，查詢優(yōu)化器可以為給定的查詢生成相應的執(zhí)行代碼。這些代碼通常是一系列函數(shù)調(diào)用的序列，它們按照預定的順序執(zhí)行查詢計劃中的各個運算。通過這種方式，數(shù)據(jù)庫系統(tǒng)能夠高效地處理查詢請求，并返回準確的結(jié)果。

第6章系統(tǒng)故障對策

日志：是支持數(shù)據(jù)可恢復性的基礎(chǔ)技術(shù)。日志以安全的方式記錄了數(shù)據(jù)庫中所有變更的歷史，包括數(shù)據(jù)的增、刪、改操作。
日志類型

• Undo 日志：記錄了如何將數(shù)據(jù)庫從當前狀態(tài)回滾到某個之前的狀態(tài)。主要用于處理事務的撤銷操作，確保在事務失敗或需要回滾時，數(shù)據(jù)庫能夠恢復到事務開始前的狀態(tài)。
• Redo 日志：記錄了如何將數(shù)據(jù)庫從某個舊狀態(tài)重新應用更改以恢復到當前狀態(tài)。在系統(tǒng)故障后，可以使用這些日志來重做所有未完成的更改，以恢復數(shù)據(jù)庫的最新狀態(tài)。
• Undo/Redo 日志：結(jié)合了上述兩種日志的特性，既能夠回滾也能夠重做數(shù)據(jù)庫的操作，提供了更靈活的恢復策略。

Undo日志和Redo日志在數(shù)據(jù)庫系統(tǒng)中各有其獨特的作用和應用場景。Undo日志主要用于事務的回滾操作，確保事務的原子性和一致性；而Redo日志則主要用于系統(tǒng)的恢復和故障處理過程，確保數(shù)據(jù)庫在崩潰或故障后能夠恢復到一致的狀態(tài)。兩者共同協(xié)作，為數(shù)據(jù)庫系統(tǒng)的可靠性和穩(wěn)定性提供了重要保障。

**檢查點技術(shù)：**減少恢復過程中需要檢查的日志量，提高恢復效率。
工作原理：定期在數(shù)據(jù)庫系統(tǒng)中創(chuàng)建一個檢查點，該點表示此時刻數(shù)據(jù)庫的狀態(tài)是一致的。在檢查點時刻，系統(tǒng)會記錄當前所有事務的狀態(tài)（如已提交、未提交等）和日志信息的位置。如果系統(tǒng)發(fā)生故障，恢復過程只需要從最近的檢查點開始，而不是從頭開始檢查日志，從而大大減少了恢復所需的時間和資源。

6.1 可恢復操作的問題和模型

6.1.1 故障模式

1. 錯誤數(shù)據(jù)輸入
:::danger
錯誤數(shù)據(jù)輸入可能由人為因素（如鍵盤輸入錯誤）或系統(tǒng)錯誤引起。這些錯誤可能難以被自動檢測，特別是當錯誤數(shù)據(jù)在格式上仍然符合規(guī)則時（如電話號碼中的一位數(shù)字錯誤）。
:::

應對措施
編寫約束：通過數(shù)據(jù)庫管理系統(tǒng)提供的約束功能（如NOT NULL、UNIQUE、CHECK等），限制輸入數(shù)據(jù)的類型和范圍，確保數(shù)據(jù)在邏輯上的一致性。
觸發(fā)器：使用觸發(fā)器在數(shù)據(jù)被插入、更新或刪除時自動執(zhí)行特定的檢查或操作，以識別并處理潛在的數(shù)據(jù)錯誤。

2. 介質(zhì)故障
:::danger
介質(zhì)故障包括磁盤的局部故障（如單個扇區(qū)損壞）和全局故障（如磁頭損壞導致整個磁盤不可訪問）。
:::

應對措施：
奇偶校驗：利用與磁盤扇區(qū)相關(guān)聯(lián)的奇偶校驗來檢測并糾正局部故障。
RAID技術(shù)：通過配置RAID（獨立磁盤冗余陣列）來提高數(shù)據(jù)的可用性和容錯性。RAID可以通過數(shù)據(jù)條帶化、鏡像、校驗等方式來減少單個磁盤故障對數(shù)據(jù)完整性的影響。
備份：定期創(chuàng)建數(shù)據(jù)庫的完整或增量備份，并將備份存儲在遠離主數(shù)據(jù)庫的安全位置。這樣，在發(fā)生介質(zhì)故障時，可以通過恢復備份來恢復數(shù)據(jù)。
分布式冗余拷貝：在多個物理節(jié)點上保存數(shù)據(jù)庫的冗余拷貝，以提高系統(tǒng)的可靠性和容錯性。同時，需要維護這些拷貝之間的一致性，確保數(shù)據(jù)的準確性。

3. 災難性故障
:::danger
災難性故障包括數(shù)據(jù)庫所在物理環(huán)境的完全毀壞，如火災、爆炸或惡意破壞，導致所有數(shù)據(jù)介質(zhì)同時失去作用。
:::

備份和冗余：與介質(zhì)故障相似，但備份需要更加頻繁和全面，以確保在災難發(fā)生后能夠恢復盡可能多的數(shù)據(jù)。
分布式冗余拷貝：將數(shù)據(jù)庫的冗余拷貝分布在不同地理位置的多個節(jié)點上，以減少單一地點災難對系統(tǒng)的影響。

4. 系統(tǒng)故障
   :::danger
   系統(tǒng)故障通常指的是導致事務狀態(tài)丟失的問題，如掉電或軟件錯誤。由于內(nèi)存是易失性的，掉電會導致主存中的數(shù)據(jù)丟失，包括事務的當前狀態(tài)和修改結(jié)果。
   :::

日志記錄：使用非易失性的日志來記錄所有對數(shù)據(jù)庫的更新操作。這樣，在系統(tǒng)故障后，可以通過日志來恢復事務的狀態(tài)和數(shù)據(jù)庫的一致性。
恢復機制：開發(fā)復雜的恢復機制，確保日志記錄能夠在不受故障干擾的情況下進行。這些機制通常包括日志的持久化、事務的原子性保證以及恢復算法等。

6.1.2 關(guān)于事務的進一步討論

事務是執(zhí)行數(shù)據(jù)庫操作的基本單位，它確保了數(shù)據(jù)的一致性和完整性。
事務的四個基本特性（ACID特性）：
原子性（Atomicity）：事務中的所有操作要么全部完成，要么全部不執(zhí)行，不能存在部分執(zhí)行的情況。
一致性（Consistency）：事務執(zhí)行的結(jié)果必須使數(shù)據(jù)庫從一個一致性狀態(tài)轉(zhuǎn)變到另一個一致性狀態(tài)。
隔離性（Isolation）：并發(fā)執(zhí)行的事務之間互不干擾，每個事務都獨立運行，如同沒有其他事務在并發(fā)執(zhí)行一樣。
持久性（Durability）：一旦事務被提交，它對數(shù)據(jù)庫的修改就是永久性的，即使系統(tǒng)發(fā)生故障也不會丟失。
日志管理器負責維護日志，確保事務的日志記錄能夠正確地存儲在磁盤上。由于日志記錄最初是存儲在內(nèi)存中的，因此它們需要在適當?shù)臅r候被拷貝到磁盤上，以確保數(shù)據(jù)的持久性。日志管理器與緩沖區(qū)管理器交互，以管理日志記錄的存儲和檢索。
恢復管理器在數(shù)據(jù)庫系統(tǒng)崩潰時被激活。它檢查日志記錄，并使用這些記錄來恢復數(shù)據(jù)庫到一致的狀態(tài)?；謴凸芾砥骺赡苄枰貪L未提交的事務，或者重做已提交但尚未寫入磁盤的事務，以確保數(shù)據(jù)庫的完整性和一致性。

6.1.3 事務的正確執(zhí)行

數(shù)據(jù)庫元素與狀態(tài)
數(shù)據(jù)庫元素（如關(guān)系、磁盤塊/頁、元組等）是數(shù)據(jù)庫操作的基本單位。選擇磁盤塊或頁作為數(shù)據(jù)庫元素的原因在于，它們通常是數(shù)據(jù)庫管理系統(tǒng)（DBMS）中數(shù)據(jù)讀寫操作的最小單位。這樣做可以簡化事務日志和恢復機制的設計，因為每次事務操作都可以針對完整的磁盤塊進行記錄，從而避免了部分數(shù)據(jù)寫入導致的復雜問題。
數(shù)據(jù)庫狀態(tài)的一致性
數(shù)據(jù)庫狀態(tài)的一致性不僅要求滿足數(shù)據(jù)庫模式中的顯式約束（如鍵約束、值約束等），還需要滿足隱式約束。隱式約束可能來源于業(yè)務邏輯、數(shù)據(jù)完整性規(guī)則或用戶界面的限制等。確保數(shù)據(jù)庫狀態(tài)的一致性對于維護數(shù)據(jù)的完整性和可靠性至關(guān)重要。
事務的正確性原則
如果事務在沒有其他任何事務和系統(tǒng)錯誤的情況下執(zhí)行，并且在它開始執(zhí)行時數(shù)據(jù)庫處于一致的狀態(tài)，那么當事務結(jié)束時數(shù)據(jù)庫仍然處于一致的狀態(tài)。

6.1.4 事務的原語操作

1. INPUT(X)
INPUT(X) 操作負責將包含數(shù)據(jù)庫元素 X 的磁盤塊讀取到主存中的一個緩沖區(qū)中。
2. READ(X, t)
READ(X, t) 操作首先檢查包含數(shù)據(jù)庫元素 X 的塊是否在主存緩沖區(qū)中。如果不在，則執(zhí)行 INPUT(X) 將其加載到緩沖區(qū)。然后，將緩沖區(qū)中 X 的值賦給事務的局部變量 t。
3. WRITE(X, t)
WRITE(X, t) 操作首先檢查包含數(shù)據(jù)庫元素 X 的塊是否在主存緩沖區(qū)中。如果不在，則執(zhí)行 INPUT(X)。然后，將事務局部變量 t 的值寫入緩沖區(qū)中 X 的位置。
4. OUTPUT(X)
OUTPUT(X) 操作負責將包含數(shù)據(jù)庫元素 X 的緩沖區(qū)中的塊寫回到磁盤上。這個操作是確保數(shù)據(jù)持久性的關(guān)鍵步驟。

6.2 undo 日志

Undo 日志：記錄了如何將數(shù)據(jù)庫從當前狀態(tài)回滾到某個之前的狀態(tài)。主要用于處理事務的撤銷操作，確保在事務失敗或需要回滾時，數(shù)據(jù)庫能夠恢復到事務開始前的狀態(tài)。

6.2.1 日志記錄

日志記錄類型的詳細解釋
1. 記錄
含義：這個記錄表示事務T已經(jīng)開始執(zhí)行。它標記了事務在日志中的起始點，有助于在恢復過程中識別哪些事務可能尚未完成。
作用：在恢復過程中， 記錄用于確認事務的存在和開始時間。雖然它本身不直接參與恢復操作，但它是事務日志完整性的重要組成部分。
2. 記錄
含義：這個記錄表示事務T已成功完成，并且其對數(shù)據(jù)庫的所有修改都應該是永久的。然而由于緩沖區(qū)管理器的行為，這些修改可能尚未寫入磁盤。
作用：在恢復過程中， 記錄是確定哪些事務應該被視為成功完成的依據(jù)。然而，由于磁盤寫入的不確定性，恢復管理器可能需要額外的步驟來確保所有已提交事務的修改都被正確地寫入磁盤。
3. 記錄
含義：這個記錄表示事務T由于某種原因（如內(nèi)部錯誤、死鎖、超時等）不能成功完成。
作用：在恢復過程中， 記錄用于標識需要回滾（撤銷）的事務?；謴凸芾砥鲗⑹褂胾ndo日志中的更新記錄來回滾這些事務所做的所有修改，以確保數(shù)據(jù)庫的一致性。
4. 更新記錄 <T, X, v>
含義：這個三元組表示事務T修改了數(shù)據(jù)庫元素X，而X的原始值是v。它記錄了事務對數(shù)據(jù)庫的具體修改。
作用：更新記錄是undo日志的核心。在恢復過程中，如果事務T被中止（即出現(xiàn)記錄），恢復管理器將使用這些更新記錄來將數(shù)據(jù)庫元素X的值恢復到它們在事務T開始之前的狀態(tài)。這樣，中止事務對數(shù)據(jù)庫的影響就被消除了。
undo日志的局限性：undo日志僅記錄舊值，不記錄新值。這意味著它只能用于回滾事務，而不能用于重做已提交事務的修改。

6.2.2 undo 日志規(guī)則

規(guī)則U1：如果事務T修改了數(shù)據(jù)庫元素X，那么表示這一修改的日志記錄（形如<T, X, v>，其中v是X的舊值）必須在X的新值被寫入磁盤之前寫入磁盤。這條規(guī)則確保了即使在系統(tǒng)崩潰時，也有足夠的信息來撤銷事務T對X所做的修改，從而恢復數(shù)據(jù)庫的一致性。
規(guī)則U2：如果事務提交，那么它的COMMIT日志記錄（）必須在事務改變的所有數(shù)據(jù)庫元素都已被寫入磁盤之后寫入磁盤，但應盡快。這條規(guī)則確保了提交操作是持久的，即一旦事務被提交，其修改就不會因為系統(tǒng)故障而丟失。

6.2.3 使用 undo 日志的恢復

恢復過程
撤銷（Undo）未提交的事務：對于那些在崩潰時尚未提交的事務，恢復管理器需要撤銷它們所做的所有修改，以確保這些事務不會留下任何不一致的狀態(tài)。
重做（Redo）可能丟失的已提交事務的修改：如果某些已提交事務的修改因為系統(tǒng)崩潰而未能完全寫入磁盤，恢復管理器需要重做這些修改。
識別事務狀態(tài)
已提交事務：這些事務的記錄已經(jīng)寫入日志。它們的修改被認為是有效的，不需要撤銷。
未提交事務：這些事務的記錄存在，但記錄不存在。它們的修改需要被撤銷，以恢復數(shù)據(jù)庫到一致狀態(tài)。
撤銷未提交事務的修改
恢復管理器從日志的末尾開始掃描，向前移動。
當遇到<T, X, v>記錄時，如果尚未掃描到記錄，則意味著事務T未提交，需要撤銷對X的修改?；謴凸芾砥鲿的值改回日志中記錄的修改前的值。
如果已經(jīng)掃描到記錄，則不對該事務的修改進行任何操作。
處理事務結(jié)束
在完成所有必要的撤銷操作后，恢復管理器會為每個未完成的事務T寫入記錄到日志中，并刷新日志，以確保這些記錄被持久化。

6.2.4 檢查點

檢查點機制通過定期地記錄數(shù)據(jù)庫和日志文件的狀態(tài)，來確保在系統(tǒng)崩潰后能夠快速地恢復到最近的一個一致狀態(tài)。

1. 停止新事務。
2. 等待所有活躍事務完成：這包括等待所有事務提交或中止，并在日志中記錄COMMIT或ABORT。這一步確保了在檢查點時刻，所有未完成的事務狀態(tài)都是已知的。
3. 刷新日志到磁盤：將內(nèi)存中的日志記錄強制寫入磁盤，確保日志的持久性。
4. 寫入記錄：在日志中寫入一個特殊的檢查點記錄，表明此點之后的所有事務都是在此檢查點之后開始的。

記錄用于標記檢查點（Checkpoint）的完成。在記錄之后的所有事務都是在當前檢查點之后開始的。記錄包含了以下關(guān)鍵信息：
時間戳：記錄了檢查點完成的具體時間點，這對于后續(xù)的恢復操作至關(guān)重要。
狀態(tài)信息：可能包含了數(shù)據(jù)庫在檢查點時刻的特定狀態(tài)信息，如活躍事務列表、已提交事務的日志位置等，這些信息有助于恢復過程快速定位到正確的恢復起點。
日志位置：在某些實現(xiàn)中，記錄還可能包含當前日志文件的寫入位置或檢查點相關(guān)的日志序列號（LSN），這有助于恢復過程確定從哪些日志記錄開始應用或忽略。
通過記錄，數(shù)據(jù)庫系統(tǒng)能夠在發(fā)生崩潰或需要恢復時，快速定位到最近的檢查點，并僅從該檢查點之后的日志記錄中恢復未完成的事務或應用已提交事務的修改。這大大減少了恢復過程所需處理的數(shù)據(jù)量，提高了恢復效率。

5. 重新開始接收事務：一旦檢查點完成，系統(tǒng)可以繼續(xù)接收新的事務。
   

6.2.5 非靜止檢查點

傳統(tǒng)的靜止檢查點要求在檢查點期間停止接收新的事務，等待所有當前活躍的事務完成，并將它們的修改寫入磁盤。然而，這種方法會導致系統(tǒng)暫停服務，影響用戶體驗。
非靜止檢查點技術(shù)允許在系統(tǒng)進行檢查點的同時，繼續(xù)接收和處理新的事務
非靜止檢查點的步驟

1. 開始檢查點：

系統(tǒng)在日志中寫入一個特殊的<STARTCKPT(T,…,T)>記錄，其中T,…,T是所有當前活躍事務的標識符。
這個記錄表明，從現(xiàn)在開始，系統(tǒng)將開始一個檢查點過程，但會繼續(xù)接收新的事務。

2. 等待活躍事務完成：

系統(tǒng)繼續(xù)運行，允許新事務進入并處理。
同時，系統(tǒng)等待記錄中列出的所有活躍事務完成（提交或中止），并將它們的修改寫入磁盤。

3. 結(jié)束檢查點：

當所有活躍事務都完成后，系統(tǒng)在日志中寫入一個記錄。
這個記錄表明，檢查點過程已完成，所有在之前開始的事務都已經(jīng)處理完畢。
恢復過程
當系統(tǒng)從故障中恢復時，它會從日志的尾部開始向后掃描：
如果先遇到記錄，那么恢復過程可以安全地忽略之前的所有日志記錄，因為它們所代表的事務更新已經(jīng)穩(wěn)定地存儲在數(shù)據(jù)庫中。恢復過程將繼續(xù)向后掃描，直到遇到下一個記錄。
如果先遇到記錄但還沒有記錄，那么系統(tǒng)崩潰發(fā)生在檢查點過程中?；謴瓦^程需要找到并撤銷那些在和崩潰之間開始且未完成的事務，以及那些在中列出但尚未在崩潰前完成的事務。

6.3 redo 日志

1. undo 日志在恢復時消除未完成事務的影響并忽略已提交事務，而redo日志忽略未完成的事務并重復已提交事務所做的改變。
2. undo日志要求我們在COMMIT日志記錄到達磁盤前將修改后的數(shù)據(jù)庫元素寫到磁盤，而redo日志要求COMMIT記錄在任何修改后的值到達磁盤前出現(xiàn)在磁盤上。
3. 對于undo日志，恢復時需要舊值（即事務開始前的值）來撤銷更改。而對于redo日志，恢復時需要的是新值（即事務提交后應該存在于數(shù)據(jù)庫中的值）來重做更改。
   

6.3.1 redo 日志規(guī)則

1. 指出被修改元素的日志記錄：

當事務T需要修改數(shù)據(jù)庫元素X時，首先會生成一條形如<T, X, v>的日志記錄，其中T是事務標識，X是被修改的數(shù)據(jù)庫元素標識，v是新的值。這條記錄會立即被寫入到日志文件中，但此時數(shù)據(jù)庫元素X本身還沒有被修改。

2. COMMIT 日志記錄：

當事務T完成所有修改并準備提交時，會生成一條的日志記錄，表示事務T已經(jīng)成功完成。這條記錄同樣會被寫入到日志文件中，并且它必須出現(xiàn)在所有與該事務相關(guān)的更新記錄之后。

3. 改變的數(shù)據(jù)庫元素自身：

只有當上述所有與事務T相關(guān)的日志記錄（包括更新記錄和提交記錄）都成功寫入到磁盤上的日志文件中之后，事務T才會實際修改數(shù)據(jù)庫元素X的值，并將這個新的值寫入到磁盤上的數(shù)據(jù)庫文件中。
這恢復過程會檢查日志文件中的記錄，并按照事務的提交順序重新執(zhí)行所有已提交的更新操作，從而恢復數(shù)據(jù)庫到崩潰前的狀態(tài)。
由于先寫日志規(guī)則的存在，即使數(shù)據(jù)庫元素本身還沒有被寫入磁盤，但是相關(guān)的日志記錄已經(jīng)存在，因此可以通過這些日志記錄來恢復數(shù)據(jù)庫的狀態(tài)。這種機制大大提高了數(shù)據(jù)庫的可靠性和恢復能力。

6.3.2 使用redo 日志的恢復

1. 確定已提交的事務
   在恢復過程開始時，首先需要確定哪些事務是已經(jīng)提交的，哪些事務是未完成的（即已啟動但尚未提交或已回滾的事務）。這通常通過檢查日志文件中的記錄來完成。如果日志中存在記錄，則事務T被認為是已提交的；否則，事務T被認為是未完成的。
   2. 從首部開始掃描日志
   接下來，從日志文件的開始部分順序掃描每一條記錄。對于遇到的每一條<T, X, v>記錄（其中T是事務標識，X是數(shù)據(jù)庫元素標識，v是新值），需要執(zhí)行以下操作：

• a) 如果T是未提交的事務

在這種情況下，由于事務T最終沒有成功提交，因此它對數(shù)據(jù)庫所做的任何修改都不應該被保留。因此，對于這樣的記錄，恢復過程將忽略它，不執(zhí)行任何操作。

• b) 如果T是提交的事務

對于已提交的事務，其修改是有效的，并且需要被應用到數(shù)據(jù)庫中。因此，恢復過程會將新值v寫入到數(shù)據(jù)庫元素X中，無論該元素當前的值是什么。這是通過redo日志實現(xiàn)的，即重新執(zhí)行已提交事務的修改操作。
3. 對每個未完成的事務T，在日志中寫入一個記錄并刷新日志
在掃描完所有日志記錄并應用了所有已提交事務的修改之后，恢復過程需要處理那些未完成的事務。雖然這些事務的修改不會被應用到數(shù)據(jù)庫中，但出于一致性和審計的目的，通常會在日志中為每個未完成的事務寫入一個記錄。這個記錄表明事務T由于某種原因（如系統(tǒng)崩潰）而未能成功完成，并且其修改應該被忽略。為了確保記錄被正確地寫入到日志文件中，通常需要執(zhí)行一個“刷新”操作，以確保日志文件的更改被持久化到磁盤上。這樣，即使系統(tǒng)再次崩潰，也能夠從日志文件中準確地了解哪些事務是已提交的，哪些事務是未完成的。

6. 3. 3 redo 日志的檢查點

1. 寫入日志記錄<START CKPT(T1,…,Tn)>，其中T1,…,Tn是所有活躍（即未提交的）事務，并刷新日志
   2. 將STARTCKPT記錄寫入日志時所有已提交事務已經(jīng)寫到緩沖區(qū)但還沒有寫到磁盤的數(shù)據(jù)庫元素寫到磁盤
   在寫入記錄之后，系統(tǒng)需要遍歷所有的緩沖區(qū)，找出那些已經(jīng)被已提交事務修改過但尚未寫入磁盤的數(shù)據(jù)庫元素（即“臟頁”）。然后，將這些臟頁寫入磁盤。這一步是檢查點過程的核心，因為它確保了所有在檢查點之前已經(jīng)提交的事務的修改都被持久化到磁盤上。
   3. 寫入日志記錄并刷新日志
   在所有必要的臟頁都被寫入磁盤之后，系統(tǒng)在redo日志中寫入一個記錄，標志著檢查點過程的結(jié)束。
   

6.3.4 使用帶檢查點 redo 日志的恢復

情況一：最后一個檢查點記錄是
<STARTCKPT(T,…,T)>記錄之前提交的所有事務的修改都已經(jīng)成功寫入了磁盤。因此，恢復過程可以簡化為：
忽略<STARTCKPT(T,…,T)>之前提交的事務，因為它們的修改已經(jīng)持久化。
關(guān)注<STARTCKPT(T,…,T)>中列出的事務以及在該檢查點之后開始的所有事務。
掃描日志，從日志的開頭或上一個檢查點之后開始，直到找到<STARTCKPT(T,…,T)>。
重做（redo）<STARTCKPT(T,…,T)>中列出的事務以及之后開始并提交的所有事務的修改。這些事務的修改可能還沒有寫入磁盤。
停止掃描日志，當遇到最早的記錄（表示一個新事務的開始）且該事務不在<STARTCKPT(T,…,T)>中時，因為這意味著后續(xù)的事務與當前恢復過程無關(guān)。
情況二：最后一個檢查點記錄是<START CKPT (T,…,Tk)>
我們不能確定在<START CKPT (T,…,Tk)>之前提交的事務的修改是否已經(jīng)被寫入磁盤。因此，恢復過程需要更多的步驟：
回溯到日志中查找最近的記錄。
找到與這個匹配的<STARTCKPT(S,…,Sn)>記錄。
重做（redo）所有在<STARTCKPT(S,…,Sn)>和<START CKPT (T,…,Tk)>之間開始并成功提交的事務的修改，因為這些事務的修改可能還沒有被寫入磁盤。
檢查<START CKPT (T,…,Tk)>之后的事務，并只重做那些已經(jīng)提交的事務的修改。

6.4 undo/redo 日志

我們已經(jīng)看到了兩種不同的日志方式，它們的差別在于當數(shù)據(jù)庫元素被修改時日志中保存舊值還是新值。它們各有其缺陷:

• undo日志要求數(shù)據(jù)在事務結(jié)束后立即寫到磁盤，可能增加需要進行的磁盤I/0次數(shù)。
• 另一方面，redo日志要求我們在事務提交和日志記錄刷新以前，將所有修改過的塊保留在緩沖區(qū)中，這樣可能增加事務需要的平均緩沖區(qū)數(shù)。
• 如果數(shù)據(jù)庫元素不是完整的塊或塊集，在檢查點過程中undo日志和redo日志在如何處理緩沖區(qū)方面都存在矛盾。例如，如果一個緩沖區(qū)中包含被提交的事務修改過的數(shù)據(jù)庫元素A和同一緩沖區(qū)中被尚未將其COMMIT記錄寫到磁盤的事務修改過的數(shù)據(jù)庫元案B。
  

6.4.1 undo/redo 規(guī)則

規(guī)則UR1：在事務T對數(shù)據(jù)庫元素X的修改（即新值w寫入磁盤上的X）之前，更新記錄<T, X, v, w>必須已經(jīng)寫入磁盤。這里，v是修改前的舊值，w是修改后的新值。這個規(guī)則確保了即使在系統(tǒng)崩潰之后，我們也有足夠的信息來恢復數(shù)據(jù)（通過重做已提交事務的修改）或撤銷未提交事務的修改。這個日志記錄為系統(tǒng)提供了足夠的信息來執(zhí)行undo（如果事務需要被回滾）或redo（如果事務已經(jīng)提交但系統(tǒng)崩潰，需要重新應用其修改）操作。

6.4.2 使用 undo/redo 日志的恢復

1. 按照從前往后做順序，重做所有已提交的事務
這一步是在系統(tǒng)恢復過程中首先執(zhí)行的。它的目的是重新應用所有已經(jīng)成功提交的事務的修改，以確保這些修改對數(shù)據(jù)庫的影響是持久的。
2. 按照從后往前做順序，撤銷所有未提交的事務
在重做所有已提交事務之后，下一步是撤銷所有未提交的事務。這是因為未提交的事務表示它們還沒有被系統(tǒng)正式接受為數(shù)據(jù)庫狀態(tài)的一部分，因此它們的修改不應該在恢復后的數(shù)據(jù)庫中反映出來。為了撤銷這些事務，系統(tǒng)會按照日志中從后往前的順序（即事務發(fā)生的逆序）來查找所有未包含日志記錄的事務，并撤銷它們所做的修改。

6.4.3 undo/redo 日志的檢查點

1. 寫入日志記錄 <START_CKPT(T,…,T)> 并刷新日志
   2. 將所有臟緩沖區(qū)寫到磁盤
   3. 寫入日志記錄 <END_CKPT> 并刷新日志
   

6.5 針對介質(zhì)故障的防護

6.5.1 備份

完全轉(zhuǎn)儲
完全轉(zhuǎn)儲涉及拷貝數(shù)據(jù)庫在某一時刻的完整狀態(tài)。這是恢復過程的基礎(chǔ)，因為它提供了一個完整的、無遺漏的數(shù)據(jù)集。完全轉(zhuǎn)儲通常被標記為“0級”轉(zhuǎn)儲，因為它不依賴于任何先前的轉(zhuǎn)儲。
增量轉(zhuǎn)儲
增量轉(zhuǎn)儲僅拷貝自上次轉(zhuǎn)儲（無論是完全轉(zhuǎn)儲還是增量轉(zhuǎn)儲）以來發(fā)生變化的數(shù)據(jù)庫元素。這種方法顯著減少了每次備份所需的數(shù)據(jù)量，但恢復過程可能需要多個轉(zhuǎn)儲文件，因為它們是按順序依賴的。增量轉(zhuǎn)儲可以進一步細分為多個級別，其中“i級”轉(zhuǎn)儲表示拷貝自最后一個小于或等于i級轉(zhuǎn)儲之后改變的所有內(nèi)容。

起始點：恢復過程通常從一個完整的轉(zhuǎn)儲（0級轉(zhuǎn)儲）開始，因為這個轉(zhuǎn)儲包含了數(shù)據(jù)庫在某個時間點的完整狀態(tài)。
增量層疊：隨后的增量轉(zhuǎn)儲（1級、2級、…、i級）都是基于之前的轉(zhuǎn)儲進行的。例如，1級增量轉(zhuǎn)儲包含了自0級轉(zhuǎn)儲以來發(fā)生變化的元素；而2級增量轉(zhuǎn)儲則包含了自最近一次1級（或更低級別）增量轉(zhuǎn)儲以來發(fā)生變化的元素，以此類推。
恢復順序：在恢復時，必須首先恢復0級轉(zhuǎn)儲，因為這是所有后續(xù)增量轉(zhuǎn)儲的基礎(chǔ)。然后，需要按照遞增的順序（1級、2級、…、i級）應用增量轉(zhuǎn)儲，以確保所有更改都被正確地應用到數(shù)據(jù)庫中。

6.5.2 非靜止轉(zhuǎn)儲

非靜止轉(zhuǎn)儲：是一種在數(shù)據(jù)庫系統(tǒng)不停止運行的情況下進行的備份策略。由于數(shù)據(jù)庫在備份過程中仍然處于活動狀態(tài)，新的事務可能會開始、修改或提交，因此備份的數(shù)據(jù)庫狀態(tài)可能會與轉(zhuǎn)儲開始時有所不同。為了解決這個問題，非靜止轉(zhuǎn)儲結(jié)合了日志記錄來確保數(shù)據(jù)庫在恢復時能夠達到一個一致的狀態(tài)。
非靜止轉(zhuǎn)儲的特點
并發(fā)性：在備份過程中，數(shù)據(jù)庫系統(tǒng)繼續(xù)處理新的事務，包括數(shù)據(jù)的插入、更新和刪除。
日志依賴：由于備份是在數(shù)據(jù)庫活動的狀態(tài)下進行的，因此備份中可能包含不一致的數(shù)據(jù)。為了恢復到一個一致的狀態(tài)，需要依賴于在備份過程中生成的日志記錄。
順序拷貝：非靜止轉(zhuǎn)儲通常按照某種固定的順序（如數(shù)據(jù)庫表的順序或數(shù)據(jù)頁的順序）來拷貝數(shù)據(jù)庫元素。然而，由于并發(fā)性，這些元素在被拷貝的過程中可能會被其他事務修改。
恢復過程：恢復過程包括將備份數(shù)據(jù)恢復到數(shù)據(jù)庫，并應用備份過程中生成的日志記錄來糾正任何不一致。這通常涉及回滾未提交的事務并應用已提交事務的更改。

6.5.3 使用備份和日志的恢復

假設發(fā)生了介質(zhì)故障，并且我們要通過此前已到達安全的遠程結(jié)點、在崩潰中未丟失的日志和最近的備份重建數(shù)據(jù)庫。我們執(zhí)行下列步驟:
1.根據(jù)備份恢復數(shù)據(jù)庫。
a)找到最近的完全轉(zhuǎn)儲，并根據(jù)它來恢復數(shù)據(jù)庫(即將備份拷貝到數(shù)據(jù)庫)。
b)如果有后續(xù)的增量轉(zhuǎn)儲，按照從前往后做的順序，根據(jù)各個增量轉(zhuǎn)儲修改數(shù)據(jù)庫。
2.用保留下來的日志修改數(shù)據(jù)庫。使用對應所用日志方式的合適的恢復機制。

第7章 并發(fā)控制

調(diào)度器：不同事務各個步驟的執(zhí)行順序由調(diào)度器完成。
調(diào)度器所要實現(xiàn)的：可串行性，或者沖突可串行性。
調(diào)度器最重要的技術(shù)：封鎖，時間戳，有效性確認。

7.1 串行調(diào)度和可串行化調(diào)度

7.1.1 調(diào)度

重要的讀寫動作發(fā)生在主存緩沖區(qū)中，而不是磁盤上。
調(diào)度是一個或多個事務的重要動作的一個序列。

7.1.2 串行調(diào)度

一個事務的所有動作完成之后才能進行下一個事務的所有動作。不同事務的調(diào)度順序結(jié)果可能不一樣。

7.1.3 可串行化調(diào)度

可串行化調(diào)度 ：它允許事務并發(fā)執(zhí)行，但產(chǎn)生的結(jié)果與某個串行調(diào)度產(chǎn)生的結(jié)果相同。
**可串行化：**如果一個并發(fā)調(diào)度（即多個事務可能同時執(zhí)行）的執(zhí)行結(jié)果與某個串行調(diào)度（即事務按某種順序一個接一個執(zhí)行）的執(zhí)行結(jié)果對于所有可能的數(shù)據(jù)庫初始狀態(tài)都是相同的，那么這個并發(fā)調(diào)度就被認為是可串行化的。

7.1.5 事務和調(diào)度的一種記法

讀操作 (rTi(X)): 表示事務讀取數(shù)據(jù)庫元素X的當前值。
寫操作 (wTi(X)): 表示事務將數(shù)據(jù)庫元素X的值更改為新值。

7.2 沖突可串行化

7.2.1 沖突

1. 同一事務的兩個動作總是沖突的。單個事務的動作順序不能改變。
2. 不同事務對同一數(shù)據(jù)庫元素的寫沖突。
3. 不同事務對同一數(shù)據(jù)庫元素的讀和寫也沖突。

總結(jié)
不同事務的任何兩個動作可以交換，除以下情況外:

1. 它們涉及同一數(shù)據(jù)庫元素。
2. 至少有一個是寫。

沖突等價
如果通過一系列相鄰動作的非沖突交換能將它們中的一個轉(zhuǎn)換為另一個，我們說兩個調(diào)度是沖突等價的。
沖突可串行化
如果一個調(diào)度 沖突等價 于一個串行調(diào)度，那么我們說該調(diào)度是沖突可串行化的。

7.2.2 優(yōu)先圖及沖突可串行化判斷

**沖突可串行化:**它確保了一個調(diào)度雖然可能包含并行執(zhí)行的事務，但這些事務的執(zhí)行順序可以重新排列成一個沒有沖突的串行執(zhí)行順序，同時保持所有事務的原始讀寫操作。如果這樣的串行順序存在，那么該調(diào)度就被稱為沖突可串行化。
優(yōu)先圖
優(yōu)先圖是一種有向圖，用于表示事務之間的先后順序關(guān)系。
根據(jù)調(diào)度序列，與r沖突的是w，與w沖突的是r，w。
例：

1. 與r2（A）沖突的是w1.3（A），因此存在一條 2——>3
2. 與r1（B）沖突的是w2.3（B），因此存在一條 1——>2
3. 與w2（A）沖突的是w1.3（A），r1.3（A）,因此存在一條2——>3
4. 與r2（B）沖突的是w1.2（B），因此存在一條2——>1

以此類推…得到優(yōu)先圖：

7.3 使用鎖的可串行化實現(xiàn)

事務獲得在它所訪問的數(shù)據(jù)庫元素上的鎖，以防止其他事務幾乎在同一時間訪問這些元素并因而引人非可串行化的可能。

7.3.1 鎖

讀寫前的鎖請求：
事務T在讀取（r(X)）或?qū)懭?#xff08;w(X)）數(shù)據(jù)庫元素X之前，必須先請求（L(X)）并獲得該元素上的鎖。這確保了當事務嘗試訪問數(shù)據(jù)庫元素時，它對該元素具有獨占訪問權(quán)，從而避免了數(shù)據(jù)的不一致性問題。
鎖請求（L(X)）和讀寫操作（r(X)或w(X)）之間不能有釋放該元素鎖的操作（u(X)）。這是為了確保在訪問元素期間，鎖是持續(xù)有效的。
鎖的釋放：
事務T在完成對數(shù)據(jù)庫元素X的讀寫操作后，必須釋放（u(X)）在該元素上的鎖。這允許其他事務在需要時能夠請求并獲取鎖，進而訪問或修改該元素。
鎖的互斥性：
任何兩個事務（T1和T2）都不能在同一時間封鎖同一個數(shù)據(jù)庫元素X，除非其中一個事務（如T1）已經(jīng)先釋放了它在X上的鎖。這意味著如果調(diào)度中存在兩個連續(xù)的鎖請求動作L(X)和L(X’)（假設它們是由不同事務發(fā)出的），那么在這兩個動作之間必須有一個對應的解鎖動作u(X)（由已經(jīng)持有鎖的事務執(zhí)行）。確保了數(shù)據(jù)庫元素在任何時候都只能被一個事務獨占訪問，從而維護了數(shù)據(jù)的一致性和完整性。

7.3.3 兩階段封鎖

加鎖階段：
在此階段，事務可以申請并獲得它需要的所有鎖。
一旦事務開始了加鎖階段，它就不能釋放任何鎖，直到進入解鎖階段。
解鎖階段：
在此階段，事務可以釋放它在加鎖階段獲得的所有鎖。
一旦事務進入了解鎖階段，它就不能再申請任何新鎖。

7.4 有多種鎖模式的封鎖系統(tǒng)

在7.3節(jié)討論的簡單封鎖模式中，每個事務在讀寫數(shù)據(jù)庫元素時都需要獲得鎖，這在實際應用中可能過于嚴格且效率低下。

• 事務T即使只想讀數(shù)據(jù)庫元素X而不寫它，也必須獲得X上的鎖。
  

7.4.1 共享鎖與排他鎖

共享鎖（Shared Lock，S鎖）：
也稱為讀鎖。
當事務需要讀取數(shù)據(jù)庫元素但不修改它時，可以請求共享鎖。
多個事務可以同時持有同一個數(shù)據(jù)庫元素上的共享鎖，這意味著它們可以同時讀取該元素。
如果某個事務已經(jīng)持有數(shù)據(jù)庫元素的共享鎖，其他事務也可以請求該元素的共享鎖，但不能請求排他鎖。
排他鎖（Exclusive Lock，X鎖）：
也稱為寫鎖。
當事務需要修改數(shù)據(jù)庫元素時，必須請求排他鎖。
排他鎖是獨占的，即在同一時間只有一個事務可以持有某個數(shù)據(jù)庫元素上的排他鎖。
如果某個事務已經(jīng)持有數(shù)據(jù)庫元素的排他鎖，其他事務既不能請求該元素的共享鎖也不能請求排他鎖

sli（X）：事務Ti申請數(shù)據(jù)庫元素X上的一個共享鎖
xli（X）：事務Ti申請數(shù)據(jù)庫元素X上的一個排他鎖
li（X）：請求鎖
ui（X）：釋放鎖

7.4.2 相容性矩陣

行：表示數(shù)據(jù)庫元素上當前已經(jīng)被其他事務持有的鎖類型。
列：表示新申請的鎖類型。
示例

	S 申請	X 申請
S 持有	是	否
X 持有	否	否

7.4.3 鎖的升級

在數(shù)據(jù)庫事務管理中，鎖機制是確保數(shù)據(jù)一致性和隔離性的重要手段。鎖升級是指事務在開始時獲取較低級別的鎖（如共享鎖），隨著操作的進行，根據(jù)需要將其升級到更高級別的鎖（如排他鎖）。
優(yōu)點：
提高并發(fā)性：在事務開始時使用共享鎖可以允許多個事務同時讀取數(shù)據(jù)，從而提高了系統(tǒng)的并發(fā)性能。
減少等待時間：事務在需要寫入數(shù)據(jù)前可能已經(jīng)完成了大部分讀取操作，此時升級鎖可以減少因等待排他鎖而導致的延遲。
缺點：
死鎖風險增加：多個事務可能同時嘗試升級同一資源的鎖，導致它們相互等待對方釋放鎖，從而引發(fā)死鎖。
出現(xiàn)死鎖：
當T和T’幾乎同時開始時，它們都會首先獲取A上的共享鎖。
隨后，它們都試圖將A上的鎖升級為排他鎖，但由于對方持有A上的共享鎖，因此都無法立即升級。
結(jié)果是，T和T’都會陷入無限等待狀態(tài)，因為它們都在等待對方釋放A上的鎖。
死鎖解決方案
使用超時機制：在嘗試升級鎖時設置超時時間，如果在規(guī)定時間內(nèi)無法升級鎖，則釋放已持有的鎖并回滾事務或采取其他恢復措施。

7.4.4 更新鎖

更新鎖介于共享鎖（S鎖）和排他鎖（X鎖）之間。更新鎖允許事務在讀取數(shù)據(jù)的同時，保留將來可能對該數(shù)據(jù)進行更新的權(quán)利。
更新鎖的特點
讀取權(quán)限：持有更新鎖的事務可以讀取數(shù)據(jù)，但不能寫入數(shù)據(jù)。
升級權(quán)限：更新鎖可以被升級為排他鎖，但共享鎖不能直接升級為排他鎖（除非先釋放共享鎖）。
互斥性：一旦資源上有了更新鎖，就不能再有其他事務在該資源上獲得任何類型的鎖（包括共享鎖、更新鎖和排他鎖），直到更新鎖被釋放或升級為排他鎖。

行：表示數(shù)據(jù)庫元素上當前已經(jīng)被其他事務持有的鎖類型。

列：表示新申請的鎖類型。

避免死鎖
在例7.16中，由于事務T和T’都試圖將共享鎖升級為排他鎖，導致它們互相等待對方釋放鎖，從而引發(fā)死鎖。通過使用更新鎖，我們可以避免這種情況。在例7.17中，事務T和T’都首先申請A上的更新鎖。由于更新鎖的互斥性，當T持有A上的更新鎖時，T’嘗試獲取A上的更新鎖將會被拒絕。這樣，T可以繼續(xù)執(zhí)行并完成其操作，然后釋放A上的鎖。之后，T’可以獲取A上的更新鎖，進而升級為排他鎖并完成其操作。

7.4.5 增量鎖

增量鎖是一種特殊的鎖機制，適用于那些僅涉及對數(shù)據(jù)庫元素進行增加或減少操作的事務。
多個事務可以同時對同一數(shù)據(jù)庫元素進行增量操作，而這些操作的結(jié)果與它們執(zhí)行的順序無關(guān)。
增量鎖的特性
增量操作的交換性：增量鎖允許多個事務同時對同一數(shù)據(jù)庫元素進行增量操作，且這些操作的順序可以交換而不影響最終結(jié)果。
鎖的兼容性：在增量鎖被持有的情況下，其他事務不能對該元素加共享鎖（S鎖）或排他鎖（X鎖），但可以同時有多個事務持有該元素的增量鎖（i鎖）。
限制讀寫操作：增量鎖不賦予事務對數(shù)據(jù)庫元素進行讀或?qū)懖僮鞯臋?quán)力，僅允許進行增量操作。

7.5 封鎖調(diào)度器的一種體系結(jié)構(gòu)

事務申請鎖，釋放鎖都是調(diào)度器的干預。

7.5.1 插入鎖動作的調(diào)度器

事務請求的動作通常通過調(diào)度器傳送并在數(shù)據(jù)庫上執(zhí)行。但是在某些情況下，事務等待個鎖而被推遲，其請求(暫時)不被傳送到數(shù)據(jù)庫。
第I部分：請求處理與鎖插入
功能：負責接收來自事務的請求流，這些請求包括數(shù)據(jù)庫訪問操作（如讀、寫、增量、更新）和必要的鎖請求。
操作：在數(shù)據(jù)庫訪問操作之前，插入適當?shù)逆i動作（如加鎖、解鎖等）。然后，將處理后的封鎖和數(shù)據(jù)庫訪問動作序列傳遞給第Ⅱ部分。
第Ⅱ部分：動作執(zhí)行與鎖管理
功能：接收第I部分傳來的封鎖和數(shù)據(jù)庫訪問動作序列，并負責它們的執(zhí)行。
操作

1. 如果一個事務由于等待鎖而被推遲，則將該動作推遲，并加入到一個待執(zhí)行列表中。
2. 如果事務的所有請求鎖都已被授予，則執(zhí)行該事務的數(shù)據(jù)庫訪問操作或封鎖動作。
3. 封鎖動作的執(zhí)行包括檢查鎖表，以確定鎖是否可以被授予。如果可以，則更新鎖表；如果不可以，則在鎖表中標記該鎖已被申請，并推遲事務直到鎖可用。

鎖釋放與通知：當事務提交或中止時，通知第I部分釋放鎖。如果有事務等待這些鎖，則通知第Ⅱ部分進行處理。
鎖的獲得與執(zhí)行：當某個數(shù)據(jù)庫元素上的鎖變得可用時，第Ⅱ部分決定哪個（或哪些）事務可以獲得這些鎖，并允許它們執(zhí)行被推遲的操作，直到它們完成或遇到新的鎖等待。

7.5.2 鎖表

鎖表是將數(shù)據(jù)庫元素與有關(guān)該元素的封鎖信息聯(lián)系起來的一個關(guān)系表。
表可以用一個散列表來實現(xiàn)，使用數(shù)據(jù)庫元素(地址)作為散列碼。任何未被封鎖的元素在表中不出現(xiàn)，因此表的大小只與被封鎖元素的數(shù)目成正比，而不是與整個數(shù)據(jù)庫的大小成正比。

一個列表描述所有或者在A上當前持有鎖，或者在等待A上的鎖的那些事務。
組模式概括事務申請A上的一個新鎖時所面臨的最苛刻的條件。
在共享-排他-更新(SXU)封鎖模式中，規(guī)則很簡單:組模式:
a)S表示被持有的只有共享鎖。
b)U表示有一個更新鎖，而且可能有一個或多個共享鎖。
c)X表示有一個排他鎖，并且沒有其他的鎖。
封鎖請求處理
檢查鎖表項：

1. 如果A的鎖表項不存在，說明A上當前沒有鎖，調(diào)度器將創(chuàng)建一個新的鎖表項，并立即同意T的請求。
2. 如果A的鎖表項存在，調(diào)度器將檢查當前的組模式（U-更新鎖、X-排他鎖、S-共享鎖）。

根據(jù)組模式?jīng)Q定請求：

1. 如果組模式是U（更新鎖），則只有T自己持有的U鎖或與其他請求相容的鎖才能被授予。否則，請求被拒絕，并在等待列表中為T的請求添加一項，設置Wait?=Yes。
2. 如果組模式是X（排他鎖），則請求同樣被拒絕，并添加等待項。
3. 如果組模式是S（共享鎖），則另一個共享鎖或更新鎖可以被授予。如果授予的是更新鎖，則組模式改為U；如果是共享鎖，則組模式保持S。

更新鎖表：

1. 無論鎖是否被授予，新的列表項都會通過Tnext和Nex字段正確地鏈接到等待列表中。
2. 調(diào)度器可以從鎖表直接獲取所需信息，無需檢查鎖的列表（但列表用于管理等待的事務）。

解鎖處理
刪除列表項：
從等待列表中刪除T關(guān)于A的項。
檢查并更新組模式：
如果T持有的鎖與組模式不同（如T持有S鎖，但組模式是U），則組模式保持不變，因為還有其他事務可能持有U鎖。
如果T的鎖與組模式相同，并且T是最后一個持有該鎖的事務（即沒有其他事務持有A上的鎖了），則組模式可能需要更改：
如果組模式是U，并且沒有其他鎖存在，則組模式變?yōu)闊o（因為沒有鎖了）。
如果組模式是S，并且還有其他事務持有S鎖，則組模式保持S；否則，也變?yōu)闊o。
授予等待的鎖：
如果存在等待的鎖（Waiting = ‘yes’），調(diào)度器需要決定如何授予這些鎖。策略包括：
先來先服務：按照請求的先后順序授予鎖，確保公平性。
共享鎖優(yōu)先：首先授予所有等待的共享鎖，然后是更新鎖，最后是排他鎖。這種策略可能導致更新鎖或排他鎖餓死。
升級優(yōu)先：如果有一個持有U鎖的事務在等待將其升級到X鎖，則優(yōu)先授予該鎖。這可以確保重要的更新或?qū)懭氩僮鞅M快完成。

7.6 數(shù)據(jù)庫元素的層次

7.6.1 多粒度的鎖

元組級鎖（最細粒度）：
優(yōu)點：支持高并發(fā)，因為每個事務只需要鎖定它所修改或查詢的元組。
缺點：管理開銷大，因為鎖的數(shù)量可能非常多，同時增加了死鎖的風險。
適用場景：當大量事務主要修改或查詢少量的數(shù)據(jù)時，如銀行的存款和取款操作，每個賬戶視為一個元組。
頁/塊級鎖：
優(yōu)點：相對于元組級鎖，減少了鎖的數(shù)量和管理開銷，同時仍然可以支持較高的并發(fā)。
缺點：可能會因為鎖定整個頁/塊而導致一些不必要的等待，尤其是當頁/塊內(nèi)只有少量數(shù)據(jù)被修改時。
適用場景：當事務傾向于修改或查詢頁/塊內(nèi)多個數(shù)據(jù)時，如銀行數(shù)據(jù)庫中同一頁內(nèi)的多個賬戶。
關(guān)系級鎖（最粗粒度）：
優(yōu)點：管理開銷最小，因為整個關(guān)系只需要一個鎖。
缺點：并發(fā)性能低，因為任何對關(guān)系內(nèi)數(shù)據(jù)的修改都需要先獲得整個關(guān)系的鎖。
適用場景：當大多數(shù)事務是讀操作且很少寫操作時，如文檔數(shù)據(jù)庫，其中文檔經(jīng)常被檢索但很少被編輯。

7.6.2 警示鎖

。警示鎖與普通鎖（如共享鎖S和排他鎖X）配合使用，以提供更靈活的鎖控制機制，特別是在處理多層次數(shù)據(jù)結(jié)構(gòu)時。
警示鎖的基本概念
定義：警示鎖通過在普通鎖前加前綴（如“意向”）來表示，例如IS（Intention Shared）和IX（Intention Exclusive）。它們用于表明事務打算在其子元素上獲取特定類型的鎖。
作用：警示鎖主要用于提高鎖管理的效率，減少不必要的鎖沖突，并幫助數(shù)據(jù)庫系統(tǒng)快速判斷某個事務是否可能與其他事務發(fā)生沖突。
警示鎖的協(xié)議規(guī)則
從根開始：在嘗試對任何元素加S或X鎖之前，必須從層次結(jié)構(gòu)的根（如關(guān)系）開始。
直接加鎖：如果當前結(jié)點就是需要封鎖的結(jié)點，則直接請求該結(jié)點上的S或X鎖。
向下傳遞警示：如果需要封鎖的結(jié)點位于層次結(jié)構(gòu)中更靠下的位置，則在當前結(jié)點上添加一個警示鎖（IS或IX）。然后，繼續(xù)向包含目標結(jié)點的子結(jié)點行進，并重復此過程。

鎖的相容性矩陣

7.6.3 幻象與插入的正確處理

幻象問題是指在一個事務執(zhí)行過程中，另一個事務插入了新的行，這些新行滿足第一個事務中某個查詢的條件，但第一個事務在開始時并未看到這些行。這會導致第一個事務的查詢結(jié)果不準確，違反了事務的隔離性。
解決方案
使用更嚴格的隔離級別：如可串行化（Serializable）隔離級別。在這個級別下，事務會完全串行執(zhí)行，從而避免了幻象的發(fā)生。但這種方法可能會顯著降低系統(tǒng)的并發(fā)性能。
使用鎖：
表級鎖：在事務開始時，對整個表加鎖，直到事務結(jié)束。這可以防止其他事務插入新行。但這種方法會限制表的并發(fā)訪問。
范圍鎖：對查詢涉及的數(shù)據(jù)范圍加鎖，防止其他事務在該范圍內(nèi)插入新行。但這種方法需要數(shù)據(jù)庫系統(tǒng)能夠預測查詢的范圍，這在很多情況下是不可行的。
幻象鎖（Phantom Locks）：一種特殊的鎖，用于防止在特定查詢條件下插入新行。雖然大多數(shù)數(shù)據(jù)庫系統(tǒng)不直接提供這種鎖，但可以通過其他機制（如索引鎖、謂詞鎖等）來實現(xiàn)類似的效果。
使用多版本并發(fā)控制（MVCC）：MVCC 允許數(shù)據(jù)庫為每個事務維護數(shù)據(jù)的一個或多個版本。當事務讀取數(shù)據(jù)時，它看到的是事務開始時數(shù)據(jù)的一個快照。這樣，即使其他事務插入了新行，也不會影響當前事務的查詢結(jié)果。

7.7 樹協(xié)議

7.7.1基于樹的封鎖的動機

在處理B-樹索引的并發(fā)訪問時，傳統(tǒng)的兩階段封鎖（2PL）協(xié)議可能會遇到嚴重的限制，導致并發(fā)性能不佳。這是因為B-樹的結(jié)構(gòu)特性使得根節(jié)點或內(nèi)部節(jié)點的鎖可能成為瓶頸，特別是在進行插入或刪除操作時，理論上可能需要重寫這些節(jié)點
基于樹的封鎖動機
減少鎖粒度：直接在B-樹的根節(jié)點或所有內(nèi)部節(jié)點上加鎖會極大地限制并發(fā)性，因為這會要求事務在繼續(xù)深入樹之前獲得這些高級別節(jié)點的鎖。通過基于樹的結(jié)構(gòu)特性來優(yōu)化鎖的使用，可以減少不必要的鎖等待和鎖沖突。
提高并發(fā)性：通過觀察和預測B-樹操作的局部性，可以設計一種機制，使得事務在確信不會修改樹的高層結(jié)構(gòu)時，能夠提前釋放高級別節(jié)點的鎖。這種策略可以顯著增加多個事務同時訪問B-樹的能力。
保持可串行性：雖然釋放鎖可能違反了兩階段封鎖的原則，但可以通過設計專門的協(xié)議來確保事務的調(diào)度仍然是可串行化的。這些協(xié)議利用了B-樹操作的特定順序性和結(jié)構(gòu)穩(wěn)定性，通過跟蹤事務對樹的訪問路徑和所做的修改來確保數(shù)據(jù)的一致性。

7.7.2 訪問樹結(jié)構(gòu)數(shù)據(jù)的規(guī)則

事務的第一個鎖可以在樹的任何結(jié)點上：
這個規(guī)則允許事務從樹的任何位置開始其操作，而不僅僅是從根節(jié)點開始。這增加了靈活性，因為事務可以根據(jù)其需要直接定位到樹中的相關(guān)部分。
只有事務當前在父結(jié)點上持有鎖時才能獲得后續(xù)的鎖：
這個規(guī)則確保了事務在深入樹結(jié)構(gòu)時遵循一種“從上到下”的順序。這有助于防止不同事務之間的鎖沖突，因為它們在樹中的路徑不會交叉。此外，這個規(guī)則還隱含了一個要求，即事務在釋放一個節(jié)點的鎖之前，必須先釋放其所有子節(jié)點的鎖。這是因為如果沒有這個要求，事務可能會陷入一個無法釋放父節(jié)點鎖的情況，因為它還持有子節(jié)點的鎖。
結(jié)點可以在任何時候解鎖：
這個規(guī)則允許事務在不再需要某個節(jié)點的鎖時立即釋放它。這有助于減少鎖持有的時間，從而提高并發(fā)性。
事務不能對一個它已經(jīng)解鎖的結(jié)點重新上鎖，即使它在該結(jié)點的父結(jié)點上仍持有鎖：
這個規(guī)則防止了事務在釋放了一個節(jié)點的鎖之后重新獲取它，除非它重新開始整個事務或重新獲得從根節(jié)點到該節(jié)點的路徑上所有節(jié)點的鎖。這有助于避免死鎖和復雜的狀態(tài)管理問題。

7.8 使用時間戳的并發(fā)控制

7.8.1 時間戳

基于系統(tǒng)時間生成：
這種方法利用操作系統(tǒng)的當前時間來為事務分配時間戳。
使用計數(shù)器生成：
調(diào)度器維護一個遞增的計數(shù)器，每當一個新事務開始時，計數(shù)器加1并將新值作為事務的時間戳。
RT(X)：X的讀時間戳。表示最后一次成功讀取X的事務的時間戳。
當事務T讀取X時，如果T的時間戳大于RT(X)，則更新RT(X)為T的時間戳。
WT(X)：X的寫時間戳。表示最后一次成功寫入X的事務的時間戳。
當事務T寫入X時，無論T的時間戳與WT(X)的關(guān)系如何，都更新WT(X)為T的時間戳。
C(X)：X的提交位。表示最后一次寫入X的事務是否已經(jīng)提交。

7.8.2 事實上不可實現(xiàn)的行為

過晚的讀
事務T試圖讀取一個在其理論上執(zhí)行之后才被寫入的值。這違反了時間戳調(diào)度器的假設，即事務的執(zhí)行順序應該與其時間戳順序一致。
我們只能中止事務T。

過晚的寫
如果事務的時間戳處于一個“過晚”的位置，即它試圖寫入一個已經(jīng)被其他事務讀取（但尚未寫入新值）的數(shù)據(jù)庫元素，并且這個讀取操作的時間戳比當前事務的時間戳還要晚，那么就發(fā)生了過晚的寫。

7.8.3 臟數(shù)據(jù)的問題

臟讀問題
臟讀發(fā)生在一個事務讀取了另一個未提交事務修改的數(shù)據(jù)。但事務最終可能由于某種原因而未能提交。
解決方法
檢查提交位C(X)，如果C(X)為假，表示X的當前值尚未被提交，因此事務T應該推遲讀取X，直到事務U提交或中止。
另一潛在問題
事務T試圖寫入X，但發(fā)現(xiàn)有一個時間戳更晚的事務U已經(jīng)寫入了X，T繼續(xù)寫的話會造成數(shù)據(jù)錯誤。

解決方法：Thomas寫法則
Thomas寫法則允許一個事務在發(fā)現(xiàn)有更晚時間戳的寫操作已經(jīng)發(fā)生時，跳過自己的寫操作。
Thomas寫法則的潛在問題
如果事務U后來中止，其寫入X的操作應該被撤銷，但此時T的寫操作已經(jīng)被跳過，無法恢復X到T寫入之前的狀態(tài)。這可能導致數(shù)據(jù)丟失或不一致。
處理策略
嘗試性寫入：當事務T寫入數(shù)據(jù)庫元素X時，調(diào)度器并不立即將X的值更新為T寫入的值，而是將這次寫入視為“嘗試性”的。調(diào)度器同時保存X的舊值和原有寫時間戳WT(X)的拷貝。
提交或中止處理：
如果事務T提交，調(diào)度器將X的值更新為T寫入的值，并將提交位C(X)設為真。
如果事務T中止，調(diào)度器將撤銷T對X的寫入，恢復X的舊值和原有寫時間戳WT(X)。

7.8.4 基于時間戳調(diào)度的規(guī)則

每個事務分配一個唯一的時間戳（TS）。

1. 讀請求的處理

當調(diào)度器收到來自事務T的對數(shù)據(jù)項X的讀請求r(X)時：

• 如果TS(T) ≥ WT(X)，即事務T的時間戳大于或等于X的最近寫時間戳，說明T的讀請求是事實上可實現(xiàn)的（即不會讀到臟數(shù)據(jù)）。
  • 如果C(X)為真（表示X的最近寫已提交），則同意請求，并根據(jù)需要更新X的讀時間戳RT(X)。
  • 如果C(X)為假（表示X的最近寫未提交），則推遲T直到C(X)為真或?qū)慩的事務中止。
• 如果TS(T) < WT(X)，即事務T的時間戳小于X的最近寫時間戳，說明T的讀請求是事實上不可實現(xiàn)的（即會讀到臟數(shù)據(jù)），因此必須回滾T并重啟。
  

2. 寫請求的處理

當調(diào)度器收到來自事務T的對數(shù)據(jù)項X的寫請求w(X)時：

• 如果TS(T) ≥ PT(X) 且 TS(T) ≥ WT(X)，即事務T的時間戳大于或等于X的最早提交時間戳和最近寫時間戳，說明T的寫請求是事實上可實現(xiàn)的，即T寫X之后暫時不會被其他寫覆蓋，必須執(zhí)行。
  • 為X寫入新值。
  • 更新WT(X)為TS(T)。
  • 將C(X)設為false，表示X的最新寫尚未提交。
• 如果TS(T) > RT(X) 但 TS(T) < WT(T)，即T的時間戳大于X的讀時間戳但小于X的最近寫時間戳，說明T的寫是事實上可實現(xiàn)的但X已有更晚的寫。
  • 如果C(X)為真，則前一個X的寫已提交，忽略T的寫。
  • 如果C(X)為假，則推遲T直到C(X)為真或?qū)慩的事務中止。
• 如果TS(T) < RT(X)，即事務T的時間戳小于X的讀時間戳，說明T的寫是事實上不可實現(xiàn)的，必須回滾T。
  

3. 提交請求的處理

當調(diào)度器收到事務T的提交請求時：

• 將T所寫的所有數(shù)據(jù)庫元素X的C(X)設為true，表示這些寫已提交。
• 允許任何等待X被提交的事務繼續(xù)進行。
  

4. 中止或回滾請求的處理

當調(diào)度器收到事務T的中止請求或決定回滾T時：

• 任何等待T所寫元素X的事務需要重新嘗試其讀或?qū)懻埱?#xff0c;檢查這些操作在T的寫被中止后是否仍然合法。
  

7.8.5 多版本時間戳

每個數(shù)據(jù)庫元素（如記錄、塊或頁）都可能有多個版本，每個版本都與一個特定的時間戳相關(guān)聯(lián)。這些版本記錄了數(shù)據(jù)在不同時間點的狀態(tài)。
多版本時間戳的主要目的是允許事務在讀取數(shù)據(jù)時，即使其他事務正在修改這些數(shù)據(jù)，也能繼續(xù)執(zhí)行而不會導致中止。這是通過讓事務讀取適合其時間戳的數(shù)據(jù)版本來實現(xiàn)的。

7.8.6 時間戳與封鎖

時間戳機制：
在高沖突場景下，由于多個事務嘗試寫入相同數(shù)據(jù)，可能導致大量事務需要回滾，增加系統(tǒng)延遲。
適用于大多數(shù)事務為只讀或并發(fā)事務較少讀寫同一數(shù)據(jù)元素的情況。
封鎖機制：
事務可能因等待鎖而阻塞，導致性能下降，甚至可能出現(xiàn)死鎖。
在高沖突場景下，即多個事務頻繁讀寫相同數(shù)據(jù)元素時，封鎖機制的性能較好。

7.9 使用有效性確認的并發(fā)控制

有效性確認與時間戳的主要區(qū)別在于調(diào)度器維護關(guān)于活躍事務正在做什么的一個記錄，而不是為所有數(shù)據(jù)庫元素保存讀時間和寫時間。事務開始為數(shù)據(jù)庫元素寫人值前的一剎那，它經(jīng)過一個“有效性確認階段”，這時用它已經(jīng)讀的和將寫的元素集合與其他活躍事務的寫集合做比較。如果存在事實上不可實現(xiàn)行為的風險該事務就被回滾。

7.9.1 基于有效性確認調(diào)度器的結(jié)構(gòu)

告知調(diào)度器事務T的讀集合RS（T）和寫集合WS（T）
讀階段：
事務讀取其讀集合（RS(T)）中的所有數(shù)據(jù)庫元素。事務在其局部地址空間中計算將要寫入的所有值，但此時不修改數(shù)據(jù)庫。
有效性確認階段：
調(diào)度器比較當前事務的讀寫集合（RS(T)和WS(T)）與其他活躍事務（即在START或VAL集合中的事務）的讀寫集合。
如果發(fā)現(xiàn)存在沖突，即當前事務的寫集合與其他事務的讀集合或?qū)懠嫌薪患?#xff0c;且不滿足可串行化的要求，則事務被回滾。
如果確認成功，事務進入下一個階段。
寫階段：
事務將其寫集合（WS(T)）中的值寫入數(shù)據(jù)庫。

為了支持做出是否確認事務有效性的決定，調(diào)度器維護三個集合:
START集合：
包含已經(jīng)開始但尚未完成有效性確認的事務。對于每個事務T，調(diào)度器記錄其開始時間START(T)。
VAL集合：
包含已經(jīng)通過有效性確認但尚未完成寫階段的事務。T確認時間VAL(T)。
FIN集合：
包含已經(jīng)完成寫階段的事務。T完成時間FIN(T)。

7.9.2 有效性確認規(guī)則

規(guī)則一：檢查讀后寫沖突

對于所有已經(jīng)過有效性確認（即在VAL或FIN集合中）且在事務T開始前沒有完成的事務U（即滿足FIN(U) > START(T)），調(diào)度器需要檢測是否存在讀后寫沖突。這種沖突發(fā)生在事務T讀取了某個數(shù)據(jù)庫元素X之后，而事務U可能（或已經(jīng)）修改了X的值。

• 具體檢查：檢查RS(T) ∩ WS(U) 是否非空。如果非空，說明事務T讀取了事務U將要修改的數(shù)據(jù)庫元素，這可能導致事務T讀到了舊值，而事務U最終會寫入新值，從而破壞了串行順序的假設。
• 處理：如果檢測到這種沖突，調(diào)度器必須回滾事務T，以避免潛在的數(shù)據(jù)不一致。
  

規(guī)則二：檢查寫-寫沖突

對于所有已經(jīng)過有效性確認（即在VAL集合中）且在事務T進入其有效性確認階段前沒有完成的事務U（即滿足FIN(U) > VAL(T)），調(diào)度器需要檢測是否存在寫-寫沖突。這種沖突發(fā)生在兩個事務都試圖修改同一個數(shù)據(jù)庫元素。

• 具體檢查：檢查WS(T) ∩ WS(U) 是否非空。如果非空，說明事務T和事務U都計劃修改同一個數(shù)據(jù)庫元素，而根據(jù)假設的串行順序，事務U應該在事務T之前完成修改。
• 處理：如果檢測到這種沖突，調(diào)度器同樣需要回滾事務T，以確保事務的執(zhí)行順序與假設的串行順序一致。