boltdb 源码导读（一）：boltdb 数据组织

boltdb 是市面上为数不多的纯 go 语言开发的、单机 KV 库。boltdb 基于 Howard Chu'sLMDB 项目 ，实现的比较清爽，去掉单元测试和适配代码，核心代码大概四千多行。简单的 API、简约的实现，也是作者的意图所在。由于作者精力所限，原 boltdb 已经封版，不再更新。若想改进，提交新的 pr，建议去 etcd 维护的 fork 版本 bbolt。
为了方便，本系列导读文章仍以不再变动的原 repo 为基础。该项目麻雀虽小，五脏俱全，仅仅四千多行代码，就实现了一个基于 B+ 树索引、支持一写多读事务的单机 KV 引擎。代码本身简约朴实、注释得当，如果你是 go 语言爱好者、如果对 KV 库感兴趣，那 boltdb 是不可错过的一个 repo。
本系列计划分成三篇文章，依次围绕数据组织、索引设计、事务实现等三个主要方面对 boltdb 源码进行剖析。由于三个方面不是完全正交解耦的，因此叙述时会不可避免的产生交织，读不懂时，暂时略过即可，待有全貌，再回来梳理。本文是篇， boltdb 数据组织。

引子

一个存储引擎底层的构成，就是处理数据在各种物理介质（比如在磁盘上、在内存里）上的组织。而这些数据组织也体现了该存储引擎在设计上的取舍哲学。

在文件系统上，boltdb 采用页（page）的组织方式，将一切数据都对齐到页；在内存中，boltdb 按 B+ 树组织数据，其基本单元是节点（node），一个内存中的树节点对应文件系统上一个或者多个连续的页。boltdb 就在数据组织上就只有这两种核心抽象，可谓设计简洁。当然，这种简洁必然是有代价的，后面文章会进行详细分析。

本文首先对节点和页的关系进行总体说明，然后逐一分析四种页的格式及其载入内存后的表示，后按照 db 的生命周期串一下 db 文件的增长过程以及载入内存的策略。

作者：青藤木鸟 https://www.qtmuniao.com/2020/11/29/bolt->, 转载请注明出处

概述

本文主要涉及到 page.go 和 freelist.go 两个源文件，主要分析了 boltdb 各种 page 在磁盘上的格式和其加载到内存中后的表示。

顶层组织

boltdb 的数据组织，自上而下来说：

1. 每个 db 对应一个文件。

2. 在逻辑上：

• 一个 db 包含多个桶（bucket），相当于多个命名空间（namespace），桶可以无限嵌套
• 每个桶对应一棵 B+ 树

3. 在物理上：

• 一个 db 文件是按页为单位进行顺序存储
• 一个页大小和操作系统的页大小保持一致（通常是 4KB）

页和节点

页分为四种类型：

• 元信息页：全局有且仅有两个 meta 页，保存在文件；它们是 boltdb 实现事务的关键
• 空闲列表页：有一种特殊的页，存放空闲页（freelist） id 列表；他们在文件中表现为一段一段的连续的页
• 两种数据页：剩下的页都是数据页，有两种类型，分别对应 B+ 树中的中间节点和叶子节点

页和节点的关系在于：

1. 页是 db 文件存储的基本单位，节点是 B+ 树的基本构成节点
2. 一个数据节点对应一到多个连续的数据页
3. 连续的数据页序列化加载到内存中就成为一个数据节点

总结一下：在文件系统上线性组织的数据页，通过页内指针，在逻辑上组织成了一棵二维的 B+ 树，该树的树根保存在元信息页中，而文件中所有其他没有用到的页的 id 列表，保存在空闲列表页中。

页格式和内存表示

boltdb 中的页分四种类型：元信息页、空闲列表页、中间节点页和叶子节点页。boltdb 使用常量枚举标记：

const (
    branchPageFlag   = 0x01
    leafPageFlag     = 0x02
    metaPageFlag     = 0x04
    freelistPageFlag = 0x10
)