第六节 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. }