第三节 node节点的相关操作

在开始分析node节点之前，我们先看一下官方对node节点的描述

node represents an in-memory, deserialized page

一个node节点，既可能是叶子节点，也可能是根节点，也可能是分支节点。是物理磁盘上读取进来的页page的内存表现形式。

3.3.1 node节点的定义

1. // node represents an in-memory, deserialized page.
2. type node struct {
3. bucket     *Bucket // 关联一个桶
4. isLeaf     bool
5. unbalanced bool   // 值为true的话，需要考虑页合并
6. spilled    bool   // 值为true的话，需要考虑页分裂
7. key        []byte // 对于分支节点的话，保留的是最小的key
8. pgid       pgid   // 分支节点关联的页id
9. parent     *node  // 该节点的parent
10. children   nodes  // 该节点的孩子节点
11. inodes     inodes // 该节点上保存的索引数据
12. }

14. // inode represents an internal node inside of a node.
15. // It can be used to point to elements in a page or point
16. // to an element which hasn't been added to a page yet.
17. type inode struct {
18. // 表示是否是子桶叶子节点还是普通叶子节点。如果flags值为1表示子桶叶子节点，否则为普通叶子节点
19. flags uint32
20. // 当inode为分支元素时，pgid才有值，为叶子元素时，则没值
21. pgid pgid
22. key  []byte
23. // 当inode为分支元素时，value为空，为叶子元素时，才有值
24. value []byte
25. }

27. type inodes []inode

3.3.2 node节点和page转换

在node对象上有两个方法，read(page)、write(page)，其中read(page)方法是用来通过page构建一个node节点；而write(page)方法则是将当前的node节点写入到page中，我们在前面他提到了node节点和page节点的相互转换，此处为了保证内容完整性，我们还是再补充下，同时也给大家加深下影响，展示下同样的数据在磁盘上如何组织的，在内存中又是如何组织的。

node->page

1. // write writes the items onto one or more pages.
2. // 将node转为page
3. func (n *node) write(p *page) {
4. // Initialize page.
5. // 判断是否是叶子节点还是非叶子节点
6. if n.isLeaf {
7. p.flags |= leafPageFlag
8. } else {
9. p.flags |= branchPageFlag
10. }

12. // 这儿叶子节点不可能溢出，因为溢出时，会分裂
13. if len(n.inodes) >= 0xFFFF {
14. panic(fmt.Sprintf("inode overflow: %d (pgid=%d)", len(n.inodes), p.id))
15. }
16. p.count = uint16(len(n.inodes))

18. // Stop here if there are no items to write.
19. if p.count == 0 {
20. return
21. }

23. // Loop over each item and write it to the page.
24. // b指向的指针为提逃过所有item头部的位置
25. b := (*[maxAllocSize]byte)(unsafe.Pointer(&p.ptr))[n.pageElementSize()*len(n.inodes):]
26. for i, item := range n.inodes {
27. _assert(len(item.key) > 0, "write: zero-length inode key")

29. // Write the page element.
30. // 写入叶子节点数据
31. if n.isLeaf {
32. elem := p.leafPageElement(uint16(i))
33. elem.pos = uint32(uintptr(unsafe.Pointer(&b[0])) - uintptr(unsafe.Pointer(elem)))
34. elem.flags = item.flags
35. elem.ksize = uint32(len(item.key))
36. elem.vsize = uint32(len(item.value))
37. } else {
38. // 写入分支节点数据
39. elem := p.branchPageElement(uint16(i))
40. elem.pos = uint32(uintptr(unsafe.Pointer(&b[0])) - uintptr(unsafe.Pointer(elem)))
41. elem.ksize = uint32(len(item.key))
42. elem.pgid = item.pgid
43. _assert(elem.pgid != p.id, "write: circular dependency occurred")
44. }

46. // If the length of key+value is larger than the max allocation size
47. // then we need to reallocate the byte array pointer.
48. //
49. // See: https://github.com/boltdb/bolt/pull/335
50. klen, vlen := len(item.key), len(item.value)
51. if len(b) < klen+vlen {
52. b = (*[maxAllocSize]byte)(unsafe.Pointer(&b[0]))[:]
53. }

55. // Write data for the element to the end of the page.
56. copy(b[0:], item.key)
57. b = b[klen:]
58. copy(b[0:], item.value)
59. b = b[vlen:]
60. }

62. // DEBUG ONLY: n.dump()
63. }

