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

spill()

  1. // spill writes all the nodes for this bucket to dirty pages.
  2. func (b *Bucket) spill() error {
  3.     // Spill all child buckets first.
  4.     for name, child := range b.buckets {
  5.         // If the child bucket is small enough and it has no child buckets then
  6.         // write it inline into the parent bucket's page. Otherwise spill it
  7.         // like a normal bucket and make the parent value a pointer to the page.
  8.         var value []byte
  9.         if child.inlineable() {
  10.             child.free()
  11.             // 重新更新bucket的val的值
  12.             value = child.write()
  13.         } else {
  14.             if err := child.spill(); err != nil {
  15.                 return err
  16.             }
  18.             // Update the child bucket header in this bucket.
  19.             // 记录value
  20.             value = make([]byte, unsafe.Sizeof(bucket{}))
  21.             var bucket = (*bucket)(unsafe.Pointer(&value[0]))
  22.             *bucket = *child.bucket
  23.         }
  25.         // Skip writing the bucket if there are no materialized nodes.
  26.         if child.rootNode == nil {
  27.             continue
  28.         }
  30.         // Update parent node.
  31.         var c = b.Cursor()
  32.         k, _, flags := c.seek([]byte(name))
  33.         if !bytes.Equal([]byte(name), k) {
  34.             panic(fmt.Sprintf("misplaced bucket header: %x -> %x", []byte(name), k))
  35.         }
  36.         if flags&bucketLeafFlag == 0 {
  37.             panic(fmt.Sprintf("unexpected bucket header flag: %x", flags))
  38.         }
  39.         // 更新子桶的value
  40.         c.node().put([]byte(name), []byte(name), value, 0, bucketLeafFlag)
  41.     }
  43.     // Ignore if there's not a materialized root node.
  44.     if b.rootNode == nil {
  45.         return nil
  46.     }
  48.     // Spill nodes.
  49.     if err := b.rootNode.spill(); err != nil {
  50.         return err
  51.     }
  52.     b.rootNode = b.rootNode.root()
  54.     // Update the root node for this bucket.
  55.     if b.rootNode.pgid >= b.tx.meta.pgid {
  56.         panic(fmt.Sprintf("pgid (%d) above high water mark (%d)", b.rootNode.pgid, b.tx.meta.pgid))
  57.     }
  58.     b.root = b.rootNode.pgid
  60.     return nil
  61. }
  63. // inlineable returns true if a bucket is small enough to be written inline
  64. // and if it contains no subbuckets. Otherwise returns false.
  65. func (b *Bucket) inlineable() bool {
  66.     var n = b.rootNode
  68.     // Bucket must only contain a single leaf node.
  69.     if n == nil || !n.isLeaf {
  70.         return false
  71.     }
  73.     // Bucket is not inlineable if it contains subbuckets or if it goes beyond
  74.     // our threshold for inline bucket size.
  75.     var size = pageHeaderSize
  76.     for _, inode := range n.inodes {
  77.         size += leafPageElementSize + len(inode.key) + len(inode.value)
  79.         if inode.flags&bucketLeafFlag != 0 {
  80.             // 有子桶时，不能内联
  81.             return false
  82.         } else if size > b.maxInlineBucketSize() {
  83.             // 如果长度大于1/4页时，就不内联了
  84.             return false
  85.         }
  86.     }
  88.     return true
  89. }
  91. // Returns the maximum total size of a bucket to make it a candidate for inlining.
  92. func (b *Bucket) maxInlineBucketSize() int {
  93.     return b.tx.db.pageSize / 4
  94. }

rebalance()

  1. // rebalance attempts to balance all nodes.
  2. func (b *Bucket) rebalance() {
  3.     for _, n := range b.nodes {
  4.         n.rebalance()
  5.     }
  6.     for _, child := range b.buckets {
  7.         child.rebalance()
  8.     }
  9. }