SQL数据库页管理算法如何实现空闲页管理与回收机制

SQL数据库以页为基本存储单位管理磁盘空间，默认页大小通常为8KB，所有表数据、索引、日志都存储在对应的页中。页管理算法需要高效维护空闲页的状态，同时处理已使用页的回收流程，避免存储空间的浪费。

空闲页管理机制

空闲页管理的核心目标是快速定位可用的空闲页，同时保证空闲页状态的准确性，常见的实现方式包含以下几个部分：

空闲页标记

数据库会在系统表空间或者专门的空闲页映射文件中维护空闲页标记，通常使用位图（bitmap）结构，每个位对应一个页的状态，0表示空闲，1表示已使用。这种结构占用空间小，查询和修改的效率都很高。

空闲页查找

当数据库需要分配新页存储数据时，会从空闲页位图中查找第一个标记为0的位，对应的页就是可用的空闲页。如果当前位图中的所有位都被标记为1，说明没有空闲页，需要向操作系统申请新的磁盘空间扩展数据库文件。

空闲页分配

分配空闲页时，首先修改对应位的状态为1，标记该页已被使用，然后返回该页的物理地址给上层调用模块，上层模块就可以往该页中写入数据。分配完成后需要同步更新空闲页位图的持久化存储，避免数据库重启后状态丢失。

以下是简化的空闲页分配逻辑代码示例：

# 空闲页位图，每个元素是一个字节，对应8个页的状态
free_page_bitmap = []
# 页大小，默认8KB
PAGE_SIZE = 8192
# 数据库文件句柄
db_file = None

def init_free_page_bitmap(db_file_path):
    """初始化空闲页位图，读取已有的空闲页状态"""
    global db_file, free_page_bitmap
    db_file = open(db_file_path, "r+b")
    # 读取系统页中的空闲页位图数据，假设前1024字节是位图区域
    db_file.seek(0)
    bitmap_data = db_file.read(1024)
    free_page_bitmap = list(bitmap_data)

def allocate_free_page():
    """分配一个空闲页，返回页号，没有空闲页返回-1"""
    global free_page_bitmap
    for byte_idx, byte_val in enumerate(free_page_bitmap):
        if byte_val != 0xFF:  # 该字节存在空闲位
            for bit_idx in range(8):
                if (byte_val & (1 << bit_idx)) == 0:  # 找到空闲位
                    page_num = byte_idx * 8 + bit_idx
                    # 标记该位为已使用
                    free_page_bitmap[byte_idx] |= (1 << bit_idx)
                    # 同步更新磁盘中的位图
                    db_file.seek(byte_idx)
                    db_file.write(bytes([free_page_bitmap[byte_idx]]))
                    db_file.flush()
                    return page_num
    return -1

页回收机制

页回收机制负责在数据被删除、表被删除或者索引被重建等场景下，将不再使用的页重新标记为空闲页，供后续分配使用，避免存储空间只增不减。

回收触发场景

常见的页回收触发场景包括：执行DELETE语句删除行数据后，对应页的已用空间低于阈值；执行DROP TABLE或者DROP INDEX语句删除数据库对象；执行ALTER TABLE语句修改表结构导致原有页不再适用；数据库定期执行的空间整理任务。

回收流程

页回收的完整流程通常包含以下步骤：

• 首先确定需要回收的页号，比如删除某行数据后，判断该行所在的页是否还有有效数据，如果没有有效数据则标记该页为可回收。
• 对可回收页进行清理，清除页内的残留数据，避免后续分配后泄露旧数据。
• 更新空闲页位图，将对应页的状态从1修改为0，标记为空闲页。
• 如果回收的页是数据库文件的最后一个页，还可以选择收缩数据库文件，释放对应的磁盘空间给操作系统。

以下是简化的页回收逻辑代码示例：

def recycle_page(page_num):
    """回收指定页号的页，将其标记为空闲页"""
    global free_page_bitmap
    byte_idx = page_num // 8
    bit_idx = page_num % 8
    # 检查该页是否已经被标记为已使用
    if (free_page_bitmap[byte_idx] & (1 << bit_idx)) == 0:
        return False  # 已经是空闲页，不需要回收
    # 清理页内数据，将页内容全部写为0
    db_file.seek(page_num * PAGE_SIZE)
    db_file.write(b'x00' * PAGE_SIZE)
    # 更新位图，标记为空闲
    free_page_bitmap[byte_idx] &= ~(1 << bit_idx)
    # 同步更新磁盘中的位图
    db_file.seek(byte_idx)
    db_file.write(bytes([free_page_bitmap[byte_idx]]))
    db_file.flush()
    return True

def shrink_db_file():
    """收缩数据库文件，释放末尾的空闲页对应的磁盘空间"""
    global free_page_bitmap
    total_pages = len(free_page_bitmap) * 8
    # 从最后一个页开始往前找，找到第一个被使用的页
    last_used_page = -1
    for page_num in range(total_pages - 1, -1, -1):
        byte_idx = page_num // 8
        bit_idx = page_num % 8
        if (free_page_bitmap[byte_idx] & (1 << bit_idx)) != 0:
            last_used_page = page_num
            break
    if last_used_page == -1:
        # 所有页都是空闲页，保留一个最小文件大小
        new_file_size = PAGE_SIZE
    else:
        new_file_size = (last_used_page + 1) * PAGE_SIZE
    db_file.truncate(new_file_size)

两种机制的协同工作

空闲页管理和回收机制需要协同工作才能保证数据库存储的高效性。分配页时优先从空闲页位图中查找已有的空闲页，而不是直接扩展文件；回收页时及时更新位图状态，让后续的分配操作可以复用这些页。同时数据库通常会引入空闲页缓存，将最近释放的空闲页放在内存缓存中，分配时优先从缓存中获取，减少磁盘IO操作。

不同SQL数据库的页管理实现会有细节差异，比如MySQL的InnoDB存储引擎使用段、区、页的三级结构管理空间，空闲页管理通过XDES entry结构维护区的状态；PostgreSQL使用FSM（空闲空间映射）文件跟踪每个页的剩余空间，不仅标记页是否空闲，还记录页的可用空间大小，方便分配合适大小的页存储数据。但核心的空闲页标记、查找、分配和回收逻辑都是相通的。

SQL_database页管理算法空闲页管理回收机制数据库存储修改时间：2026-07-17 06:21:31