CS 411 資料庫底層機制互動圖解

有索引，不代表不必讀資料。有 join，不代表兩張表各讀一次就做完。交易同時執行，也不代表結果一定等同於輪流執行。

這篇不講 SQL 怎麼寫，而是往下看資料庫怎麼完成工作。七張互動圖依照 CS 411 講義的機制，用小例子呈現資料移動與狀態改變；不是特定資料庫產品的完整實作。

按「下一步」觀察一次變化，「上一步」對照前後，「重設」重新走過。切換情境會從頭開始。手機上的圖可以左右捲動，不會把文字一起縮得很小。

資料頁與掃描

課程把磁碟與記憶體之間的搬運單位叫作 page，也就是 block。就算只需要一筆紀錄，通常也要先把它所在的一頁讀進來。

圖中有十二筆紀錄，每頁兩筆。目標是找出 key 5 到 8。先比較全表掃描與索引掃描，再把同樣的目標紀錄分散到不同頁。

答案都是四筆，但集中配置的索引路徑只讀兩個資料頁，分散配置要讀四頁；全表掃描則讀六頁。索引裡的 key 有排序，不代表實際資料也靠在一起。

這裡只計算資料頁讀取，索引本身的導航成本另計。假設從冷快取開始、已讀的頁不被淘汰，而且需要的欄位不全在索引內，不能只讀索引就回答。真實系統還會受到 buffer pool、預讀、循序與隨機 I/O 的影響。頁數能幫助推理，但不是執行秒數。

B+ tree 導航與 leaf 分裂

Internal node 的 key 用來指路，leaf entry 再指向資料紀錄。範圍搜尋只要先找到下界，接著沿 leaf chain 往前讀，直到超過上界。

範圍 [25,65] 裡雖然沒有 key 25，仍能找到 30、40、50、60、65。看到 80，就知道可以停了。從索引找到位置和真正取得資料紀錄，是兩段不同的工作。

切換到插入。依講義的定義，d=2 時，非 root leaf 至少兩個、最多四個 key。把 25 插入已滿的 leaf，會先出現 overflow，再拆成兩個與三個 entry，接好 next-leaf 指標，最後把右側第一個 key 複製到父節點。Leaf 裡的 30 不會消失。

中途畫面是為了拆解更新步驟，不表示其他交易能看到這些暫態。這次父節點還有空位；若父節點也滿，分裂可能往上傳，甚至產生新的 root。Internal node 分裂的規則不完全等同於 leaf 複製分隔鍵；刪除、借位、latch 與復原也沒有塞進這張小圖。

Hash 目錄擴張與 bucket 分裂

Hash index 用 hash bit 分組，不像 B+ tree 維持一條有序的 leaf chain。這張圖示範 extensible hashing，採用講義的最左側 bit 慣例。

先分清兩個數字：global depth 決定目錄有多大；local depth 表示某個 bucket 用幾個 bit 區分。同一個實體 bucket 可以被多個目錄項目指向。

第一個情境中，滿的 bucket 之 local depth 等於 global depth。先擴大目錄，再用多一個 bit 拆開 bucket、重新分配紀錄。注意：目錄加倍，不是所有資料頁都加倍。

第二個情境接續第一次插入，並先放入 0000。此時目錄已看兩個 bit，但共用的 0 bucket 只看一個。插入 0101 時，只需分裂這個 bucket 並改指標，目錄仍是四格。

圖中的 bit string 是 hash 輸出，不是加密。例子避開相同 hash，也不處理四個 bit 都用完的情況。若許多值共享很長的 prefix，可能要連續擴張；「目錄在記憶體、只讀一個 bucket」是條件，不是永遠一次 I/O 的保證。講義另外介紹的 linear hashing 則逐步增加 bucket，並可能保留 overflow page，兩者不要混在一起。

外部合併排序

資料放不進記憶體，排序就需要借助磁碟。先把一批能放進記憶體的資料排序，寫成一段 run；再合併這些 run。合併時不用把所有 run 全部載入，只保留每段目前要讀的一頁，以及輸出 buffer。

這裡 B(R)=6、M=3。產生 run 時，先讀六頁、寫六頁；合併時再讀六頁。每次比較目前的頭部值，選最小的輸出；輸入頁用完才按需補下一頁，重複值也會留下來。

課程通常不計最後一次輸出寫入，因為下一個 operator 可能直接接走結果。因此成本是 3B(R)=18 次 page I/O。切到「最終結果也落盤」，再加六頁寫入，就變成 4B(R)=24。兩種模式都會計入中間 run 的寫入，不能全部省略。