page->node

1. // 根据page来初始化node
2. // read initializes the node from a page.
3. func (n *node) read(p *page) {
4. n.pgid = p.id
5. n.isLeaf = ((p.flags & leafPageFlag) != 0)
6. // 一个inodes对应一个xxxPageElement对象
7. n.inodes = make(inodes, int(p.count))

9. for i := 0; i < int(p.count); i++ {
10. inode := &n.inodes[i]
11. if n.isLeaf {
12. // 获取第i个叶子节点
13. elem := p.leafPageElement(uint16(i))
14. inode.flags = elem.flags
15. inode.key = elem.key()
16. inode.value = elem.value()
17. } else {
18. // 树枝节点
19. elem := p.branchPageElement(uint16(i))
20. inode.pgid = elem.pgid
21. inode.key = elem.key()
22. }
23. _assert(len(inode.key) > 0, "read: zero-length inode key")
24. }

26. // Save first key so we can find the node in the parent when we spill.
27. if len(n.inodes) > 0 {
28. // 保存第1个元素的值
29. n.key = n.inodes[0].key
30. _assert(len(n.key) > 0, "read: zero-length node key")
31. } else {
32. n.key = nil
33. }
34. }

3.3.3 node节点的增删改查

put(k,v)

1. // put inserts a key/value.
2. // 如果put的是一个key、value的话，不需要指定pgid。
3. // 如果put的一个树枝节点，则需要指定pgid，不需要指定value
4. func (n *node) put(oldKey, newKey, value []byte, pgid pgid, flags uint32) {
5. if pgid >= n.bucket.tx.meta.pgid {
6. panic(fmt.Sprintf("pgid (%d) above high water mark (%d)", pgid, n.bucket.tx.meta.pgid))
7. } else if len(oldKey) <= 0 {
8. panic("put: zero-length old key")
9. } else if len(newKey) <= 0 {
10. panic("put: zero-length new key")
11. }

13. // Find insertion index.
14. index := sort.Search(len(n.inodes), func(i int) bool { return bytes.Compare(n.inodes[i].key, oldKey) != -1 })

16. // Add capacity and shift nodes if we don't have an exact match and need to insert.
17. exact := (len(n.inodes) > 0 && index < len(n.inodes) && bytes.Equal(n.inodes[index].key, oldKey))
18. if !exact {
19. n.inodes = append(n.inodes, inode{})
20. copy(n.inodes[index+1:], n.inodes[index:])
21. }

23. inode := &n.inodes[index]
24. inode.flags = flags
25. inode.key = newKey
26. inode.value = value
27. inode.pgid = pgid
28. _assert(len(inode.key) > 0, "put: zero-length inode key")
29. }

get(k)

在node中，没有get(k)的方法，其本质是在Cursor中就返回了get的数据。大家可以看看Cursor中的keyValue()方法。

del(k)

1. // del removes a key from the node.
2. func (n *node) del(key []byte) {
3. // Find index of key.
4. index := sort.Search(len(n.inodes), func(i int) bool { return bytes.Compare(n.inodes[i].key, key) != -1 })

6. // Exit if the key isn't found.
7. if index >= len(n.inodes) || !bytes.Equal(n.inodes[index].key, key) {
8. return
9. }

11. // Delete inode from the node.
12. n.inodes = append(n.inodes[:index], n.inodes[index+1:]...)

14. // Mark the node as needing rebalancing.
15. n.unbalanced = true
16. }

nextSibling()、prevSibling()

2. // nextSibling returns the next node with the same parent.
3. // 返回下一个兄弟节点
4. func (n *node) nextSibling() *node {
5. if n.parent == nil {
6. return nil
7. }
8. index := n.parent.childIndex(n)
9. if index >= n.parent.numChildren()-1 {
10. return nil
11. }
12. return n.parent.childAt(index + 1)
13. }

