diff options
| -rw-r--r-- | TODO | 1 | ||||
| -rw-r--r-- | bnode.go | 3 | ||||
| -rw-r--r-- | branch.go | 64 | ||||
| -rw-r--r-- | branch_test.go | 113 | ||||
| -rw-r--r-- | leaf.go | 25 | ||||
| -rw-r--r-- | leaf_test.go | 22 |
6 files changed, 202 insertions, 26 deletions
@@ -4,7 +4,6 @@ X Open DB. X Initialize transaction. - Cursor First, Goto(key), Next - RWTransaction.insert() - - page split - rebalance - adjust cursors - RWTransaction Commmit @@ -15,5 +15,6 @@ type bnode struct { // key returns a byte slice of the node key. func (n *bnode) key() []byte { - return (*[MaxKeySize]byte)(unsafe.Pointer(&n))[n.pos : n.pos+n.ksize] + buf := (*[maxAllocSize]byte)(unsafe.Pointer(n)) + return buf[n.pos : n.pos+n.ksize] } @@ -11,6 +11,15 @@ type branch struct { items branchItems } +// size returns the size of the branch after serialization. +func (b *branch) size() int { + var size int = pageHeaderSize + for _, item := range b.items { + size += bnodeSize + len(item.key) + } + return size +} + // put adds a new node or replaces an existing node. func (b *branch) put(id pgid, newid pgid, key []byte, replace bool) { var index int @@ -40,10 +49,65 @@ func (b *branch) read(page *page) { for i := 0; i < ncount; i++ { bnode := &bnodes[i] item := &b.items[i] + item.pgid = bnode.pgid item.key = bnode.key() } } +// write writes the items onto a branch page. +func (b *branch) write(p *page) { + // Initialize page. + p.flags |= p_branch + p.count = uint16(len(b.items)) + + // Loop over each item and write it to the page. + bnodes := (*[maxNodesPerPage]bnode)(unsafe.Pointer(&p.ptr)) + buf := (*[maxAllocSize]byte)(unsafe.Pointer(&p.ptr))[lnodeSize*len(b.items):] + for index, item := range b.items { + // Write node. + bnode := &bnodes[index] + bnode.pgid = item.pgid + bnode.pos = uint32(uintptr(unsafe.Pointer(&buf[0])) - uintptr(unsafe.Pointer(bnode))) + bnode.ksize = uint32(len(item.key)) + + // Write key to the end of the page. + copy(buf[0:], item.key) + buf = buf[len(item.key):] + } +} + +// split divides up the noes in the branch into appropriately sized groups. +func (b *branch) split(pageSize int) []*branch { + // 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(b.items) <= (minKeysPerPage * 2) || b.size() < pageSize { + return []*branch{b} + } + + // Set fill threshold to 50%. + threshold := pageSize / 2 + + // Otherwise group into smaller pages and target a given fill size. + size := 0 + current := &branch{} + branches := make([]*branch, 0) + + for index, item := range b.items { + nodeSize := bnodeSize + len(item.key) + + if (len(current.items) >= minKeysPerPage && index < len(b.items)-minKeysPerPage && size+nodeSize > threshold) { + size = pageHeaderSize + branches = append(branches, current) + current = &branch{} + } + + size += nodeSize + current.items = append(current.items, item) + } + branches = append(branches, current) + + return branches +} type branchItems []branchItem diff --git a/branch_test.go b/branch_test.go index 0687b20..4a810c8 100644 --- a/branch_test.go +++ b/branch_test.go @@ -2,6 +2,7 @@ package bolt import ( "testing" + "unsafe" "github.com/stretchr/testify/assert" ) @@ -46,3 +47,115 @@ func TestBranchPutInsert(t *testing.T) { assert.Equal(t, b.items[3].pgid, pgid(5)) assert.Equal(t, string(b.items[3].key), "zzz") } + +// Ensure that a branch can deserialize from a page. +func TestBranchRead(t *testing.T) { + // Create a page. + var buf [4096]byte + page := (*page)(unsafe.Pointer(&buf[0])) + page.count = 2 + + // Insert 2 items at the beginning. sizeof(bnode) == 16 + nodes := (*[3]bnode)(unsafe.Pointer(&page.ptr)) + nodes[0] = bnode{pos: 32, ksize: 3, pgid: 100} // pos = sizeof(bnode) * 2 + nodes[1] = bnode{pos: 19, ksize: 10, pgid: 101} // pos = sizeof(bnode) + 3 + + // Write data for the nodes at the end. + data := (*[4096]byte)(unsafe.Pointer(&nodes[2])) + copy(data[:], []byte("bar")) + copy(data[3:], []byte("helloworld")) + + // Deserialize page into a branch. + b := &branch{} + b.read(page) + + // Check that there are two items with correct data. + assert.Equal(t, len(b.items), 2) + assert.Equal(t, b.items[0].key, []byte("bar")) + assert.Equal(t, b.items[1].key, []byte("helloworld")) +} + +// Ensure that a branch can serialize itself. +func TestBranchWrite(t *testing.T) { + b := &branch{ + items: branchItems{ + branchItem{pgid: 1, key: []byte("susy")}, + branchItem{pgid: 2, key: []byte("ricki")}, + branchItem{pgid: 3, key: []byte("john")}, + }, + } + + // Write it to a page. + var buf [4096]byte + p := (*page)(unsafe.Pointer(&buf[0])) + b.write(p) + + // Read the page back in. + b2 := &branch{} + b2.read(p) + + // Check that the two pages are the same. + assert.Equal(t, len(b2.items), 3) + assert.Equal(t, b2.items[0].pgid, pgid(1)) + assert.Equal(t, b2.items[0].key, []byte("susy")) + assert.Equal(t, b2.items[1].pgid, pgid(2)) + assert.Equal(t, b2.items[1].key, []byte("ricki")) + assert.Equal(t, b2.items[2].pgid, pgid(3)) + assert.Equal(t, b2.items[2].key, []byte("john")) +} + +// Ensure that a branch can split into appropriate subgroups. +func TestBranchSplit(t *testing.T) { + // Create a branch. + b := &branch{ + items: branchItems{ + branchItem{pgid: 1, key: []byte("00000001")}, + branchItem{pgid: 2, key: []byte("00000002")}, + branchItem{pgid: 3, key: []byte("00000003")}, + branchItem{pgid: 4, key: []byte("00000004")}, + branchItem{pgid: 5, key: []byte("00000005")}, + }, + } + + // Split between 3 & 4. + branches := b.split(100) + + assert.Equal(t, len(branches), 2) + assert.Equal(t, len(branches[0].items), 2) + assert.Equal(t, len(branches[1].items), 3) +} + +// Ensure that a branch with the minimum number of items just returns a single branch. +func TestBranchSplitWithMinKeys(t *testing.T) { + // Create a branch. + b := &branch{ + items: branchItems{ + branchItem{pgid: 1, key: []byte("00000001")}, + branchItem{pgid: 2, key: []byte("00000002")}, + }, + } + + // Split. + branches := b.split(20) + assert.Equal(t, len(branches), 1) + assert.Equal(t, len(branches[0].items), 2) +} + +// Ensure that a branch that has keys that all fit on a page just returns one branch. +func TestBranchSplitFitsInPage(t *testing.T) { + // Create a branch. + b := &branch{ + items: branchItems{ + branchItem{pgid: 1, key: []byte("00000001")}, + branchItem{pgid: 2, key: []byte("00000002")}, + branchItem{pgid: 3, key: []byte("00000003")}, + branchItem{pgid: 4, key: []byte("00000004")}, + branchItem{pgid: 5, key: []byte("00000005")}, + }, + } + + // Split. + branches := b.split(4096) + assert.Equal(t, len(branches), 1) + assert.Equal(t, len(branches[0].items), 5) +} @@ -6,13 +6,21 @@ import ( "unsafe" ) -// leaf represents a temporary in-memory leaf page. -// It is deserialized from an memory-mapped page and is not restricted by page size. +// leaf represents an in-memory, deserialized leaf page. type leaf struct { parent *branch items leafItems } +// size returns the size of the leaf after serialization. +func (l *leaf) size() int { + var size int = pageHeaderSize + for _, item := range l.items { + size += lnodeSize + len(item.key) + len(item.value) + } + return size +} + // put inserts or replaces a key on a leaf page. func (l *leaf) put(key []byte, value []byte) { // Find insertion index. @@ -29,15 +37,6 @@ func (l *leaf) put(key []byte, value []byte) { l.items[index].value = value } -// size returns the size of the leaf after serialization. -func (l *leaf) size() int { - var size int = pageHeaderSize - for _, item := range l.items { - size += lnodeSize + len(item.key) + len(item.value) - } - return size -} - // read initializes the item data from an on-disk page. func (l *leaf) read(p *page) { ncount := int(p.count) @@ -83,8 +82,8 @@ func (l *leaf) split(pageSize int) []*leaf { return []*leaf{l} } - // Set fill threshold to 25%. - threshold := pageSize >> 4 + // Set fill threshold to 50%. + threshold := pageSize / 2 // Otherwise group into smaller pages and target a given fill size. size := 0 diff --git a/leaf_test.go b/leaf_test.go index 3b2235f..ce98e37 100644 --- a/leaf_test.go +++ b/leaf_test.go @@ -7,7 +7,7 @@ import ( "github.com/stretchr/testify/assert" ) -// Ensure that a temporary page can insert a key/value. +// Ensure that a leaf can insert a key/value. func TestLeafPut(t *testing.T) { l := &leaf{items: make(leafItems, 0)} l.put([]byte("baz"), []byte("2")) @@ -20,7 +20,7 @@ func TestLeafPut(t *testing.T) { assert.Equal(t, l.items[2], leafItem{[]byte("foo"), []byte("3")}) } -// Ensure that a temporary page can deserialize from a page. +// Ensure that a leaf can deserialize from a page. func TestLeafRead(t *testing.T) { // Create a page. var buf [4096]byte @@ -37,7 +37,7 @@ func TestLeafRead(t *testing.T) { copy(data[:], []byte("barfooz")) copy(data[7:], []byte("helloworldbye")) - // Deserialize page into a temporary page. + // Deserialize page into a leaf. l := &leaf{} l.read(page) @@ -49,9 +49,9 @@ func TestLeafRead(t *testing.T) { assert.Equal(t, l.items[1].value, []byte("bye")) } -// Ensure that a temporary page can serialize itself. +// Ensure that a leaf can serialize itself. func TestLeafWrite(t *testing.T) { - // Create a temp page. + // Create a leaf. l := &leaf{items: make(leafItems, 0)} l.put([]byte("susy"), []byte("que")) l.put([]byte("ricki"), []byte("lake")) @@ -76,9 +76,9 @@ func TestLeafWrite(t *testing.T) { assert.Equal(t, l2.items[2].value, []byte("que")) } -// Ensure that a temporary page can split into appropriate subgroups. +// Ensure that a leaf can split into appropriate subgroups. func TestLeafSplit(t *testing.T) { - // Create a temp page. + // Create a leaf. l := &leaf{items: make(leafItems, 0)} l.put([]byte("00000001"), []byte("0123456701234567")) l.put([]byte("00000002"), []byte("0123456701234567")) @@ -94,9 +94,9 @@ func TestLeafSplit(t *testing.T) { assert.Equal(t, len(leafs[1].items), 3) } -// Ensure that a temporary page with the minimum number of items just returns a single split group. +// Ensure that a leaf with the minimum number of items just returns a single leaf. func TestLeafSplitWithMinKeys(t *testing.T) { - // Create a temp page. + // Create a leaf. l := &leaf{items: make(leafItems, 0)} l.put([]byte("00000001"), []byte("0123456701234567")) l.put([]byte("00000002"), []byte("0123456701234567")) @@ -107,9 +107,9 @@ func TestLeafSplitWithMinKeys(t *testing.T) { assert.Equal(t, len(leafs[0].items), 2) } -// Ensure that a temporary page that has keys that all fit on a page just returns one split group. +// Ensure that a leaf that has keys that all fit on a page just returns one leaf. func TestLeafSplitFitsInPage(t *testing.T) { - // Create a temp page. + // Create a leaf. l := &leaf{items: make(leafItems, 0)} l.put([]byte("00000001"), []byte("0123456701234567")) l.put([]byte("00000002"), []byte("0123456701234567")) |