LevelDB 和 BoltDB 都是k/v存储，LevelDB的实现是基于LSM树，没有事务，LevelDB实现了一个日志结构化的merge tree，将随机的写变成顺序写，每次都把数据写入新文件。

LSM树而且通过批量存储技术规避磁盘随机写入问题。 LSM树的设计原理是把一颗大树拆分成N棵小树， 数据首先写入到内存中，在内存中构建一颗有序小树，随着小树越来越大，内存的小树会flush到磁盘上。磁盘中的树定期可以做merge操作，合并成一棵大树，以优化读性能。

Bolt 是受 LMDB 项目启发的一个纯粹的 Go key/value数据库，BoltDB使用一个单独的内存映射的文件(.db)，实现一个写入时拷贝的B+树，这能让读取更快。BoltDB的载入时间很快，它不需要通过读log恢复事务，它仅仅从两个B+树的根节点读取ID就可以加载出完整数据。具有以下特点：

1、直接使用API接口存取数据，没有查询语句。

2、支持完全可序列化的ACID事务

3、数据保存在内存映射的文件里。没有wal、线程压缩和垃圾回收。

4、通过COW技术保证即使在机器异常时也可以达到数据一致性，读写可并发，但是写写不能并发，适合与读多写少的场景。

ACID：事务具有4个特征，分别是原子性（atomicity)、一致性（consistency)、隔离性（isolation）和持久性（durability），简称事务的ACID特性。

COW：CopyOnWrite,写时复制

整体结构图：

                          

Bolt就是将db文件通过mmp映射到内存，在db中创建bucket，每个bucket相当于一张表，在bucket中记录kv。插入删除kv通过rwtx，查询kv通过rtx。数据在磁盘存放在page中，page分为几种类型：

MetaPage：记录根元数据，通过此元数据可以遍历出所有数据

branchPage：记录非叶子节点

leafPage：记录叶子节点，即最终的kv

freelistPage：记录空闲可用的page。

为了加快操作速度，将page在内存对应的数据组织称node结构，node就是b+tree。使用cursor在page和node之间来回查询直到结束。

1、主要内存数据结构：

type DB struct {
	//提交数据时是否进行校验
	StrictMode bool

	// 提交数据后是否进行fsync操作
	NoSync bool

	NoGrowSync bool

	// 是否开启文件到内存的映射
	MmapFlags int

	// 一次提交最大数据量. 默认值 DefaultMaxBatchSize 
	MaxBatchSize int

	// 批处理最大时延
	MaxBatchDelay time.Duration

	// db文件一次增长量
	AllocSize int

	path     string//db文件路径
	file     *os.File//db文件打开句柄
	lockfile *os.File // windows only
	dataref  []byte   // mmap'ed readonly, write throws SEGV
	data     *[maxMapSize]byte//文件到内存映射对应的buf
	datasz   int
	filesz   int // current on disk file size
	meta0    *meta//两个根元数据之一
	meta1    *meta//两个根元数据之一
	pageSize int//page 大小
	opened   bool
	rwtx     *Tx//读写事务
	txs      []*Tx//读事务，可以多个
	freelist *freelist//freepage 记录链表
	stats    Stats

	pagePool sync.Pool//page 内存池

	batchMu sync.Mutex
	batch   *batch

	rwlock   sync.Mutex   // Allows only one writer at a time.
	metalock sync.Mutex   // Protects meta page access.
	mmaplock sync.RWMutex // Protects mmap access during remapping.
	statlock sync.RWMutex // Protects stats access.

	ops struct {
		writeAt func(b []byte, off int64) (n int, err error)//db写接口
	}

	// 以只读模式打开的db
	readOnly bool
}



type Bucket struct {
	*bucket
	tx       *Tx                // 对应的事务
	buckets  map[string]*Bucket // 具体执行读写的bucket
	page     *page              // inline page reference
	rootNode *node              // page对应内存node的入口
	nodes    map[pgid]*node     // node cache

	// 节点分裂时使用
	FillPercent float64
}

// 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，如果roo是0就表明该bucket是inline的
	sequence uint64 // monotonically incrementing, used by NextSequence()
}


type Cursor struct {
	bucket *Bucket//查找目标
	stack  []elemRef//记录查找路径
}

