知识卡片

结构图卡 · 2280.j.5

B树与页面结构

理解等级:未标注

和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
这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《数据密集型应用系统设计》第三章《存储与检索》"B树""让B树更可靠" (源文件:_epub-src/ch3_split_002.html) - 结论依据:原文详述B树按固定大小页面组织、分支因子决定树深度为O(log n)、更新 和插入(含页面分裂)的具体机制,以及多页面覆盖导致崩溃时可能损坏索引、因此需要 预写式日志来在崩溃后恢复一致状态,直接支撑本卡片的结构梳理。 - 原始内容:B树将数据库分解成固定大小的块或页面,传统上大小为4KB……该算法确保树保持平衡:具有 n 个键的B树总是具有 $O(log n)$ 的深度。……为了使数据库对崩溃具有韧性,B树实现通常会带有一个额外的磁盘数据结构:预写式日志(WAL, write-ahead-log)(也称为重做日志(redo log))。……当数据库在崩溃后恢复时,这个日志被用来使B树恢复到一致的状态