第03课：页式存储

存储引擎 第3课 / 共25课

📖 课程概述

页式存储是数据库存储引擎的基础。数据在磁盘上以固定大小的页(Page)为单位组织，这是磁盘I/O和内存管理的基本单位。本课深入讲解页的内部结构、行格式、空闲空间管理，以及页的分裂与合并。

本课目标：掌握页的内部结构设计，理解行格式与变长字段存储，实现页级空闲空间管理。

📄 页的内部结构

InnoDB数据页结构 (16KB): ┌──────────────────────────────────────┐ │ File Header (38B) 文件头 │ ← 页的元信息 ├──────────────────────────────────────┤ │ Page Header (56B) 页头 │ ← 页内统计信息 ├──────────────────────────────────────┤ │ Infimum + Supremum (26B) 最小最大记录│ ← 虚拟记录 ├──────────────────────────────────────┤ │ User Records 用户记录 │ ← 从低地址向高地址增长 │ ┌──────────┐┌──────────┐ │ │ │ Record 1 ││ Record 2 │ ... │ │ └──────────┘└──────────┘ │ ├──────────────────────────────────────┤ │ Free Space 空闲空间 │ ← 中间区域 ├──────────────────────────────────────┤ │ Page Directory 页目录 │ ← 从高地址向低地址增长 │ [Slot3][Slot2][Slot1] │ ← 二分查找槽 ├──────────────────────────────────────┤ │ File Trailer (8B) 文件尾 │ ← 校验信息 └──────────────────────────────────────┘

行格式详解

Compact行格式: ┌──────────┬──────────┬──────┬──────────┬─────────┬──────────┐ │ 变长字段 │ NULL值 │记录头│ 隐藏列 │ 列数据 │ 溢出页 │ │ 长度列表 │ 位图 │信息 │(trx_id │ │ 指针 │ │ │ │ │ roll_id) │ │ │ │ 2-3B/列 │ N/8字节 │ 5B │ 12B │ 变长 │ 20B │ └──────────┴──────────┴──────┴──────────┴─────────┴──────────┘ 记录头信息 (5字节): ┌──────┬──────┬──────┬──────┬──────┬──────┬──────┐ │delete│min_re│n_own│heap_n│record│next_r│ ... │ │_flag │c_flag│ed │ |_type │ec_off│ │ └──────┴──────┴──────┴──────┴──────┴──────┴──────┘

💻 C语言实现：页式存储引擎

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

#define PAGE_SIZE 4096
#define MAX_RECORDS_PER_PAGE 200
#define MAX_FIELD_SIZE 255
#define MAX_FIELDS 8

// ============ 记录头 ============
typedef struct {
    uint32_t record_id;
    uint16_t data_offset;    // 数据在页内的偏移
    uint16_t data_length;
    uint8_t  delete_flag;    // 删除标记
    uint8_t  field_count;
    uint16_t field_offsets[MAX_FIELDS]; // 每个字段的偏移
} RecordHeader;

// ============ 页头 ============
typedef struct {
    uint32_t page_id;
    uint32_t prev_page;       // 前一页(链表)
    uint32_t next_page;       // 后一页
    uint16_t num_records;
    uint16_t first_free;      // 第一个空闲记录偏移
    uint16_t data_free_start; // 数据区空闲起始
    uint16_t data_free_end;   // 数据区空闲结束(从页尾算)
    uint16_t num_deleted;     // 已删除记录数
} PageHeader;

// ============ 页目录 ============
typedef struct {
    uint16_t slot_offset;     // 槽指向的记录偏移
    uint16_t owned_records;   // 该槽拥有的记录数
} PageDirectorySlot;

// ============ 完整页面 ============
typedef struct {
    PageHeader         header;
    RecordHeader       records[MAX_RECORDS_PER_PAGE];
    PageDirectorySlot  dir_slots[32];
    uint8_t            data[PAGE_SIZE - sizeof(PageHeader)
                           - sizeof(RecordHeader) * MAX_RECORDS_PER_PAGE
                           - sizeof(PageDirectorySlot) * 32];
} Page;

// ============ 页操作 ============
Page* page_create(uint32_t page_id) {
    Page* p = calloc(1, sizeof(Page));
    p->header.page_id = page_id;
    p->header.prev_page = UINT32_MAX;
    p->header.next_page = UINT32_MAX;
    p->header.data_free_start = 0;
    p->header.data_free_end = sizeof(p->data);
    printf("[Page] 创建页 %u，数据区大小: %zu 字节\n",
           page_id, sizeof(p->data));
    return p;
}

// 计算记录所需空间
int record_size(int field_count, const int* field_sizes) {
    int total = 0;
    for (int i = 0; i < field_count; i++) {
        total += field_sizes[i];
    }
    return total;
}

