boltdb 1.3.0实现分析（二）

type DB struct {
   ...
    meta0    *meta
    meta1    *meta  
}


type meta struct {
   ...
    root     bucket     根bucket的信息
}


type Bucket struct {
    *bucket


   ...
  buckets  map[string]*Bucket  存储子bucket的对应关系
}


type bucket struct {
     根节点的page id
    root pgid  page id of the bucket's root-level page
     单调递增的序列号
    sequence uint64  monotonically incrementing, used by NextSequence()
}

type Bucket struct {
    *bucket
    tx       *Tx                 the associated transaction
    buckets  map[string]*Bucket  subbucket cache
    page     *page              / inline page reference
    rootNode *node              // materialized node for the root page.
    nodes    map[pgid]*node     // node cache


    // Sets the threshold for filling nodes when they split. By default,
    // the bucket will fill to 50% but it can be useful to increase this
    // amount if you know that your write workloads are mostly append-only.
    //
    // This is non-persisted across transactions so it must be set in every Tx.
    FillPercent float64
}

// leafPageElement represents a node on a leaf page.
type leafPageElement struct {
    flags uint32
    pos   uint32
    ksize uint32
    vsize uint32
}

const (
    bucketLeafFlag = 0x01
)

func (b *Bucket) Bucket(name []byte) *Bucket {
    // Move cursor to key.
    // 否则创建一个Cursor查询
    c := b.Cursor()
    k, v, flags := c.seek(name)


    // Return nil if the key doesn't exist or it is not a bucket.
    // 查询不到，或者不是子bucket节点，都返回nil
    if !bytes.Equal(name, k) || (flags&bucketLeafFlag) == 0 {
        return nil
    }


    // Otherwise create a bucket and cache it.
    // 打开这个bucket并且cache到buckets map中
    var child = b.openBucket(v)
    if b.buckets != nil {
        b.buckets[string(name)] = child
    }


    return child
}


func (b *Bucket) openBucket(value []byte) *Bucket {
    // 创建一个bucket
    var child = newBucket(b.tx)


    // If this is a writable transaction then we need to copy the bucket entry.
    // Read-only transactions can point directly at the mmap entry.
    if b.tx.writable {
        child.bucket = &bucket{}
        *child.bucket = *(*bucket)(unsafe.Pointer(&value[0]))
    } else {
        child.bucket = (*bucket)(unsafe.Pointer(&value[0]))
    }


    // Save a reference to the inline page if the bucket is inline.
    // inline bucket
    if child.root == 0 {
        // bucket的page
        child.page = (*page)(unsafe.Pointer(&value[bucketHeaderSize]))
    }


    return &child
}

// inlineable returns true if a bucket is small enough to be written inline
// and if it contains no subbuckets. Otherwise returns false.
// 返回这个bucket是否能够inline操作
func (b *Bucket) inlineable() bool {
    var n = b.rootNode


    // Bucket must only contain a single leaf node.
    // 如果没有根节点，或者根节点不是叶子节点的不能进行inline操作
    if n == nil || !n.isLeaf {
        return false
    }


    // Bucket is not inlineable if it contains subbuckets or if it goes beyond
    // our threshold for inline bucket size.
    // 有子bucket，或者大小超过maxInlineBucketSize阈值的，都不能进行inline操作
    var size = pageHeaderSize
    for _, inode := range n.inodes {
        size += leafPageElementSize + len(inode.key) + len(inode.value)


        if inode.flags&bucketLeafFlag != 0 {
            return false
        } else if size > b.maxInlineBucketSize() {
            return false
        }
    }


    return true
}


// Returns the maximum total size of a bucket to make it a candidate for inlining.
func (b *Bucket) maxInlineBucketSize() int {
    return b.tx.db.pageSize / 4
}

type Cursor struct {
    bucket *Bucket        // 对应的bucket
    stack  []elemRef    // 存储递归遍历时中间过程的栈，由于栈是先进后出结构，所以遍历的过程中层次高的在栈的低端。
}


// 光标移动过程中，中间过程的信息
type elemRef struct {
    page  *page    // 页面
    node  *node    // 内存中的页面信息
    index int        // 保存在当前page、node遍历到了哪个节点
}

// 移动到bucket的个元素上，返回其key value数据
func (c *Cursor) First() (key []byte, value []byte) {
    _assert(c.bucket.tx.db != nil, "tx closed")
    // 修改stack只保存个stack，及栈底部
    c.stack = c.stack[:0]
    // 返回root节点的page、node
    p, n := c.bucket.pageNode(c.bucket.root)
    // 将root节点所在的page、node信息放到栈顶，index为0，表示从个子节点开始遍历
    c.stack = append(c.stack, elemRef{page: p, node: n, index: 0})
    // 移动到当前的个元素
    // first函数做的事情：从树顶端开始，从左边一直往下遍历到叶子节点为止
    // 因为B树是中序遍历的，所以左边的节点数据小
    c.first()


    // If we land on an empty page then move to the next value.
    // https://github.com/boltdb/bolt/issues/450
    // 如果没有元素，就移动到下一个元素
    if c.stack[len(c.stack)-1].count() == 0 {
        c.next()
    }


    // 拿到k、v、flags
    k, v, flags := c.keyValue()
    // 如果是子bucket，就返回k以及nil
    if (flags & uint32(bucketLeafFlag)) != 0 {
        return k, nil
    }
    return k, v


}


// first moves the cursor to the first leaf element under the last page in the stack.
// 找到stack后一个页面中的个叶子节点
func (c *Cursor) first() {
    for {    // 找到左边个叶子节点
        // Exit when we hit a leaf page.
        // 每次循环取出后一个元素
        var ref = &c.stack[len(c.stack)-1]
        if ref.isLeaf() {    // 如果是叶子节点就退出循环，即这个循环终止的条件是向下一直找到叶子节点为止
            break
        }


        // Keep adding pages pointing to the first element to the stack.
        // 根据ref.index拿到pgid
        var pgid pgid
        if ref.node != nil {
            pgid = ref.node.inodes[ref.index].pgid
        } else {
            pgid = ref.page.branchPageElement(uint16(ref.index)).pgid
        }
        // 拿到对应的page、node
        p, n := c.bucket.pageNode(pgid)
        // 放到栈顶，注意这里的index是0
        // 即向下查找的时候取的都是左边的节点
        c.stack = append(c.stack, elemRef{page: p, node: n, index: 0})
    }
}