15. // prevSibling returns the previous node with the same parent.
16. // 返回上一个兄弟节点
17. func (n *node) prevSibling() *node {
18. if n.parent == nil {
19. return nil
20. }
21. // 首先找下标
22. index := n.parent.childIndex(n)
23. if index == 0 {
24. return nil
25. }
26. // 然后返回
27. return n.parent.childAt(index - 1)
28. }

30. // childIndex returns the index of a given child node.
31. func (n *node) childIndex(child *node) int {
32. index := sort.Search(len(n.inodes), func(i int) bool { return bytes.Compare(n.inodes[i].key, child.key) != -1 })
33. return index
34. }

37. // childAt returns the child node at a given index.
38. // 只有树枝节点才有孩子
39. func (n *node) childAt(index int) *node {
40. if n.isLeaf {
41. panic(fmt.Sprintf("invalid childAt(%d) on a leaf node", index))
42. }
43. return n.bucket.node(n.inodes[index].pgid, n)
44. }

46. // node creates a node from a page and associates it with a given parent.
47. // 根据pgid创建一个node
48. func (b *Bucket) node(pgid pgid, parent *node) *node {
49. _assert(b.nodes != nil, "nodes map expected")

51. // Retrieve node if it's already been created.
52. if n := b.nodes[pgid]; n != nil {
53. return n
54. }

56. // Otherwise create a node and cache it.
57. n := &node{bucket: b, parent: parent}
58. if parent == nil {
59. b.rootNode = n
60. } else {
61. parent.children = append(parent.children, n)
62. }

64. // Use the inline page if this is an inline bucket.
65. // 如果第二次进来，b.page不为空
66. // 此处的pgid和b.page只会有一个是有值的。
67. var p = b.page
68. // 说明不是内联桶
69. if p == nil {
70. p = b.tx.page(pgid)
71. }

73. // Read the page into the node and cache it.
74. n.read(p)
75. // 缓存
76. b.nodes[pgid] = n

78. // Update statistics.
79. b.tx.stats.NodeCount++

81. return n
82. }

3.3.4 node节点的分裂和合并

上面我们看了对node节点的操作，包括put和del方法。经过这些操作后，可能会导致当前的page填充度过高或者过低。因此就引出了node节点的分裂和合并。下面简单介绍下什么是分裂和合并。

分裂: 当一个node中的数据过多时，最简单就是当超过了page的填充度时，就需要将当前的node拆分成两个，也就是底层会将一页数据拆分存放到两页中。

合并: 当删除了一个或者一批对象时，此时可能会导致一页数据的填充度过低，此时空间可能会浪费比较多。所以就需要考虑对页之间进行数据合并。

有了大概的了解，下面我们就看一下对一个node分裂和合并的实现过程。

分裂spill()

spill writes the nodes to dirty pages and splits nodes as it goes. Returns an error if dirty pages cannot be allocated.