// 插入记录
int page_insert(Page* p, int field_count, const int* field_sizes,
                const char** field_data) {
    if (p->header.num_records >= MAX_RECORDS_PER_PAGE) {
        printf("[Page] 页 %u: 记录数已满\n", p->header.page_id);
        return -1;
    }
    int total_data = record_size(field_count, field_sizes);
    int avail = p->header.data_free_end - p->header.data_free_start;
    if (total_data > avail) {
        printf("[Page] 页 %u: 空间不足 (需要%d, 可用%d)\n",
               p->header.page_id, total_data, avail);
        return -1;
    }
    // 分配记录头
    int rid = p->header.num_records;
    RecordHeader* rh = &p->records[rid];
    rh->record_id = rid;
    rh->delete_flag = 0;
    rh->field_count = field_count;
    // 从页尾分配数据空间
    p->header.data_free_end -= total_data;
    rh->data_offset = p->header.data_free_end;
    rh->data_length = total_data;
    // 复制字段数据
    int offset = 0;
    for (int i = 0; i < field_count; i++) {
        rh->field_offsets[i] = offset;
        memcpy(p->data + rh->data_offset + offset,
               field_data[i], field_sizes[i]);
        offset += field_sizes[i];
    }
    p->header.num_records++;
    printf("[Page] 页 %u: 插入记录 %d (数据%d字节, 剩余%d字节)\n",
           p->header.page_id, rid, total_data,
           p->header.data_free_end - p->header.data_free_start);
    return rid;
}

// 删除记录(标记删除)
void page_delete(Page* p, int record_id) {
    if (record_id >= (int)p->header.num_records) return;
    p->records[record_id].delete_flag = 1;
    p->header.num_deleted++;
    printf("[Page] 页 %u: 删除记录 %d (标记删除)\n",
           p->header.page_id, record_id);
}

// 读取字段
const char* page_get_field(Page* p, int record_id, int field_idx,
                           int* out_size) {
    if (record_id >= (int)p->header.num_records) return NULL;
    RecordHeader* rh = &p->records[record_id];
    if (rh->delete_flag) {
        printf("[Page] 记录 %d 已删除\n", record_id);
        return NULL;
    }
    int start = rh->field_offsets[field_idx];
    int end = (field_idx + 1 < rh->field_count)
              ? rh->field_offsets[field_idx + 1]
              : rh->data_length;
    *out_size = end - start;
    return (const char*)(p->data + rh->data_offset + start);
}

// 页压缩(清除已删除记录)
void page_compact(Page* p) {
    int write_rid = 0;
    for (int i = 0; i < (int)p->header.num_records; i++) {
        if (!p->records[i].delete_flag) {
            if (write_rid != i) {
                p->records[write_rid] = p->records[i];
                p->records[write_rid].record_id = write_rid;
            }
            write_rid++;
        }
    }
    p->header.num_records = write_rid;
    p->header.num_deleted = 0;
    printf("[Page] 页 %u: 压缩完成，剩余 %u 条记录\n",
           p->header.page_id, p->header.num_records);
}

// 打印页状态
void page_dump(Page* p) {
    printf("\n=== 页 %u 状态 ===\n", p->header.page_id);
    printf("记录数: %u  已删除: %u\n",
           p->header.num_records, p->header.num_deleted);
    printf("数据区: [%u, %u)  空闲: %d 字节\n",
           p->header.data_free_start, p->header.data_free_end,
           p->header.data_free_end - p->header.data_free_start);
    for (uint32_t i = 0; i < p->header.num_records; i++) {
        RecordHeader* rh = &p->records[i];
        printf("  记录%u: offset=%u len=%u deleted=%d fields=%d\n",
               rh->record_id, rh->data_offset, rh->data_length,
               rh->delete_flag, rh->field_count);
    }
}

// ========== 主函数 ==========
int main() {
    printf("╔══════════════════════════════════════╗\n");
    printf("║   页式存储引擎 v0.1                  ║\n");
    printf("╚══════════════════════════════════════╝\n\n");

    Page* p = page_create(0);

    // 插入记录
    printf("--- 插入记录 ---\n");
    for (int i = 0; i < 8; i++) {
        char name[32], city[32];
        snprintf(name, sizeof(name), "User_%d", i);
        snprintf(city, sizeof(city), "City_%d", i * 7 % 5);
        int age = 20 + i * 3;
        const char* data[] = {name, (char*)&age, city};
        int sizes[] = {strlen(name), sizeof(int), strlen(city)};
        page_insert(p, 3, sizes, data);
    }

    page_dump(p);

    // 删除部分记录
    printf("\n--- 删除记录 ---\n");
    page_delete(p, 2);
    page_delete(p, 4);
    page_delete(p, 5);

    page_dump(p);

    // 页压缩
    printf("\n--- 页压缩 ---\n");
    page_compact(p);
    page_dump(p);

    printf("\n✅ 页式存储引擎运行完成\n");
    return 0;
}

🐍 Python实现：页级空间管理模拟

"""
页级空间管理模拟 - 展示行格式与碎片整理
"""
from dataclasses import dataclass, field
from typing import List, Optional, Tuple

@dataclass
class Record:
    rid: int
    fields: List[bytes]
    deleted: bool = False

