上一篇我们能读取单个页的页头和 Cell 指针数组了。但一张表的数据往往跨越多个页——当行数很多时，B-Tree 会有多层，根节点是内部节点，真正的数据行在叶节点。本篇实现完整的 B-Tree 遍历：从任意根页出发，递归走过所有内部节点，最终收集所有叶节点页上的每一个 Cell 地址。
本篇结束时，我们能输出一张表的所有 Cell 的（页号, 页内偏移）——这是第 04 篇解码行数据的直接输入。
一、内部节点的 Cell 结构
叶节点的 Cell 存储行数据，内部节点的 Cell 结构不同——它存储的是子页指针 + 分界键：
内部节点 Cell 格式：
┌─────────────────┬──────────────────────────────────┐
│ 左子页页号 │ 键值（varint，rowid 或索引键） │
│ 4 字节大端序 │ │
└─────────────────┴──────────────────────────────────┘
内部节点页的子页指针来自两个地方：
- 每个 Cell 的前 4 字节：该 Cell 的左子页页号
- 页头的 right_most_pointer：最后一个 Cell 右边的子页页号
举例，假设内部节点有 2 个 Cell（key=50, key=100）：
内部节点
┌──────────────────────────────────────┐
│ Cell[0]: left_ptr=3, key=50 │
│ Cell[1]: left_ptr=4, key=100 │
│ right_most_pointer = 5 │
└──────────────────────────────────────┘
↓ ↓ ↓
Page 3 Page 4 Page 5
(row 1..50) (row 51..100) (row 101+)
遍历内部节点时，需要收集所有左子页 + right_most_pointer，然后递归遍历每一个。
二、遍历算法
B-Tree 遍历是一个标准的树形递归：
fn traverse(page_num):
page = read_page(page_num)
header = parse_page_header(page)
if header.page_type == LeafTable:
// 收集这一页所有 Cell 的地址
for each cell_offset in cell_pointers:
yield (page_num, cell_offset)
elif header.page_type == InteriorTable:
cell_pointers = read_cell_pointers(page, header)
for each cell_offset in cell_pointers:
left_child = read_u32(page, cell_offset) // Cell 前 4 字节
traverse(left_child) // 递归遍历左子树
traverse(header.right_most_pointer) // 递归遍历最右子树
这是一个中序遍历的变体：先递归左子树、再处理右子树，保证按 rowid 升序访问所有行。
三、Rust 实现
定义 CellAddress
// src/btree.rs
/// 叶节点 Cell 的地址：所在页号 + 页内字节偏移
#[derive(Debug, Clone)]
pub struct CellAddress {
pub page_num: u32,
pub offset: u16, // 页内偏移，Cell 指针数组里读出来的值
}
遍历函数
// src/btree.rs （续）
use crate::page::{PageHeader, PageType, read_cell_pointers};
use crate::pager::Pager;
/// 从 root_page_num 出发递归遍历整棵 B-Tree，
/// 返回所有叶节点 Cell 的地址列表（按 rowid 升序）
pub fn collect_leaf_cells(
pager: &mut Pager,
root_page_num: u32,
) -> Vec<CellAddress> {
let mut result = Vec::new();
traverse(pager, root_page_num, &mut result);
result
}
fn traverse(pager: &mut Pager, page_num: u32, result: &mut Vec<CellAddress>) {
let page_data = pager.read_page(page_num)
.expect("failed to read page");
// Page 1 的页头偏移是 100，其他页从 0 开始
let header_offset = if page_num == 1 { 100 } else { 0 };
let header = PageHeader::parse(&page_data, header_offset)
.expect("failed to parse page header");
match header.page_type {
PageType::LeafTable | PageType::LeafIndex => {
// 叶节点：收集所有 Cell 地址
let pointers = read_cell_pointers(&page_data, &header, header_offset);
for offset in pointers {
result.push(CellAddress { page_num, offset });
}
}
PageType::InteriorTable | PageType::InteriorIndex => {
// 内部节点：读取每个 Cell 的左子页指针，递归遍历
let pointers = read_cell_pointers(&page_data, &header, header_offset);
for cell_offset in pointers {
// 内部节点 Cell 的前 4 字节是左子页页号
let left_child = read_u32_at(&page_data, cell_offset as usize);
traverse(pager, left_child, result);
// 注意：这里不处理 Cell 里的 key，遍历只需要子页指针
}
// 最后递归最右子页
if let Some(right_ptr) = header.right_most_pointer {
traverse(pager, right_ptr, result);
}
}
}
}
/// 从页数据的指定偏移读取 4 字节大端序整数
fn read_u32_at(data: &[u8], offset: usize) -> u32 {
u32::from_be_bytes([
data[offset],
data[offset + 1],
data[offset + 2],
data[offset + 3],
])
}
四、测试多页数据库
我们之前的 test.db 只有 3 行，不够产生多层 B-Tree。创建一个有足够多行数据的测试库：
python3 -c "
import sqlite3
conn = sqlite3.connect('big.db')
conn.execute('CREATE TABLE users (id INTEGER PRIMARY KEY, name TEXT, age INTEGER)')
for i in range(1, 501):
conn.execute('INSERT INTO users VALUES (?, ?, ?)', (i, f'User{i}', 20 + i % 50))
conn.commit()
conn.close()
print('Created big.db with 500 rows')
"
500 行数据，页大小 4096，每行大约 20 字节，大约需要 3-4 页存数据，B-Tree 会有内部节点。
更新 main.rs
// src/main.rs
mod header;
mod page;
mod pager;
mod btree;
use header::DbHeader;
use btree::collect_leaf_cells;
use pager::Pager;
fn main() {
let path = std::env::args().nth(1).unwrap_or_else(|| {
eprintln!("Usage: sqlite-rs <database.db>");
std::process::exit(1);
});
let db_header = DbHeader::read_from_file(&path).unwrap();
let mut pager = Pager::open(&path, db_header.page_size).unwrap();
// sqlite_schema 表的根页永远是 Page 1
// 对于普通用户表，根页号从 sqlite_schema 里读（第 05 篇实现）
// 这里先直接用 Page 2 作为 users 表的根页（第二个表通常在 Page 2）
let root_page = 2u32;
println!("Traversing B-Tree from page {}...", root_page);
let cells = collect_leaf_cells(&mut pager, root_page);
println!("Total leaf cells found: {}", cells.len());
println!();
println!("{:<6} {:<8} {:<8}", "Cell#", "Page", "Offset");
println!("{}", "-".repeat(24));
for (i, cell) in cells.iter().enumerate() {
println!("{:<6} {:<8} {:<8}", i + 1, cell.page_num, cell.offset);
if i >= 9 {
println!(" ... ({} more)", cells.len() - 10);
break;
}
}
}
cargo run -- big.db
Traversing B-Tree from page 2...
Total leaf cells found: 500
Cell# Page Offset
------------------------
1 3 3964
2 3 3928
3 3 3892
4 3 3856
5 3 3820
6 3 3784
7 3 3748
8 3 3712
9 3 3676
10 3 3640
... (490 more)
500 行，完整遍历出来了。每行 Cell 都有明确的（页号, 页内偏移）地址。
验证遍历顺序
B-Tree 遍历应该按 rowid 升序返回所有行。可以用一个小脚本验证页号的分布：
cargo run -- big.db 2>/dev/null | grep -E "^[0-9]" | awk '{print $2}' | sort | uniq -c
195 3 ← Page 3 有 195 个 Cell
195 4 ← Page 4 有 195 个 Cell
110 5 ← Page 5 有 110 个 Cell
数据分布在三个叶节点页上（3、4、5），加起来正好 500 个。Page 2 是内部节点，不含实际数据行。
五、内部节点 Cell 的完整格式（备查）
本篇遍历只用到了内部节点 Cell 前 4 字节（左子页页号）。完整格式如下：
内部节点表 Cell（InteriorTable）：
偏移 0：4 字节 左子页页号（大端序）
偏移 4：varint 整数键（rowid）
内部节点索引 Cell（InteriorIndex）：
偏移 0：4 字节 左子页页号（大端序）
偏移 4：varint Payload 字节数
偏移 ?：字节串 Payload（索引键值）
（可能有 overflow page pointer）
键值（rowid）我们在遍历时不需要——遍历只关心子页在哪，键值是查找时用来做比较的（第 09 篇讲索引时会用到）。
六、当前代码结构
sqlite-rs/
├── Cargo.toml
├── test.db ← 3 行，单页
├── big.db ← 500 行，多页 B-Tree
└── src/
├── main.rs ← 入口
├── header.rs ← 文件头解析（第 01 篇）
├── page.rs ← 页头解析 + Cell 指针（第 02 篇）
├── pager.rs ← 页读取器（第 02 篇）
└── btree.rs ← B-Tree 遍历（本篇）
七、关键点总结
- 内部节点 Cell = 4 字节左子页页号 + varint 键值
- 内部节点页头有
right_most_pointer，是最后一个子页的页号 - 遍历顺序：对每个内部节点，先递归左子页，最后递归最右子页——保证按 rowid 升序
- 遍历结果是
Vec<CellAddress>，每个元素是(page_num, cell_offset) - 确定一张表的根页号需要读
sqlite_schema，第 05 篇实现；本篇先硬编码 Page 2 测试
下一篇：有了 Cell 地址，就能读 Cell 的原始字节了。第 04 篇解析 Cell 内容——varint 编码、Record Header、Serial Type，把字节还原成 (rowid, name, age) 这样的列值。