跳轉到

8.1 資料庫如何使用磁碟#

概念說明#

資料庫儲存引擎把磁碟空間組織成「表空間（tablespace）→ 段（segment）→ 區（extent）→ 分頁」的層次，所有 I/O 以分頁為單位（InnoDB 預設 16KB），並以緩衝池（buffer pool）為中介：

  • 表檔案：每張表一個（或多個）檔案，檔案被切成編號的分頁。
  • 主鍵叢集索引：InnoDB 中表本身就是主鍵 B+tree，葉分頁放完整記錄（叢集組織）。
  • 二級索引：另一棵 B+tree，葉分頁放「索引鍵 + 主鍵」，查詢後需回表。
  • 緩衝池：記憶體中最大的區域，用改進型 LRU 管理（見 2.3 節）；所有頁讀寫都經過它。
  • 系統表空間 / undo / redo log：支援交易與當機恢復。

讀取一列資料的完整路徑（以主鍵查詢為例）：

  1. SQL 層解析、優化器選擇用主鍵索引。
  2. B+tree 從根分頁下行：根分頁幾乎一定在緩衝池（命中率接近 100%）。
  3. 中間與葉分頁：熱資料在緩衝池（0 次 I/O），冷資料 1~2 次隨機 I/O。
  4. 葉分頁即記錄（叢集索引），直接回傳。

這條路徑解釋了兩個實務現象：熱資料查詢為什麼快如記憶體（緩衝池命中），以及為什麼資料庫伺服器的記憶體那麼重要（緩衝池命中率每降 10%，平均延遲可能翻倍）。

演算法步驟：緩衝池驅動的分頁讀取#

  1. 計算目標分頁編號（由索引或全表掃描決定）。
  2. 緩衝池查哈希表：命中 → 直接返回頁。
  3. 未命中 → 選犧牲頁（LRU/時鐘），髒頁先寫回，讀入新頁。
  4. 頁內以槽頁結構（2.2 節）定位記錄。

Python 範例：迷你儲存引擎#

import bisect, random

class Page:
    def __init__(self, pid):
        self.pid, self.records, self.dirty = pid, {}, False

class MiniStorageEngine:
    def __init__(self, buf_size=4, disk=None):
        self.buf_size = buf_size
        self.buffer = {}              # pid → Page（LRU 用 OrderedDict 概念）
        self.lru = []
        self.disk = disk if disk is not None else {}
        self.io = {"r": 0, "w": 0}
        self.index = []               # 簡化：主鍵有序列表（真實為 B+tree）
        self.pages_of = {}            # 主鍵 → pid

    def _get_page(self, pid):
        if pid in self.buffer:
            self.lru.remove(pid); self.lru.append(pid)
            return self.buffer[pid]
        self.io["r"] += 1
        page = Page(pid)
        page.records = self.disk.get(pid, {})
        if len(self.buffer) >= self.buf_size:      # 驅逐 LRU
            victim = self.lru.pop(0)
            vpage = self.buffer.pop(victim)
            if vpage.dirty:
                self.io["w"] += 1
                self.disk[victim] = vpage.records
        self.buffer[pid] = page; self.lru.append(pid)
        return page

    def insert(self, key, val):
        if not self.pages_of or key > self.index[-1]:
            pid = (max(self.pages_of.values()) + 1) if self.pages_of else 0
        else:
            pid = self.pages_of[self.index[bisect.bisect_left(self.index, key)]]
        page = self._get_page(pid)
        page.records[key] = val; page.dirty = True
        bisect.insort(self.index, key)
        self.pages_of[key] = pid

    def point_query(self, key):
        if key not in self.pages_of: return None
        page = self._get_page(self.pages_of[key])
        return page.records.get(key)

eng = MiniStorageEngine(buf_size=3)
for i in range(10):
    eng.insert(i, f"val{i}")
random.seed(1)
hot = [3, 4, 5]
for _ in range(20):
    eng.point_query(random.choice(hot))      # 熱資料重複查
print("熱資料 20 次查詢 → 磁碟讀:", eng.io["r"], "（緩衝池命中）")
eng.point_query(9)                            # 冷頁可能需驅逐
print("含冷頁後 I/O:", eng.io)

複雜度與 I/O 成本分析#

  • 主鍵點查詢：樹高 h 次 I/O；緩衝池命中上層時，冷葉頁 1 次、熱葉頁 0 次。
  • 二級索引查詢：索引樹 h 次 + 回表 h 次，最壞 2h 次 I/O——覆蓋索引可省一半。
  • 插入（自增主鍵）：只碰最右葉，緩衝池友好；隨機主鍵：每筆可能觸發不同葉頁換入換出。
  • 緩衝池命中率 H 時，平均每查詢 I/O ≈ h × (1−H)。

練習#

  1. 用 buf_size=2 重跑熱資料查詢，觀察命中率下降對 I/O 的影響，畫出「命中率 vs 緩衝池大小」。
  2. 說明二級索引為何需要「回表」，並解釋覆蓋索引省 I/O 的原理。
  3. 比較 InnoDB（叢集）與 PostgreSQL（堆檔 + 索引）在主鍵範圍掃描的 I/O 差異。