Build your own database

B-Tree 与崩溃恢复

B-Tree 是一种非常优秀的数据结构，适用于数据库和文件系统等场景。本文将从以下几个角度解析 B-Tree 的特点与实现。

许多实用的二叉树（如 AVL 树或红黑树）被称为**高度平衡树**，即树的高度（从根到叶的深度）被限制为 \(O(\log(N))\)，因此查找操作的复杂度为 \(O(\log(N))\)。

B-Tree 同样是一种高度平衡的树，其所有叶节点的高度相同，这确保了其良好的查找性能。

可能是以前没有接触过类似的数据结构设计，反复阅读了几遍依然有些不太理解。今天，我决定从读者的角度一步一步介绍我对这个数据结构的理解。

一个节点应该包含以下几个部分：

| type | nkeys |  pointers  |   offsets  | key-values | unused |
|  2B  |   2B  | nkeys * 8B | nkeys * 2B |     ...    |        |

每个 key-value 对的格式如下：

| klen | vlen | key | val |
|  2B  |  2B  | ... | ... |

数据库有三个核心概念：持久性、索引和 并发性。