Boltdb学习笔记之二--数据结构

在boltdb中，核心的数据结构当属B+树了。B+树是数据库或文件系统中常见的数据结构，它的特点是能够保证数据稳定有序，因为每个叶子节点的深度都相同，因此其插入和修改操作拥有较稳定的时间复杂度。

那么boltdb中B+树的节点是如何表示的呢？答案是node。node对应page在内存中的数据结构，node序列化之后便是page，page反序列化之后是node。因为node在内存中，且node对应B+树的一个节点

在概念上，boltdb中的一个Bucket对应一棵B+树。如下图所示

node

node分为两种，branch node和leaf node。

branch node如下所示，需要注意的是，boltdb中的branch node与通常的B+树略有不同，通常B+树中branch node的key数量比子节点数量多1， 而boltdb中key和子节点是一一对应的，这里应该是出于简化设计的考虑。因此在boltdb的branch node中，子节点i子树中的key应当介于key(i)和key(i+1)之间，左闭右开。

leaf node如下所示。我们注意到叶子节点的数据除了key和value之外，还有一个flags，它的作用是为了区分普通数据和子Bucket数据。当flags != 0时，key为当前Bucket下的子Bucket名，value可反序列化为bucket结构，其中记录着子Bucket对应B+树的根节点所在的page id。稍后在Bucket一节中我们将会深入探讨。

node代码如下：

type nodes []*node

// inode represents an internal node inside of a node.
// It can be used to point to elements in a page or point
// to an element which hasn't been added to a page yet.
type inode struct {
 flags uint32
 pgid  pgid
 key   []byte
 value []byte
}

type inodes []inode

// node represents an in-memory, deserialized page.
type node struct {
 bucket     *Bucket
 isLeaf     bool
 unbalanced bool
 spilled    bool
 key        []byte
 pgid       pgid
 parent     *node
 children   nodes
 inodes     inodes
}