B树用固定大小页面树保证O(logn)深度并靠WAL防崩溃损坏

和SSTable/LSM树按可变大小段追加写入的思路完全不同，B树把数据库分解成固定大小的 页面（传统上4KB，贴合底层磁盘的固定块结构），每次只读写一个页面。每个页面有自己的 地址，可以像指针一样被其他页面引用，从而构成一棵页面树：从根页面开始查找，每个 非叶页面包含若干键和对子页面的引用，每个子页面负责一段连续的键范围；一路往下直到 叶页面，叶页面包含每个键的内联值或指向值所在位置的引用。一个页面里子页面引用的 数量叫分支因子，实践中通常是几百，这保证了含n个键的B树深度是O(log n)——分支因子 500的4KB页面构成的四层树能存储多达256TB，绝大多数数据库都能塞进三四层B树，查找 不需要追踪很多层页面引用。更新一个已有键：找到含该键的叶页面，改值，把整页写回 磁盘（对该页的所有引用保持有效）；插入一个不属于任何现有页面空间的新键：如果目标 页没有足够空间，就把它拆成两个半满页面，并更新父页面反映新的键范围划分——这意味着 一次插入可能需要连续覆盖好几个不同页面，如果数据库在只写完部分页面时崩溃，就会 留下损坏的索引（比如出现一个不属于任何父页面的孤儿页面）。为此B树实现通常配一份 额外的预写式日志（WAL，也叫重做日志）：每次B树修改先记进这个仅追加文件，数据库 崩溃后重启时用WAL把B树恢复到一致状态。

结构图：

flowchart TD
    A[根页面] -->|按键范围引用子页面| B[中间页面]
    B -->|继续细分键范围| C[叶页面: 含键的内联值或引用]
    D[更新已有键] --> D1[找到叶页面, 改值, 整页写回磁盘]
    E[插入导致页面空间不足] --> E1[拆分为两个半满页面]
    E1 --> E2[更新父页面反映新的键范围划分]
    E2 -.多页面连续覆盖, 崩溃时可能损坏.-> F[预写式日志WAL先记录每次修改]
    F -.崩溃重启后用WAL恢复B树到一致状态.-> F