第六节 Bucket的页分裂、页合并

spill()

// spill writes all the nodes for this bucket to dirty pages.
func (b *Bucket) spill() error {
    // Spill all child buckets first.
    for name, child := range b.buckets {
        // If the child bucket is small enough and it has no child buckets then
        // write it inline into the parent bucket's page. Otherwise spill it
        // like a normal bucket and make the parent value a pointer to the page.
        var value []byte
        if child.inlineable() {
            child.free()
            // 重新更新bucket的val的值
            value = child.write()
        } else {
            if err := child.spill(); err != nil {
                return err
            }

            // Update the child bucket header in this bucket.
            // 记录value
            value = make([]byte, unsafe.Sizeof(bucket{}))
            var bucket = (*bucket)(unsafe.Pointer(&value[0]))
            *bucket = *child.bucket
        }

        // Skip writing the bucket if there are no materialized nodes.
        if child.rootNode == nil {
            continue
        }

        // Update parent node.
        var c = b.Cursor()
        k, _, flags := c.seek([]byte(name))
        if !bytes.Equal([]byte(name), k) {
            panic(fmt.Sprintf("misplaced bucket header: %x -> %x", []byte(name), k))
        }
        if flags&bucketLeafFlag == 0 {
            panic(fmt.Sprintf("unexpected bucket header flag: %x", flags))
        }
        // 更新子桶的value
        c.node().put([]byte(name), []byte(name), value, 0, bucketLeafFlag)
    }

    // Ignore if there's not a materialized root node.
    if b.rootNode == nil {
        return nil
    }

    // Spill nodes.
    if err := b.rootNode.spill(); err != nil {
        return err
    }
    b.rootNode = b.rootNode.root()

    // Update the root node for this bucket.
    if b.rootNode.pgid >= b.tx.meta.pgid {
        panic(fmt.Sprintf("pgid (%d) above high water mark (%d)", b.rootNode.pgid, b.tx.meta.pgid))
    }
    b.root = b.rootNode.pgid

    return nil
}

// inlineable returns true if a bucket is small enough to be written inline
// and if it contains no subbuckets. Otherwise returns false.
func (b *Bucket) inlineable() bool {
    var n = b.rootNode

    // Bucket must only contain a single leaf node.
    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.
    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() {
            // 如果长度大于1/4页时，就不内联了
            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
}

rebalance()

// rebalance attempts to balance all nodes.
func (b *Bucket) rebalance() {
    for _, n := range b.nodes {
        n.rebalance()
    }
    for _, child := range b.buckets {
        child.rebalance()
    }
}