前一篇文章介绍了bbolt如何利用B+树来存储并索引数据。本文继续介绍与存储相关的另外两个概念：bucket和freelist。
Bucket
Bucket是数据库中key-value对的集合。一个bucket中的所有key必须唯一，但是不同bucket之间的key可以重复。例如，下面的例子创建了一个名为“b1”的bucket，然后在该bucket里面添加一条数据“name":"ben"。
db.Update(func(tx *bolt.Tx) error {b := tx.Bucket([]byte("b1"))err := b.Put([]byte("name"), []byte("ben"))return err})
那么bucket中的数据该如何保存在文件中呢？这里分两种情况：
1、bucket里面包含的数据足够少，大小总和小于或等于一个页面的1/4；
2、bucket里面包含的数据的大小超过了一个页面的1/4。
对于第一种情况，bucket中的所有数据会以内联(inline)的方式存储在当前页面中。该内联记录的key就是bucket的名称，对应的value包含bucket中所有的key-value对的数据。value的大体格式如下：
bucket header的具体格式如下，其中root的值就是该内联bucket实际所在的页面ID，暂时忽略sequence。
// bucket represents the on-file representation of a bucket.// This is stored as the "value" of a bucket key. If the bucket is small enough,// then its root page can be stored inline in the "value", after the bucket// header. In the case of inline buckets, the "root" will be 0.type bucket struct {root pgid page id of the bucket's root-level pagesequence uint64 monotonically incrementing, used by NextSequence()}
后面的page header、leafPageElement以及key-value data在前一篇文章已经介绍过，就不重复了。但是这里要注意一点，在这种情况下，leafPageElement中的flags不再是0了，而应该是0x01：
const (bucketLeafFlag = 0x01)
对于第二种情况，则会为bucket中的数据分配单独的page(可能会有多个page)，具体存储方式与前一篇文章介绍的完全一样，也就是会按照B+树节点的方式存储。
而在当前页面中，也会插入一条key-value记录，key同样也是bucket的名称，而value只包含bucket header。细心的读者看到这里可能会有一个疑问，如果为bucket分配了多个页面，而bucket header中只能保存一个page ID，那它保存的是哪个page ID呢？当为bucket分配了多个page，那这些page会组织为层次结构(hierarchy)，会有一个page在最顶层。bucket header中保存的就是顶层的page ID。
Freelist
Freelist就是空闲页面ID列表。当对bbolt进行增、删、改一段时间后，文件中间可能会零散的存在一些空闲页面(类似于内存碎片)，bbolt当前的设计和实现很难回收这些空间。目前的做法是使用一个单独的页面来保存freelist。下图是freelist的存储布局示意图。
上面的例子中，第三个页面(编号为2)的页面用来保存这些空闲页面的ID。flag:0x10表示当前页面用于保存空闲页面的ID。count表示空闲页面的数量。如果空闲页面很多，一个页面保存不下，就会申请几个连续的页面来保存；这时就要用到字段overflow了。假设总共需要3个连续的页面的空间来保存所有的空闲页面ID，那么pgid就是第一个页面的ID，overflow的值就是2；例如pgid的值是6，那么就是编号为6、7、8的这三个页面。
当然，也可以不保存freelist。那么在打开数据文件时，会扫描整个数据库文件，找到所有可达的(reachable)页面ID。凡是不在可达页面集合中的，都是空闲页面。具体遍历的方法，就需要用到上一节要提到的B+树，从最顶层的页面开始，一直遍历完所有的叶子节点。
--END--
相关文章