// elemRef represents a reference to an element on a given page/node.
type elemRef struct {
	page  *page//查找最终结果对应的page 
	node  *node//查找最终结果对应的node
	index int//所在page/node中的位置
}

// node represents an in-memory, deserialized page.
type node struct {
	bucket     *Bucket
	isLeaf     bool//是否叶子节点
	unbalanced bool
	spilled    bool//是否spil过
	key        []byte
	pgid       pgid//page id
	parent     *node//上一层的反向指针
	children   nodes//该节点下一层子节点
	inodes     inodes//如果是叶子节点记录kv
}

// 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
}

// freelist represents a list of all pages that are available for allocation.
// It also tracks pages that have been freed but are still in use by open transactions.
type freelist struct {
	ids     []pgid          // all free and available free page ids.
	pending map[txid][]pgid // mapping of soon-to-be free page ids by tx.
	cache   map[pgid]bool   // fast lookup of all free and pending page ids.
}

type Tx struct {
	writable       bool//是否写事务
	managed        bool
	db             *DB//对应的db
	meta           *meta
	root           Bucket
	pages          map[pgid]*page//本事务涉及的变化需要下盘的page
	stats          TxStats
	commitHandlers []func()

	// WriteFlag specifies the flag for write-related methods like WriteTo().
	// Tx opens the database file with the specified flag to copy the data.
	//
	// By default, the flag is unset, which works well for mostly in-memory
	// workloads. For databases that are much larger than available RAM,
	// set the flag to syscall.O_DIRECT to avoid trashing the page cache.
	WriteFlag int
}

2、物理结构

2.1 MetaPage

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

type page struct {
    id       pgid
    flags    uint16
    count    uint16
    overflow uint32
    ptr      uintptr
}
type meta struct {
    magic    uint32
    version  uint32
    pageSize uint32
    flags    uint32
    root     bucket//磁盘上根page id
    freelist pgid  //磁盘上空闲page id
    pgid     pgid
    txid     txid
    checksum uint64
}
// meta returns a pointer to the metadata section of the page.
func (p *page) meta() *meta {
    return (*meta)(unsafe.Pointer(&p.ptr))
}

Metapage一共两个，每次数据变更这两个page轮流使用，使用哪个page是根据meta中的txid，数据变化时txid会递增。

2.2 branchPage

type branchPageElement struct {
    pos   uint32   //key本page内偏移
    ksize uint32   //key大小
    pgid  pgid    //key对应的page id
}
// branchPageElement retrieves the branch node by index
func (p *page) branchPageElement(index uint16) *branchPageElement {
    return &((*[0x7FFFFFF]branchPageElement)(unsafe.Pointer(&p.ptr)))[index]
}

// branchPageElements retrieves a list of branch nodes.
func (p *page) branchPageElements() []branchPageElement {
    if p.count == 0 {
        return nil
    }
    return ((*[0x7FFFFFF]branchPageElement)(unsafe.Pointer(&p.ptr)))[:]
}

 branchPage存储b+tree的非叶子节点， count 表示后面多少个 branchPageElement。branchPageElement 中的 pos 和 ksize 用于定位当前页中 key 的位置，由于本page是非叶子节点，找到该key会进入下一级，pgid 代表 key 对应下一级的page id，这个 key 该节点管理范围内，最小的叶子节点key。

2.3 leafPage

type leafPageElement struct {
    flags uint32
    pos   uint32  //kv在本page内偏移
    ksize uint32  //key大小
    vsize uint32  //value大小
}
// leafPageElement retrieves the leaf node by index
func (p *page) leafPageElement(index uint16) *leafPageElement {
    n := &((*[0x7FFFFFF]leafPageElement)(unsafe.Pointer(&p.ptr)))[index]
    return n
}
// leafPageElements retrieves a list of leaf nodes.
func (p *page) leafPageElements() []leafPageElement {
    if p.count == 0 {
        return nil
    }
    return ((*[0x7FFFFFF]leafPageElement)(unsafe.Pointer(&p.ptr)))[:]
}

 

2.4 freelistPage

count 表示后面的元素个数，如果flags是 freelist，表示 page id 个数。由于 count 是 2 bytes, 所以如果 count 值为 0xffff，那么紧临的第一个 int64 就不是 page id 而是真正的个数