1.2 磁碟的物理結構與存取成本#

概念說明#

傳統硬碟（HDD）是機械裝置。一顆硬碟內有多片碟盤（platter），每片碟盤由磁頭（head）讀寫，碟盤分為許多磁軌（track），每條磁軌再切成多個磁區（sector，實體最小單位，通常 512B），作業系統再把多個磁區合成區塊（block，邏輯最小單位，常為 4KB）。所有碟盤同一半徑上的磁軌疊成一個磁柱（cylinder）。

完成一次磁碟 I/O，時間由四部分組成：

1. 尋找時間（seek time）：磁頭移動到目標磁軌的時間。全行程約 8~12ms，平均約 4~8ms。
2. 旋轉延遲（rotational latency）：等待葉片轉到目標磁區。7200 RPM 轉一圈 8.33ms，平均旋轉延遲約 4.17ms。
3. 傳輸時間（transfer time）：實際讀寫資料。循序讀取約 100~250MB/s。
4. 控制器與佇列時間：定址、排隊等。

典型 7200 RPM 硬碟，一次隨機存取約 5~12ms。這個毫秒級常數乘上千萬次 I/O，就是所有磁碟演算法的成本核心。關鍵洞察：

• 隨機 I/O 天價，循序 I/O 便宜：讀連續磁區幾乎不需尋找與旋轉時間，吞吐量高達 200MB/s；隨機 4KB 讀取卻只有 100~200 IOPS。
• 一次多帶一點：若一頁 4KB 已花 10ms，順便多讀 100KB 只要 0.5ms，攤提成本極低。這催生了預讀（readahead）、多頁節點、合併排序等所有磁碟演算法。

演算法步驟：推導成本模型與模擬#

步驟 1：寫下單次 I/O 時間 T = seek_avg + rotational_avg + B/transfer_rate

步驟 2：演算法總時間 = T × I/O 次數，把「I/O 次數」當作與計數比較同等重要的一階複雜度。

步驟 3：比較不同佈局策略的 I/O 次數（連續 vs 隨機）。

# 01.2 範例：HDD 成本模型模擬
import random, math

DISK = {
    "rpm": 7200,
    "seek_avg_ms": 6.0,
    "transfer_rate_MBps": 150,   # 循序傳輸
}

def rotation_avg_ms(rpm: int) -> float:
    return 60_000 / rpm / 2          # 平均半圈

def io_time_ms(block_kb: float, seek_ms: float = DISK["seek_avg_ms"]) -> float:
    rot = rotation_avg_ms(DISK["rpm"])
    transfer = block_kb / 1024 / DISK["transfer_rate_MBps"] * 1000
    return seek_ms + rot + transfer

def read_blocks_random(n, block_kb=4):
    """隨機讀 n 個 4KB 區塊"""
    per = io_time_ms(block_kb)
    return n * per

def read_blocks_sequential(n, block_kb=4):
    """循序讀相鄰區塊：只有第一次要尋找"""
    total_kbytes = n * block_kb
    return DISK["seek_avg_ms"] + rotation_avg_ms(DISK["rpm"]) + \
           total_kbytes / 1024 / DISK["transfer_rate_MBps"] * 1000

# 展示：量級比較
n = 100_000   # 100 萬個... 這裡示 10 萬個 4KB 區塊（約 400MB）
print(f"平均單次 4KB 隨機 I/O   : {io_time_ms(4):.2f} ms")
print(f"10 萬區塊隨機讀取      : {read_blocks_random(n)/1000:.1f} 秒")
print(f"10 萬區塊循序讀取      : {read_blocks_sequential(n)/1000:.1f} 秒")
print(f"循序/隨機加速倍數      : {read_blocks_random(n)/read_blocks_sequential(n):.2f}x")

# QPS / IOPS 推導
print(f"HDD 隨機 4KB IOPS 理論上限: {1000 / io_time_ms(4):.0f} 次/秒")

執行後可見：同樣 400MB 資料，隨機讀約需 20 分鐘（10ms × 10 萬），循序讀只要約 3 秒，相差數百倍。任何排序、索引演算法都應該依此取捨。

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

設平均尋找 6ms、旋轉延遲 4.17ms、傳輸 150MB/s：

結論：增加每顆 I/O 的資料量幾乎不增加時間，因此「大頁、批次、預讀」是磁碟演算法的三大基石。這也導致磁碟演算法習慣以「I/O 次數」為第一階複雜度，例如檔案系統檔案指標定址鏈的長度、B-tree 的高度等。

練習#

1. 一顆 7200 RPM 硬碟，平均尋找 8ms，請推導一次隨機 4KB 讀取所需時間，以及每秒最多能服務多少隨機讀取。
2. 同上硬碟，讀 100MB 的容量（一個 100MB 的檔案），若資料連續存放與隨機分散成 2 萬個 4KB 片段，各需多久？由此推論檔案碎片的效能影響。
3. 寫程式改模擬以上成本模型，改變 block_kb 從 1 到 64 KB，畫出「吞吐量 vs 區塊大小」曲線，並說明為何越大區塊但傳輸時間不是問題。