2.2 記錄與槽頁結構#
概念說明#
上一節的頁結構有明顯缺陷：刪除一筆記錄後浪費空間；記錄在頁內的位置一旦改變，所有指向它的指標都會失效。資料庫與檔案系統普遍採用槽頁（slotted page）解決這些問題，核心思想是把頁分成兩端：
┌────────────────────────┐
│ 頁首 header │ ← slot_count, free_ptr, ...
│ slot[0] (offset,size) │
│ slot[1] │
│ ... │
│ slot[n-1] │ ← slot 目錄與記錄資料相向增長
│ 空閒空間 │
│ record[n-1] (資料) │
│ ... │
│ record[1] │
│ record[0] │ ← 頁尾
└────────────────────────┘
- slot 目錄（slot directory）：每個槽存放「記錄資料在頁內的偏移」與「長度」，槽編號固定，因此可用「(頁號, 槽號)」當作記錄的"位址"，即使資料在頁內被搬移也不會失效。
- 刪除記錄時，其資料區可以回收，槽可以標為空，或壓縮合併。
- 更新記錄時：若新記錄，放不下，可以放溢位（overflow）頁；或把指標改為「間接引用」。
記錄（tuple）本身通常分成： - 定長記錄：每筆大小相同，可直接用槽號計算偏移，效率最高。 - 變長記錄：長度不一，需要槽；常見做法是「slot 內放 offset+size」，或記錄開頭放一個「類型／NULL 位圖 + 各欄長度」。
演算法步驟：槽頁的插入、刪除、更新#
- 插入：從 free_ptr 取得 free_start，寫入
slot[n] = (free_ptr - len, len)，slot_count + 1。 - 刪除：
- 資料區不動，slot 標記為「空」或在 slot 目錄做壓縮排尋。
- 壓縮合併：把位於附近的 slot 去重。
- 更新：
- 新長度 ≤ 舊長度：原地壓縮（可選：
<nil 時減 slot.size）。 - 新長度 > 舊長度：若頁內 free 空間夠，搬移資料；否則走溢位頁。
- 壓縮（compaction）：把有效記錄往頁尾搬齊，讓 free 空間連續。
# 02.2 範例：完整的槽頁實作
import struct
PAGE_SIZE = 128
EMPTY = 0xFFFFFFFE
class SlottedPage:
PAGE_HDR = 4 # u16 slot_count + u16 free_ptr
SLOT_SIZE = 4 # u16 offset + u16 size
def __init__(self, data: bytearray | None = None):
self.p = data if data is not None else bytearray(PAGE_SIZE)
struct.pack_into("<HH", self.p, 0, 0, PAGE_SIZE) # (count, free_ptr)
@property
def count(self) -> int:
return struct.unpack_from("<H", self.p, 0)[0]
@property
def free_ptr(self) -> int:
return struct.unpack_from("<H", self.p, 2)[0]
def _set_header(self, count, free_ptr):
struct.pack_into("<HH", self.p, 0, count, free_ptr)
def new_slot(self, rec: bytes) -> int:
"""插入記錄，回傳槽號；空間不足回 -1"""
need = self.SLOT_SIZE + len(rec)
slots_end = self.PAGE_HDR + self.count * self.SLOT_SIZE
if self.free_ptr - slots_end < need:
return -1
off = self.free_ptr - len(rec)
self.p[off:off + len(rec)] = rec
struct.pack_into("<HH", self.p,
self.PAGE_HDR + self.count * self.SLOT_SIZE,
off, len(rec))
self._set_header(self.count + 1, off)
return self.count - 1
def get(self, sid: int) -> bytes:
base = self.PAGE_HDR + sid * self.SLOT_SIZE
off, size = struct.unpack_from("<HH", self.p, base)
return bytes(self.p[off:off + size])
def delete(self, sid: int):
base = self.PAGE_HDR + sid * self.SLOT_SIZE
struct.pack_into("<HH", self.p, base, 0, 0) # slot 清空
def compact(self):
"""壓縮：把所有有效記錄往頁尾搬齊，slot 同步重排"""
recs = []
for i in range(self.count):
base = self.PAGE_HDR + i * self.SLOT_SIZE
off, size = struct.unpack_from("<HH", self.p, base)
if size:
recs.append(bytes(self.p[off:off + size]))
new_p = bytearray(PAGE_SIZE)
struct.pack_into("<HH", new_p, 0, len(recs), PAGE_SIZE)
off = PAGE_SIZE
for i, r in enumerate(recs):
off -= len(r)
new_p[off:off + len(r)] = r
struct.pack_into("<HH", new_p, self.PAGE_HDR + i * self.SLOT_SIZE,
off, len(r))
self.p = new_p
def demo():
page = SlottedPage()
ids = []
for i in range(20):
sid = page.new_slot(f"rec{i:03d}".encode())
if sid >= 0:
ids.append(sid)
print(f"放入 {len(ids)} 筆記錄, free_ptr = {page.free_ptr}")
page.delete(ids[3]); page.delete(ids[7])
print("刪除 2 筆後:", sum(1 for i in range(page.count)
if struct.unpack_from('<H', page.p,
page.PAGE_HDR+i*page.SLOT_SIZE+2)[0]))
page.compact()
print(f"壓縮後 free_ptr = {page.free_ptr}, 槽數 = {page.count}")
if __name__ == "__main__":
demo()
複雜度與 I/O 成本分析#
- 插入：O(1)（頁內），I/O 成本：1 讀 + 1 寫。
- 點存取（給定頁號+槽號）：O(1)，1 筆 I/O。
- 刪除：O(1)；壓縮：O(頁內記錄數) 但僅頁內操作，無額外 I/O。
- 頁空間利用率：槽頁跟純定長結構接近，會留
'slot 目錄 + free_ptr'一些 overhead，一般可達 95% 以上。 - 指標穩定性：
(pid, sid)是不變的"地址"，即使頁內資料搬移或壓縮，指標仍有效；這是槽頁最重要的工程意義——索引、外鍵都依賴它。
練習#
- 改寫
compact()支援「回收空槽」而非全量重建，讓槽號不位移（保留 dual-slot：有效 + 空槽）。分析這對誰有利、誰不利。 - 增加
update(sid, new_rec)：若 new_rec 比舊記錄大且頁內放不下，配置一個新的溢位頁，並在原 slot 存「溢位指標」。實作這段程式。 - 想一個情境：為什麼「append-only（只插入不刪除）」的資料集使用「純定長頁」比使用槽頁更好？