From b1dbd35da1d7abea5e52b7aacdb7bed2812dd9db Mon Sep 17 00:00:00 2001
From: Ben Johnson <benbjohnson@yahoo.com>
Date: Wed, 18 Jun 2014 16:16:58 -0600
Subject: Fix merge-split regression.

This commit reverts merge-split and fixes the node.split() to do a multi-page split. This issue
caused problems with bulk loading because it would split into a small page and a very large page.
The very large page, in turn, would be an arbitrary size so when it was freed later it would be
difficult to reuse and would cause serious fragmentation issues.
---
 node.go | 49 ++++++++++++++++++++++++++++++++-----------------
 1 file changed, 32 insertions(+), 17 deletions(-)

(limited to 'node.go')

diff --git a/node.go b/node.go
index 1865ffe..a2c31fb 100644
--- a/node.go
+++ b/node.go
@@ -9,6 +9,7 @@ import (
 // node represents an in-memory, deserialized page.
 type node struct {
 	bucket     *Bucket
+	dirty      bool
 	isLeaf     bool
 	unbalanced bool
 	key        []byte
@@ -205,14 +206,37 @@ func (n *node) write(p *page) {
 	// DEBUG ONLY: n.dump()
 }
 
-// split breaks up a node into two smaller nodes, if appropriate.
+// split breaks up a node into multiple smaller nodes, if appropriate.
 // This should only be called from the spill() function.
 func (n *node) split(pageSize int) []*node {
+	var nodes []*node
+
+	node := n
+	for {
+		// Split node into two.
+		a, b := node.splitTwo(pageSize)
+		nodes = append(nodes, a)
+
+		// If we can't split then exit the loop.
+		if b == nil {
+			break
+		}
+
+		// Set node to b so it gets split on the next iteration.
+		node = b
+	}
+
+	return nodes
+}
+
+// splitTwo breaks up a node into two smaller nodes, if appropriate.
+// This should only be called from the split() function.
+func (n *node) splitTwo(pageSize int) (*node, *node) {
 	// Ignore the split if the page doesn't have at least enough nodes for
 	// two pages or if the data can fit on a single page.
 	sz := n.size()
 	if len(n.inodes) <= (minKeysPerPage*2) || sz < pageSize {
-		return []*node{n}
+		return n, nil
 	}
 
 	// Determine the threshold before starting a new node.
@@ -225,18 +249,10 @@ func (n *node) split(pageSize int) []*node {
 	threshold := int(float64(pageSize) * fillPercent)
 
 	// Determine split position and sizes of the two pages.
-	splitIndex, sz0 := n.splitIndex(threshold)
-	sz1 := pageHeaderSize + (sz - sz0)
-
-	// If we can fit our extra keys on the next page then merge into it.
-	if next := n.nextSibling(); next != nil && next.size()+sz1 < threshold {
-		next.inodes = append(n.inodes[splitIndex:], next.inodes...)
-		n.inodes = n.inodes[:splitIndex]
-		return []*node{n}
-	}
+	splitIndex, _ := n.splitIndex(threshold)
 
-	// Otherwise split node into two separate nodes. If there's no parent then
-	// we'll need to create one.
+	// Split node into two separate nodes.
+	// If there's no parent then we'll need to create one.
 	if n.parent == nil {
 		n.parent = &node{bucket: n.bucket, children: []*node{n}}
 	}
@@ -252,7 +268,7 @@ func (n *node) split(pageSize int) []*node {
 	// Update the statistics.
 	n.bucket.tx.stats.Split++
 
-	return []*node{n, next}
+	return n, next
 }
 
 // splitIndex finds the position where a page will fill a given threshold.
@@ -298,8 +314,7 @@ func (n *node) spill() error {
 	// We no longer need the child list because it's only used for spill tracking.
 	n.children = nil
 
-	// Spill nodes by deepest first. The first node returned from split() will
-	// always be "n".
+	// Split nodes into appropriate sizes. The first node will always be n.
 	var nodes = n.split(tx.db.pageSize)
 	for _, node := range nodes {
 		// Add node's page to the freelist if it's not new.
@@ -328,7 +343,7 @@ func (n *node) spill() error {
 
 			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")
+			_assert(len(node.key) > 0, "spill: zero-length node key")
 		}
 
 		// Update the statistics.
-- 
cgit v1.2.3