1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
|
package bolt
import (
"bytes"
"sort"
"unsafe"
)
// node represents an in-memory, deserialized page.
type node struct {
isLeaf bool
key []byte
depth int
pgid pgid
parent *node
inodes inodes
}
// size returns the size of the node after serialization.
func (n *node) size() int {
var elementSize int = n.pageElementSize()
var size int = pageHeaderSize
for _, item := range n.inodes {
size += elementSize + len(item.key) + len(item.value)
}
return size
}
// pageElementSize returns the size of each page element based on the type of node.
func (n *node) pageElementSize() int {
if n.isLeaf {
return leafPageElementSize
}
return branchPageElementSize
}
// root returns the root node in the tree.
func (n *node) root() *node {
if n.parent == nil {
return n
}
return n.parent
}
// put inserts a key/value.
func (n *node) put(oldKey, newKey, value []byte, pgid pgid) {
// Find insertion index.
index := sort.Search(len(n.inodes), func(i int) bool { return bytes.Compare(n.inodes[i].key, oldKey) != -1 })
// Add capacity and shift nodes if we don't have an exact match and need to insert.
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.key = newKey
inode.value = value
inode.pgid = pgid
}
// del removes a key from the node.
func (n *node) del(key []byte) {
// Find index of key.
index := sort.Search(len(n.inodes), func(i int) bool { return bytes.Compare(n.inodes[i].key, key) != -1 })
// Exit if the key isn't found.
if !bytes.Equal(n.inodes[index].key, key) {
return
}
// Delete inode from the node.
n.inodes = append(n.inodes[:index], n.inodes[index+1:]...)
}
// read initializes the node from a page.
func (n *node) read(p *page) {
n.pgid = p.id
n.isLeaf = ((p.flags & p_leaf) != 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.key = elem.key()
inode.value = elem.value()
} else {
elem := p.branchPageElement(uint16(i))
inode.pgid = elem.pgid
inode.key = elem.key()
}
}
// Save first key so we can find the node in the parent when we spill.
if len(n.inodes) > 0 {
n.key = n.inodes[0].key
} else {
n.key = nil
}
}
// write writes the items onto one or more pages.
func (n *node) write(p *page) {
// Initialize page.
if n.isLeaf {
p.flags |= p_leaf
} else {
p.flags |= p_branch
}
p.count = uint16(len(n.inodes))
// Loop over each item and write it to the page.
b := (*[maxAllocSize]byte)(unsafe.Pointer(&p.ptr))[n.pageElementSize()*len(n.inodes):]
for i, item := range n.inodes {
// Write the page element.
if n.isLeaf {
elem := p.leafPageElement(uint16(i))
elem.pos = uint32(uintptr(unsafe.Pointer(&b[0])) - uintptr(unsafe.Pointer(elem)))
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
}
// Write data for the element to the end of the page.
copy(b[0:], item.key)
b = b[len(item.key):]
copy(b[0:], item.value)
b = b[len(item.value):]
}
}
// split divides up the node into appropriately sized nodes.
func (n *node) split(pageSize int) []*node {
// Ignore the split if the page doesn't have at least enough nodes for
// multiple pages or if the data can fit on a single page.
if len(n.inodes) <= (minKeysPerPage*2) || n.size() < pageSize {
return []*node{n}
}
// Set fill threshold to 50%.
threshold := pageSize / 2
// Group into smaller pages and target a given fill size.
size := 0
current := &node{isLeaf: n.isLeaf}
nodes := make([]*node, 0)
for i, inode := range n.inodes {
elemSize := n.pageElementSize() + len(inode.key) + len(inode.value)
if len(current.inodes) >= minKeysPerPage && i < len(n.inodes)-minKeysPerPage && size+elemSize > threshold {
size = pageHeaderSize
nodes = append(nodes, current)
current = &node{isLeaf: n.isLeaf}
}
size += elemSize
current.inodes = append(current.inodes, inode)
}
nodes = append(nodes, current)
return nodes
}
// nodesByDepth sorts a list of branches by deepest first.
type nodesByDepth []*node
func (s nodesByDepth) Len() int { return len(s) }
func (s nodesByDepth) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func (s nodesByDepth) Less(i, j int) bool { return s[i].depth > s[j].depth }
// inode represents an internal node inside of a node.
// It can be used to point to elements in a page or point
// to an element which hasn't been added to a page yet.
type inode struct {
pgid pgid
key []byte
value []byte
}
type inodes []inode
func (s inodes) Len() int { return len(s) }
func (s inodes) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func (s inodes) Less(i, j int) bool { return bytes.Compare(s[i].key, s[j].key) == -1 }
|