1. // spill writes the nodes to dirty pages and splits nodes as it goes.
2. // Returns an error if dirty pages cannot be allocated.
3. func (n *node) spill() error {
4. var tx = n.bucket.tx
5. if n.spilled {
6. return nil
7. }

9. // Spill child nodes first. Child nodes can materialize sibling nodes in
10. // the case of split-merge so we cannot use a range loop. We have to check
11. // the children size on every loop iteration.
12. sort.Sort(n.children)
13. for i := 0; i < len(n.children); i++ {
14. if err := n.children[i].spill(); err != nil {
15. return err
16. }
17. }

19. // We no longer need the child list because it's only used for spill tracking.
20. n.children = nil

22. // Split nodes into appropriate sizes. The first node will always be n.
23. // 将当前的node进行拆分成多个node
24. var nodes = n.split(tx.db.pageSize)
25. for _, node := range nodes {
26. // Add node's page to the freelist if it's not new.
27. if node.pgid > 0 {
28. tx.db.freelist.free(tx.meta.txid, tx.page(node.pgid))
29. node.pgid = 0
30. }

32. // Allocate contiguous space for the node.
33. p, err := tx.allocate((node.size() / tx.db.pageSize) + 1)
34. if err != nil {
35. return err
36. }

38. // Write the node.
39. if p.id >= tx.meta.pgid {
40. // 不可能发生
41. panic(fmt.Sprintf("pgid (%d) above high water mark (%d)", p.id, tx.meta.pgid))
42. }
43. node.pgid = p.id
44. node.write(p)
45. // 已经拆分过了
46. node.spilled = true

48. // Insert into parent inodes.
49. if node.parent != nil {
50. var key = node.key
51. if key == nil {
52. key = node.inodes[0].key
53. }

55. // 放入父亲节点中
56. node.parent.put(key, node.inodes[0].key, nil, node.pgid, 0)
57. node.key = node.inodes[0].key
58. _assert(len(node.key) > 0, "spill: zero-length node key")
59. }

61. // Update the statistics.
62. tx.stats.Spill++
63. }

65. // If the root node split and created a new root then we need to spill that
66. // as well. We'll clear out the children to make sure it doesn't try to respill.
67. if n.parent != nil && n.parent.pgid == 0 {
68. n.children = nil
69. return n.parent.spill()
70. }

72. return nil
73. }

75. // split breaks up a node into multiple smaller nodes, if appropriate.
76. // This should only be called from the spill() function.
77. func (n *node) split(pageSize int) []*node {
78. var nodes []*node

80. node := n
81. for {
82. // Split node into two.
83. a, b := node.splitTwo(pageSize)
84. nodes = append(nodes, a)

86. // If we can't split then exit the loop.
87. if b == nil {
88. break
89. }

91. // Set node to b so it gets split on the next iteration.
92. node = b
93. }

95. return nodes
96. }

98. // splitTwo breaks up a node into two smaller nodes, if appropriate.
99. // This should only be called from the split() function.
100. func (n *node) splitTwo(pageSize int) (*node, *node) {
101. // Ignore the split if the page doesn't have at least enough nodes for
102. // two pages or if the nodes can fit in a single page.
103. // 太小的话，就不拆分了
104. if len(n.inodes) <= (minKeysPerPage*2) || n.sizeLessThan(pageSize) {
105. return n, nil
106. }

108. // Determine the threshold before starting a new node.
109. var fillPercent = n.bucket.FillPercent
110. if fillPercent < minFillPercent {
111. fillPercent = minFillPercent
112. } else if fillPercent > maxFillPercent {
113. fillPercent = maxFillPercent
114. }
115. threshold := int(float64(pageSize) * fillPercent)

117. // Determine split position and sizes of the two pages.
118. splitIndex, _ := n.splitIndex(threshold)

120. // Split node into two separate nodes.
121. // If there's no parent then we'll need to create one.
122. if n.parent == nil {
123. n.parent = &node{bucket: n.bucket, children: []*node{n}}
124. }

126. // Create a new node and add it to the parent.
127. // 拆分出一个新节点
128. next := &node{bucket: n.bucket, isLeaf: n.isLeaf, parent: n.parent}
129. n.parent.children = append(n.parent.children, next)

131. // Split inodes across two nodes.
132. next.inodes = n.inodes[splitIndex:]
133. n.inodes = n.inodes[:splitIndex]

135. // Update the statistics.
136. n.bucket.tx.stats.Split++

138. return n, next
139. }

141. // splitIndex finds the position where a page will fill a given threshold.
142. // It returns the index as well as the size of the first page.
143. // This is only be called from split().
144. // 找到合适的index
145. func (n *node) splitIndex(threshold int) (index, sz int) {
146. sz = pageHeaderSize

148. // Loop until we only have the minimum number of keys required for the second page.
149. for i := 0; i < len(n.inodes)-minKeysPerPage; i++ {
150. index = i
151. inode := n.inodes[i]
152. elsize := n.pageElementSize() + len(inode.key) + len(inode.value)

154. // If we have at least the minimum number of keys and adding another
155. // node would put us over the threshold then exit and return.
156. if i >= minKeysPerPage && sz+elsize > threshold {
157. break
158. }

160. // Add the element size to the total size.
161. sz += elsize
162. }

164. return
165. }

