func (n *node) free() {
	if n.pgid != 0 {
		n.bucket.tx.db.freelist.free(n.bucket.tx.id(), n.bucket.tx.page(n.pgid))
		n.pgid = 0
	}
}
free adds the node's underlying page to the freelist.
package bolt
import (
	"bytes"
	"sort"
	"unsafe"
)
type node struct {
	bucket     *Bucket
	isLeaf     bool
	unbalanced bool
	key        []byte
	pgid       pgid
	parent     *node
	children   []*node
	inodes     inodes
}
func (n *node) root() *node {
	if n.parent == nil {
		return n
	}
	return n.parent.root()
}
func (n *node) minKeys() int {
	if n.isLeaf {
		return 1
	}
	return 2
}
func (n *node) size() int {
	var elementSize = n.pageElementSize()
	var size = pageHeaderSize
	for _, item := range n.inodes {
		size += elementSize + len(item.key) + len(item.value)
	}
	return size
}
func (n *node) pageElementSize() int {
	if n.isLeaf {
		return leafPageElementSize
	}
	return branchPageElementSize
}
func (n *node) childAt(index int) *node {
	_assert(!n.isLeaf, "invalid childAt(%d) on a leaf node", index)
	return n.bucket.node(n.inodes[index].pgid, n)
}
func (n *node) childIndex(child *node) int {
	index := sort.Search(len(n.inodes), func(i int) bool { return bytes.Compare(n.inodes[i].key, child.key) != -1 })
	return index
}
func (n *node) numChildren() int {
	return len(n.inodes)
}
func (n *node) nextSibling() *node {
	if n.parent == nil {
		return nil
	}
	index := n.parent.childIndex(n)
	if index >= n.parent.numChildren()-1 {
		return nil
	}
	return n.parent.childAt(index + 1)
}
func (n *node) prevSibling() *node {
	if n.parent == nil {
		return nil
	}
	index := n.parent.childIndex(n)
	if index == 0 {
		return nil
	}
	return n.parent.childAt(index - 1)
}
func (n *node) put(oldKey, newKey, value []byte, pgid pgid, flags uint32) {
	_assert(pgid < n.bucket.tx.meta.pgid, "pgid (%d) above high water mark (%d)", pgid, n.bucket.tx.meta.pgid)
	_assert(len(oldKey) > 0, "put: zero-length old key")
	_assert(len(newKey) > 0, "put: zero-length new key")
	index := sort.Search(len(n.inodes), func(i int) bool { return bytes.Compare(n.inodes[i].key, oldKey) != -1 })
	exact := (len(n.inodes) > 0 && index < len(n.inodes) && bytes.Equal(n.inodes[index].key, oldKey))
	if !exact {
		n.inodes = append(n.inodes, inode{})
		copy(n.inodes[index+1:], n.inodes[index:])
	}
	inode := &n.inodes[index]
	inode.flags = flags
	inode.key = newKey
	inode.value = value
	inode.pgid = pgid
	_assert(len(inode.key) > 0, "put: zero-length inode key")
}
func (n *node) del(key []byte) {
	index := sort.Search(len(n.inodes), func(i int) bool { return bytes.Compare(n.inodes[i].key, key) != -1 })
	if index >= len(n.inodes) || !bytes.Equal(n.inodes[index].key, key) {
		return
	}
	n.inodes = append(n.inodes[:index], n.inodes[index+1:]...)
	n.unbalanced = true
}
func (n *node) read(p *page) {
	n.pgid = p.id
	n.isLeaf = ((p.flags & leafPageFlag) != 0)
	n.inodes = make(inodes, int(p.count))
	for i := 0; i < int(p.count); i++ {
		inode := &n.inodes[i]
		if n.isLeaf {
			elem := p.leafPageElement(uint16(i))
			inode.flags = elem.flags
			inode.key = elem.key()
			inode.value = elem.value()
		} else {
			elem := p.branchPageElement(uint16(i))
			inode.pgid = elem.pgid
			inode.key = elem.key()
		}
		_assert(len(inode.key) > 0, "read: zero-length inode key")
	}
	if len(n.inodes) > 0 {
		n.key = n.inodes[0].key
		_assert(len(n.key) > 0, "read: zero-length node key")
	} else {
		n.key = nil
	}
}
func (n *node) write(p *page) {
	if n.isLeaf {
		p.flags |= leafPageFlag
	} else {
		p.flags |= branchPageFlag
	}
	p.count = uint16(len(n.inodes))
	b := (*[maxAllocSize]byte)(unsafe.Pointer(&p.ptr))[n.pageElementSize()*len(n.inodes):]
	for i, item := range n.inodes {
		_assert(len(item.key) > 0, "write: zero-length inode key")
		if n.isLeaf {
			elem := p.leafPageElement(uint16(i))
			elem.pos = uint32(uintptr(unsafe.Pointer(&b[0])) - uintptr(unsafe.Pointer(elem)))
			elem.flags = item.flags
			elem.ksize = uint32(len(item.key))
			elem.vsize = uint32(len(item.value))
		} else {
			elem := p.branchPageElement(uint16(i))
			elem.pos = uint32(uintptr(unsafe.Pointer(&b[0])) - uintptr(unsafe.Pointer(elem)))
			elem.ksize = uint32(len(item.key))
			elem.pgid = item.pgid
		}
		copy(b[0:], item.key)
		b = b[len(item.key):]
		copy(b[0:], item.value)
		b = b[len(item.value):]
	}
}
func (n *node) split(pageSize int) []*node {
	var nodes = []*node{n}
	if len(n.inodes) <= (minKeysPerPage*2) || n.size() < pageSize {
		return nodes
	}
	var fillPercent = n.bucket.tx.db.FillPercent
	if fillPercent < minFillPercent {
		fillPercent = minFillPercent
	} else if fillPercent > maxFillPercent {
		fillPercent = maxFillPercent
	}
	threshold := int(float64(pageSize) * fillPercent)
	size := pageHeaderSize
	internalNodes := n.inodes
	current := n
	current.inodes = nil
	for i, inode := range internalNodes {
		elemSize := n.pageElementSize() + len(inode.key) + len(inode.value)
		if len(current.inodes) >= minKeysPerPage && i < len(internalNodes)-minKeysPerPage && size+elemSize > threshold {
			if n.parent == nil {
				n.parent = &node{bucket: n.bucket, children: []*node{n}}
			}
			current = &node{bucket: n.bucket, isLeaf: n.isLeaf, parent: n.parent}
			n.parent.children = append(n.parent.children, current)
			nodes = append(nodes, current)
			size = pageHeaderSize
			n.bucket.tx.stats.Split++
		}
		size += elemSize
		current.inodes = append(current.inodes, inode)
	}
	return nodes
}
func (n *node) spill() error {
	var tx = n.bucket.tx
	for _, child := range n.children {
		if err := child.spill(); err != nil {
			return err
		}
	}
	if n.pgid > 0 {
		tx.db.freelist.free(tx.id(), tx.page(n.pgid))
		n.pgid = 0
	}
	var nodes = n.split(tx.db.pageSize)
	for _, node := range nodes {
		p, err := tx.allocate((node.size() / tx.db.pageSize) + 1)
		if err != nil {
			return err
		}
		_assert(p.id < tx.meta.pgid, "pgid (%d) above high water mark (%d)", p.id, tx.meta.pgid)
		node.pgid = p.id
		node.write(p)
		if node.parent != nil {
			var key = node.key
			if key == nil {
				key = node.inodes[0].key
			}
			node.parent.put(key, node.inodes[0].key, nil, node.pgid, 0)
			node.key = node.inodes[0].key
			_assert(len(n.key) > 0, "spill: zero-length node key")
		}
		tx.stats.Spill++
	}
	var parent = n.parent
	if parent != nil && parent.pgid == 0 {
		p, err := tx.allocate((parent.size() / tx.db.pageSize) + 1)
		if err != nil {
			return err
		}
		_assert(p.id < tx.meta.pgid, "pgid (%d) above high water mark (%d)", p.id, tx.meta.pgid)
		parent.pgid = p.id
		parent.write(p)
	}
	return nil
}
func (n *node) rebalance() {
	if !n.unbalanced {
		return
	}
	n.unbalanced = false
	n.bucket.tx.stats.Rebalance++
	var threshold = n.bucket.tx.db.pageSize / 4
	if n.size() > threshold && len(n.inodes) > n.minKeys() {
		return
	}
	if n.parent == nil {
		if !n.isLeaf && len(n.inodes) == 1 {
			child := n.bucket.node(n.inodes[0].pgid, n)
			n.isLeaf = child.isLeaf
			n.inodes = child.inodes[:]
			n.children = child.children
			for _, inode := range n.inodes {
				if child, ok := n.bucket.nodes[inode.pgid]; ok {
					child.parent = n
				}
			}
			child.parent = nil
			delete(n.bucket.nodes, child.pgid)
			child.free()
		}
		return
	}
	if n.numChildren() == 0 {
		n.parent.del(n.key)
		n.parent.removeChild(n)
		delete(n.bucket.nodes, n.pgid)
		n.free()
		n.parent.rebalance()
		return
	}
	_assert(n.parent.numChildren() > 1, "parent must have at least 2 children")
	var target *node
	var useNextSibling = (n.parent.childIndex(n) == 0)
	if useNextSibling {
		target = n.nextSibling()
	} else {
		target = n.prevSibling()
	}
	if target.numChildren() > target.minKeys() {
		if useNextSibling {
			if child, ok := n.bucket.nodes[target.inodes[0].pgid]; ok {
				child.parent.removeChild(child)
				child.parent = n
				child.parent.children = append(child.parent.children, child)
			}
			n.inodes = append(n.inodes, target.inodes[0])
			target.inodes = target.inodes[1:]
			target.parent.put(target.key, target.inodes[0].key, nil, target.pgid, 0)
			target.key = target.inodes[0].key
			_assert(len(target.key) > 0, "rebalance(1): zero-length node key")
		} else {
			if child, ok := n.bucket.nodes[target.inodes[len(target.inodes)-1].pgid]; ok {
				child.parent.removeChild(child)
				child.parent = n
				child.parent.children = append(child.parent.children, child)
			}
			n.inodes = append(n.inodes, inode{})
			copy(n.inodes[1:], n.inodes)
			n.inodes[0] = target.inodes[len(target.inodes)-1]
			target.inodes = target.inodes[:len(target.inodes)-1]
		}
		n.parent.put(n.key, n.inodes[0].key, nil, n.pgid, 0)
		n.key = n.inodes[0].key
		_assert(len(n.key) > 0, "rebalance(2): zero-length node key")
		return
	}
	if useNextSibling {
		for _, inode := range target.inodes {
			if child, ok := n.bucket.nodes[inode.pgid]; ok {
				child.parent.removeChild(child)
				child.parent = n
				child.parent.children = append(child.parent.children, child)
			}
		}
		n.inodes = append(n.inodes, target.inodes...)
		n.parent.del(target.key)
		n.parent.removeChild(target)
		delete(n.bucket.nodes, target.pgid)
		target.free()
	} else {
		for _, inode := range n.inodes {
			if child, ok := n.bucket.nodes[inode.pgid]; ok {
				child.parent.removeChild(child)
				child.parent = target
				child.parent.children = append(child.parent.children, child)
			}
		}
		target.inodes = append(target.inodes, n.inodes...)
		n.parent.del(n.key)
		n.parent.removeChild(n)
		n.parent.put(target.key, target.inodes[0].key, nil, target.pgid, 0)
		delete(n.bucket.nodes, n.pgid)
		n.free()
	}
	n.parent.rebalance()
}
func (n *node) removeChild(target *node) {
	for i, child := range n.children {
		if child == target {
			n.children = append(n.children[:i], n.children[i+1:]...)
			return
		}
	}
}
func (n *node) dereference() {
	if n.key != nil {
		key := make([]byte, len(n.key))
		copy(key, n.key)
		n.key = key
		_assert(n.pgid == 0 || len(n.key) > 0, "dereference: zero-length node key on existing node")
	}
	for i := range n.inodes {
		inode := &n.inodes[i]
		key := make([]byte, len(inode.key))
		copy(key, inode.key)
		inode.key = key
		_assert(len(inode.key) > 0, "dereference: zero-length inode key")
		value := make([]byte, len(inode.value))
		copy(value, inode.value)
		inode.value = value
	}
	for _, child := range n.children {
		child.dereference()
	}
	n.bucket.tx.stats.NodeDeref++
}