Optimize large append.

This commit fixes an issue where large nodes would take up most of
the insert time because the entire node size would be calculated to
check if it could fit in a page or not. This changes the behavior
so that a node's size is only calculated up to the size it needs to
check and then returns.

1 files changed, 21 insertions, 8 deletions

diff --git a/node.go b/node.go
index a2c31fb..242e423 100644
--- a/node.go
+++ b/node.go
@@ -37,13 +37,27 @@ func (n *node) minKeys() int {
 
 // size returns the size of the node after serialization.
 func (n *node) size() int {
-	var elementSize = n.pageElementSize()
+	sz, elsz := pageHeaderSize, n.pageElementSize()
+	for i := 0; i < len(n.inodes); i++ {
+		item := &n.inodes[i]
+		sz += elsz + len(item.key) + len(item.value)
+	}
+	return sz
+}
 
-	var size = pageHeaderSize
-	for _, item := range n.inodes {
-		size += elementSize + len(item.key) + len(item.value)
+// sizeLessThan returns true if the node is less than a given size.
+// This is an optimization to avoid calculating a large node when we only need
+// to know if it fits inside a certain page size.
+func (n *node) sizeLessThan(v int) bool {
+	sz, elsz := pageHeaderSize, n.pageElementSize()
+	for i := 0; i < len(n.inodes); i++ {
+		item := &n.inodes[i]
+		sz += elsz + len(item.key) + len(item.value)
+		if sz >= v {
+			return false
+		}
 	}
-	return size
+	return true
 }
 
 // pageElementSize returns the size of each page element based on the type of node.
@@ -233,9 +247,8 @@ func (n *node) split(pageSize int) []*node {
 // 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 {
+	// two pages or if the nodes can fit in a single page.
+	if len(n.inodes) <= (minKeysPerPage*2) || n.sizeLessThan(pageSize) {
 		return n, nil
 	}