合并rebalance()

rebalance attempts to combine the node with sibling nodes if the node fill size is below a threshold or if there are not enough keys.

页合并有点复杂，虽然能看懂，但要自己写感觉还是挺难写出bug free的

1. // rebalance attempts to combine the node with sibling nodes if the node fill
2. // size is below a threshold or if there are not enough keys.
3. // 填充率太低或者没有足够的key时，进行页合并
4. func (n *node) rebalance() {
5. if !n.unbalanced {
6. return
7. }
8. n.unbalanced = false

10. // Update statistics.
11. n.bucket.tx.stats.Rebalance++

13. // Ignore if node is above threshold (25%) and has enough keys.
14. var threshold = n.bucket.tx.db.pageSize / 4
15. if n.size() > threshold && len(n.inodes) > n.minKeys() {
16. return
17. }

19. // Root node has special handling.
20. if n.parent == nil {
21. // If root node is a branch and only has one node then collapse it.
22. if !n.isLeaf && len(n.inodes) == 1 {
23. // Move root's child up.
24. child := n.bucket.node(n.inodes[0].pgid, n)
25. n.isLeaf = child.isLeaf
26. n.inodes = child.inodes[:]
27. n.children = child.children

29. // Reparent all child nodes being moved.
30. for _, inode := range n.inodes {
31. if child, ok := n.bucket.nodes[inode.pgid]; ok {
32. child.parent = n
33. }
34. }

36. // Remove old child.
37. child.parent = nil
38. delete(n.bucket.nodes, child.pgid)
39. child.free()
40. }

42. return
43. }

45. // If node has no keys then just remove it.
46. if n.numChildren() == 0 {
47. n.parent.del(n.key)
48. n.parent.removeChild(n)
49. delete(n.bucket.nodes, n.pgid)
50. n.free()
51. n.parent.rebalance()
52. return
53. }

55. _assert(n.parent.numChildren() > 1, "parent must have at least 2 children")

57. // Destination node is right sibling if idx == 0, otherwise left sibling.
58. var target *node
59. // 判断当前node是否是parent的第一个孩子节点，是的话，就要找它的下一个兄弟节点，否则的话，就找上一个兄弟节点
60. var useNextSibling = (n.parent.childIndex(n) == 0)
61. if useNextSibling {
62. target = n.nextSibling()
63. } else {
64. target = n.prevSibling()
65. }

67. // If both this node and the target node are too small then merge them.
68. // 合并当前node和target，target合到node
69. if useNextSibling {
70. // Reparent all child nodes being moved.
71. for _, inode := range target.inodes {
72. if child, ok := n.bucket.nodes[inode.pgid]; ok {
73. // 之前的父亲移除该孩子
74. child.parent.removeChild(child)
75. // 重新指定父亲节点
76. child.parent = n
77. // 父亲节点指当前孩子
78. child.parent.children = append(child.parent.children, child)
79. }
80. }

82. // Copy over inodes from target and remove target.
83. n.inodes = append(n.inodes, target.inodes...)
84. n.parent.del(target.key)
85. n.parent.removeChild(target)
86. delete(n.bucket.nodes, target.pgid)
87. target.free()
88. } else {
89. // node合到target
90. // Reparent all child nodes being moved.
91. for _, inode := range n.inodes {
92. if child, ok := n.bucket.nodes[inode.pgid]; ok {
93. child.parent.removeChild(child)
94. child.parent = target
95. child.parent.children = append(child.parent.children, child)
96. }
97. }

99. // Copy over inodes to target and remove node.
100. target.inodes = append(target.inodes, n.inodes...)
101. n.parent.del(n.key)
102. n.parent.removeChild(n)
103. delete(n.bucket.nodes, n.pgid)
104. n.free()
105. }

107. // Either this node or the target node was deleted from the parent so rebalance it.
108. n.parent.rebalance()
109. }