兩趟排序需要滿足 ceil(B(R)/M) ≤ M−1：第一趟產生的 run 數量，要放得下第二趟的輸入 buffer。三個 buffer 可以兩趟處理六頁；如果變成九頁，就會產生三段 run，需要再多一趟合併。這是固定長度 run 的基本演算法，沒有模擬 replacement selection 或產品特有的最佳化。

Join 的 buffer 配置與重讀成本

Block nested-loop join 會先把外側 relation 的一批資料留在記憶體，再掃描內側 relation。成本常常不只在比對，而是換下一批之後，內側又必須從頭讀一遍。

一頁留給內側輸入，一頁留給輸出，剩下 M−2 頁裝外側資料。完整讀取成本是：

B(R) + ceil(B(R) / (M − 2)) × B(S)

兩邊各四頁時，只有三個 buffer，就要完整掃 S 四次；四個 buffer 時，降成兩次；六個 buffer 能放下全部 R，所以 S 只掃一次。這個模型假設沒有額外快取把 S 留到下一輪，不計輸出寫入與 CPU 比對成本。

這不代表 nested loop 一定最適合。較小的一邊若能連同查找結構放進記憶體，one-pass hash join 可以先 build，再掃另一邊做 probe。資料更大時，partitioned hash join 會先把兩邊分桶寫到磁碟，再逐對處理；但某個 key 太集中，單一 partition 仍可能大到放不下。輸入已排序時，merge join 也可能合適。要一起看記憶體、key 分布、索引和後續是否需要排序。

過濾位置與中間資料量

在決定用哪種實體 join 之前，邏輯計畫本身也能調整。假如 inner join 後面的條件只用到客戶欄位，就可以先在客戶端過濾，再 join，讓較少紀錄進入後續處理。

這份示意資料刻意設得均勻：一百位客戶，每人剛好十筆訂單，每筆訂單都正確指向一位唯一的客戶。篩出 5% 客戶時，先過濾能讓 join 只產生五十筆，而不是一千筆；篩出 80% 時，差距就小很多。

圖裡的是筆數，不是耗時估算。 兩方案仍完整掃描底層資料，沒有利用索引捷徑。中間結果也可能直接 pipeline 給下一步，不一定寫成暫存表。這裡單獨比較的是通過 join 的資料量。

Optimizer 還會比較掃描路徑、join 順序、實體演算法與統計資料。講義用 dynamic programming 從小的候選計畫逐步組出大的計畫。如果資料傾斜、欄位相關性讓筆數估錯，原本看起來便宜的計畫就可能很貴。這張圖的改寫也不能直接套到所有 outer join、aggregate 或帶副作用的運算。

交易排程與衝突圖

「有沒有交錯執行」和「能不能等同序列執行」是兩個問題。要檢查 conflict serializability，可以把讀寫順序轉成 precedence graph。

每個節點是一筆 transaction。不同交易碰到同一個資料項，且至少有一個是 write，就從較早操作的交易，連向較晚操作的交易。Read/read 不衝突；檢查時也不能只看相鄰操作，先前相關的操作都要考慮。

兩個例子都保留各交易自己的 R(A)、W(A)、R(B)、W(B) 順序，只改變交錯方式。第一種在 A、B 上都要求 T1 在 T2 前。第二種在 A 上要求 T1 在前，在 B 上卻要求 T2 在前，於是形成 cycle。

完整的 precedence graph 沒有 cycle，就符合 conflict serializability；拓樸排序能給出一個等價的序列順序。目前還沒出現 cycle，不代表尚未完成的排程已經通過檢查。 有 cycle 可以否定 conflict serializability，但不能單靠它判斷更廣的 view serializability。

這不是 deadlock 圖：邊代表衝突操作的先後，不是正在等誰的鎖。Commit、abort、可恢復性、鎖定協定和 MVCC 是其他層次的問題，不能因為這張圖通過就一起推論成立。

怎麼用這些圖複習

按下一步前，先猜這次需要改的是哪個東西：記憶體裡的一頁、指標、buffer 配置、中間筆數，還是一條圖的邊。再說出為什麼非改不可。能預測下一個狀態，比記得動畫長什麼樣更有用。

想接著讀完整筆記，可以看 B+ tree 與 hash index、實體運算子、查詢最佳化，以及交易與隔離。

講義來源與範圍

依據提供的 CS 411 Database Systems 課程資料，投影片作者為 Abdu Alawini。互動圖是另外繪製的小例子，不是課程官方動畫。解說對照相應逐字稿，口述或轉錄中的數字誤差不直接當成定義。

這次提供的講義沒有獨立的 recovery 講次，因此這篇先不增加 WAL／復原互動圖。SQL、ER 建模與特定資料庫產品的行為，也不在這篇範圍內。