Linux下使用C++实现B树时如何测量磁盘访问次数

核心建模规则对齐 #

首先和《算法导论》第18章的B树磁盘模型完全对齐统计规则：

• B树运行时间拆分两个独立衡量维度：磁盘访问次数、CPU计算时间，其中磁盘访问以实际读写的磁盘页数量为统计单位
• 节点访问规则严格匹配书中伪代码定义：
  • 若节点指针x指向的内容已在主存，可直接访问x.key等属性，无IO开销
  • 若节点存储在磁盘上，必须先执行DISK-READ(x)将对应页加载到主存才可访问；若节点已在主存，DISK-READ(x)为空操作，不产生磁盘访问计数
  • 节点属性修改完成后，必须执行DISK-WRITE(x)将变更刷回磁盘，产生一次写IO计数

Linux内存映射核心入门API #

不需要依赖第三方库，掌握4个系统调用+1个 libc 接口即可实现类boost::mapped_file的功能，所有接口的man手册就是最准确的入门资料：

• open()：打开/创建持久化存储B树数据的磁盘文件，通常传O_RDWR | O_CREAT标志开启读写权限、文件不存在时自动创建
• ftruncate()：调整映射文件的大小，B树新增节点需要扩容时，调用该接口把文件长度拓展到对应大小即可
• mmap()：核心内存映射接口，把打开文件的指定长度区间映射到进程虚拟地址空间；映射时需传PROT_READ | PROT_WRITE开启内存读写权限，MAP_SHARED标记保证内存修改可同步回磁盘；映射完成后直接读写对应内存地址即可操作文件内容，无需额外调用read/write接口
• munmap()：取消地址空间与文件的映射关系，在程序退出或不需要某段映射时调用
• msync()：强制把指定区间的内存修改刷回磁盘，是实现DISK-WRITE精确统计的核心接口

注意：mmap()本身仅建立虚拟地址和文件的映射关系，不会立刻把文件内容加载到物理内存——第一次访问映射地址对应的页时会触发缺页中断，由内核自动把对应磁盘页加载到物理内存，这个原生行为正好可以模拟真实DISK-READ的开销。Linux默认页大小可通过getpagesize()接口获取，通常为4KB。

分步实现指引 #

第一步：实现带页状态跟踪的内存映射管理器 #

不要一次性映射整个文件，按磁盘页为单位做管理，核心逻辑如下：

1. 内部维护页表结构，记录每个页号的三个状态：未加载、已加载且干净、已加载且脏（已修改未刷盘）
2. 实现DISK-READ(page_id)接口：
   • 若对应页已标记为已加载，直接返回对应内存指针，不增加读计数
   • 若页未加载，可通过访问对应地址触发缺页加载，或调用madvise(addr, size, MADV_WILLNEED)提示内核提前加载页，标记页为已加载干净状态，读计数器+1，返回内存指针
3. 实现mark_dirty(page_id)接口：节点内容修改后调用，标记对应页为脏状态
4. 实现DISK-WRITE(page_id)接口：
   • 若页不是脏状态，直接返回，不增加写计数
   • 若为脏页，调用msync(addr, page_size, MS_SYNC)强制把页内容刷回磁盘，标记页为干净状态，写计数器+1

   若不主动调用msync，内核会在内存紧张或取消映射时自动刷脏页，无法精确匹配伪代码的写操作统计点，因此必须手动触发刷盘。

5. 初期可暂不实现页淘汰逻辑，把所有访问过的页都留在内存中，先对齐伪代码逻辑；后续可按需增加缓存上限，超过阈值时把干净页标记为未加载、脏页先刷盘再移出缓存，模拟有限内存的真实运行环境。

第二步：实现对接映射管理器的自定义分配器 #

你之前实现的C++20内存版B树仅需替换分配器、少量修改节点指针包装即可复用核心逻辑（包括迭代器实现）：

1. 分配器的allocate()接口不调用malloc，而是向内存映射管理器申请对应大小的页空间，返回映射后的内存指针
2. 给B树节点指针包装一层轻量代理结构，重载->和*运算符，在访问成员前自动调用DISK-READ(x)逻辑，无需在每个节点访问点手动加读调用，和原有内存版B树的访问逻辑完全兼容，原有迭代器代码几乎不需要修改
3. 在B树插入、删除、分裂、合并等修改节点的逻辑点，按照CLRS伪代码的调用位置，在节点修改完成后调用mark_dirty+DISK-WRITE(x)即可

第三步：IO统计接入 #

在映射管理器中维护两个计数器：

• disk_read_count：每次触发实际缺页加载时+1
• disk_write_count：每次触发实际脏页刷盘时+1
  每次B树操作（查找、插入、删除）执行完成后，直接读取两个计数器的值即可得到对应操作的磁盘访问次数，剩下的逻辑执行耗时即为CPU计算时间，完全匹配书中的两个衡量维度。

入门验证建议 #

不需要一开始就做复杂功能，先跑通最小验证流程：

• 先写百行以内的测试demo，验证mmap核心行为：打开文件、映射1个页大小的空间、写入测试值、调用msync刷盘、取消映射退出，重新打开文件能读到之前写入的值，就算掌握核心API用法
• 基础映射逻辑跑通后，先接入无页淘汰的简单页表，跑通B树的插入、查找、删除流程，验证IO计数和书中的复杂度结论匹配（比如高度为h的B树，查找最多产生h次读IO，插入最多产生h次读+h次写IO）
• 基础逻辑验证正确后，再按需增加页淘汰、批量刷盘等高级特性即可。

内容的提问来源于stack exchange，提问作者frozenca