class StoragePage:
    """模拟数据库页的存储管理"""
    PAGE_SIZE = 4096
    HEADER_SIZE = 64
    SLOT_SIZE = 8  # 每个槽占8字节(偏移+长度)

    def __init__(self, page_id: int):
        self.page_id = page_id
        self.records: List[Record] = []
        self.free_space = self.PAGE_SIZE - self.HEADER_SIZE
        self.fragmented_space = 0  # 碎片空间(删除记录释放)
        self.slot_count = 0
        self.next_rid = 0

    def _used_space(self) -> int:
        total = self.HEADER_SIZE + self.slot_count * self.SLOT_SIZE
        for r in self.records:
            if not r.deleted:
                total += sum(len(f) for f in r.fields)
        return total

    def insert(self, *field_values) -> Optional[int]:
        """插入一条记录，字段值自动转为bytes"""
        fields = []
        for v in field_values:
            if isinstance(v, int):
                fields.append(v.to_bytes(4, 'little'))
            elif isinstance(v, str):
                fields.append(v.encode('utf-8'))
            elif isinstance(v, bytes):
                fields.append(v)
            else:
                fields.append(str(v).encode('utf-8'))

        record_size = sum(len(f) for f in fields)
        needed = record_size + self.SLOT_SIZE

        if needed > self.free_space:
            # 尝试压缩后插入
            self.compact()
            if needed > self.free_space:
                return None  # 页满

        rid = self.next_rid
        self.next_rid += 1
        self.records.append(Record(rid=rid, fields=fields))
        self.free_space -= needed
        self.slot_count += 1
        return rid

    def delete(self, rid: int) -> bool:
        for r in self.records:
            if r.rid == rid and not r.deleted:
                r.deleted = True
                freed = sum(len(f) for f in r.fields) + self.SLOT_SIZE
                self.fragmented_space += freed
                return True
        return False

    def compact(self):
        """碎片整理 - 清除删除标记的记录，回收空间"""
        before = self.fragmented_space
        self.records = [r for r in self.records if not r.deleted]
        # 重新编号
        for i, r in enumerate(self.records):
            r.rid = i
        self.next_rid = len(self.records)
        self.slot_count = len(self.records)
        self.free_space += self.fragmented_space
        self.fragmented_space = 0
        return before

    def get_record(self, rid: int) -> Optional[Record]:
        for r in self.records:
            if r.rid == rid and not r.deleted:
                return r
        return None

    def scan(self) -> List[Record]:
        return [r for r in self.records if not r.deleted]

    def stats(self) -> dict:
        active = len([r for r in self.records if not r.deleted])
        deleted = len([r for r in self.records if r.deleted])
        total_data = sum(sum(len(f) for f in r.fields)
                        for r in self.records if not r.deleted)
        return {
            "page_id": self.page_id,
            "active_records": active,
            "deleted_records": deleted,
            "free_space": self.free_space,
            "fragmented": self.fragmented_space,
            "data_bytes": total_data,
            "utilization": f"{(total_data / self.PAGE_SIZE * 100):.1f}%"
        }

# ========== 演示 ==========
page = StoragePage(0)
print("=== 页式存储模拟 ===\n")

# 插入数据
rids = []
for i in range(20):
    rid = page.insert(f"user_{i}", 20 + i, f"city_{i%3}",
                      f"email_{i}@test.com")
    rids.append(rid)
    if rid is None:
        print(f"  插入第{i}条记录时页满!")
        break

print(f"\n插入后状态: {page.stats()}")

# 删除一些记录
for i in range(0, len(rids), 3):
    page.delete(rids[i])
print(f"删除后状态: {page.stats()}")

# 压缩
freed = page.compact()
print(f"压缩回收: {freed} 字节")
print(f"压缩后状态: {page.stats()}")

# 继续插入
for i in range(20, 30):
    rid = page.insert(f"user_{i}", 20 + i, f"city_{i%3}")
    if rid is None:
        break
print(f"\n最终状态: {page.stats()}")

# 扫描
print(f"\n活跃记录:")
for r in page.scan():
    fields = [f.decode('utf-8', errors='replace') for f in r.fields]
    print(f"  RID={r.rid}: {fields}")

print("\n✅ Python页式存储模拟完成")

📊 性能分析

页大小对性能的影响: ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 页大小 I/O效率 空间利用率 适用场景 1KB 低 高(87%) 嵌入式/小记录 4KB 中 高(83%) 通用(大部分OS默认) 8KB 中高 中(78%) OLTP(InnoDB用16KB) 16KB 高 中(72%) 大记录/范围扫描 32KB 高 低(65%) OLAP/列存储 64KB 很高 低(58%) 大数据扫描 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ InnoDB选择16KB: OLTP场景的I/O和空间折中

🔑 关键概念总结

📝 练习

  1. 实现溢出页机制：当一条记录超过页大小一半时，将部分数据存储到溢出页
  2. 添加页目录的二分查找功能，测量10万次查找的性能
  3. 模拟不同页大小(1K/4K/8K/16K)下的空间利用率，找出最优页大小
  4. 实现多页链表(双向链表)，支持跨页的范围扫描
📄

🏆 成就解锁：页式架构师

掌握页式存储，你已理解数据库如何在磁盘上组织数据！

✅ 页内部结构 · ✅ 行格式设计 · ✅ 空间管理