跳轉到

2.1 分頁與區塊的觀念#

概念說明#

磁碟 I/O 的最小邏輯單位是「區塊（block）」，作業系統與資料庫習慣稱之為「分頁（page）」。硬碟的物理最小單位是磁區（傳統 512 bytes，現代 4KB），而檔案系統與資料庫會把多個磁區組成一個分頁，常見大小為 4KB、8KB、16KB（MySQL InnoDB 預設 16KB）或 32KB。

為什麼要以分頁為單位？因為磁碟的存取成本主要由「尋找時間 + 旋轉延遲」組成（見 1.2 節），這兩項是固定開銷，與你讀 1 byte 或 16KB 幾乎無關。因此一次讀取越大塊，單位資料的平均成本就越低——這就是「空間局部性」換來的經濟效益。分頁就是這個經濟效益的體制化：所有磁碟演算法（B-tree、外部排序、緩衝池）都以「分頁讀寫次數」為成本單位，而非資料筆數。

分頁設計的三個核心參數：

  1. 分頁大小 P：越大，單次 I/O 攤提越好，但緩衝池能容納的分頁數變少、小記錄浪費的內部碎片變多。
  2. 記錄數/分頁：決定樹狀索引的高度、排序的合併趟數。
  3. 對齊：分頁邊界對齊磁區邊界（甚至 SSD 的 erase block），可避免讀寫放大。

演算法步驟：分頁式檔案的讀取#

  1. 給定記錄編號 r，計算所在分頁：page = r // records_per_page。
  2. 檢查緩衝池是否快取該分頁；若否，發出一次磁碟讀取（成本 1 次 I/O）。
  3. 在分頁內以記憶體速度定位記錄：offset = (r % records_per_page) * record_size。
  4. 若連續讀取多筆記錄，盡量讓它們落在相鄰分頁，觸發預讀（prefetch）。

Python 範例：模擬磁碟分頁#

import random

class Disk:
    """模擬磁碟：以分頁為單位讀寫，統計 I/O 次數"""
    def __init__(self, page_size=4, io_count=0):
        self.page_size = page_size
        self.pages = {}
        self.io_count = 0

    def read_page(self, pid):
        self.io_count += 1
        return self.pages.get(pid, [])

    def write_page(self, pid, data):
        self.io_count += 1
        assert len(data) <= self.page_size, "分頁溢位！"
        self.pages[pid] = data

class PagedFile:
    """把 N 筆記錄依分頁大小切存放進磁碟"""
    def __init__(self, disk, records, record_per_page):
        self.disk = disk
        self.rpp = record_per_page
        self.n = len(records)
        for pid in range((self.n + self.rpp - 1) // self.rpp):
            chunk = records[pid*self.rpp:(pid+1)*self.rpp]
            disk.write_page(pid, chunk)

    def get_record(self, r):
        pid = r // self.rpp
        page = self.disk.read_page(pid)
        return page[r % self.rpp]

random.seed(42)
records = random.sample(range(100000), 1000)
disk = Disk(page_size=100)
pf = PagedFile(disk, records, record_per_page=100)
print(pf.get_record(0), pf.get_record(150))
print("總 I/O 次數（含建檔）:", disk.io_count)

執行後可看到：連續讀取同一分頁內的記錄不必重新讀磁碟（在真實系統中由緩衝池快取），而跨分頁的讀取則各付出一次 I/O。

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

  • 記錄定位：記憶體內 O(1)。
  • 讀取 k 筆隨機記錄：最壞 k 次 I/O；若記錄依序存放且連續，僅 ⌈k/R⌉ 次 I/O。
  • 全檔掃描：N 筆記錄、每分頁 R 筆，共 ⌈N/R⌉ 次 I/O——這是所有磁碟演算法成本的計算基礎。

練習#

  1. 分頁大小從 4KB 加倍到 16KB，全檔掃描的 I/O 次數如何變化？緩衝池固定 64MB 時可快取的分頁數變成多少？
  2. 修改範例程式，統計隨機讀取 100 筆記錄所需的 I/O 次數，與連續讀取前 100 筆比較。
  3. 說明為何分頁大小過大反而可能傷害隨機查詢效能。