第四节分支节点页

第四节分支节点页

分支节点主要用来构建索引，方便提升查询效率。下面我们来看看boltdb的分支节点的数据是如何存储的。

1. 分支节点页中元素定义：

分支节点在存储时，一个分支节点页上会存储多个分支页元素即branchPageElement。这个信息可以记做为分支页元素元信息。元信息中定义了具体该元素的页id(pgid)、该元素所指向的页中存储的最小key的值大小、最小key的值存储的位置距离当前的元信息的偏移量pos。下面是branchPageElement的详细定义：

1. // branchPageElement represents a node on a branch page.
2. type branchPageElement struct {
3. pos   uint32 //该元信息和真实key之间的偏移量
4. ksize uint32
5. pgid  pgid
6. }

8. // key returns a byte slice of the node key.
9. func (n *branchPageElement) key() []byte {
10. buf := (*[maxAllocSize]byte)(unsafe.Pointer(n))
11. // pos~ksize
12. return (*[maxAllocSize]byte)(unsafe.Pointer(&buf[n.pos]))[:n.ksize]
13. }

2. 分支节点页page中获取下标为index的某一个element的信息和获取全部的elements信息

1. // branchPageElement retrieves the branch node by index
2. func (p *page) branchPageElement(index uint16) *branchPageElement {
3. return &((*[0x7FFFFFF]branchPageElement)(unsafe.Pointer(&p.ptr)))[index]
4. }

6. // branchPageElements retrieves a list of branch nodes.
7. func (p *page) branchPageElements() []branchPageElement {
8. if p.count == 0 {
9. return nil
10. }
11. return ((*[0x7FFFFFF]branchPageElement)(unsafe.Pointer(&p.ptr)))[:]
12. }

下图展现的是非叶子节点存储方式。

在内存中，分支节点页和叶子节点页都是通过node来表示，只不过的区别是通过其node中的isLeaf这个字段来区分。下面和大家分析分支节点页page和内存中的node的转换关系。

下面在介绍具体的转换关系前，我们介绍一下内存中的分支节点和叶子节点是如何描述的。

1. // node represents an in-memory, deserialized page.
2. type node struct {
3. bucket     *Bucket
4. isLeaf     bool
5. unbalanced bool
6. spilled    bool
7. key        []byte
8. pgid       pgid
9. parent     *node
10. children   nodes
11. inodes     inodes
12. }

在内存中，具体的一个分支节点或者叶子节点都被抽象为一个node对象，其中是分支节点还是叶子节点主要通通过其isLeaf字段来区分。下面对分支节点和叶子节点做两点说明：

对叶子节点而言，其没有children这个信息。同时也没有key信息。isLeaf字段为true，其上存储的key、value都保存在inodes中
对于分支节点而言，其具有key信息，同时children也不一定为空。isLeaf字段为false，同时该节点上的数据保存在inode中。

为了方便大家理解，node和page的转换，下面大概介绍下inode和nodes结构。我们在下一章会详细介绍node。

2. const (
3. bucketLeafFlag = 0x01
4. )

7. type nodes []*node

9. func (s nodes) Len() int           { return len(s) }
10. func (s nodes) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
11. func (s nodes) Less(i, j int) bool { return bytes.Compare(s[i].inodes[0].key, s[j].inodes[0].key) == -1 }

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

26. type inodes []inode

3. page->node

通过分支节点页来构建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. n.inodes = make(inodes, int(p.count))

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

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

4. 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. }

第四节 分支节点页

第四节 分支节点页

第四节分支节点页

第四节分支节点页