跳轉到

6.1 ISAM 索引#

概念說明#

ISAM（Indexed Sequential Access Method，索引順序存取法）是資料庫史上最古老的索引結構之一，IBM 在 1960 年代為磁帶與磁碟設計。它的立場很極端：索引建好之後就不再修改。

結構分三層：

  1. 資料頁（主區）：記錄依鍵排序存放，頁與頁之間以鏈結串列相連。
  2. 葉層索引：每個資料頁一個項目（該頁最大鍵 + 頁指標）。
  3. 上層索引：對葉層索引再建索引，通常 2~3 層，頂層小到常駐記憶體。

查詢與 B+tree 相同：從頂層往下走到資料頁。因為索引是靜態的，頂層索引讀一次後可以常駐記憶體，實際磁碟 I/O 常常只有 1 次（讀資料頁）——比 B+tree 更快。

代價是插入與刪除。ISAM 的資料頁預留一些空位，插入時就地放入；頁滿了就開溢位頁（overflow page），掛在鏈尾。刪除只標記刪除，不回收。隨著插入越來越多，溢位鏈越拉越長，查詢從「1 次 I/O」退化成「1 + 鏈長次 I/O」。唯一的解法是定期重建（drop and rebuild），離線把資料重新排序、重建靜態索引。

因此 ISAM 適合：資料建好後幾乎只讀不寫的場景——人口統計、字典、歷史歸檔。PostgreSQL 至今仍提供 ISAM 型的靜態索引供這類需求使用。

演算法步驟#

查詢（鍵 k）： 1. 頂層索引定位到葉索引區段（常駐記憶體，0 次 I/O）。 2. 葉索引定位到資料頁 p（1 次 I/O）。 3. 在 p 中二分搜尋；若沒有，沿溢位鏈逐頁找。

插入（鍵 k）： 1. 定位到資料頁 p。 2. p 有空位：插入並維持排序。 3. p 滿：分配新溢位頁，接到 p 的鏈尾，放入該頁。

Python 範例#

import math

class ISAM:
    def __init__(self, data, page_cap=4):
        self.cap = page_cap
        self.pages = []                       # 資料頁：每頁 dict(key→val) + overflow 鏈
        self.overflow = {}                    # 頁編號 → 溢位頁 list
        s = sorted(data)
        self.pages = [s[i:i+page_cap] for i in range(0, len(s), page_cap)]
        # 靜態多層索引
        self.leaf_idx = [p[-1] for p in self.pages]      # 每頁最大鍵
        self.upper = []                                   # 上層索引
        step = page_cap
        layer = self.leaf_idx
        while len(layer) > 1:
            self.upper.append(layer[::step])
            layer = [layer[i] for i in range(0, len(layer), step)]
        self.upper.reverse()
        self.io = 0

    def _find_page(self, key):
        import bisect
        self.io += 1
        i = bisect.bisect_right(self.leaf_idx, key)
        return min(i, len(self.pages) - 1)

    def search(self, key):
        p = self._find_page(key)
        self.io += 1
        if key in self.pages[p]:
            return True
        chain = self.overflow.get(p, [])
        self.io += math.ceil(len(chain) / self.cap)
        return key in chain

    def insert(self, key):
        p = self._find_page(key)
        self.io += 1
        if len(self.pages[p]) < self.cap:
            self.pages[p].append(key); self.pages[p].sort()
        else:
            self.overflow.setdefault(p, []).append(key)

isam = ISAM([5, 12, 3, 21, 8, 17, 30, 2, 9, 25, 14, 6], page_cap=4)
print("資料頁:", isam.pages)
print("查詢 17:", isam.search(17), "| 查詢 99:", isam.search(99))
for k in [31, 32, 33, 34, 35]:
    isam.insert(k)
print("插入後查詢 35:", isam.search(35), "| I/O:", isam.io)
print("溢位鏈:", isam.overflow)

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

  • 查詢（無溢位）：1 次 I/O（頂層常駐記憶體）；比 B+tree 省下葉索引層。
  • 查詢（有溢位）：1 + ⌈鏈長/頁容量⌉ 次 I/O，最壞退化到線性。
  • 插入：1~2 次 I/O，非常便宜（寫溢位頁是追加性質）。
  • 空間：初始主區 + 溢位區；溢位頁利用率低。
  • 定位：ISAM = 讀快寫會退化；B+tree = 讀稍慢但寫不退化。資料靜態選 ISAM，動態選 B+tree。

練習#

  1. page_cap=4，對 20 筆亂數建 ISAM，畫出葉索引與上層索引。
  2. 依序插入 10 個比最大鍵大的鍵，觀察溢位鏈成長與查詢 I/O 的關係。
  3. 設計「鏈長 > 3 觸發局部重建」的策略，說明其與 B+tree 分裂的取捨差異。