boltdb是怎么组织和持久化数据的?

2022-03-16 00:00:00 数据 节点 的是 页面 叶子

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引入nodeinodes两个数据结构,用于表示内存中“反序列化”的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
        }
        复制

        相关文章