Appearance
| 教材名称 | 金融智能：理论与实践 |
| 作者 | 郑小林 |
| 出版社 | 高等教育出版社 |
| 版本 | 1 |
| 教材名称 | Operating System Concepts |
| 作者 | Avi Silberschatz |
| 出版社 | John Wiley & Sons |
| 版本 | 10 |
| 教材名称 | Computer Networks |
| 作者 | Andrew S.Tanebaum |
| 出版社 | 清华大学出版社 |
| 版本 | 6 |
| 教材名称 | Elements of the Theory of Computation |
| 作者 | H. R. Lewis |
| 出版社 | Prentice Hall |
| 版本 | 2 |
markdown
| LSN | 事务 | 日志类型 | 关键字段 | `prev_lsn_` |
| --- | --- | --- | --- | --- |
| 0 | T0 | `kBegin` | - | `INVALID_LSN` |
| 1 | T0 | `kUpdate` | `old_key_="A"`, `new_key_="A"` | 0 |
| 2 | - | CheckPoint | `checkpoint_lsn_=2` | - |
| 3 | T1 | `kBegin` | - | `INVALID_LSN` |
| 4 | T1 | `kInsert` | `new_key_="C"` | 3 |
| 5 | T1 | `kCommit` | - | 4 |
| 6 | T2 | `kInsert` | `new_key_="D"` | ... |
| CheckPoint 字段 | 含义 | 示例 |
| --- | --- | --- |
| `checkpoint_lsn_` | 检查点对应的 LSN | 2 |
| `active_txns_` | 检查点时还没结束的事务及 last LSN | `{ T0 -> 1 }` |
| `persist_data_` | 检查点时已经持久化的数据快照 | `{ "A" -> 2050 }` |
| 阶段 | 处理范围 | 处理方式 |
| --- | --- | --- |
| `RedoPhase()` | `lsn_ > checkpoint_lsn_` 的日志 | 按 LSN 顺序重放 `kInsert`、`kDelete`、`kUpdate`，遇到 `kCommit` 移出 `active_txns_` |
| `UndoPhase()` | Redo 后仍留在 `active_txns_` 中的事务 | 从 last LSN 开始沿 `prev_lsn_` 反向回滚 |
| 事务 | `prev_lsn_` 链 | 恢复阶段中的作用 |
| --- | --- | --- |
| T1 | 5 -> 4 -> 3 | 已 commit，Redo 后从 `active_txns_` 移除 |
| T2 | 6 -> ... | 未 commit，Undo 时沿链回滚 |html
<div style="font-family: Arial, sans-serif; margin: 16px 0; padding: 14px; border: 1px solid #d0d7de; border-radius: 6px;">
<div style="text-align: center; font-weight: 600; margin-bottom: 12px;">B+ 树节点结构</div>
<div style="display: flex; flex-direction: column; align-items: center; gap: 10px;">
<div style="border: 2px solid #57606a; border-radius: 6px; padding: 10px 14px; background: #f6f8fa; min-width: 520px;">
<div style="font-weight: 600; margin-bottom: 6px;">BPlusTreeInternalPage</div>
<div style="font-size: 13px; color: #57606a; margin-bottom: 6px;">
page_id_=10, parent_page_id_=INVALID_PAGE_ID, size_=3
</div>
<div style="display: grid; grid-template-columns: repeat(5, 1fr); border: 1px solid #8c959f; text-align: center; font-size: 13px;">
<div style="padding: 6px; border-right: 1px solid #8c959f;">P0=21</div>
<div style="padding: 6px; border-right: 1px solid #8c959f;">K1=40</div>
<div style="padding: 6px; border-right: 1px solid #8c959f;">P1=22</div>
<div style="padding: 6px; border-right: 1px solid #8c959f;">K2=80</div>
<div style="padding: 6px;">P2=23</div>
</div>
</div>
<svg width="820" height="92" viewBox="0 0 820 92" xmlns="http://www.w3.org/2000/svg" style="overflow: visible;">
<defs>
<marker id="bpt-arrow" markerWidth="8" markerHeight="8" refX="6" refY="3" orient="auto" markerUnits="strokeWidth">
<path d="M0,0 L0,6 L6,3 z" fill="#57606a" />
</marker>
</defs>
<path d="M220 6 L118 78" stroke="#57606a" stroke-width="2" fill="none" marker-end="url(#bpt-arrow)" />
<path d="M410 6 L410 78" stroke="#57606a" stroke-width="2" fill="none" marker-end="url(#bpt-arrow)" />
<path d="M600 6 L702 78" stroke="#57606a" stroke-width="2" fill="none" marker-end="url(#bpt-arrow)" />
<!-- <text x="218" y="34" font-size="13" fill="#57606a">P0 -> page_id_=21</text>
<text x="424" y="44" font-size="13" fill="#57606a">P1 -> page_id_=22</text>
<text x="570" y="34" font-size="13" fill="#57606a">P2 -> page_id_=23</text> -->
</svg>
<div style="display: flex; align-items: stretch; gap: 10px;">
<div style="border: 2px solid #0969da; border-radius: 6px; padding: 10px; background: #ddf4ff; width: 235px;">
<div style="font-weight: 600; margin-bottom: 6px;">BPlusTreeLeafPage</div>
<div style="font-size: 13px; color: #57606a; margin-bottom: 6px;">page_id_=21, next_page_id_=22</div>
<div style="border: 1px solid #0969da; font-size: 13px;">
<div style="padding: 5px; border-bottom: 1px solid #0969da;">K=12 -> RowId(5, 0)</div>
<div style="padding: 5px; border-bottom: 1px solid #0969da;">K=28 -> RowId(5, 1)</div>
<div style="padding: 5px;">K=39 -> RowId(8, 2)</div>
</div>
</div>
<div style="display: flex; align-items: center; font-size: 22px; color: #0969da;">→</div>
<div style="border: 2px solid #0969da; border-radius: 6px; padding: 10px; background: #ddf4ff; width: 235px;">
<div style="font-weight: 600; margin-bottom: 6px;">BPlusTreeLeafPage</div>
<div style="font-size: 13px; color: #57606a; margin-bottom: 6px;">page_id_=22, next_page_id_=23</div>
<div style="border: 1px solid #0969da; font-size: 13px;">
<div style="padding: 5px; border-bottom: 1px solid #0969da;">K=45 -> RowId(9, 0)</div>
<div style="padding: 5px; border-bottom: 1px solid #0969da;">K=61 -> RowId(9, 1)</div>
<div style="padding: 5px;">K=77 -> RowId(11, 3)</div>
</div>
</div>
<div style="display: flex; align-items: center; font-size: 22px; color: #0969da;">→</div>
<div style="border: 2px solid #0969da; border-radius: 6px; padding: 10px; background: #ddf4ff; width: 235px;">
<div style="font-weight: 600; margin-bottom: 6px;">BPlusTreeLeafPage</div>
<div style="font-size: 13px; color: #57606a; margin-bottom: 6px;">page_id_=23, next_page_id_=INVALID_PAGE_ID</div>
<div style="border: 1px solid #0969da; font-size: 13px;">
<div style="padding: 5px; border-bottom: 1px solid #0969da;">K=83 -> RowId(13, 0)</div>
<div style="padding: 5px; border-bottom: 1px solid #0969da;">K=91 -> RowId(13, 1)</div>
<div style="padding: 5px;">K=99 -> RowId(14, 2)</div>
</div>
</div>
</div>
<div style="font-size: 22px; color: #57606a;">↓</div>
<div style="border: 2px solid #1a7f37; border-radius: 6px; padding: 10px 14px; background: #dafbe1; min-width: 520px;">
<div style="font-weight: 600; margin-bottom: 6px;">TablePage / TableHeap</div>
<div style="font-size: 13px;">
RowId(page_id, slot_num) 定位到表页中的具体 slot，例如 RowId(9, 1) 表示 table page 9 的 slot 1。
</div>
</div>
</div>
</div>