boltdb是怎么组织和持久化数据的?
在boltdb探秘系列的篇里介绍boltdb的基本使用,本文是boltdb探秘系列的第二篇,将对boltdb的存储格式以及索引结构进行分析,预计耗时7~8分钟。
玩DB,心里不能没点B+树
写时复制B+树
boltdb用B+树组织数据和索引,叶子节点存储数据,中间节点存储子节点。索引数据的时间复杂度为O(logN),由于中间节点存储足够多的Key,B+树整体深度不大,可以减少磁盘IO。
这里与常见B+树略微不同的是
1. 中间节点存储的是叶子节点的个Key。
2. 叶子结点没有形成链表,无法对顺序查找进行优化(boltdb也不支持顺序查找)。
写事务不会修改已有的树,而是对数据进行拷贝,在拷贝上修改。比如下图对叶子节点leaf 7修改,会先复制出leaf 8再进行修改,其父节点也随之复制。读写事务读到的是不同的数据版本。
新增加的节点以追加的方式顺序写入db文件。
原则上每开启一个新的写事务都可以开启一个新版本。但boltdb规定任意时刻都只有一个写操作,这样可以避免垃圾回收带来的性能下降,且B+树优先使用被标记为空闲的块,而不是无限制的追加新的块。另外boltdb只维护两个版本的数据。
物理布局
数据库以meta页面为起点找到B+树的,从而找到数据。在写事务里从freelist分配页面,实现写时复制。
磁盘的page,内存的node
前文提到boltdb使用B+树来组织数据的,本节将介绍如何在数据库文件中存储这么一棵树,节点如何在磁盘文件和内存中表示B+树的节点。
页page
基本存储结构是页,结构体page的内存布局与文件中的存储格式相对应,且每个页面与操作系统的页大小一样,为4k(后面的文章会说明原因)。一个页分为页头(前16字节)和数据区。
id(uint64): 页id,标识,从0开始递增。
flags(uint16): 标记页的类型,共有四种,分别是
metaPageFlag: db文件的元信息页,共有两份,在db文件的开头。
branchPageFlag: b+树中的中间节点。
leafPageFlag: b+树中的叶子节点。
freelistPageFlag: 空闲页列表,空闲页用于写数据时存储修改或新增的页。
count(uint16): 当数据区是存储具体的KV对数据时,表示该页存储的KV对的数量。
overflow(uint32): 数据溢出了多少页。当一个页面装不完数据(比如存储一个大小超过4k的字节数组时),需要再追加连续的几页来进行存储,这些溢出的页没有页头,全部用来存储数据。
ptr(uintptr): 指向数据区域。
B+树由叶子节点和中间节点组成,两者的区别在flags和数据区的分布上。
叶子节点(leafPage)主要存数据,以存储了(foo, bar)和(Tenz, Ok)两个KV对的叶子节点页面为例。
数据区域分为元素元数据列表(leafPageElement)和数据两个区域,数据区域是连续的字节数组。leafPage有几个字段:
flags: 标记位,0x0时为普通数据。
pos: position,表示从这个element的起点开始偏移pos个字节即可找到对应KV在数据区的位置。
ksize: KV对中Key的长度
vsize: KV对中Value的长度
中间节点(branchPage)记录key所在的页面。与叶子节点相似,分为元数据列表和数据区。不同的是,数据区只存Key的值,而元数据(branchPageElement)数据结构变成
type branchPageElement struct {
pos uint32 // Key的偏移
ksize uint32 // Key的长度
pgid pgid // Key所在的页的id
}
node与inode
如果直接在页面上进行数据操作,需要引入各种指针运算。为了方便操作,boltdb引入node和inodes两个数据结构,用于表示内存中“反序列化”的page,相当于利用node在内存中构建一棵B+树。
type node struct {
bucket *Bucket // node所在的bucket
isLeaf bool // 是否是叶子节点
unbalanced bool // 子树是否平衡
spilled bool // 是否在写事务中修改过数据
key []byte // key
pgid pgid // 对应页的id
parent *node // 父节点
children nodes // 子节点
inodes inodes // KV对数组
}
其中inode的数据结构为叶子节点页面数据区所有KV对反序列化的结果
type inode struct {
flags uint32 // 标记位,0x0是数据
pgid pgid // 所在页的id
key []byte // Key
value []byte // Value
}
复制相关文章