跳轉到

4.3 雜湊索引的實務議題#

概念說明#

理論上的雜湊索引「一次 I/O 查到」，實務上有許多折扣因素，設計時必須逐項檢視：

  1. 範圍查詢無效：雜湊打散了鍵的順序，WHERE age BETWEEN 20 AND 30 必須逐桶探測或全表掃描。這是 B+tree 在資料庫中勝出的主因——雜湊索引只適合等值查詢（=、IN）與唯一鍵查找（如主鍵、雜湊 join 的建表階段）。
  2. 雜湊函數的品質：磁碟雜湊常用乘法雜湊、MurmurHash、或資料庫內建的 64-bit 雜湊。若鍵有結構性偏斜（如遞增序號、日期），mod 型雜湊會產生熱點，必須用「攪拌（avalanche）」良好的函數。
  3. 溢位鏈管理：靜態雜湊依賴溢位頁，鏈過長時查詢退化。實務上要監控平均鏈長，超過門檻就重建（rehash to new table），重建成本 O(N) 次 I/O，通常在離峰時段執行。
  4. 桶大小與分頁對齊：一桶一頁最簡單，但桶利用率常僅 60~70%；可讓一桶占多頁或一頁多桶，在空間與 I/O 之間權衡。
  5. 與緩衝池互動：目錄與熱門桶若能常駐緩衝池，等效 I/O 可降為 1 甚至 0；冷熱差異大的工作負載應把熱桶集中配置。
  6. 並發控制：分裂時的鎖順序（先桶後目錄）、latch crabbing 等議題與 B-tree 類似，讀多寫少時可用讀寫鎖。

Python 範例：監控與重建#

import random

class StaticHash:
    def __init__(self, m):
        self.m = m
        self.buckets = [[] for _ in range(m)]
        self.io = 0

    def insert(self, key):
        self.io += 1
        self.buckets[key % self.m].append(key)

    def stats(self):
        lens = [len(b) for b in self.buckets]
        avg = sum(lens) / len(lens)
        var = sum((l - avg) ** 2 for l in lens) / len(lens)
        return avg, var ** 0.5, max(lens)   # 平均、標準差、最長鏈

    def rehash(self, new_m):
        self.io += sum(1 for b in self.buckets if b)   # 讀每個非空桶
        self.m = new_m
        flat = [k for b in self.buckets for k in b]
        self.io += len(flat)                            # 寫回
        self.buckets = [[] for _ in range(new_m)]
        for k in flat:
            self.buckets[k % new_m].append(k)

random.seed(3)
h = StaticHash(m=32)
for _ in range(500):
    h.insert(random.randrange(10**6))
print("M=32 統計（平均, 標準差, 最長）:", h.stats())
h.rehash(128)
print("M=128 統計:", h.stats())

# 展示偏斜鍵的問題：遞增鍵 mod M 完全均勻，但前綴鍵會集中
h2 = StaticHash(m=32)
for i in range(500):
    h2.insert(i * 32)        # 全部落在桶 0
print("偏斜鍵最長鏈:", h2.stats()[2], "→ 必須換雜湊函數")

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

  • 等值查詢：理想 1 次 I/O；含溢位鏈 L 頁時為 L+1 次。
  • 重建：O(N) 次 I/O，但把之後的每次查詢降回 1 次 I/O，屬於典型的攤 sweet spot 決策。
  • 經驗法則：負載因子（記錄數 / 桶容量總和）超過 0.75~0.85 就該規劃重建或改用可成長結構。

練習#

  1. 用範例統計 M=64、記錄 1000 筆時的桶長分布，估計查詢的期望 I/O 次數。
  2. 實作「平均鏈長 > 2 自動 rehash」的策略，比較重建前後的累計 I/O。
  3. 說明什麼樣的工作負載該選雜湊索引、什麼情況必須退讓給 B+tree，各舉一例。