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