diff --git a/.github/workflows/go.yml b/.github/workflows/go.yml
new file mode 100644
index 0000000..411e2bd
--- /dev/null
+++ b/.github/workflows/go.yml
@@ -0,0 +1,36 @@
+name: Go
+
+on:
+  push:
+    branches: [ master ]
+  pull_request:
+    branches: [ master ]
+
+jobs:
+
+  build:
+    name: Build
+    runs-on: ubuntu-latest
+    steps:
+
+    - name: Set up Go 1.x
+      uses: actions/setup-go@v2
+      with:
+        go-version: ^1.15
+
+    - name: Check out code into the Go module directory
+      uses: actions/checkout@v2
+
+    - name: Get dependencies
+      run: |
+        go get -v -t -d ./...
+        if [ -f Gopkg.toml ]; then
+            curl https://raw.githubusercontent.com/golang/dep/master/install.sh | sh
+            dep ensure
+        fi
+
+    - name: Build
+      run: go build -v .
+
+    - name: Test
+      run: go test -v ./...
diff --git a/PATH_HINT.md b/PATH_HINT.md
new file mode 100644
index 0000000..4f243c4
--- /dev/null
+++ b/PATH_HINT.md
@@ -0,0 +1,45 @@
+# B-tree Path Hints
+
+I use a thing I call path hints in my B-tree [C](https://github.com/tidwall/btree.c) and [Go](https://github.com/tidwall/btree) implementations. It's a search optimization.
+
+## The B-tree
+
+A standard [B-tree](https://en.wikipedia.org/wiki/B-tree) is an ordered tree-based data structure that stores its items in nodes. The B-tree has a single root node, which may have children nodes, and those children nodes may also have children nodes. 
+
+<img width="322" alt="image" src="https://user-images.githubusercontent.com/1156077/127664015-14ca38bb-1a3b-4d2f-80ff-27be0bd3d886.png">
+
+Searching for items in a B-tree is fast. [O(log N)](https://en.wikipedia.org/wiki/Big_O_notation) to be exact.
+This is because the [binary search algorithm](https://en.wikipedia.org/wiki/Binary_search_algorithm) is used. 
+
+A binary search works by first comparing the item at the middle-most index of the root node with the target item. 
+If the middle item is greater than the target item, then it divides the node in two and does the binary search on the left part of the node. If the middle is less, it searches the right part. And so on. If the target item is found, then the search stop. If the item is not found, then the search is passed to the child node at the appropriate index. This traversal terminates when item is found or there are no more child nodes.
+
+<img width="600" alt="image" src="https://user-images.githubusercontent.com/1156077/127664822-6ab4f8f6-8ab5-477e-8e17-f52346f02819.png">
+
+## The Path
+
+Each index is a component of the path to the item (or where the item should be stored, if it does not exist in the tree).
+
+Take the first example image. The item 9 is at path “1/0”. The item 16 is at path “1”. The item 21 is at path “2/1”. The item 5 is at path “0/2”.
+
+## The Path Hint
+
+A Path Hint is a predefined path that is provided to B-tree operations. It’s just a hint that says, “Hey B-tree, instead of starting your binary search with the middle index, start with what I provide you. My path may be wrong, and if so please provide me with the correct path so I get it right the next time.”
+
+I’ve found using path hints can lead to a little performance increase of 150% - 300%. This is because in real-world cases the items that I’m working with are usually nearby each other in the tree.
+
+Take for example inserting a group of timeseries points. They may often be received as chucks of near-contiguous items.  
+Or, I'm sequentially inserting an ordered group of rows somewhere in the middle of a table.  
+Or, I have a Redis-style key/value store, where the keys look have the common structure “user:98512:name”, “user:98512:email”, and I want to update a bunch of values for specified user.  
+Using a path hint may help to avoid the unnecessary binary searching in each of these examples.
+
+While I may see a 3x boost in when the path hint is right on, I'll only see around 5% decrease when the path hint is totally wrong.
+
+## Using a Path Hint
+
+All of the functions that take in a path hint argument mutate the path hint argument.
+
+For single-threaded programs, it’s possible to use one shared path hint per B-tree for the life of the program.  
+For multi-threaded programs, I find it best to use one path hint per B-tree , per thread.  
+For server-client programs, one path hint per B-tree, per client should suffice.  
+
diff --git a/README.md b/README.md
index 0a3fa5d..7d00f5a 100644
--- a/README.md
+++ b/README.md
@@ -4,6 +4,15 @@
 
 An [efficient](#performance) [B-tree](https://en.wikipedia.org/wiki/B-tree) implementation in Go. 
 
+*Check out the [generics branch](https://github.com/tidwall/btree/tree/generics) if you want to try out btree with generic support for Go 1.18+*
+
+## Features
+
+- `Copy()` method with copy-on-write support.
+- Fast bulk loading for pre-ordered data using the `Load()` method.
+- All operations are thread-safe.
+- [Path hinting](PATH_HINT.md) optimization for operations with nearby keys.
+
 ## Installing
 
 To start using btree, install Go and run `go get`:
@@ -109,10 +118,10 @@ func main() {
 ### Basic
 
 ```
-Len()                   # return the number of items in the btree
-Set(item)               # insert or replace an existing item
 Get(item)               # get an existing item
+Set(item)               # insert or replace an existing item
 Delete(item)            # delete an item
+Len()                   # return the number of items in the btree
 ```
 
 ### Iteration
@@ -120,6 +129,7 @@ Delete(item)            # delete an item
 ```
 Ascend(pivot, iter)     # scan items in ascending order starting at pivot.
 Descend(pivot, iter)    # scan items in descending order starting at pivot.
+Iter()                  # returns a read-only iterator for for-loops.
 ```
 
 ### Queues
@@ -144,39 +154,48 @@ GetHint(item, *hint)    # get an existing item
 DeleteHint(item, *hint) # delete an item
 ```
 
+### Array-like operations
+
+```
+GetAt(index)     # returns the value at index
+DeleteAt(index)  # deletes the item at index
+```
+
 ## Performance
 
 This implementation was designed with performance in mind. 
 
-The following benchmarks were run on my 2019 Macbook Pro (2.4 GHz 8-Core Intel Core i9) using Go 1.15.3. The items are simple 8-byte ints. 
+The following benchmarks were run on my 2019 Macbook Pro (2.4 GHz 8-Core Intel Core i9) using Go 1.17.3. The items are simple 8-byte ints. 
 
-- `tidwall`: The [tidwall/btree](https://github.com/tidwall/btree) package
 - `google`: The [google/btree](https://github.com/google/btree) package
+- `tidwall`: The [tidwall/btree](https://github.com/tidwall/btree) package
 - `go-arr`: Just a simple Go array
 
 ```
 ** sequential set **
-tidwall: set-seq       1,000,000 ops in 143ms, 6,996,275/sec, 142 ns/op, 30.9 MB, 32 bytes/op
-tidwall: set-seq-hint  1,000,000 ops in 65ms, 15,441,082/sec, 64 ns/op, 30.9 MB, 32 bytes/op
-tidwall: load-seq      1,000,000 ops in 19ms, 53,242,398/sec, 18 ns/op, 30.9 MB, 32 bytes/op
-google:  set-seq       1,000,000 ops in 175ms, 5,700,922/sec, 175 ns/op, 33.1 MB, 34 bytes/op
-go-arr:  append        1,000,000 ops in 52ms, 19,153,714/sec, 52 ns/op, 41.3 MB, 43 bytes/op
+google:  set-seq        1,000,000 ops in 178ms, 5,618,049/sec, 177 ns/op, 39.0 MB, 40 bytes/op
+tidwall: set-seq        1,000,000 ops in 156ms, 6,389,837/sec, 156 ns/op, 23.5 MB, 24 bytes/op
+tidwall: set-seq-hint   1,000,000 ops in 78ms, 12,895,355/sec, 77 ns/op, 23.5 MB, 24 bytes/op
+tidwall: load-seq       1,000,000 ops in 53ms, 18,937,400/sec, 52 ns/op, 23.5 MB, 24 bytes/op
+go-arr:  append         1,000,000 ops in 78ms, 12,843,432/sec, 77 ns/op
 
 ** random set **
-tidwall: set-rand      1,000,000 ops in 589ms, 1,697,471/sec, 589 ns/op, 22.5 MB, 23 bytes/op
-tidwall: set-rand-hint 1,000,000 ops in 592ms, 1,688,184/sec, 592 ns/op, 22.2 MB, 23 bytes/op
-tidwall: load-rand     1,000,000 ops in 578ms, 1,728,932/sec, 578 ns/op, 22.3 MB, 23 bytes/op
-google:  set-rand      1,000,000 ops in 662ms, 1,509,924/sec, 662 ns/op, 32.1 MB, 33 bytes/op
+google:  set-rand       1,000,000 ops in 555ms, 1,803,133/sec, 554 ns/op, 29.7 MB, 31 bytes/op
+tidwall: set-rand       1,000,000 ops in 545ms, 1,835,818/sec, 544 ns/op, 29.6 MB, 31 bytes/op
+tidwall: set-rand-hint  1,000,000 ops in 670ms, 1,493,473/sec, 669 ns/op, 29.6 MB, 31 bytes/op
+tidwall: set-again      1,000,000 ops in 681ms, 1,469,038/sec, 680 ns/op
+tidwall: set-after-copy 1,000,000 ops in 670ms, 1,493,230/sec, 669 ns/op
+tidwall: load-rand      1,000,000 ops in 569ms, 1,756,187/sec, 569 ns/op, 29.6 MB, 31 bytes/op
 
 ** sequential get **
-tidwall: get-seq       1,000,000 ops in 111ms, 8,995,090/sec, 111 ns/op
-tidwall: get-seq-hint  1,000,000 ops in 56ms, 18,017,397/sec, 55 ns/op
-google:  get-seq       1,000,000 ops in 135ms, 7,414,046/sec, 134 ns/op
+google:  get-seq        1,000,000 ops in 165ms, 6,048,307/sec, 165 ns/op
+tidwall: get-seq        1,000,000 ops in 144ms, 6,940,120/sec, 144 ns/op
+tidwall: get-seq-hint   1,000,000 ops in 78ms, 12,815,243/sec, 78 ns/op
 
 ** random get **
-tidwall: get-rand      1,000,000 ops in 139ms, 7,214,017/sec, 138 ns/op
-tidwall: get-rand-hint 1,000,000 ops in 191ms, 5,243,833/sec, 190 ns/op
-google:  get-rand      1,000,000 ops in 161ms, 6,199,818/sec, 161 ns/op
+google:  get-rand       1,000,000 ops in 701ms, 1,427,507/sec, 700 ns/op
+tidwall: get-rand       1,000,000 ops in 679ms, 1,473,531/sec, 678 ns/op
+tidwall: get-rand-hint  1,000,000 ops in 824ms, 1,213,805/sec, 823 ns/op
 ```
 
 *You can find the benchmark utility at [tidwall/btree-benchmark](https://github.com/tidwall/btree-benchmark)*
diff --git a/btree.go b/btree.go
index 8689531..c8cdac2 100644
--- a/btree.go
+++ b/btree.go
@@ -1,214 +1,68 @@
 // Copyright 2020 Joshua J Baker. All rights reserved.
 // Use of this source code is governed by an MIT-style
 // license that can be found in the LICENSE file.
-
 package btree
 
-//tinygen:T interface{}
-
-const maxItems = 255
-const minItems = maxItems * 40 / 100
-
-type node struct {
-	leaf     bool
-	numItems int16
-	items    [maxItems]interface{}
-	children *[maxItems + 1]*node
-}
-
-type justaLeaf struct {
-	leaf     bool
-	numItems int16
-	items    [maxItems]interface{}
-}
+import btree "github.com/tidwall/btree/internal"
 
-// BTree is an ordered set items
 type BTree struct {
-	root   *node
-	length int
-	less   func(a, b interface{}) bool
-	lnode  *node
-}
-
-func newNode(leaf bool) *node {
-	n := &node{leaf: leaf}
-	if !leaf {
-		n.children = new([maxItems + 1]*node)
-	}
-	return n
+	base *btree.BTree
 }
 
 // PathHint is a utility type used with the *Hint() functions. Hints provide
 // faster operations for clustered keys.
-type PathHint struct {
-	path [8]uint8
-}
+type PathHint = btree.PathHint
 
 // New returns a new BTree
 func New(less func(a, b interface{}) bool) *BTree {
 	if less == nil {
 		panic("nil less")
 	}
-	tr := new(BTree)
-	tr.less = less
-	return tr
+	return &BTree{
+		base: btree.NewOptions(btree.Options{
+			Context: less,
+		}),
+	}
 }
 
-// Less is a convenience function that performs a comparison of two items
-// using the same "less" function provided to New.
-func (tr *BTree) Less(a, b interface{}) bool {
-	return tr.less(a, b)
-}
-
-func (n *node) find(key interface{}, less func(a, b interface{}) bool,
-	hint *PathHint, depth int,
-) (index int16, found bool) {
-	low := int16(0)
-	high := n.numItems - 1
-	if hint != nil && depth < 8 {
-		index = int16(hint.path[depth])
-		if index > n.numItems-1 {
-			index = n.numItems - 1
-		}
-		if less(key, n.items[index]) {
-			high = index - 1
-		} else if less(n.items[index], key) {
-			low = index + 1
-		} else {
-			found = true
-			goto done
-		}
-	}
-	for low <= high {
-		mid := low + ((high+1)-low)/2
-		if !less(key, n.items[mid]) {
-			low = mid + 1
-		} else {
-			high = mid - 1
-		}
-	}
-	if low > 0 && !less(n.items[low-1], key) &&
-		!less(key, n.items[low-1]) {
-		index = low - 1
-		found = true
-	} else {
-		index = low
-		found = false
+// NewNonConcurrent returns a new BTree which is not safe for concurrent
+// write operations by multiple goroutines.
+//
+// This is useful for when you do not need the BTree to manage the locking,
+// but would rather do it yourself.
+func NewNonConcurrent(less func(a, b interface{}) bool) *BTree {
+	if less == nil {
+		panic("nil less")
 	}
-done:
-	if hint != nil && depth < 8 {
-		if n.leaf && found {
-			hint.path[depth] = byte(index + 1)
-		} else {
-			hint.path[depth] = byte(index)
-		}
+	return &BTree{
+		base: btree.NewOptions(btree.Options{
+			Context: less,
+			NoLocks: true,
+		}),
 	}
-	return index, found
 }
 
-// SetHint sets or replace a value for a key using a path hint
-func (tr *BTree) SetHint(item interface{}, hint *PathHint) (prev interface{}) {
-	if item == nil {
-		panic("nil item")
-	}
-	if tr.root == nil {
-		tr.root = newNode(true)
-		tr.root.items[0] = item
-		tr.root.numItems = 1
-		tr.length = 1
-		return
-	}
-	prev = tr.root.set(item, tr.less, hint, 0)
-	if prev != nil {
-		return prev
-	}
-	tr.lnode = nil
-	if tr.root.numItems == maxItems {
-		n := tr.root
-		right, median := n.split()
-		tr.root = newNode(false)
-		tr.root.children[0] = n
-		tr.root.items[0] = median
-		tr.root.children[1] = right
-		tr.root.numItems = 1
-	}
-	tr.length++
-	return prev
+// Less is a convenience function that performs a comparison of two items
+// using the same "less" function provided to New.
+func (tr *BTree) Less(a, b interface{}) bool {
+	return tr.base.Less(a, b)
 }
 
 // Set or replace a value for a key
-func (tr *BTree) Set(item interface{}) (prev interface{}) {
+func (tr *BTree) Set(item interface{}) interface{} {
 	return tr.SetHint(item, nil)
 }
 
-func (n *node) split() (right *node, median interface{}) {
-	right = newNode(n.leaf)
-	median = n.items[maxItems/2]
-	copy(right.items[:maxItems/2], n.items[maxItems/2+1:])
-	if !n.leaf {
-		copy(right.children[:maxItems/2+1], n.children[maxItems/2+1:])
-	}
-	right.numItems = maxItems / 2
-	if !n.leaf {
-		for i := maxItems/2 + 1; i < maxItems+1; i++ {
-			n.children[i] = nil
-		}
-	}
-	for i := maxItems / 2; i < maxItems; i++ {
-		n.items[i] = nil
-	}
-	n.numItems = maxItems / 2
-	return right, median
-}
-
-func (n *node) set(item interface{}, less func(a, b interface{}) bool,
-	hint *PathHint, depth int,
-) (prev interface{}) {
-	i, found := n.find(item, less, hint, depth)
-	if found {
-		prev = n.items[i]
-		n.items[i] = item
-		return prev
+// SetHint sets or replace a value for a key using a path hint
+func (tr *BTree) SetHint(item interface{}, hint *PathHint) (prev interface{}) {
+	if item == nil {
+		panic("nil item")
 	}
-	if n.leaf {
-		copy(n.items[i+1:n.numItems+1], n.items[i:n.numItems])
-		n.items[i] = item
-		n.numItems++
+	v, ok := tr.base.SetHint(item, hint)
+	if !ok {
 		return nil
 	}
-	prev = n.children[i].set(item, less, hint, depth+1)
-	if prev != nil {
-		return prev
-	}
-	if n.children[i].numItems == maxItems {
-		right, median := n.children[i].split()
-		copy(n.children[i+1:], n.children[i:])
-		copy(n.items[i+1:], n.items[i:])
-		n.items[i] = median
-		n.children[i+1] = right
-		n.numItems++
-	}
-	return prev
-}
-
-func (n *node) scan(iter func(item interface{}) bool) bool {
-	if n.leaf {
-		for i := int16(0); i < n.numItems; i++ {
-			if !iter(n.items[i]) {
-				return false
-			}
-		}
-		return true
-	}
-	for i := int16(0); i < n.numItems; i++ {
-		if !n.children[i].scan(iter) {
-			return false
-		}
-		if !iter(n.items[i]) {
-			return false
-		}
-	}
-	return n.children[n.numItems].scan(iter)
+	return v
 }
 
 // Get a value for key
@@ -218,27 +72,19 @@ func (tr *BTree) Get(key interface{}) interface{} {
 
 // GetHint gets a value for key using a path hint
 func (tr *BTree) GetHint(key interface{}, hint *PathHint) interface{} {
-	if tr.root == nil || key == nil {
+	if key == nil {
 		return nil
 	}
-	depth := 0
-	n := tr.root
-	for {
-		i, found := n.find(key, tr.less, hint, depth)
-		if found {
-			return n.items[i]
-		}
-		if n.leaf {
-			return nil
-		}
-		n = n.children[i]
-		depth++
+	v, ok := tr.base.GetHint(key, hint)
+	if !ok {
+		return nil
 	}
+	return v
 }
 
 // Len returns the number of items in the tree
 func (tr *BTree) Len() int {
-	return tr.length
+	return tr.base.Len()
 }
 
 // Delete a value for a key
@@ -248,220 +94,36 @@ func (tr *BTree) Delete(key interface{}) interface{} {
 
 // DeleteHint deletes a value for a key using a path hint
 func (tr *BTree) DeleteHint(key interface{}, hint *PathHint) interface{} {
-	if tr.root == nil || key == nil {
+	if key == nil {
 		return nil
 	}
-	prev := tr.root.delete(false, key, tr.less, hint, 0)
-	if prev == nil {
+	v, ok := tr.base.DeleteHint(key, nil)
+	if !ok {
 		return nil
 	}
-	tr.lnode = nil
-	if tr.root.numItems == 0 && !tr.root.leaf {
-		tr.root = tr.root.children[0]
-	}
-	tr.length--
-	if tr.length == 0 {
-		tr.root = nil
-	}
-	return prev
-}
-
-func (n *node) delete(max bool, key interface{},
-	less func(a, b interface{}) bool, hint *PathHint, depth int,
-) interface{} {
-	var i int16
-	var found bool
-	if max {
-		i, found = n.numItems-1, true
-	} else {
-		i, found = n.find(key, less, hint, depth)
-	}
-	if n.leaf {
-		if found {
-			prev := n.items[i]
-			// found the items at the leaf, remove it and return.
-			copy(n.items[i:], n.items[i+1:n.numItems])
-			n.items[n.numItems-1] = nil
-			n.numItems--
-			return prev
-		}
-		return nil
-	}
-
-	var prev interface{}
-	if found {
-		if max {
-			i++
-			prev = n.children[i].delete(true, "", less, nil, 0)
-		} else {
-			prev = n.items[i]
-			maxItem := n.children[i].delete(true, "", less, nil, 0)
-			n.items[i] = maxItem
-		}
-	} else {
-		prev = n.children[i].delete(max, key, less, hint, depth+1)
-	}
-	if prev == nil {
-		return nil
-	}
-	if n.children[i].numItems < minItems {
-		if i == n.numItems {
-			i--
-		}
-		if n.children[i].numItems+n.children[i+1].numItems+1 < maxItems {
-			// merge left + item + right
-			n.children[i].items[n.children[i].numItems] = n.items[i]
-			copy(n.children[i].items[n.children[i].numItems+1:],
-				n.children[i+1].items[:n.children[i+1].numItems])
-			if !n.children[0].leaf {
-				copy(n.children[i].children[n.children[i].numItems+1:],
-					n.children[i+1].children[:n.children[i+1].numItems+1])
-			}
-			n.children[i].numItems += n.children[i+1].numItems + 1
-			copy(n.items[i:], n.items[i+1:n.numItems])
-			copy(n.children[i+1:], n.children[i+2:n.numItems+1])
-			n.items[n.numItems] = nil
-			n.children[n.numItems+1] = nil
-			n.numItems--
-		} else if n.children[i].numItems > n.children[i+1].numItems {
-			// move left -> right
-			copy(n.children[i+1].items[1:],
-				n.children[i+1].items[:n.children[i+1].numItems])
-			if !n.children[0].leaf {
-				copy(n.children[i+1].children[1:],
-					n.children[i+1].children[:n.children[i+1].numItems+1])
-			}
-			n.children[i+1].items[0] = n.items[i]
-			if !n.children[0].leaf {
-				n.children[i+1].children[0] =
-					n.children[i].children[n.children[i].numItems]
-			}
-			n.children[i+1].numItems++
-			n.items[i] = n.children[i].items[n.children[i].numItems-1]
-			n.children[i].items[n.children[i].numItems-1] = nil
-			if !n.children[0].leaf {
-				n.children[i].children[n.children[i].numItems] = nil
-			}
-			n.children[i].numItems--
-		} else {
-			// move right -> left
-			n.children[i].items[n.children[i].numItems] = n.items[i]
-			if !n.children[0].leaf {
-				n.children[i].children[n.children[i].numItems+1] =
-					n.children[i+1].children[0]
-			}
-			n.children[i].numItems++
-			n.items[i] = n.children[i+1].items[0]
-			copy(n.children[i+1].items[:],
-				n.children[i+1].items[1:n.children[i+1].numItems])
-			if !n.children[0].leaf {
-				copy(n.children[i+1].children[:],
-					n.children[i+1].children[1:n.children[i+1].numItems+1])
-			}
-			n.children[i+1].numItems--
-		}
-	}
-	return prev
+	return v
 }
 
 // Ascend the tree within the range [pivot, last]
 // Pass nil for pivot to scan all item in ascending order
 // Return false to stop iterating
 func (tr *BTree) Ascend(pivot interface{}, iter func(item interface{}) bool) {
-	if tr.root == nil {
-		return
-	}
 	if pivot == nil {
-		tr.root.scan(iter)
-	} else if tr.root != nil {
-		tr.root.ascend(pivot, tr.less, nil, 0, iter)
-	}
-}
-
-func (n *node) ascend(pivot interface{}, less func(a, b interface{}) bool,
-	hint *PathHint, depth int, iter func(item interface{}) bool,
-) bool {
-	i, found := n.find(pivot, less, hint, depth)
-	if !found {
-		if !n.leaf {
-			if !n.children[i].ascend(pivot, less, hint, depth+1, iter) {
-				return false
-			}
-		}
-	}
-	for ; i < n.numItems; i++ {
-		if !iter(n.items[i]) {
-			return false
-		}
-		if !n.leaf {
-			if !n.children[i+1].scan(iter) {
-				return false
-			}
-		}
-	}
-	return true
-}
-
-func (n *node) reverse(iter func(item interface{}) bool) bool {
-	if n.leaf {
-		for i := n.numItems - 1; i >= 0; i-- {
-			if !iter(n.items[i]) {
-				return false
-			}
-		}
-		return true
-	}
-	if !n.children[n.numItems].reverse(iter) {
-		return false
-	}
-	for i := n.numItems - 1; i >= 0; i-- {
-		if !iter(n.items[i]) {
-			return false
-		}
-		if !n.children[i].reverse(iter) {
-			return false
-		}
+		tr.base.Scan(iter)
+	} else {
+		tr.base.Ascend(pivot, iter)
 	}
-	return true
 }
 
 // Descend the tree within the range [pivot, first]
 // Pass nil for pivot to scan all item in descending order
 // Return false to stop iterating
 func (tr *BTree) Descend(pivot interface{}, iter func(item interface{}) bool) {
-	if tr.root == nil {
-		return
-	}
 	if pivot == nil {
-		tr.root.reverse(iter)
-	} else if tr.root != nil {
-		tr.root.descend(pivot, tr.less, nil, 0, iter)
-	}
-}
-
-func (n *node) descend(pivot interface{}, less func(a, b interface{}) bool,
-	hint *PathHint, depth int, iter func(item interface{}) bool,
-) bool {
-	i, found := n.find(pivot, less, hint, depth)
-	if !found {
-		if !n.leaf {
-			if !n.children[i].descend(pivot, less, hint, depth+1, iter) {
-				return false
-			}
-		}
-		i--
-	}
-	for ; i >= 0; i-- {
-		if !iter(n.items[i]) {
-			return false
-		}
-		if !n.leaf {
-			if !n.children[i].reverse(iter) {
-				return false
-			}
-		}
+		tr.base.Reverse(iter)
+	} else {
+		tr.base.Descend(pivot, iter)
 	}
-	return true
 }
 
 // Load is for bulk loading pre-sorted items
@@ -469,139 +131,143 @@ func (tr *BTree) Load(item interface{}) interface{} {
 	if item == nil {
 		panic("nil item")
 	}
-	if tr.lnode != nil && tr.lnode.numItems < maxItems-2 {
-		if tr.less(tr.lnode.items[tr.lnode.numItems-1], item) {
-			tr.lnode.items[tr.lnode.numItems] = item
-			tr.lnode.numItems++
-			tr.length++
-			return nil
-		}
-	}
-	prev := tr.Set(item)
-	if prev != nil {
-		return prev
-	}
-	n := tr.root
-	for {
-		if n.leaf {
-			tr.lnode = n
-			break
-		}
-		n = n.children[n.numItems]
+	v, ok := tr.base.Load(item)
+	if !ok {
+		return nil
 	}
-	return nil
+	return v
 }
 
 // Min returns the minimum item in tree.
 // Returns nil if the tree has no items.
 func (tr *BTree) Min() interface{} {
-	if tr.root == nil {
+	v, ok := tr.base.Min()
+	if !ok {
 		return nil
 	}
-	n := tr.root
-	for {
-		if n.leaf {
-			return n.items[0]
-		}
-		n = n.children[0]
-	}
+	return v
 }
 
 // Max returns the maximum item in tree.
 // Returns nil if the tree has no items.
 func (tr *BTree) Max() interface{} {
-	if tr.root == nil {
+	v, ok := tr.base.Max()
+	if !ok {
 		return nil
 	}
-	n := tr.root
-	for {
-		if n.leaf {
-			return n.items[n.numItems-1]
-		}
-		n = n.children[n.numItems]
-	}
+	return v
 }
 
 // PopMin removes the minimum item in tree and returns it.
 // Returns nil if the tree has no items.
 func (tr *BTree) PopMin() interface{} {
-	if tr.root == nil {
+	v, ok := tr.base.PopMin()
+	if !ok {
 		return nil
 	}
-	tr.lnode = nil
-	n := tr.root
-	for {
-		if n.leaf {
-			item := n.items[0]
-			if n.numItems == minItems {
-				return tr.Delete(item)
-			}
-			copy(n.items[:], n.items[1:])
-			n.items[n.numItems-1] = nil
-			n.numItems--
-			tr.length--
-			return item
-		}
-		n = n.children[0]
-	}
+	return v
 }
 
 // PopMax removes the minimum item in tree and returns it.
 // Returns nil if the tree has no items.
 func (tr *BTree) PopMax() interface{} {
-	if tr.root == nil {
+	v, ok := tr.base.PopMax()
+	if !ok {
+		return nil
+	}
+	return v
+}
+
+// GetAt returns the value at index.
+// Return nil if the tree is empty or the index is out of bounds.
+func (tr *BTree) GetAt(index int) interface{} {
+	v, ok := tr.base.GetAt(index)
+	if !ok {
 		return nil
 	}
-	tr.lnode = nil
-	n := tr.root
-	for {
-		if n.leaf {
-			item := n.items[n.numItems-1]
-			if n.numItems == minItems {
-				return tr.Delete(item)
-			}
-			n.items[n.numItems-1] = nil
-			n.numItems--
-			tr.length--
-			return item
-		}
-		n = n.children[n.numItems]
+	return v
+}
+
+// DeleteAt deletes the item at index.
+// Return nil if the tree is empty or the index is out of bounds.
+func (tr *BTree) DeleteAt(index int) interface{} {
+	v, ok := tr.base.DeleteAt(index)
+	if !ok {
+		return nil
 	}
+	return v
 }
 
 // Height returns the height of the tree.
 // Returns zero if tree has no items.
 func (tr *BTree) Height() int {
-	var height int
-	if tr.root != nil {
-		n := tr.root
-		for {
-			height++
-			if n.leaf {
-				break
-			}
-			n = n.children[n.numItems]
-		}
-	}
-	return height
+	return tr.base.Height()
 }
 
 // Walk iterates over all items in tree, in order.
 // The items param will contain one or more items.
-func (tr *BTree) Walk(iter func(item []interface{})) {
-	if tr.root != nil {
-		tr.root.walk(iter)
-	}
+func (tr *BTree) Walk(iter func(items []interface{})) {
+	tr.base.Walk(func(items []interface{}) bool {
+		iter(items)
+		return true
+	})
 }
 
-func (n *node) walk(iter func(item []interface{})) {
-	if n.leaf {
-		iter(n.items[:n.numItems])
-	} else {
-		for i := int16(0); i < n.numItems; i++ {
-			n.children[i].walk(iter)
-			iter(n.items[i : i+1])
-		}
-		n.children[n.numItems].walk(iter)
-	}
+// Copy the tree. This is a copy-on-write operation and is very fast because
+// it only performs a shadowed copy.
+func (tr *BTree) Copy() *BTree {
+	return &BTree{base: tr.base.Copy()}
+}
+
+type Iter struct {
+	base btree.Iter
+}
+
+// Iter returns a read-only iterator.
+// The Release method must be called finished with iterator.
+func (tr *BTree) Iter() Iter {
+	return Iter{tr.base.Iter()}
+}
+
+// Seek to item greater-or-equal-to key.
+// Returns false if there was no item found.
+func (iter *Iter) Seek(key interface{}) bool {
+	return iter.base.Seek(key)
+}
+
+// First moves iterator to first item in tree.
+// Returns false if the tree is empty.
+func (iter *Iter) First() bool {
+	return iter.base.First()
+}
+
+// Last moves iterator to last item in tree.
+// Returns false if the tree is empty.
+func (iter *Iter) Last() bool {
+	return iter.base.Last()
+}
+
+// First moves iterator to first item in tree.
+// Returns false if the tree is empty.
+func (iter *Iter) Release() {
+	iter.base.Release()
+}
+
+// Next moves iterator to the next item in iterator.
+// Returns false if the tree is empty or the iterator is at the end of
+// the tree.
+func (iter *Iter) Next() bool {
+	return iter.base.Next()
+}
+
+// Prev moves iterator to the previous item in iterator.
+// Returns false if the tree is empty or the iterator is at the beginning of
+// the tree.
+func (iter *Iter) Prev() bool {
+	return iter.base.Prev()
+}
+
+// Item returns the current iterator item.
+func (iter *Iter) Item() interface{} {
+	return iter.base.Item()
 }
diff --git a/btree_test.go b/btree_test.go
index 1be7171..04435cf 100644
--- a/btree_test.go
+++ b/btree_test.go
@@ -1,561 +1,28 @@
-// Copyright 2020 Joshua J Baker. All rights reserved.
-// Use of this source code is governed by an MIT-style
-// license that can be found in the LICENSE file.
-
 package btree
 
-// SEED=1603717878394178000 go test -run Random
-
 import (
 	"fmt"
 	"math/rand"
 	"os"
-	"sort"
 	"strconv"
-	"strings"
+	"sync"
 	"testing"
 	"time"
 )
 
-var seed int64
-
 func init() {
-	var err error
-	seed, err = strconv.ParseInt(os.Getenv("SEED"), 10, 64)
+	seed, err := strconv.ParseInt(os.Getenv("SEED"), 10, 64)
 	if err != nil {
 		seed = time.Now().UnixNano()
 	}
+	// seed = 1637859071499249000
 	fmt.Printf("seed: %d\n", seed)
 	rand.Seed(seed)
 }
 
-func randKeys(N int) (keys []string) {
-	format := fmt.Sprintf("%%0%dd", len(fmt.Sprintf("%d", N-1)))
-	for _, i := range rand.Perm(N) {
-		keys = append(keys, fmt.Sprintf(format, i))
-	}
-	return
-}
-
-const flatLeaf = true
-
-func (tr *BTree) print() {
-	tr.root.print(0, tr.Height())
-}
-
-func (n *node) print(level, height int) {
-	if n == nil {
-		println("NIL")
-		return
-	}
-	if height == 0 && flatLeaf {
-		fmt.Printf("%v", strings.Repeat("  ", level))
-	}
-	for i := int16(0); i < n.numItems; i++ {
-		if height > 0 {
-			n.children[i].print(level+1, height-1)
-		}
-		if height > 0 || (height == 0 && !flatLeaf) {
-			fmt.Printf("%v%v\n", strings.Repeat("  ", level), n.items[i])
-		} else {
-			if i > 0 {
-				fmt.Printf(",")
-			}
-			fmt.Printf("%v", n.items[i])
-		}
-	}
-	if height == 0 && flatLeaf {
-		fmt.Printf("\n")
-	}
-	if height > 0 {
-		n.children[n.numItems].print(level+1, height-1)
-	}
-}
-
-func (tr *BTree) deepPrint() {
-	fmt.Printf("%#v\n", tr)
-	tr.root.deepPrint(0)
-}
-
-func (n *node) deepPrint(level int) {
-	if n == nil {
-		fmt.Printf("%v %#v\n", strings.Repeat("  ", level), n)
-		return
-	}
-	fmt.Printf("%v count: %v\n", strings.Repeat("  ", level), n.numItems)
-	fmt.Printf("%v items: %v\n", strings.Repeat("  ", level), n.items[:n.numItems])
-	if !n.leaf {
-		fmt.Printf("%v child: %v\n", strings.Repeat("  ", level), n.children)
-	}
-	if !n.leaf {
-		for i := int16(0); i < n.numItems; i++ {
-			n.children[i].deepPrint(level + 1)
-		}
-		n.children[n.numItems].deepPrint(level + 1)
-	}
-}
-
-func stringsEquals(a, b []string) bool {
-	if len(a) != len(b) {
-		return false
-	}
-	for i := 0; i < len(a); i++ {
-		if a[i] != b[i] {
-			return false
-		}
-	}
-	return true
-}
-
-type pair struct {
-	key   string
-	value interface{}
-}
-
-func pairLess(a, b interface{}) bool {
-	return a.(pair).key < b.(pair).key
-}
-
-func TestDescend(t *testing.T) {
-	tr := New(pairLess)
-	var count int
-	tr.Descend(pair{"1", nil}, func(item interface{}) bool {
-		count++
-		return true
-	})
-	if count > 0 {
-		t.Fatalf("expected 0, got %v", count)
-	}
-	var keys []string
-	for i := 0; i < 1000; i += 10 {
-		keys = append(keys, fmt.Sprintf("%03d", i))
-		tr.Set(pair{keys[len(keys)-1], nil})
-	}
-	var exp []string
-	tr.Descend(nil, func(item interface{}) bool {
-		exp = append(exp, item.(pair).key)
-		return true
-	})
-	for i := 999; i >= 0; i-- {
-		var key string
-		key = fmt.Sprintf("%03d", i)
-		var all []string
-		tr.Descend(pair{key, nil}, func(item interface{}) bool {
-			all = append(all, item.(pair).key)
-			return true
-		})
-		for len(exp) > 0 && key < exp[0] {
-			exp = exp[1:]
-		}
-		var count int
-		tr.Descend(pair{key, nil}, func(item interface{}) bool {
-			if count == (i+1)%maxItems {
-				return false
-			}
-			count++
-			return true
-		})
-		if count > len(exp) {
-			t.Fatalf("expected 1, got %v", count)
-		}
-		if !stringsEquals(exp, all) {
-			fmt.Printf("exp: %v\n", exp)
-			fmt.Printf("all: %v\n", all)
-			t.Fatal("mismatch")
-		}
-	}
-}
-
-func TestAscend(t *testing.T) {
-	tr := New(pairLess)
-	var count int
-	tr.Ascend(pair{"1", nil}, func(item interface{}) bool {
-		count++
-		return true
-	})
-	if count > 0 {
-		t.Fatalf("expected 0, got %v", count)
-	}
-	var keys []string
-	for i := 0; i < 1000; i += 10 {
-		keys = append(keys, fmt.Sprintf("%03d", i))
-		tr.Set(pair{keys[len(keys)-1], nil})
-	}
-	exp := keys
-	for i := -1; i < 1000; i++ {
-		var key string
-		if i == -1 {
-			key = ""
-		} else {
-			key = fmt.Sprintf("%03d", i)
-		}
-		var all []string
-		tr.Ascend(pair{key, nil}, func(item interface{}) bool {
-			all = append(all, item.(pair).key)
-			return true
-		})
-
-		for len(exp) > 0 && key > exp[0] {
-			exp = exp[1:]
-		}
-		var count int
-		tr.Ascend(pair{key, nil}, func(item interface{}) bool {
-			if count == (i+1)%maxItems {
-				return false
-			}
-			count++
-			return true
-		})
-		if count > len(exp) {
-			t.Fatalf("expected 1, got %v", count)
-		}
-		if !stringsEquals(exp, all) {
-			t.Fatal("mismatch")
-		}
-	}
-}
-
-func TestBTree(t *testing.T) {
-
-	N := 10000
-	tr := New(pairLess)
-	tr.sane()
-	keys := randKeys(N)
-
-	// insert all items
-	for _, key := range keys {
-		item := tr.Set(pair{key, key})
-		tr.sane()
-		if item != nil {
-			t.Fatal("expected nil")
-		}
-	}
-
-	// check length
-	if tr.Len() != len(keys) {
-		t.Fatalf("expected %v, got %v", len(keys), tr.Len())
-	}
-
-	// get each value
-	for _, key := range keys {
-		item := tr.Get(pair{key, nil})
-		if item == nil || item.(pair).value != key {
-			t.Fatalf("expected '%v', got '%v'", key, item.(pair).value)
-		}
-	}
-
-	// scan all items
-	var last string
-	all := make(map[string]interface{})
-	tr.Ascend(nil, func(item interface{}) bool {
-		key := item.(pair).key
-		value := item.(pair).value
-		if key <= last {
-			t.Fatal("out of order")
-		}
-		if value.(string) != key {
-			t.Fatalf("mismatch")
-		}
-		last = key
-		all[key] = value
-		return true
-	})
-	if len(all) != len(keys) {
-		t.Fatalf("expected '%v', got '%v'", len(keys), len(all))
-	}
-
-	// reverse all items
-	var prev string
-	all = make(map[string]interface{})
-	tr.Descend(nil, func(item interface{}) bool {
-		key := item.(pair).key
-		value := item.(pair).value
-		if prev != "" && key >= prev {
-			t.Fatal("out of order")
-		}
-		if value.(string) != key {
-			t.Fatalf("mismatch")
-		}
-		prev = key
-		all[key] = value
-		return true
-	})
-	if len(all) != len(keys) {
-		t.Fatalf("expected '%v', got '%v'", len(keys), len(all))
-	}
-
-	// try to get an invalid item
-	item := tr.Get(pair{"invalid", nil})
-	if item != nil {
-		t.Fatal("expected nil")
-	}
-
-	// scan and quit at various steps
-	for i := 0; i < 100; i++ {
-		var j int
-		tr.Ascend(nil, func(item interface{}) bool {
-			if j == i {
-				return false
-			}
-			j++
-			return true
-		})
-	}
-
-	// reverse and quit at various steps
-	for i := 0; i < 100; i++ {
-		var j int
-		tr.Descend(nil, func(item interface{}) bool {
-			if j == i {
-				return false
-			}
-			j++
-			return true
-		})
-	}
-
-	// delete half the items
-	for _, key := range keys[:len(keys)/2] {
-		item := tr.Delete(pair{key, nil})
-		if item == nil {
-			t.Fatal("expected true")
-		}
-		value := item.(pair).value
-		if value == nil || value.(string) != key {
-			t.Fatalf("expected '%v', got '%v'", key, value)
-		}
-	}
-
-	// check length
-	if tr.Len() != len(keys)/2 {
-		t.Fatalf("expected %v, got %v", len(keys)/2, tr.Len())
-	}
-
-	// try delete half again
-	for _, key := range keys[:len(keys)/2] {
-		item := tr.Delete(pair{key, nil})
-		tr.sane()
-		if item != nil {
-			t.Fatal("expected false")
-		}
-	}
-
-	// try delete half again
-	for _, key := range keys[:len(keys)/2] {
-		item := tr.Delete(pair{key, nil})
-		tr.sane()
-		if item != nil {
-			t.Fatal("expected false")
-		}
-	}
-
-	// check length
-	if tr.Len() != len(keys)/2 {
-		t.Fatalf("expected %v, got %v", len(keys)/2, tr.Len())
-	}
-
-	// scan items
-	last = ""
-	all = make(map[string]interface{})
-	tr.Ascend(nil, func(item interface{}) bool {
-		key := item.(pair).key
-		value := item.(pair).value
-		if key <= last {
-			t.Fatal("out of order")
-		}
-		if value.(string) != key {
-			t.Fatalf("mismatch")
-		}
-		last = key
-		all[key] = value
-		return true
-	})
-	if len(all) != len(keys)/2 {
-		t.Fatalf("expected '%v', got '%v'", len(keys), len(all))
-	}
-
-	// replace second half
-	for _, key := range keys[len(keys)/2:] {
-		item := tr.Set(pair{key, key})
-		tr.sane()
-		if item == nil {
-			t.Fatal("expected not nil")
-		}
-		value := item.(pair).value
-		if value == nil || value.(string) != key {
-			t.Fatalf("expected '%v', got '%v'", key, value)
-		}
-	}
-
-	// delete next half the items
-	for _, key := range keys[len(keys)/2:] {
-		item := tr.Delete(pair{key, nil})
-		tr.sane()
-		if item == nil {
-			t.Fatal("expected not nil")
-		}
-		value := item.(pair).value
-		if value == nil || value.(string) != key {
-			t.Fatalf("expected '%v', got '%v'", key, value)
-		}
-	}
-
-	// check length
-	if tr.Len() != 0 {
-		t.Fatalf("expected %v, got %v", 0, tr.Len())
-	}
-
-	// do some stuff on an empty tree
-	item = tr.Get(pair{keys[0], nil})
-	if item != nil {
-		t.Fatal("expected nil")
-	}
-	tr.Ascend(nil, func(item interface{}) bool {
-		t.Fatal("should not be reached")
-		return true
-	})
-	tr.Descend(nil, func(item interface{}) bool {
-		t.Fatal("should not be reached")
-		return true
-	})
-
-	item = tr.Delete(pair{"invalid", nil})
-	tr.sane()
-	if item != nil {
-		t.Fatal("expected nil")
-	}
-}
-
-func BenchmarkTidwallSequentialSet(b *testing.B) {
-	tr := New(intLess)
-	keys := rand.Perm(b.N)
-	sort.Ints(keys)
-	b.ResetTimer()
-	for i := 0; i < b.N; i++ {
-		tr.Set(keys[i])
-	}
-}
-
-func BenchmarkTidwallSequentialGet(b *testing.B) {
-	tr := New(intLess)
-	keys := rand.Perm(b.N)
-	sort.Ints(keys)
-	for i := 0; i < b.N; i++ {
-		tr.Set(keys[i])
-	}
-	b.ResetTimer()
-	for i := 0; i < b.N; i++ {
-		tr.Get(keys[i])
-	}
-}
-
-func BenchmarkTidwallRandomSet(b *testing.B) {
-	tr := New(intLess)
-	keys := rand.Perm(b.N)
-	b.ResetTimer()
-	for i := 0; i < b.N; i++ {
-		tr.Set(keys[i])
-	}
-}
-
-func BenchmarkTidwallRandomGet(b *testing.B) {
-	tr := New(intLess)
-	keys := rand.Perm(b.N)
-	for i := 0; i < b.N; i++ {
-		tr.Set(keys[i])
-	}
-	b.ResetTimer()
-	for i := 0; i < b.N; i++ {
-		tr.Get(keys[i])
-	}
-}
-
-func BenchmarkTidwallSequentialSetHint(b *testing.B) {
-	tr := New(intLess)
-	keys := rand.Perm(b.N)
-	sort.Ints(keys)
-	b.ResetTimer()
-	var hint PathHint
-	for i := 0; i < b.N; i++ {
-		tr.SetHint(keys[i], &hint)
-	}
-}
-
-func BenchmarkTidwallSequentialGetHint(b *testing.B) {
-	// println("\n----------------------------------------------------------------")
-	tr := New(intLess)
-	keys := rand.Perm(b.N)
-	sort.Ints(keys)
-	for i := 0; i < b.N; i++ {
-		tr.Set(keys[i])
-	}
-	b.ResetTimer()
-	var hint PathHint
-	for i := 0; i < b.N; i++ {
-		tr.GetHint(keys[i], &hint)
-		// fmt.Printf("%064b\n", hint)
-	}
-}
-
-func BenchmarkTidwallLoad(b *testing.B) {
-	tr := New(intLess)
-	keys := rand.Perm(b.N)
-	sort.Ints(keys)
-	b.ResetTimer()
-	for i := 0; i < b.N; i++ {
-		tr.Load(keys[i])
-	}
-}
-
-func TestBTreeOne(t *testing.T) {
-	tr := New(pairLess)
-	tr.Set(pair{"1", "1"})
-	tr.Delete(pair{"1", nil})
-	tr.Set(pair{"1", "1"})
-	tr.Delete(pair{"1", nil})
-	tr.Set(pair{"1", "1"})
-	tr.Delete(pair{"1", nil})
-}
-
-func TestBTree256(t *testing.T) {
-	tr := New(pairLess)
-	var n int
-	for j := 0; j < 2; j++ {
-		for _, i := range rand.Perm(256) {
-			tr.Set(pair{fmt.Sprintf("%d", i), i})
-			n++
-			if tr.Len() != n {
-				t.Fatalf("expected 256, got %d", n)
-			}
-		}
-		for _, i := range rand.Perm(256) {
-			item := tr.Get(pair{fmt.Sprintf("%d", i), nil})
-			if item == nil {
-				t.Fatal("expected true")
-			}
-			if item.(pair).value.(int) != i {
-				t.Fatalf("expected %d, got %d", i, item.(pair).value.(int))
-			}
-		}
-		for _, i := range rand.Perm(256) {
-			tr.Delete(pair{fmt.Sprintf("%d", i), nil})
-			n--
-			if tr.Len() != n {
-				t.Fatalf("expected 256, got %d", n)
-			}
-		}
-		for _, i := range rand.Perm(256) {
-			item := tr.Get(pair{fmt.Sprintf("%d", i), nil})
-			if item != nil {
-				t.Fatal("expected nil")
-			}
-		}
-	}
-}
-func shuffle(r *rand.Rand, keys []int) {
-	for i := range keys {
-		j := r.Intn(i + 1)
-		keys[i], keys[j] = keys[j], keys[i]
+func assert(x bool) {
+	if !x {
+		panic("assert failed")
 	}
 }
 
@@ -563,449 +30,246 @@ func intLess(a, b interface{}) bool {
 	return a.(int) < b.(int)
 }
 
-func TestRandom(t *testing.T) {
-	r := rand.New(rand.NewSource(seed))
-	N := 200000
-	keys := rand.Perm(N)
+func TestBTree(t *testing.T) {
 	func() {
 		defer func() {
-			msg := fmt.Sprint(recover())
-			if msg != "nil less" {
-				t.Fatal("expected 'nil less' panic")
-			}
+			msg, ok := recover().(string)
+			assert(ok && msg == "nil less")
 		}()
 		New(nil)
-		t.Fatalf("reached invalid code")
 	}()
-	tr := New(intLess)
-	checkSane := func() {
-		// tr.sane()
-	}
-	checkSane()
-	if tr.Min() != nil {
-		t.Fatalf("expected nil")
-	}
-	if tr.Max() != nil {
-		t.Fatalf("expected nil")
-	}
-	if tr.PopMin() != nil {
-		t.Fatalf("expected nil")
-	}
-	if tr.PopMax() != nil {
-		t.Fatalf("expected nil")
-	}
-	if tr.Height() != 0 {
-		t.Fatalf("expected 0, got %d", tr.Height())
-	}
-	checkSane()
 	func() {
 		defer func() {
-			msg := fmt.Sprint(recover())
-			if msg != "nil item" {
-				t.Fatal("expected 'nil item' panic")
-			}
+			msg, ok := recover().(string)
+			assert(ok && msg == "nil less")
 		}()
-		tr.Set(nil)
-		t.Fatalf("reached invalid code")
+		NewNonConcurrent(nil)
 	}()
-	// keys = keys[:rand.Intn(len(keys))]
-	shuffle(r, keys)
-	for i := 0; i < len(keys); i++ {
-		prev := tr.Set(keys[i])
-		checkSane()
-		if prev != nil {
-			t.Fatalf("expected nil")
-		}
-		if i%12345 == 0 {
-			tr.sane()
+	N := 1_000_000
+	for j := 0; j < 2; j++ {
+		var tr *BTree
+		if j == 0 {
+			tr = New(intLess)
+		} else {
+			tr = NewNonConcurrent(intLess)
 		}
-	}
-	tr.sane()
-	sort.Ints(keys)
-	var n int
-	tr.Ascend(nil, func(item interface{}) bool {
-		n++
-		return false
-	})
-	if n != 1 {
-		t.Fatalf("expected 1, got %d", n)
-	}
-
-	n = 0
-	tr.Ascend(nil, func(item interface{}) bool {
-		if item != keys[n] {
-			t.Fatalf("expected %d, got %d", keys[n], item)
+		for i := 0; i < N; i++ {
+			assert(tr.Load(i) == nil)
 		}
-		n++
-		return true
-	})
-	if n != len(keys) {
-		t.Fatalf("expected %d, got %d", len(keys), n)
-	}
-	if tr.Len() != len(keys) {
-		t.Fatalf("expected %d, got %d", tr.Len(), len(keys))
-	}
-
-	n = 0
-	tr.Descend(nil, func(item interface{}) bool {
-		n++
-		return false
-	})
-	if n != 1 {
-		t.Fatalf("expected 1, got %d", n)
-	}
-	n = 0
-	tr.Descend(nil, func(item interface{}) bool {
-		if item != keys[len(keys)-n-1] {
-			t.Fatalf("expected %d, got %d", keys[len(keys)-n-1], item)
+		assert(tr.Len() == N)
+		for i := 0; i < N; i++ {
+			assert(tr.Get(i) == i)
 		}
-		n++
-		return true
-	})
-	if n != len(keys) {
-		t.Fatalf("expected %d, got %d", len(keys), n)
-	}
-	if tr.Len() != len(keys) {
-		t.Fatalf("expected %d, got %d", tr.Len(), len(keys))
-	}
-
-	checkSane()
 
-	// tr.deepPrint()
-
-	n = 0
-	for i := 0; i < 1000; i++ {
-		n := 0
-		tr.Ascend(nil, func(item interface{}) bool {
-			if n == i {
-				return false
-			}
-			n++
+		count := 0
+		tr.Ascend(nil, func(_ interface{}) bool {
+			count++
 			return true
 		})
-		if n != i {
-			t.Fatalf("expected %d, got %d", i, n)
-		}
-	}
-
-	n = 0
-	for i := 0; i < 1000; i++ {
-		n = 0
-		tr.Descend(nil, func(item interface{}) bool {
-			if n == i {
-				return false
-			}
-			n++
+		assert(count == N)
+		count = 0
+		tr.Ascend(N/2, func(_ interface{}) bool {
+			count++
 			return true
 		})
-		if n != i {
-			t.Fatalf("expected %d, got %d", i, n)
-		}
-	}
+		assert(count == N/2)
 
-	sort.Ints(keys)
-	for i := 0; i < len(keys); i++ {
-		var res interface{}
-		var j int
-		tr.Ascend(keys[i], func(item interface{}) bool {
-			if j == 0 {
-				res = item
-			}
-			j++
-			return j == i%500
+		count = 0
+		tr.Descend(nil, func(_ interface{}) bool {
+			count++
+			return true
 		})
-		if res != keys[i] {
-			t.Fatal("not equal")
-		}
-	}
-	for i := len(keys) - 1; i >= 0; i-- {
-		var res interface{}
-		var j int
-		tr.Descend(keys[i], func(item interface{}) bool {
-			if j == 0 {
-				res = item
-			}
-			j++
-			return j == i%500
+		assert(count == N)
+		count = 0
+		tr.Descend(N/2, func(_ interface{}) bool {
+			count++
+			return true
 		})
-		if res != keys[i] {
-			t.Fatal("not equal")
-		}
-	}
-
-	if tr.Height() == 0 {
-		t.Fatalf("expected non-zero")
-	}
-	if tr.Min() != keys[0] {
-		t.Fatalf("expected '%v', got '%v'", keys[0], tr.Min())
-	}
-	if tr.Max() != keys[len(keys)-1] {
-		t.Fatalf("expected '%v', got '%v'", keys[len(keys)-1], tr.Max())
-	}
-	min := tr.PopMin()
-	checkSane()
-	if min != keys[0] {
-		t.Fatalf("expected '%v', got '%v'", keys[0], min)
-	}
-	max := tr.PopMax()
-	checkSane()
-	if max != keys[len(keys)-1] {
-		t.Fatalf("expected '%v', got '%v'", keys[len(keys)-1], max)
-	}
-	tr.Set(min)
-	tr.Set(max)
-	shuffle(r, keys)
-	var hint PathHint
-	for i := 0; i < len(keys); i++ {
-		prev := tr.Get(keys[i])
-		if prev == nil || prev.(int) != keys[i] {
-			t.Fatalf("expected '%v', got '%v'", keys[i], prev)
-		}
-		prev = tr.GetHint(keys[i], &hint)
-		if prev == nil || prev.(int) != keys[i] {
-			t.Fatalf("expected '%v', got '%v'", keys[i], prev)
-		}
-	}
-	sort.Ints(keys)
-	for i := 0; i < len(keys); i++ {
-		item := tr.PopMin()
-		if item != keys[i] {
-			t.Fatalf("expected '%v', got '%v'", keys[i], item)
+		assert(count == N/2+1)
+
+		for i := 0; i < N; i++ {
+			assert(tr.Delete(i) == i)
+		}
+		assert(tr.Len() == 0)
+		assert(tr.Min() == nil)
+		assert(tr.Max() == nil)
+		assert(tr.PopMin() == nil)
+		assert(tr.PopMax() == nil)
+
+		for i := 0; i < N; i++ {
+			assert(tr.Get(i) == nil)
+		}
+		for i := 0; i < N; i++ {
+			assert(tr.Set(i) == nil)
+		}
+		assert(tr.Len() == N)
+		var hint PathHint
+		for i := 0; i < N; i++ {
+			assert(tr.SetHint(i, &hint) == i)
+		}
+		assert(tr.Len() == N)
+		for i := 0; i < N; i++ {
+			assert(tr.Load(i) == i)
+		}
+		assert(tr.Len() == N)
+		assert(tr.Min() == 0)
+		assert(tr.Max() == N-1)
+		assert(tr.PopMin() == 0)
+		assert(tr.PopMax() == N-1)
+		assert(tr.Set(0) == nil)
+		assert(tr.Set(N-1) == nil)
+		assert(tr.GetAt(0) == 0)
+		assert(tr.GetAt(N) == nil)
+		assert(tr.Set(N-1) == N-1)
+		assert(tr.Height() > 0)
+		assert(tr.DeleteAt(0) == 0)
+		assert(tr.Set(0) == nil)
+		assert(tr.DeleteAt(N-1) == N-1)
+		assert(tr.DeleteAt(N) == nil)
+		var wg sync.WaitGroup
+		wg.Add(1)
+		go func(tr *BTree) {
+			wg.Wait()
+			count := 0
+			tr.Walk(func(items []interface{}) {
+				count += len(items)
+			})
+			assert(count == N-1)
+		}(tr.Copy())
+		for i := 0; i < N/2; i++ {
+			tr.Delete(i)
+		}
+		for i := 0; i < N; i++ {
+			tr.Set(i)
+		}
+		wg.Done()
+
+		count = 0
+		tr.Walk(func(items []interface{}) {
+			count += len(items)
+		})
+		assert(count == N)
+
+		func() {
+			defer func() {
+				msg, ok := recover().(string)
+				assert(ok && msg == "nil item")
+			}()
+			tr := NewNonConcurrent(intLess)
+			tr.Set(nil)
+		}()
+		func() {
+			defer func() {
+				msg, ok := recover().(string)
+				assert(ok && msg == "nil item")
+			}()
+			tr := NewNonConcurrent(intLess)
+			tr.Load(nil)
+		}()
+		assert(tr.Get(nil) == nil)
+		assert(tr.Delete(nil) == nil)
+		for i := 0; i < N; i++ {
+			assert(tr.GetHint(i, &hint) == i)
 		}
-	}
-	for i := 0; i < len(keys); i++ {
-		prev := tr.Set(keys[i])
-		if prev != nil {
-			t.Fatalf("expected nil")
+		for i := 0; i < N; i++ {
+			assert(tr.DeleteHint(i, &hint) == i)
 		}
-	}
-	for i := len(keys) - 1; i >= 0; i-- {
-		item := tr.PopMax()
-		if item != keys[i] {
-			t.Fatalf("expected '%v', got '%v'", keys[i], item)
+		for i := 0; i < N; i++ {
+			assert(tr.GetHint(i, &hint) == nil)
 		}
-	}
-	for i := 0; i < len(keys); i++ {
-		prev := tr.Set(keys[i])
-		if prev != nil {
-			t.Fatalf("expected nil")
+		for i := 0; i < N; i++ {
+			assert(tr.DeleteHint(i, &hint) == nil)
 		}
-	}
-
-	if tr.Delete(nil) != nil {
-		t.Fatal("expected nil")
-	}
-	checkSane()
 
-	shuffle(r, keys)
-	item := tr.Delete(keys[len(keys)/2])
-	checkSane()
-	if item != keys[len(keys)/2] {
-		t.Fatalf("expected '%v', got '%v'", keys[len(keys)/2], item)
+		assert(tr.Less(1, 2))
+		assert(tr.Less(2, 10))
 	}
-	item2 := tr.Delete(keys[len(keys)/2])
-	checkSane()
-	if item2 != nil {
-		t.Fatalf("expected '%v', got '%v'", nil, item2)
+}
+func TestIter(t *testing.T) {
+	N := 100_000
+	lt := func(a, b interface{}) bool { return a.(int) < b.(int) }
+	eq := func(a, b interface{}) bool { return !lt(a, b) && !lt(b, a) }
+	tr := New(lt)
+	var all []int
+	for i := 0; i < N; i++ {
+		tr.Load(i)
+		all = append(all, i)
 	}
-
-	tr.Set(item)
-	checkSane()
-	for i := 0; i < len(keys); i++ {
-		prev := tr.Delete(keys[i])
-		checkSane()
-		if prev == nil || prev.(int) != keys[i] {
-			t.Fatalf("expected '%v', got '%v'", keys[i], prev)
-		}
-		prev = tr.Get(keys[i])
-		if prev != nil {
-			t.Fatalf("expected nil")
-		}
-		prev = tr.GetHint(keys[i], &hint)
-		if prev != nil {
-			t.Fatalf("expected nil")
-		}
-		if i%12345 == 0 {
-			tr.sane()
+	var count int
+	var i int
+	iter := tr.Iter()
+	for ok := iter.First(); ok; ok = iter.Next() {
+		if !eq(all[i], iter.Item()) {
+			panic("!")
 		}
+		count++
+		i++
 	}
-	if tr.Height() != 0 {
-		t.Fatalf("expected 0, got %d", tr.Height())
+	if count != N {
+		t.Fatalf("expected %v, got %v", N, count)
 	}
-	shuffle(r, keys)
-	for i := 0; i < len(keys); i++ {
-		prev := tr.Load(keys[i])
-		checkSane()
-		if prev != nil {
-			t.Fatalf("expected nil")
+	iter.Release()
+	count = 0
+	i = len(all) - 1
+	iter = tr.Iter()
+	for ok := iter.Last(); ok; ok = iter.Prev() {
+		if !eq(all[i], iter.Item()) {
+			panic("!")
 		}
+		i--
+		count++
 	}
-	for i := 0; i < len(keys); i++ {
-		prev := tr.Get(keys[i])
-		if prev == nil || prev.(int) != keys[i] {
-			t.Fatalf("expected '%v', got '%v'", keys[i], prev)
-		}
+	if count != N {
+		t.Fatalf("expected %v, got %v", N, count)
 	}
-	shuffle(r, keys)
-	for i := 0; i < len(keys); i++ {
-		prev := tr.Delete(keys[i])
-		checkSane()
-		if prev == nil || prev.(int) != keys[i] {
-			t.Fatalf("expected '%v', got '%v'", keys[i], prev)
-		}
-		prev = tr.Get(keys[i])
-		if prev != nil {
-			t.Fatalf("expected nil")
+	iter.Release()
+	i = 0
+	iter = tr.Iter()
+	for ok := iter.First(); ok; ok = iter.Next() {
+		if !eq(all[i], iter.Item()) {
+			panic("!")
 		}
+		i++
 	}
-	sort.Ints(keys)
-	for i := 0; i < len(keys); i++ {
-		prev := tr.Load(keys[i])
-		checkSane()
-		if prev != nil {
-			t.Fatalf("expected nil")
+	i--
+	for ok := iter.Prev(); ok; ok = iter.Prev() {
+		i--
+		if !eq(all[i], iter.Item()) {
+			panic("!")
 		}
-	}
-	shuffle(r, keys)
-	item = tr.Load(keys[0])
-	checkSane()
-	if item != keys[0] {
-		t.Fatalf("expected '%v', got '%v'", keys[0], item)
-	}
-	func() {
-		defer func() {
-			msg := fmt.Sprint(recover())
-			if msg != "nil item" {
-				t.Fatal("expected 'nil item' panic")
-			}
-		}()
-		tr.Load(nil)
-		checkSane()
-		t.Fatalf("reached invalid code")
-	}()
-}
 
-func (n *node) saneheight(height, maxheight int) bool {
-	if n.leaf {
-		if height != maxheight {
-			return false
-		}
-	} else {
-		i := int16(0)
-		for ; i < n.numItems; i++ {
-			if !n.children[i].saneheight(height+1, maxheight) {
-				return false
-			}
-		}
-		if !n.children[i].saneheight(height+1, maxheight) {
-			return false
-		}
 	}
-	return true
-}
-
-// btree_saneheight returns true if the height of all leaves match the height
-// of the btree.
-func (tr *BTree) saneheight() bool {
-	height := tr.Height()
-	if tr.root != nil {
-		if height == 0 {
-			return false
-		}
-		return tr.root.saneheight(1, height)
+	if i != 0 {
+		panic("!")
 	}
-	return height == 0
-}
 
-func (n *node) deepcount() int {
-	count := int(n.numItems)
-	if !n.leaf {
-		for i := int16(0); i <= n.numItems; i++ {
-			count += n.children[i].deepcount()
+	i++
+	for ok := iter.Next(); ok; ok = iter.Next() {
+		if !eq(all[i], iter.Item()) {
+			panic("!")
 		}
-	}
-	return count
-}
+		i++
 
-// btree_deepcount returns the number of items in the btree.
-func (tr *BTree) deepcount() int {
-	if tr.root != nil {
-		return tr.root.deepcount()
 	}
-	return 0
-}
-
-func (tr *BTree) nodesaneprops(n *node, height int) bool {
-	if height == 1 {
-		if n.numItems < 1 || n.numItems > maxItems {
-			return false
-		}
-	} else {
-		if n.numItems < minItems || n.numItems > maxItems {
-			return false
-		}
+	if i != N {
+		panic("!")
 	}
-	if !n.leaf {
-		for i := int16(0); i < n.numItems; i++ {
-			if !tr.nodesaneprops(n.children[i], height+1) {
-				return false
-			}
-		}
-		if !tr.nodesaneprops(n.children[n.numItems], height+1) {
-			return false
-		}
-	}
-	return true
-}
 
-func (tr *BTree) saneprops() bool {
-	if tr.root != nil {
-		return tr.nodesaneprops(tr.root, 1)
-	}
-	return true
-}
-
-func (tr *BTree) saneorder() bool {
-	var last interface{}
-	var count int
-	var bad bool
-	tr.Walk(func(items []interface{}) {
-		for _, item := range items {
-			if bad {
-				return
-			}
-			if last != nil {
-				if !tr.less(last, item) {
-					bad = true
-					return
+	i = 0
+	for ok := iter.First(); ok; ok = iter.Next() {
+		if !eq(all[i], iter.Item()) {
+			panic("!")
+		}
+		if eq(iter.Item(), N/2) {
+			for ok = iter.Prev(); ok; ok = iter.Prev() {
+				i--
+				if !eq(all[i], iter.Item()) {
+					panic("!")
 				}
 			}
-			last = item
-			count++
+			break
 		}
-	})
-	return !bad && count == tr.length
-}
-
-// btree_sane returns true if the entire btree and every node are valid.
-// - height of all leaves are the equal to the btree height.
-// - deep count matches the btree count.
-// - all nodes have the correct number of items and counts.
-// - all items are in order.
-func (tr *BTree) sane() {
-	if tr == nil {
-		panic("nil tree")
-	}
-	if !tr.saneheight() {
-		panic("!sane-height")
-	}
-	if tr.Len() != tr.length || tr.deepcount() != tr.length {
-		panic("!sane-count")
-	}
-	if !tr.saneprops() {
-		panic("!sane-props")
-	}
-	if !tr.saneorder() {
-		panic("!sane-order")
+		i++
 	}
+	iter.Release()
 }
diff --git a/debian/changelog b/debian/changelog
index 9fad39d..c056013 100644
--- a/debian/changelog
+++ b/debian/changelog
@@ -1,3 +1,9 @@
+golang-github-tidwall-btree (1.1.0-1) UNRELEASED; urgency=low
+
+  * New upstream release.
+
+ -- Debian Janitor <janitor@jelmer.uk>  Mon, 14 Mar 2022 12:32:41 -0000
+
 golang-github-tidwall-btree (0.3.0-1) unstable; urgency=medium
 
   [ Debian Janitor ]
diff --git a/go.mod b/go.mod
new file mode 100644
index 0000000..1e35900
--- /dev/null
+++ b/go.mod
@@ -0,0 +1,3 @@
+module github.com/tidwall/btree
+
+go 1.16
diff --git a/internal/btree.go b/internal/btree.go
new file mode 100644
index 0000000..bde59ec
--- /dev/null
+++ b/internal/btree.go
@@ -0,0 +1,1275 @@
+// Copyright 2020 Joshua J Baker. All rights reserved.
+// Use of this source code is governed by an MIT-style license that can be
+// found in the LICENSE file at https://github.com/tidwall/btree/LICENSE
+
+///////////////////////////////////////////////////////////////////////////////
+// BEGIN PARAMS
+///////////////////////////////////////////////////////////////////////////////
+
+package btree
+
+import "sync"
+
+// degree is the B-Tree degree, which is equal to maximum number of children
+// pre node times two.
+// The default is 128, which means each node can have 255 items and 256 child
+// nodes.
+const degree = 128
+
+// kind is the item type.
+// It's important to use the equal symbol, which tells Go to create an alias of
+// the type, rather than creating an entirely new type.
+type kind = interface{}
+
+// contextKind is the kind of context that can be passed to NewOptions and the
+// less function
+type contextKind = interface{}
+
+// less returns true if A is less than B.
+// The value of context will be whatever was passed to NewOptions through the
+// Options.Context field, otherwise nil if the field was not set.
+func less(a, b kind, context contextKind) bool {
+	return context.(func(a, b contextKind) bool)(a, b)
+}
+
+// BTree aliases
+// These are aliases to the local bTree types and functions, which are exported
+// to allow for public use at a package level.
+// Rename them if desired, or comment them out to make the library private.
+type BTree = bTree
+type Options = bOptions
+type PathHint = bPathHint
+type Iter = bIter
+
+func New(less func(a, b kind) bool) *bTree { return bNew() }
+func NewOptions(opts bOptions) *bTree      { return bNewOptions(opts) }
+
+// The functions below, which begin with "test*", are required by the
+// btree_test.go file. If you choose not use include the btree_test.go file in
+// your project then these functions may be omitted.
+
+// testCustomSeed can be used to generate a custom random seed for testing.
+// Returning false will use time.Now().UnixNano()
+func testCustomSeed() (seed int64, ok bool) {
+	return 0, false
+}
+
+// testMakeItem must return a valid item for testing.
+// It's required that the returned item maintains equal order as the
+// provided int, such that:
+//    testMakeItem(0) < testMakeItem(1) < testMakeItem(2) < testMakeItem(10)
+func testMakeItem(x int) (item kind) {
+	return x
+}
+
+// testNewBTree must return an operational btree for testing.
+func testNewBTree() *bTree {
+	return bNewOptions(bOptions{
+		Context: func(a, b contextKind) bool {
+			if a == nil {
+				return b != nil
+			} else if b == nil {
+				return false
+			}
+			return a.(int) < b.(int)
+		},
+	})
+}
+
+///////////////////////////////////////////////////////////////////////////////
+// END PARAMS
+///////////////////////////////////////////////////////////////////////////////
+
+// Do not edit code below this line.
+
+const maxItems = degree*2 - 1 // max items per node. max children is +1
+const minItems = maxItems / 2
+
+type bTree struct {
+	mu    *sync.RWMutex
+	cow   *cow
+	root  *node
+	count int
+	ctx   contextKind
+	locks bool
+	empty kind
+}
+
+type node struct {
+	cow      *cow
+	count    int
+	items    []kind
+	children *[]*node
+}
+
+type cow struct {
+	_ int // cannot be an empty struct
+}
+
+func (tr *bTree) newNode(leaf bool) *node {
+	n := &node{cow: tr.cow}
+	if !leaf {
+		n.children = new([]*node)
+	}
+	return n
+}
+
+// leaf returns true if the node is a leaf.
+func (n *node) leaf() bool {
+	return n.children == nil
+}
+
+// PathHint is a utility type used with the *Hint() functions. Hints provide
+// faster operations for clustered keys.
+type bPathHint struct {
+	used [8]bool
+	path [8]uint8
+}
+
+type bOptions struct {
+	NoLocks bool
+	Context contextKind
+}
+
+// New returns a new BTree
+func bNew() *bTree {
+	return bNewOptions(bOptions{})
+}
+
+func bNewOptions(opts bOptions) *bTree {
+	tr := new(bTree)
+	tr.cow = new(cow)
+	tr.mu = new(sync.RWMutex)
+	tr.ctx = opts.Context
+	tr.locks = !opts.NoLocks
+	return tr
+}
+
+// Less is a convenience function that performs a comparison of two items
+// using the same "less" function provided to New.
+func (tr *bTree) Less(a, b kind) bool {
+	return less(a, b, tr.ctx)
+}
+
+func (tr *bTree) find(n *node, key kind,
+	hint *bPathHint, depth int,
+) (index int, found bool) {
+	if hint == nil {
+		// fast path for no hinting
+		low := 0
+		high := len(n.items)
+		for low < high {
+			mid := (low + high) / 2
+			if !tr.Less(key, n.items[mid]) {
+				low = mid + 1
+			} else {
+				high = mid
+			}
+		}
+		if low > 0 && !tr.Less(n.items[low-1], key) {
+			return low - 1, true
+		}
+		return low, false
+	}
+
+	// Try using hint.
+	// Best case finds the exact match, updates the hint and returns.
+	// Worst case, updates the low and high bounds to binary search between.
+	low := 0
+	high := len(n.items) - 1
+	if depth < 8 && hint.used[depth] {
+		index = int(hint.path[depth])
+		if index >= len(n.items) {
+			// tail item
+			if tr.Less(n.items[len(n.items)-1], key) {
+				index = len(n.items)
+				goto path_match
+			}
+			index = len(n.items) - 1
+		}
+		if tr.Less(key, n.items[index]) {
+			if index == 0 || tr.Less(n.items[index-1], key) {
+				goto path_match
+			}
+			high = index - 1
+		} else if tr.Less(n.items[index], key) {
+			low = index + 1
+		} else {
+			found = true
+			goto path_match
+		}
+	}
+
+	// Do a binary search between low and high
+	// keep on going until low > high, where the guarantee on low is that
+	// key >= items[low - 1]
+	for low <= high {
+		mid := low + ((high+1)-low)/2
+		// if key >= n.items[mid], low = mid + 1
+		// which implies that key >= everything below low
+		if !tr.Less(key, n.items[mid]) {
+			low = mid + 1
+		} else {
+			high = mid - 1
+		}
+	}
+
+	// if low > 0, n.items[low - 1] >= key,
+	// we have from before that key >= n.items[low - 1]
+	// therefore key = n.items[low - 1],
+	// and we have found the entry for key.
+	// Otherwise we must keep searching for the key in index `low`.
+	if low > 0 && !tr.Less(n.items[low-1], key) {
+		index = low - 1
+		found = true
+	} else {
+		index = low
+		found = false
+	}
+
+path_match:
+	if depth < 8 {
+		hint.used[depth] = true
+		var pathIndex uint8
+		if n.leaf() && found {
+			pathIndex = uint8(index + 1)
+		} else {
+			pathIndex = uint8(index)
+		}
+		if pathIndex != hint.path[depth] {
+			hint.path[depth] = pathIndex
+			for i := depth + 1; i < 8; i++ {
+				hint.used[i] = false
+			}
+		}
+	}
+	return index, found
+}
+
+// SetHint sets or replace a value for a key using a path hint
+func (tr *bTree) SetHint(item kind, hint *bPathHint) (prev kind, replaced bool) {
+	if tr.lock() {
+		defer tr.unlock()
+	}
+	return tr.setHint(item, hint)
+}
+
+func (tr *bTree) setHint(item kind, hint *bPathHint) (prev kind, replaced bool) {
+	if tr.root == nil {
+		tr.root = tr.newNode(true)
+		tr.root.items = append([]kind{}, item)
+		tr.root.count = 1
+		tr.count = 1
+		return tr.empty, false
+	}
+	prev, replaced, split := tr.nodeSet(&tr.root, item, hint, 0)
+	if split {
+		left := tr.cowLoad(&tr.root)
+		right, median := tr.nodeSplit(left)
+		tr.root = tr.newNode(false)
+		*tr.root.children = make([]*node, 0, maxItems+1)
+		*tr.root.children = append([]*node{}, left, right)
+		tr.root.items = append([]kind{}, median)
+		tr.root.updateCount()
+		return tr.setHint(item, hint)
+	}
+	if replaced {
+		return prev, true
+	}
+	tr.count++
+	return tr.empty, false
+}
+
+// Set or replace a value for a key
+func (tr *bTree) Set(item kind) (kind, bool) {
+	return tr.SetHint(item, nil)
+}
+
+func (tr *bTree) nodeSplit(n *node) (right *node, median kind) {
+	i := maxItems / 2
+	median = n.items[i]
+
+	// left node
+	left := tr.newNode(n.leaf())
+	left.items = make([]kind, len(n.items[:i]), maxItems/2)
+	copy(left.items, n.items[:i])
+	if !n.leaf() {
+		*left.children = make([]*node, len((*n.children)[:i+1]), maxItems+1)
+		copy(*left.children, (*n.children)[:i+1])
+	}
+	left.updateCount()
+
+	// right node
+	right = tr.newNode(n.leaf())
+	right.items = make([]kind, len(n.items[i+1:]), maxItems/2)
+	copy(right.items, n.items[i+1:])
+	if !n.leaf() {
+		*right.children = make([]*node, len((*n.children)[i+1:]), maxItems+1)
+		copy(*right.children, (*n.children)[i+1:])
+	}
+	right.updateCount()
+
+	*n = *left
+	return right, median
+}
+
+func (n *node) updateCount() {
+	n.count = len(n.items)
+	if !n.leaf() {
+		for i := 0; i < len(*n.children); i++ {
+			n.count += (*n.children)[i].count
+		}
+	}
+}
+
+// This operation should not be inlined because it's expensive and rarely
+// called outside of heavy copy-on-write situations. Marking it "noinline"
+// allows for the parent cowLoad to be inlined.
+// go:noinline
+func (tr *bTree) copy(n *node) *node {
+	n2 := new(node)
+	n2.cow = tr.cow
+	n2.count = n.count
+	n2.items = make([]kind, len(n.items), cap(n.items))
+	copy(n2.items, n.items)
+	if !n.leaf() {
+		n2.children = new([]*node)
+		*n2.children = make([]*node, len(*n.children), maxItems+1)
+		copy(*n2.children, *n.children)
+	}
+	return n2
+}
+
+// cowLoad loads the provided node and, if needed, performs a copy-on-write.
+func (tr *bTree) cowLoad(cn **node) *node {
+	if (*cn).cow != tr.cow {
+		*cn = tr.copy(*cn)
+	}
+	return *cn
+}
+
+func (tr *bTree) nodeSet(cn **node, item kind,
+	hint *bPathHint, depth int,
+) (prev kind, replaced bool, split bool) {
+	n := tr.cowLoad(cn)
+	i, found := tr.find(n, item, hint, depth)
+	if found {
+		prev = n.items[i]
+		n.items[i] = item
+		return prev, true, false
+	}
+	if n.leaf() {
+		if len(n.items) == maxItems {
+			return tr.empty, false, true
+		}
+		n.items = append(n.items, tr.empty)
+		copy(n.items[i+1:], n.items[i:])
+		n.items[i] = item
+		n.count++
+		return tr.empty, false, false
+	}
+	prev, replaced, split = tr.nodeSet(&(*n.children)[i], item, hint, depth+1)
+	if split {
+		if len(n.items) == maxItems {
+			return tr.empty, false, true
+		}
+		right, median := tr.nodeSplit((*n.children)[i])
+		*n.children = append(*n.children, nil)
+		copy((*n.children)[i+1:], (*n.children)[i:])
+		(*n.children)[i+1] = right
+		n.items = append(n.items, tr.empty)
+		copy(n.items[i+1:], n.items[i:])
+		n.items[i] = median
+		return tr.nodeSet(&n, item, hint, depth)
+	}
+	if !replaced {
+		n.count++
+	}
+	return prev, replaced, false
+}
+
+func (tr *bTree) Scan(iter func(item kind) bool) {
+	if tr.rlock() {
+		defer tr.runlock()
+	}
+	if tr.root == nil {
+		return
+	}
+	tr.root.scan(iter)
+}
+
+func (n *node) scan(iter func(item kind) bool) bool {
+	if n.leaf() {
+		for i := 0; i < len(n.items); i++ {
+			if !iter(n.items[i]) {
+				return false
+			}
+		}
+		return true
+	}
+	for i := 0; i < len(n.items); i++ {
+		if !(*n.children)[i].scan(iter) {
+			return false
+		}
+		if !iter(n.items[i]) {
+			return false
+		}
+	}
+	return (*n.children)[len(*n.children)-1].scan(iter)
+}
+
+// Get a value for key
+func (tr *bTree) Get(key kind) (kind, bool) {
+	return tr.GetHint(key, nil)
+}
+
+// GetHint gets a value for key using a path hint
+func (tr *bTree) GetHint(key kind, hint *bPathHint) (kind, bool) {
+	if tr.rlock() {
+		defer tr.runlock()
+	}
+	if tr.root == nil {
+		return tr.empty, false
+	}
+	n := tr.root
+	depth := 0
+	for {
+		i, found := tr.find(n, key, hint, depth)
+		if found {
+			return n.items[i], true
+		}
+		if n.children == nil {
+			return tr.empty, false
+		}
+		n = (*n.children)[i]
+		depth++
+	}
+}
+
+// Len returns the number of items in the tree
+func (tr *bTree) Len() int {
+	return tr.count
+}
+
+// Delete a value for a key
+func (tr *bTree) Delete(key kind) (kind, bool) {
+	return tr.DeleteHint(key, nil)
+}
+
+// DeleteHint deletes a value for a key using a path hint
+func (tr *bTree) DeleteHint(key kind, hint *bPathHint) (kind, bool) {
+	if tr.lock() {
+		defer tr.unlock()
+	}
+	return tr.deleteHint(key, hint)
+}
+
+func (tr *bTree) deleteHint(key kind, hint *bPathHint) (kind, bool) {
+	if tr.root == nil {
+		return tr.empty, false
+	}
+	prev, deleted := tr.delete(&tr.root, false, key, hint, 0)
+	if !deleted {
+		return tr.empty, false
+	}
+	if len(tr.root.items) == 0 && !tr.root.leaf() {
+		tr.root = (*tr.root.children)[0]
+	}
+	tr.count--
+	if tr.count == 0 {
+		tr.root = nil
+	}
+	return prev, true
+}
+
+func (tr *bTree) delete(cn **node, max bool, key kind,
+	hint *bPathHint, depth int,
+) (kind, bool) {
+	n := tr.cowLoad(cn)
+	var i int
+	var found bool
+	if max {
+		i, found = len(n.items)-1, true
+	} else {
+		i, found = tr.find(n, key, hint, depth)
+	}
+	if n.leaf() {
+		if found {
+			// found the items at the leaf, remove it and return.
+			prev := n.items[i]
+			copy(n.items[i:], n.items[i+1:])
+			n.items[len(n.items)-1] = tr.empty
+			n.items = n.items[:len(n.items)-1]
+			n.count--
+			return prev, true
+		}
+		return tr.empty, false
+	}
+
+	var prev kind
+	var deleted bool
+	if found {
+		if max {
+			i++
+			prev, deleted = tr.delete(&(*n.children)[i], true, tr.empty, nil, 0)
+		} else {
+			prev = n.items[i]
+			maxItem, _ := tr.delete(&(*n.children)[i], true, tr.empty, nil, 0)
+			deleted = true
+			n.items[i] = maxItem
+		}
+	} else {
+		prev, deleted = tr.delete(&(*n.children)[i], max, key, hint, depth+1)
+	}
+	if !deleted {
+		return tr.empty, false
+	}
+	n.count--
+	if len((*n.children)[i].items) < minItems {
+		tr.nodeRebalance(n, i)
+	}
+	return prev, true
+
+}
+
+// nodeRebalance rebalances the child nodes following a delete operation.
+// Provide the index of the child node with the number of items that fell
+// below minItems.
+func (tr *bTree) nodeRebalance(n *node, i int) {
+	if i == len(n.items) {
+		i--
+	}
+
+	// ensure copy-on-write
+	left := tr.cowLoad(&(*n.children)[i])
+	right := tr.cowLoad(&(*n.children)[i+1])
+
+	if len(left.items)+len(right.items) < maxItems {
+		// Merges the left and right children nodes together as a single node
+		// that includes (left,item,right), and places the contents into the
+		// existing left node. Delete the right node altogether and move the
+		// following items and child nodes to the left by one slot.
+
+		// merge (left,item,right)
+		left.items = append(left.items, n.items[i])
+		left.items = append(left.items, right.items...)
+		if !left.leaf() {
+			*left.children = append(*left.children, *right.children...)
+		}
+		left.count += right.count + 1
+
+		// move the items over one slot
+		copy(n.items[i:], n.items[i+1:])
+		n.items[len(n.items)-1] = tr.empty
+		n.items = n.items[:len(n.items)-1]
+
+		// move the children over one slot
+		copy((*n.children)[i+1:], (*n.children)[i+2:])
+		(*n.children)[len(*n.children)-1] = nil
+		(*n.children) = (*n.children)[:len(*n.children)-1]
+	} else if len(left.items) > len(right.items) {
+		// move left -> right over one slot
+
+		// Move the item of the parent node at index into the right-node first
+		// slot, and move the left-node last item into the previously moved
+		// parent item slot.
+		right.items = append(right.items, tr.empty)
+		copy(right.items[1:], right.items)
+		right.items[0] = n.items[i]
+		right.count++
+		n.items[i] = left.items[len(left.items)-1]
+		left.items[len(left.items)-1] = tr.empty
+		left.items = left.items[:len(left.items)-1]
+		left.count--
+
+		if !left.leaf() {
+			// move the left-node last child into the right-node first slot
+			*right.children = append(*right.children, nil)
+			copy((*right.children)[1:], *right.children)
+			(*right.children)[0] = (*left.children)[len(*left.children)-1]
+			(*left.children)[len(*left.children)-1] = nil
+			(*left.children) = (*left.children)[:len(*left.children)-1]
+			left.count -= (*right.children)[0].count
+			right.count += (*right.children)[0].count
+		}
+	} else {
+		// move left <- right over one slot
+
+		// Same as above but the other direction
+		left.items = append(left.items, n.items[i])
+		left.count++
+		n.items[i] = right.items[0]
+		copy(right.items, right.items[1:])
+		right.items[len(right.items)-1] = tr.empty
+		right.items = right.items[:len(right.items)-1]
+		right.count--
+
+		if !left.leaf() {
+			*left.children = append(*left.children, (*right.children)[0])
+			copy(*right.children, (*right.children)[1:])
+			(*right.children)[len(*right.children)-1] = nil
+			*right.children = (*right.children)[:len(*right.children)-1]
+			left.count += (*left.children)[len(*left.children)-1].count
+			right.count -= (*left.children)[len(*left.children)-1].count
+		}
+	}
+}
+
+// Ascend the tree within the range [pivot, last]
+// Pass nil for pivot to scan all item in ascending order
+// Return false to stop iterating
+func (tr *bTree) Ascend(pivot kind, iter func(item kind) bool) {
+	if tr.rlock() {
+		defer tr.runlock()
+	}
+	if tr.root == nil {
+		return
+	}
+	tr.ascend(tr.root, pivot, nil, 0, iter)
+}
+
+// The return value of this function determines whether we should keep iterating
+// upon this functions return.
+func (tr *bTree) ascend(n *node, pivot kind,
+	hint *bPathHint, depth int, iter func(item kind) bool,
+) bool {
+	i, found := tr.find(n, pivot, hint, depth)
+	if !found {
+		if !n.leaf() {
+			if !tr.ascend((*n.children)[i], pivot, hint, depth+1, iter) {
+				return false
+			}
+		}
+	}
+	// We are either in the case that
+	// - node is found, we should iterate through it starting at `i`,
+	//   the index it was located at.
+	// - node is not found, and TODO: fill in.
+	for ; i < len(n.items); i++ {
+		if !iter(n.items[i]) {
+			return false
+		}
+		if !n.leaf() {
+			if !(*n.children)[i+1].scan(iter) {
+				return false
+			}
+		}
+	}
+	return true
+}
+
+func (tr *bTree) Reverse(iter func(item kind) bool) {
+	if tr.rlock() {
+		defer tr.runlock()
+	}
+	if tr.root == nil {
+		return
+	}
+	tr.root.reverse(iter)
+}
+
+func (n *node) reverse(iter func(item kind) bool) bool {
+	if n.leaf() {
+		for i := len(n.items) - 1; i >= 0; i-- {
+			if !iter(n.items[i]) {
+				return false
+			}
+		}
+		return true
+	}
+	if !(*n.children)[len(*n.children)-1].reverse(iter) {
+		return false
+	}
+	for i := len(n.items) - 1; i >= 0; i-- {
+		if !iter(n.items[i]) {
+			return false
+		}
+		if !(*n.children)[i].reverse(iter) {
+			return false
+		}
+	}
+	return true
+}
+
+// Descend the tree within the range [pivot, first]
+// Pass nil for pivot to scan all item in descending order
+// Return false to stop iterating
+func (tr *bTree) Descend(pivot kind, iter func(item kind) bool) {
+	if tr.rlock() {
+		defer tr.runlock()
+	}
+	if tr.root == nil {
+		return
+	}
+	tr.descend(tr.root, pivot, nil, 0, iter)
+}
+
+func (tr *bTree) descend(n *node, pivot kind,
+	hint *bPathHint, depth int, iter func(item kind) bool,
+) bool {
+	i, found := tr.find(n, pivot, hint, depth)
+	if !found {
+		if !n.leaf() {
+			if !tr.descend((*n.children)[i], pivot, hint, depth+1, iter) {
+				return false
+			}
+		}
+		i--
+	}
+	for ; i >= 0; i-- {
+		if !iter(n.items[i]) {
+			return false
+		}
+		if !n.leaf() {
+			if !(*n.children)[i].reverse(iter) {
+				return false
+			}
+		}
+	}
+	return true
+}
+
+// Load is for bulk loading pre-sorted items
+func (tr *bTree) Load(item kind) (kind, bool) {
+	if tr.lock() {
+		defer tr.unlock()
+	}
+	if tr.root == nil {
+		return tr.setHint(item, nil)
+	}
+	n := tr.cowLoad(&tr.root)
+	for {
+		n.count++ // optimistically update counts
+		if n.leaf() {
+			if len(n.items) < maxItems {
+				if tr.Less(n.items[len(n.items)-1], item) {
+					n.items = append(n.items, item)
+					tr.count++
+					return tr.empty, false
+				}
+			}
+			break
+		}
+		n = tr.cowLoad(&(*n.children)[len(*n.children)-1])
+	}
+	// revert the counts
+	n = tr.root
+	for {
+		n.count--
+		if n.leaf() {
+			break
+		}
+		n = (*n.children)[len(*n.children)-1]
+	}
+	return tr.setHint(item, nil)
+}
+
+// Min returns the minimum item in tree.
+// Returns nil if the tree has no items.
+func (tr *bTree) Min() (kind, bool) {
+	if tr.rlock() {
+		defer tr.runlock()
+	}
+	if tr.root == nil {
+		return tr.empty, false
+	}
+	n := tr.root
+	for {
+		if n.leaf() {
+			return n.items[0], true
+		}
+		n = (*n.children)[0]
+	}
+}
+
+// Max returns the maximum item in tree.
+// Returns nil if the tree has no items.
+func (tr *bTree) Max() (kind, bool) {
+	if tr.rlock() {
+		defer tr.runlock()
+	}
+	if tr.root == nil {
+		return tr.empty, false
+	}
+	n := tr.root
+	for {
+		if n.leaf() {
+			return n.items[len(n.items)-1], true
+		}
+		n = (*n.children)[len(*n.children)-1]
+	}
+}
+
+// PopMin removes the minimum item in tree and returns it.
+// Returns nil if the tree has no items.
+func (tr *bTree) PopMin() (kind, bool) {
+	if tr.lock() {
+		defer tr.unlock()
+	}
+	if tr.root == nil {
+		return tr.empty, false
+	}
+	n := tr.cowLoad(&tr.root)
+	var item kind
+	for {
+		n.count-- // optimistically update counts
+		if n.leaf() {
+			item = n.items[0]
+			if len(n.items) == minItems {
+				break
+			}
+			copy(n.items[:], n.items[1:])
+			n.items[len(n.items)-1] = tr.empty
+			n.items = n.items[:len(n.items)-1]
+			tr.count--
+			if tr.count == 0 {
+				tr.root = nil
+			}
+			return item, true
+		}
+		n = tr.cowLoad(&(*n.children)[0])
+	}
+	// revert the counts
+	n = tr.root
+	for {
+		n.count++
+		if n.leaf() {
+			break
+		}
+		n = (*n.children)[0]
+	}
+	return tr.deleteHint(item, nil)
+}
+
+// PopMax removes the minimum item in tree and returns it.
+// Returns nil if the tree has no items.
+func (tr *bTree) PopMax() (kind, bool) {
+	if tr.lock() {
+		defer tr.unlock()
+	}
+	if tr.root == nil {
+		return tr.empty, false
+	}
+	n := tr.cowLoad(&tr.root)
+	var item kind
+	for {
+		n.count-- // optimistically update counts
+		if n.leaf() {
+			item = n.items[len(n.items)-1]
+			if len(n.items) == minItems {
+				break
+			}
+			n.items[len(n.items)-1] = tr.empty
+			n.items = n.items[:len(n.items)-1]
+			tr.count--
+			if tr.count == 0 {
+				tr.root = nil
+			}
+			return item, true
+		}
+		n = tr.cowLoad(&(*n.children)[len(*n.children)-1])
+	}
+	// revert the counts
+	n = tr.root
+	for {
+		n.count++
+		if n.leaf() {
+			break
+		}
+		n = (*n.children)[len(*n.children)-1]
+	}
+	return tr.deleteHint(item, nil)
+}
+
+// GetAt returns the value at index.
+// Return nil if the tree is empty or the index is out of bounds.
+func (tr *bTree) GetAt(index int) (kind, bool) {
+	if tr.rlock() {
+		defer tr.runlock()
+	}
+	if tr.root == nil || index < 0 || index >= tr.count {
+		return tr.empty, false
+	}
+	n := tr.root
+	for {
+		if n.leaf() {
+			return n.items[index], true
+		}
+		i := 0
+		for ; i < len(n.items); i++ {
+			if index < (*n.children)[i].count {
+				break
+			} else if index == (*n.children)[i].count {
+				return n.items[i], true
+			}
+			index -= (*n.children)[i].count + 1
+		}
+		n = (*n.children)[i]
+	}
+}
+
+// DeleteAt deletes the item at index.
+// Return nil if the tree is empty or the index is out of bounds.
+func (tr *bTree) DeleteAt(index int) (kind, bool) {
+	if tr.lock() {
+		defer tr.unlock()
+	}
+	if tr.root == nil || index < 0 || index >= tr.count {
+		return tr.empty, false
+	}
+	var pathbuf [8]uint8 // track the path
+	path := pathbuf[:0]
+	var item kind
+	n := tr.cowLoad(&tr.root)
+outer:
+	for {
+		n.count-- // optimistically update counts
+		if n.leaf() {
+			// the index is the item position
+			item = n.items[index]
+			if len(n.items) == minItems {
+				path = append(path, uint8(index))
+				break outer
+			}
+			copy(n.items[index:], n.items[index+1:])
+			n.items[len(n.items)-1] = tr.empty
+			n.items = n.items[:len(n.items)-1]
+			tr.count--
+			if tr.count == 0 {
+				tr.root = nil
+			}
+			return item, true
+		}
+		i := 0
+		for ; i < len(n.items); i++ {
+			if index < (*n.children)[i].count {
+				break
+			} else if index == (*n.children)[i].count {
+				item = n.items[i]
+				path = append(path, uint8(i))
+				break outer
+			}
+			index -= (*n.children)[i].count + 1
+		}
+		path = append(path, uint8(i))
+		n = tr.cowLoad(&(*n.children)[i])
+	}
+	// revert the counts
+	var hint bPathHint
+	n = tr.root
+	for i := 0; i < len(path); i++ {
+		if i < len(hint.path) {
+			hint.path[i] = uint8(path[i])
+			hint.used[i] = true
+		}
+		n.count++
+		if !n.leaf() {
+			n = (*n.children)[uint8(path[i])]
+		}
+	}
+	return tr.deleteHint(item, &hint)
+}
+
+// Height returns the height of the tree.
+// Returns zero if tree has no items.
+func (tr *bTree) Height() int {
+	if tr.rlock() {
+		defer tr.runlock()
+	}
+	var height int
+	if tr.root != nil {
+		n := tr.root
+		for {
+			height++
+			if n.leaf() {
+				break
+			}
+			n = (*n.children)[0]
+		}
+	}
+	return height
+}
+
+// Walk iterates over all items in tree, in order.
+// The items param will contain one or more items.
+func (tr *bTree) Walk(iter func(item []kind) bool) {
+	if tr.rlock() {
+		defer tr.runlock()
+	}
+	if tr.root != nil {
+		tr.root.walk(iter)
+	}
+}
+
+func (n *node) walk(iter func(item []kind) bool) bool {
+	if n.leaf() {
+		if !iter(n.items) {
+			return false
+		}
+	} else {
+		for i := 0; i < len(n.items); i++ {
+			(*n.children)[i].walk(iter)
+			if !iter(n.items[i : i+1]) {
+				return false
+			}
+		}
+		(*n.children)[len(n.items)].walk(iter)
+	}
+	return true
+}
+
+// Copy the tree. This is a copy-on-write operation and is very fast because
+// it only performs a shadowed copy.
+func (tr *bTree) Copy() *bTree {
+	if tr.lock() {
+		defer tr.unlock()
+	}
+	tr.cow = new(cow)
+	tr2 := new(bTree)
+	*tr2 = *tr
+	tr2.mu = new(sync.RWMutex)
+	tr2.cow = new(cow)
+	return tr2
+}
+
+func (tr *bTree) lock() bool {
+	if tr.locks {
+		tr.mu.Lock()
+	}
+	return tr.locks
+}
+
+func (tr *bTree) unlock() {
+	tr.mu.Unlock()
+}
+
+func (tr *bTree) rlock() bool {
+	if tr.locks {
+		tr.mu.RLock()
+	}
+	return tr.locks
+}
+
+func (tr *bTree) runlock() {
+	tr.mu.RUnlock()
+}
+
+// Iter represents an iterator
+type bIter struct {
+	tr      *bTree
+	locked  bool
+	seeked  bool
+	atstart bool
+	atend   bool
+	stack   []iterStackItem
+	item    kind
+}
+
+type iterStackItem struct {
+	n *node
+	i int
+}
+
+// Iter returns a read-only iterator.
+// The Release method must be called finished with iterator.
+func (tr *bTree) Iter() bIter {
+	var iter bIter
+	iter.tr = tr
+	iter.locked = tr.rlock()
+	return iter
+}
+
+// Seek to item greater-or-equal-to key.
+// Returns false if there was no item found.
+func (iter *bIter) Seek(key kind) bool {
+	if iter.tr == nil {
+		return false
+	}
+	iter.seeked = true
+	iter.stack = iter.stack[:0]
+	if iter.tr.root == nil {
+		return false
+	}
+	n := iter.tr.root
+	for {
+		i, found := iter.tr.find(n, key, nil, 0)
+		iter.stack = append(iter.stack, iterStackItem{n, i})
+		if found {
+			return true
+		}
+		if n.leaf() {
+			if i == len(n.items) {
+				iter.stack = iter.stack[:0]
+				return false
+			}
+			return true
+		}
+		n = (*n.children)[i]
+	}
+}
+
+// First moves iterator to first item in tree.
+// Returns false if the tree is empty.
+func (iter *bIter) First() bool {
+	if iter.tr == nil {
+		return false
+	}
+	iter.atend = false
+	iter.atstart = false
+	iter.seeked = true
+	iter.stack = iter.stack[:0]
+	if iter.tr.root == nil {
+		return false
+	}
+	n := iter.tr.root
+	for {
+		iter.stack = append(iter.stack, iterStackItem{n, 0})
+		if n.leaf() {
+			break
+		}
+		n = (*n.children)[0]
+	}
+	s := &iter.stack[len(iter.stack)-1]
+	iter.item = s.n.items[s.i]
+	return true
+}
+
+// Last moves iterator to last item in tree.
+// Returns false if the tree is empty.
+func (iter *bIter) Last() bool {
+	if iter.tr == nil {
+		return false
+	}
+	iter.seeked = true
+	iter.stack = iter.stack[:0]
+	if iter.tr.root == nil {
+		return false
+	}
+	n := iter.tr.root
+	for {
+		iter.stack = append(iter.stack, iterStackItem{n, len(n.items)})
+		if n.leaf() {
+			iter.stack[len(iter.stack)-1].i--
+			break
+		}
+		n = (*n.children)[len(n.items)]
+	}
+	s := &iter.stack[len(iter.stack)-1]
+	iter.item = s.n.items[s.i]
+	return true
+}
+
+// First moves iterator to first item in tree.
+// Returns false if the tree is empty.
+func (iter *bIter) Release() {
+	if iter.tr == nil {
+		return
+	}
+	if iter.locked {
+		iter.tr.runlock()
+		iter.locked = false
+	}
+	iter.stack = nil
+	iter.tr = nil
+}
+
+// Next moves iterator to the next item in iterator.
+// Returns false if the tree is empty or the iterator is at the end of
+// the tree.
+func (iter *bIter) Next() bool {
+	if iter.tr == nil {
+		return false
+	}
+	if !iter.seeked {
+		return iter.First()
+	}
+	if len(iter.stack) == 0 {
+		if iter.atstart {
+			return iter.First() && iter.Next()
+		}
+		return false
+	}
+	s := &iter.stack[len(iter.stack)-1]
+	s.i++
+	if s.n.leaf() {
+		if s.i == len(s.n.items) {
+			for {
+				iter.stack = iter.stack[:len(iter.stack)-1]
+				if len(iter.stack) == 0 {
+					iter.atend = true
+					return false
+				}
+				s = &iter.stack[len(iter.stack)-1]
+				if s.i < len(s.n.items) {
+					break
+				}
+			}
+		}
+	} else {
+		n := (*s.n.children)[s.i]
+		for {
+			iter.stack = append(iter.stack, iterStackItem{n, 0})
+			if n.leaf() {
+				break
+			}
+			n = (*n.children)[0]
+		}
+	}
+	s = &iter.stack[len(iter.stack)-1]
+	iter.item = s.n.items[s.i]
+	return true
+}
+
+// Prev moves iterator to the previous item in iterator.
+// Returns false if the tree is empty or the iterator is at the beginning of
+// the tree.
+func (iter *bIter) Prev() bool {
+	if iter.tr == nil {
+		return false
+	}
+	if !iter.seeked {
+		return false
+	}
+	if len(iter.stack) == 0 {
+		if iter.atend {
+			return iter.Last() && iter.Prev()
+		}
+		return false
+	}
+	s := &iter.stack[len(iter.stack)-1]
+	if s.n.leaf() {
+		s.i--
+		if s.i == -1 {
+			for {
+				iter.stack = iter.stack[:len(iter.stack)-1]
+				if len(iter.stack) == 0 {
+					iter.atstart = true
+					return false
+				}
+				s = &iter.stack[len(iter.stack)-1]
+				s.i--
+				if s.i > -1 {
+					break
+				}
+			}
+		}
+	} else {
+		n := (*s.n.children)[s.i]
+		for {
+			iter.stack = append(iter.stack, iterStackItem{n, len(n.items)})
+			if n.leaf() {
+				iter.stack[len(iter.stack)-1].i--
+				break
+			}
+			n = (*n.children)[len(n.items)]
+		}
+	}
+	s = &iter.stack[len(iter.stack)-1]
+	iter.item = s.n.items[s.i]
+	return true
+}
+
+// Item returns the current iterator item.
+func (iter *bIter) Item() kind {
+	return iter.item
+}
diff --git a/internal/btree_test.go b/internal/btree_test.go
new file mode 100644
index 0000000..50f7bc7
--- /dev/null
+++ b/internal/btree_test.go
@@ -0,0 +1,1260 @@
+package btree
+
+import (
+	"fmt"
+	"math/rand"
+	"os"
+	"runtime"
+	"sort"
+	"strconv"
+	"sync/atomic"
+	"testing"
+	"time"
+)
+
+var seed int64
+
+func init() {
+	var ok bool
+	seed, ok = testCustomSeed()
+	if !ok {
+		var err error
+		seed, err = strconv.ParseInt(os.Getenv("SEED"), 10, 64)
+		if err != nil {
+			seed = time.Now().UnixNano()
+		}
+	}
+	fmt.Printf("seed: %d\n", seed)
+	rand.Seed(seed)
+}
+
+func randKeys(N int) (keys []kind) {
+	keys = make([]kind, N)
+	for _, i := range rand.Perm(N) {
+		keys[i] = testMakeItem(i)
+	}
+	return keys
+}
+
+// eqtr is used for testing equality
+var eqtr = testNewBTree()
+
+func lt(a, b kind) bool  { return eqtr.Less(a, b) }
+func eq(a, b kind) bool  { return !(lt(a, b) || lt(b, a)) }
+func lte(a, b kind) bool { return lt(a, b) || eq(a, b) }
+func gt(a, b kind) bool  { return lt(b, a) }
+func gte(a, b kind) bool { return gt(a, b) || eq(a, b) }
+
+func kindsAreEqual(a, b []kind) bool {
+	if len(a) != len(b) {
+		return false
+	}
+	for i := 0; i < len(a); i++ {
+		if !eq(a[i], b[i]) {
+			return false
+		}
+	}
+	return true
+}
+
+func TestMakeItemOrder(t *testing.T) {
+	ints := []int{0, 1, 2, 3, 4, 10, 20, 30, 40, 100, 200, 300, 400}
+	for i := 0; i < len(ints)-1; i++ {
+		a := testMakeItem(ints[i])
+		b := testMakeItem(ints[i+1])
+		if !lt(a, b) {
+			t.Fatalf("bad ordering for testMakeItem: '%v' !< '%v'", a, b)
+		}
+	}
+}
+
+func TestDescend(t *testing.T) {
+	tr := testNewBTree()
+	var count int
+	tr.Descend(testMakeItem(rand.Int()), func(item kind) bool {
+		count++
+		return true
+	})
+	if count > 0 {
+		t.Fatalf("expected 0, got %v", count)
+	}
+	var keys []kind
+	for i := 0; i < 1000; i += 10 {
+		keys = append(keys, testMakeItem(i))
+		tr.Set(keys[len(keys)-1])
+	}
+	var exp []kind
+	tr.Reverse(func(item kind) bool {
+		exp = append(exp, item)
+		return true
+	})
+	for i := 999; i >= 0; i-- {
+		key := testMakeItem(i)
+		var all []kind
+		tr.Descend(key, func(item kind) bool {
+			all = append(all, item)
+			return true
+		})
+		for len(exp) > 0 && tr.Less(key, exp[0]) {
+			exp = exp[1:]
+		}
+		var count int
+		tr.Descend(key, func(item kind) bool {
+			if count == (i+1)%maxItems {
+				return false
+			}
+			count++
+			return true
+		})
+		if count > len(exp) {
+			t.Fatalf("expected 1, got %v", count)
+		}
+		if !kindsAreEqual(exp, all) {
+			fmt.Printf("exp: %v\n", exp)
+			fmt.Printf("all: %v\n", all)
+			t.Fatal("mismatch")
+		}
+		for j := 0; j < tr.Len(); j++ {
+			count = 0
+			tr.Descend(key, func(item kind) bool {
+				if count == j {
+					return false
+				}
+				count++
+				return true
+			})
+		}
+	}
+}
+
+func TestAscend(t *testing.T) {
+	tr := testNewBTree()
+	var count int
+	tr.Ascend(testMakeItem(1), func(item kind) bool {
+		count++
+		return true
+	})
+	if count > 0 {
+		t.Fatalf("expected 0, got %v", count)
+	}
+	var keys []kind
+	for i := 0; i < 1000; i += 10 {
+		keys = append(keys, testMakeItem(i))
+		tr.Set(keys[len(keys)-1])
+		tr.sane()
+	}
+	exp := keys
+	for i := -1; i < 1000; i++ {
+		key := testMakeItem(i)
+		var all []kind
+		tr.Ascend(key, func(item kind) bool {
+			all = append(all, item)
+			return true
+		})
+		for len(exp) > 0 && tr.Less(exp[0], key) {
+			exp = exp[1:]
+		}
+		var count int
+		tr.Ascend(key, func(item kind) bool {
+			if count == (i+1)%maxItems {
+				return false
+			}
+			count++
+			return true
+		})
+		if count > len(exp) {
+			t.Fatalf("expected 1, got %v", count)
+		}
+		if !kindsAreEqual(exp, all) {
+			t.Fatal("mismatch")
+		}
+	}
+}
+
+func TestSimpleRandom(t *testing.T) {
+	start := time.Now()
+	for time.Since(start) < time.Second*2 {
+		N := 100_000
+		items := randKeys(N)
+		tr := testNewBTree()
+		tr.sane()
+		for i := 0; i < len(items); i++ {
+			if v, ok := tr.Get(items[i]); ok || !eq(v, tr.empty) {
+				panic("!")
+			}
+			if v, ok := tr.Set(items[i]); ok || !eq(v, tr.empty) {
+				panic("!")
+			}
+			if v, ok := tr.Get(items[i]); !ok || !eq(v, items[i]) {
+				panic("!")
+			}
+		}
+		tr.sane()
+		for i := 0; i < len(items); i++ {
+			if v, ok := tr.Set(items[i]); !ok || !eq(v, items[i]) {
+				panic("!")
+			}
+		}
+		pivot := items[len(items)/2]
+		tr.Ascend(pivot, func(item kind) bool {
+			if tr.Less(item, pivot) {
+				panic("!")
+			}
+			return true
+		})
+		var min kind
+		index := 0
+		tr.Scan(func(item kind) bool {
+			if index == len(items)/2 {
+				return false
+			}
+			if index > 0 {
+				if tr.Less(item, min) {
+					panic("!")
+				}
+			}
+			min = item
+			index++
+			return true
+		})
+		tr.sane()
+		for i := 0; i < len(items); i++ {
+			if v, ok := tr.Delete(items[i]); !ok || !eq(v, items[i]) {
+				panic("!")
+			}
+			if i%97 == 0 {
+				tr.sane()
+			}
+			if v, ok := tr.Delete(items[i]); ok || !eq(v, tr.empty) {
+				panic("!")
+			}
+		}
+		if tr.Len() != 0 {
+			panic("!")
+		}
+		tr.sane()
+		for i := 0; i < len(items); i++ {
+			if v, ok := tr.Delete(items[i]); ok || !eq(v, tr.empty) {
+				panic("!")
+			}
+		}
+		tr.sane()
+		tr.Scan(func(item kind) bool {
+			panic("!")
+		})
+	}
+}
+
+func TestBTree(t *testing.T) {
+	N := 10000
+	tr := testNewBTree()
+	tr.sane()
+	keys := randKeys(N)
+
+	// insert all items
+	for _, key := range keys {
+		if v, ok := tr.Set(key); ok || !eq(v, tr.empty) {
+			t.Fatal("expected false")
+		}
+		tr.sane()
+	}
+
+	// check length
+	if tr.Len() != len(keys) {
+		t.Fatalf("expected %v, got %v", len(keys), tr.Len())
+	}
+
+	// get each value
+	for _, key := range keys {
+		if v, ok := tr.Get(key); !ok || !eq(v, key) {
+			t.Fatalf("expected '%v', got '%v'", key, v)
+		}
+	}
+
+	// scan all items
+	var prev kind
+	var count int
+	tr.Scan(func(item kind) bool {
+		if count > 0 {
+			if lte(item, prev) {
+				t.Fatal("out of order")
+			}
+		}
+		prev = item
+		count++
+		return true
+	})
+	if count != len(keys) {
+		t.Fatalf("expected '%v', got '%v'", len(keys), count)
+	}
+
+	// reverse all items
+	count = 0
+	tr.Reverse(func(item kind) bool {
+		if count > 0 {
+			if gte(item, prev) {
+				t.Fatal("out of order")
+			}
+		}
+		prev = item
+		count++
+		return true
+	})
+	if count != len(keys) {
+		t.Fatalf("expected '%v', got '%v'", len(keys), count)
+	}
+
+	// try to get an invalid item
+	if v, ok := tr.Get(testMakeItem(-1)); ok || !eq(v, tr.empty) {
+		t.Fatal("expected nil")
+	}
+
+	// scan and quit at various steps
+	for i := 0; i < 100; i++ {
+		var j int
+		tr.Scan(func(item kind) bool {
+			if j == i {
+				return false
+			}
+			j++
+			return true
+		})
+	}
+
+	// reverse and quit at various steps
+	for i := 0; i < 100; i++ {
+		var j int
+		tr.Reverse(func(item kind) bool {
+			if j == i {
+				return false
+			}
+			j++
+			return true
+		})
+	}
+
+	// delete half the items
+	for _, key := range keys[:len(keys)/2] {
+		if v, ok := tr.Delete(key); !ok || !eq(v, key) {
+			t.Fatalf("expected '%v', got '%v'", key, v)
+		}
+	}
+
+	// check length
+	if tr.Len() != len(keys)/2 {
+		t.Fatalf("expected %v, got %v", len(keys)/2, tr.Len())
+	}
+
+	// try delete half again
+	for _, key := range keys[:len(keys)/2] {
+		if v, ok := tr.Delete(key); ok || !eq(v, tr.empty) {
+			t.Fatal("expected false")
+		}
+		tr.sane()
+	}
+
+	// check length
+	if tr.Len() != len(keys)/2 {
+		t.Fatalf("expected %v, got %v", len(keys)/2, tr.Len())
+	}
+
+	// scan items
+	count = 0
+	tr.Scan(func(item kind) bool {
+		if count > 0 {
+			if lte(item, prev) {
+				t.Fatal("out of order")
+			}
+		}
+		prev = item
+		count++
+		return true
+	})
+	if count != len(keys)/2 {
+		t.Fatalf("expected '%v', got '%v'", len(keys), count)
+	}
+
+	// replace second half
+	for _, key := range keys[len(keys)/2:] {
+		if v, ok := tr.Set(key); !ok || !eq(v, key) {
+			t.Fatalf("expected '%v', got '%v'", key, v)
+		}
+		tr.sane()
+	}
+
+	// delete next half the items
+	for _, key := range keys[len(keys)/2:] {
+		if v, ok := tr.Delete(key); !ok || !eq(v, key) {
+			t.Fatalf("expected '%v', got '%v'", key, v)
+		}
+		tr.sane()
+	}
+
+	// check length
+	if tr.Len() != 0 {
+		t.Fatalf("expected %v, got %v", 0, tr.Len())
+	}
+
+	// do some stuff on an empty tree
+	if v, ok := tr.Get(keys[0]); ok || !eq(v, tr.empty) {
+		t.Fatal("expected nil")
+	}
+	tr.Scan(func(item kind) bool {
+		t.Fatal("should not be reached")
+		return true
+	})
+	tr.Reverse(func(item kind) bool {
+		t.Fatal("should not be reached")
+		return true
+	})
+	if v, ok := tr.Delete(testMakeItem(-1)); ok || !eq(v, tr.empty) {
+		t.Fatal("expected nil")
+	}
+	tr.sane()
+}
+
+func TestBTreeOne(t *testing.T) {
+	tr := testNewBTree()
+	tr.Set(testMakeItem(1))
+	tr.Delete(testMakeItem(1))
+	tr.Set(testMakeItem(1))
+	tr.Delete(testMakeItem(1))
+	tr.Set(testMakeItem(1))
+	tr.Delete(testMakeItem(1))
+	if tr.Len() != 0 {
+		panic("!")
+	}
+	tr.sane()
+}
+
+func TestBTree256(t *testing.T) {
+	tr := testNewBTree()
+	var n int
+	for j := 0; j < 2; j++ {
+		for _, i := range rand.Perm(256) {
+			tr.Set(testMakeItem(i))
+			n++
+			if tr.Len() != n {
+				t.Fatalf("expected 256, got %d", n)
+			}
+		}
+		for _, i := range rand.Perm(256) {
+			if v, ok := tr.Get(testMakeItem(i)); !ok || !eq(v, testMakeItem(i)) {
+				t.Fatalf("expected %v, got %v", i, v)
+			}
+		}
+		for _, i := range rand.Perm(256) {
+			tr.Delete(testMakeItem(i))
+			n--
+			if tr.Len() != n {
+				t.Fatalf("expected 256, got %d", n)
+			}
+		}
+		for _, i := range rand.Perm(256) {
+			if v, ok := tr.Get(testMakeItem(i)); ok || !eq(v, tr.empty) {
+				t.Fatal("expected nil")
+			}
+		}
+	}
+}
+
+func shuffleItems(keys []kind) {
+	for i := range keys {
+		j := rand.Intn(i + 1)
+		keys[i], keys[j] = keys[j], keys[i]
+	}
+}
+
+func sortItems(keys []kind) {
+	sort.Slice(keys, func(i, j int) bool {
+		return lt(keys[i], keys[j])
+	})
+}
+
+func TestRandom(t *testing.T) {
+	N := 200000
+	keys := randKeys(N)
+	tr := testNewBTree()
+	tr.sane()
+	if v, ok := tr.Min(); ok || !eq(v, tr.empty) {
+		t.Fatalf("expected nil")
+	}
+	if v, ok := tr.Max(); ok || !eq(v, tr.empty) {
+		t.Fatalf("expected nil")
+	}
+	if v, ok := tr.PopMin(); ok || !eq(v, tr.empty) {
+		t.Fatalf("expected nil")
+	}
+	if v, ok := tr.PopMax(); ok || !eq(v, tr.empty) {
+		t.Fatalf("expected nil")
+	}
+	if tr.Height() != 0 {
+		t.Fatalf("expected 0, got %d", tr.Height())
+	}
+	tr.sane()
+	shuffleItems(keys)
+	for i := 0; i < len(keys); i++ {
+		if v, ok := tr.Set(keys[i]); ok || !eq(v, tr.empty) {
+			t.Fatalf("expected nil")
+		}
+		if i%123 == 0 {
+			tr.sane()
+		}
+	}
+	tr.sane()
+	sortItems(keys)
+	var n int
+	tr.Scan(func(item kind) bool {
+		n++
+		return false
+	})
+	if n != 1 {
+		t.Fatalf("expected 1, got %d", n)
+	}
+
+	n = 0
+	tr.Scan(func(item kind) bool {
+		if !eq(item, keys[n]) {
+			t.Fatalf("expected %v, got %v", keys[n], item)
+		}
+		n++
+		return true
+	})
+	if n != len(keys) {
+		t.Fatalf("expected %d, got %d", len(keys), n)
+	}
+	if tr.Len() != len(keys) {
+		t.Fatalf("expected %d, got %d", tr.Len(), len(keys))
+	}
+
+	for i := 0; i < tr.Len(); i++ {
+		if v, ok := tr.GetAt(i); !ok || !eq(v, keys[i]) {
+			t.Fatalf("expected %v, got %v", keys[i], v)
+		}
+	}
+
+	n = 0
+	tr.Reverse(func(item kind) bool {
+		n++
+		return false
+	})
+	if n != 1 {
+		t.Fatalf("expected 1, got %d", n)
+	}
+	n = 0
+	tr.Reverse(func(item kind) bool {
+		if !eq(item, keys[len(keys)-n-1]) {
+			t.Fatalf("expected %v, got %v", keys[len(keys)-n-1], item)
+		}
+		n++
+		return true
+	})
+	if n != len(keys) {
+		t.Fatalf("expected %d, got %d", len(keys), n)
+	}
+	if tr.Len() != len(keys) {
+		t.Fatalf("expected %d, got %d", tr.Len(), len(keys))
+	}
+
+	tr.sane()
+
+	n = 0
+	for i := 0; i < 1000; i++ {
+		n := 0
+		tr.Scan(func(item kind) bool {
+			if n == i {
+				return false
+			}
+			n++
+			return true
+		})
+		if n != i {
+			t.Fatalf("expected %d, got %d", i, n)
+		}
+	}
+
+	n = 0
+	for i := 0; i < 1000; i++ {
+		n = 0
+		tr.Reverse(func(item kind) bool {
+			if n == i {
+				return false
+			}
+			n++
+			return true
+		})
+		if n != i {
+			t.Fatalf("expected %d, got %d", i, n)
+		}
+	}
+
+	sortItems(keys)
+	for i := 0; i < len(keys); i++ {
+		var res kind
+		var j int
+		tr.Ascend(keys[i], func(item kind) bool {
+			if j == 0 {
+				res = item
+			}
+			j++
+			return j == i%500
+		})
+		if !eq(res, keys[i]) {
+			t.Fatal("not equal")
+		}
+	}
+	for i := len(keys) - 1; i >= 0; i-- {
+		var res kind
+		var j int
+		tr.Descend(keys[i], func(item kind) bool {
+			if j == 0 {
+				res = item
+			}
+			j++
+			return j == i%500
+		})
+		if !eq(res, keys[i]) {
+			t.Fatal("not equal")
+		}
+	}
+
+	if tr.Height() == 0 {
+		t.Fatalf("expected non-zero")
+	}
+	if v, ok := tr.Min(); !ok || !eq(v, keys[0]) {
+		t.Fatalf("expected '%v', got '%v'", keys[0], v)
+	}
+	if v, ok := tr.Max(); !ok || !eq(v, keys[len(keys)-1]) {
+		t.Fatalf("expected '%v', got '%v'", keys[len(keys)-1], v)
+	}
+	if v, ok := tr.PopMin(); !ok || !eq(v, keys[0]) {
+		t.Fatalf("expected '%v', got '%v'", keys[0], v)
+	}
+	tr.sane()
+	if v, ok := tr.PopMax(); !ok || !eq(v, keys[len(keys)-1]) {
+		t.Fatalf("expected '%v', got '%v'", keys[len(keys)-1], v)
+	}
+	tr.sane()
+	tr.Set(keys[0])
+	tr.Set(keys[len(keys)-1])
+	shuffleItems(keys)
+	var hint bPathHint
+	for i := 0; i < len(keys); i++ {
+		if v, ok := tr.Get(keys[i]); !ok || !eq(v, keys[i]) {
+			t.Fatalf("expected '%v', got '%v'", keys[i], v)
+		}
+		if v, ok := tr.GetHint(keys[i], &hint); !ok || !eq(v, keys[i]) {
+			t.Fatalf("expected '%v', got '%v'", keys[i], v)
+		}
+	}
+	sortItems(keys)
+	for i := 0; i < len(keys); i++ {
+		if v, ok := tr.PopMin(); !ok || !eq(v, keys[i]) {
+			t.Fatalf("expected '%v', got '%v'", keys[i], v)
+		}
+	}
+	for i := 0; i < len(keys); i++ {
+		if v, ok := tr.Set(keys[i]); ok || !eq(v, tr.empty) {
+			t.Fatalf("expected nil")
+		}
+	}
+	for i := len(keys) - 1; i >= 0; i-- {
+		if v, ok := tr.PopMax(); !ok || !eq(v, keys[i]) {
+			t.Fatalf("expected '%v', got '%v'", keys[i], v)
+		}
+	}
+	for i := 0; i < len(keys); i++ {
+		if v, ok := tr.Set(keys[i]); ok || !eq(v, tr.empty) {
+			t.Fatalf("expected nil")
+		}
+	}
+	if v, ok := tr.Delete(testMakeItem(-1)); ok || !eq(v, tr.empty) {
+		t.Fatal("expected nil")
+	}
+	tr.sane()
+	shuffleItems(keys)
+	if v, ok := tr.Delete(keys[len(keys)/2]); !ok || !eq(v, keys[len(keys)/2]) {
+		t.Fatalf("expected '%v', got '%v'", keys[len(keys)/2], v)
+	}
+	tr.sane()
+	if v, ok := tr.Delete(keys[len(keys)/2]); ok || !eq(v, tr.empty) {
+		t.Fatalf("expected '%v', got '%v'", tr.empty, v)
+	}
+	tr.sane()
+	tr.Set(keys[len(keys)/2])
+	tr.sane()
+	for i := 0; i < len(keys); i++ {
+		if v, ok := tr.Delete(keys[i]); !ok || !eq(v, keys[i]) {
+			t.Fatalf("expected '%v', got '%v'", keys[i], v)
+		}
+		if v, ok := tr.Get(keys[i]); ok || !eq(v, tr.empty) {
+			t.Fatalf("expected nil")
+		}
+		if v, ok := tr.GetHint(keys[i], &hint); ok || !eq(v, tr.empty) {
+			t.Fatalf("expected nil")
+		}
+		if i%97 == 0 {
+			tr.sane()
+		}
+	}
+	if tr.Height() != 0 {
+		t.Fatalf("expected 0, got %d", tr.Height())
+	}
+	shuffleItems(keys)
+	for i := 0; i < len(keys); i++ {
+		if v, ok := tr.Load(keys[i]); ok || !eq(v, tr.empty) {
+			t.Fatalf("expected nil")
+		}
+		if i%97 == 0 {
+			tr.sane()
+		}
+	}
+	for i := 0; i < len(keys); i++ {
+		if v, ok := tr.Get(keys[i]); !ok || !eq(v, keys[i]) {
+			t.Fatalf("expected '%v', got '%v'", keys[i], v)
+		}
+	}
+	shuffleItems(keys)
+	for i := 0; i < len(keys); i++ {
+		if v, ok := tr.Delete(keys[i]); !ok || !eq(v, keys[i]) {
+			t.Fatalf("expected '%v', got '%v'", keys[i], v)
+		}
+		if v, ok := tr.Get(keys[i]); ok || !eq(v, tr.empty) {
+			t.Fatalf("expected nil")
+		}
+	}
+	sortItems(keys)
+	for i := 0; i < len(keys); i++ {
+		if v, ok := tr.Load(keys[i]); ok || !eq(v, tr.empty) {
+			t.Fatalf("expected nil")
+		}
+		if i%97 == 0 {
+			tr.sane()
+		}
+	}
+	shuffleItems(keys)
+	if v, ok := tr.Load(keys[0]); !ok || !eq(v, keys[0]) {
+		t.Fatalf("expected '%v', got '%v'", keys[0], v)
+	}
+	tr.sane()
+}
+
+func TestLess(t *testing.T) {
+	tr := testNewBTree()
+	if !tr.Less(testMakeItem(1), testMakeItem(2)) {
+		panic("invalid")
+	}
+	if tr.Less(testMakeItem(2), testMakeItem(1)) {
+		panic("invalid")
+	}
+	if tr.Less(testMakeItem(1), testMakeItem(1)) {
+		panic("invalid")
+	}
+}
+
+func TestDeleteRandom(t *testing.T) {
+	N := 2_000_000
+	tr := testNewBTree()
+	for i := 0; i < N; i++ {
+		tr.Load(testMakeItem(i))
+	}
+	tr.sane()
+	for tr.Len() > 0 {
+		var item kind
+		var ok bool
+		switch rand.Int() % 3 {
+		case 0:
+			item, ok = tr.GetAt(tr.Len() / 2)
+		case 1:
+			item, ok = tr.Min()
+		case 2:
+			item, ok = tr.Max()
+		}
+		if !ok {
+			panic("!")
+		}
+		v, ok := tr.Delete(item)
+		if !ok || !eq(v, item) {
+			panic("!")
+		}
+	}
+}
+
+func TestDeleteAt(t *testing.T) {
+	N := 10_000
+	tr := testNewBTree()
+	keys := randKeys(N)
+	for _, key := range keys {
+		tr.Set(key)
+	}
+	tr.sane()
+	for tr.Len() > 0 {
+		index := rand.Intn(tr.Len())
+		item1, ok1 := tr.GetAt(index)
+		item2, ok2 := tr.DeleteAt(index)
+		if !ok1 || !ok2 || !eq(item1, item2) {
+			panic("mismatch")
+		}
+		tr.sane()
+	}
+}
+
+func TestCopy(t *testing.T) {
+	items := randKeys(100000)
+	itemsM := testNewBTree()
+	for i := 0; i < len(items); i++ {
+		itemsM.Set(items[i])
+	}
+	tr := testNewBTree()
+	for i := 0; i < len(items); i++ {
+		tr.Set(items[i])
+	}
+	var wait int32
+	var testCopyDeep func(tr *bTree, parent bool)
+
+	testCopyDeep = func(tr *bTree, parent bool) {
+		defer func() { atomic.AddInt32(&wait, -1) }()
+		if parent {
+			// 2 grandchildren
+			for i := 0; i < 2; i++ {
+				atomic.AddInt32(&wait, 1)
+				go testCopyDeep(tr.Copy(), false)
+			}
+		}
+
+		items2 := make([]kind, 10000)
+		for i := 0; i < len(items2); i++ {
+			x := testMakeItem(rand.Int())
+			_, ok := itemsM.Get(x)
+			for ok {
+				x = testMakeItem(rand.Int())
+				_, ok = itemsM.Get(x)
+			}
+			items2[i] = x
+		}
+		for i := 0; i < len(items2); i++ {
+			if v, ok := tr.Set(items2[i]); ok || !eq(v, tr.empty) {
+				panic("!")
+			}
+		}
+		tr.sane()
+		if tr.Len() != len(items)+len(items2) {
+			panic("!")
+		}
+		for i := 0; i < len(items); i++ {
+			if v, ok := tr.Get(items[i]); !ok || !eq(v, items[i]) {
+				panic("!")
+			}
+		}
+		for i := 0; i < len(items2); i++ {
+			if v, ok := tr.Get(items2[i]); !ok || !eq(v, items2[i]) {
+				panic("!")
+			}
+		}
+
+		for i := 0; i < len(items); i++ {
+			if v, ok := tr.Delete(items[i]); !ok || !eq(v, items[i]) {
+				panic("!")
+			}
+		}
+		tr.sane()
+		if tr.Len() != len(items2) {
+			panic("!")
+		}
+		for i := 0; i < len(items2); i++ {
+			if v, ok := tr.Get(items2[i]); !ok || !eq(v, items2[i]) {
+				panic("!")
+			}
+		}
+		sortItems(items2)
+		var i int
+		for len(items2) > 0 {
+			if i%2 == 0 {
+				if v, ok := tr.PopMin(); !ok || !eq(v, items2[0]) {
+					panic("!")
+				}
+				items2 = items2[1:]
+			} else {
+				if v, ok := tr.PopMax(); !ok || !eq(v, items2[len(items2)-1]) {
+					panic("!")
+				}
+				items2 = items2[:len(items2)-1]
+			}
+			if i%123 == 0 {
+				tr.sane()
+				if tr.Len() != len(items2) {
+					panic("!")
+				}
+				for i := 0; i < len(items2); i++ {
+					if v, ok := tr.Get(items2[i]); !ok || !eq(v, items2[i]) {
+						panic("!")
+					}
+				}
+			}
+			i++
+		}
+		tr.sane()
+		if tr.Len() != len(items2) {
+			panic("!")
+		}
+	}
+
+	// 10 children
+	for i := 0; i < 10; i++ {
+		atomic.AddInt32(&wait, 1)
+		go testCopyDeep(tr.Copy(), true)
+	}
+
+	for atomic.LoadInt32(&wait) > 0 {
+		tr.sane()
+		if tr.Len() != len(items) {
+			panic("!")
+		}
+		for i := 0; i < len(items); i++ {
+			if v, ok := tr.Get(items[i]); !ok || !eq(v, items[i]) {
+				panic("!")
+			}
+		}
+		runtime.Gosched()
+	}
+}
+
+func TestVarious(t *testing.T) {
+	N := 1_000_000
+	tr := testNewBTree()
+	var hint bPathHint
+	for _, i := range randKeys(N) {
+		if v, ok := tr.SetHint(i, &hint); ok || !eq(v, tr.empty) {
+			panic("!")
+		}
+	}
+	for _, i := range randKeys(N) {
+		if v, ok := tr.GetHint(i, &hint); !ok || !eq(v, i) {
+			panic("!")
+		}
+	}
+	for _, i := range randKeys(N) {
+		if v, ok := tr.DeleteHint(i, &hint); !ok || !eq(v, i) {
+			panic("!")
+		}
+	}
+	if v, ok := tr.DeleteAt(0); ok || !eq(v, tr.empty) {
+		panic("!")
+	}
+	if v, ok := tr.GetAt(0); ok || !eq(v, tr.empty) {
+		panic("!")
+	}
+	for i := 0; i < N; i++ {
+		item := testMakeItem(i)
+		if v, ok := tr.SetHint(item, &hint); ok || !eq(v, tr.empty) {
+			panic("!")
+		}
+		item = testMakeItem(i)
+		if v, ok := tr.SetHint(item, &hint); !ok || !eq(v, item) {
+			panic("!")
+		}
+		item = testMakeItem(i)
+		if v, ok := tr.SetHint(item, &hint); !ok || !eq(v, item) {
+			panic("!")
+		}
+	}
+	for i := 0; i < N; i++ {
+		item := testMakeItem(i)
+		if v, ok := tr.GetHint(item, &hint); !ok || !eq(v, item) {
+			panic("!")
+		}
+	}
+	for i := 0; i < 100; i++ {
+		var count int
+		tr.Walk(func(_ []kind) bool {
+			if count == i {
+				return false
+			}
+			count++
+			return true
+		})
+	}
+
+	for i := 0; i < N; i++ {
+		item := testMakeItem(i)
+		if v, ok := tr.DeleteHint(item, &hint); !ok || !eq(v, item) {
+			panic("!")
+		}
+	}
+}
+
+func (tr *bTree) sane() {
+	if err := tr.Sane(); err != nil {
+		panic(err)
+	}
+}
+
+type saneError string
+
+func (err saneError) Error() string {
+	return string(err)
+}
+
+// btree_sane returns true if the entire btree and every node are valid.
+// - height of all leaves are the equal to the btree height.
+// - deep count matches the btree count.
+// - all nodes have the correct number of items and counts.
+// - all items are in order.
+func (tr *bTree) Sane() error {
+	if tr == nil {
+		return nil
+	}
+	if !tr.saneheight() {
+		return saneError("!sane-height")
+	}
+	if tr.Len() != tr.count || tr.deepcount() != tr.count {
+		return saneError("!sane-count")
+	}
+	if !tr.saneprops() {
+		return saneError("!sane-props")
+	}
+	if !tr.saneorder() {
+		return saneError("!sane-order")
+	}
+	if !tr.sanenils() {
+		return saneError("!sane-nils")
+	}
+	return nil
+}
+
+// btree_saneheight returns true if the height of all leaves match the height
+// of the btree.
+func (tr *bTree) saneheight() bool {
+	height := tr.Height()
+	if tr.root != nil {
+		if height == 0 {
+			return false
+		}
+		return tr.root.saneheight(1, height)
+	}
+	return height == 0
+}
+
+func (n *node) saneheight(height, maxheight int) bool {
+	if n.leaf() {
+		if height != maxheight {
+			return false
+		}
+	} else {
+		i := 0
+		for ; i < len(n.items); i++ {
+			if !(*n.children)[i].saneheight(height+1, maxheight) {
+				return false
+			}
+		}
+		if !(*n.children)[i].saneheight(height+1, maxheight) {
+			return false
+		}
+	}
+	return true
+}
+
+// btree_deepcount returns the number of items in the btree.
+func (tr *bTree) deepcount() int {
+	if tr.root != nil {
+		return tr.root.deepcount()
+	}
+	return 0
+}
+
+func (n *node) deepcount() int {
+	count := len(n.items)
+	if !n.leaf() {
+		for i := 0; i <= len(n.items); i++ {
+			count += (*n.children)[i].deepcount()
+		}
+	}
+	if n.count != count {
+		return -1
+	}
+	return count
+}
+
+func (tr *bTree) nodesaneprops(n *node, height int) bool {
+	if height == 1 {
+		if len(n.items) < 1 || len(n.items) > maxItems {
+			println(len(n.items) < 1)
+			return false
+		}
+	} else {
+		if len(n.items) < minItems || len(n.items) > maxItems {
+			println(2)
+			return false
+		}
+	}
+	if !n.leaf() {
+		if len(*n.children) != len(n.items)+1 {
+			println(3)
+			return false
+		}
+		for i := 0; i < len(n.items); i++ {
+			if !tr.nodesaneprops((*n.children)[i], height+1) {
+				println(4)
+				return false
+			}
+		}
+		if !tr.nodesaneprops((*n.children)[len(n.items)], height+1) {
+			println(5)
+			return false
+		}
+	}
+	return true
+}
+
+func (tr *bTree) saneprops() bool {
+	if tr.root != nil {
+		return tr.nodesaneprops(tr.root, 1)
+	}
+	return true
+}
+
+func (tr *bTree) sanenilsnode(n *node) bool {
+	items := n.items[:cap(n.items):cap(n.items)]
+	for i := len(n.items); i < len(items); i++ {
+		if items[i] != tr.empty {
+			return false
+		}
+	}
+	if !n.leaf() {
+		for i := 0; i < len(*n.children); i++ {
+			if (*n.children)[i] == nil {
+				return false
+			}
+		}
+		children := (*n.children)[:cap(*n.children):cap(*n.children)]
+		for i := len(*n.children); i < len(children); i++ {
+			if children[i] != nil {
+				return false
+			}
+		}
+		for i := 0; i < len(*n.children); i++ {
+			if !tr.sanenilsnode((*n.children)[i]) {
+				return false
+			}
+		}
+	}
+	return true
+}
+
+// sanenils checks that all the slots in the item slice that are not used,
+//   n.items[len(n.items):cap(n.items):cap(n.items)]
+// are equal to the empty value of the kind.
+func (tr *bTree) sanenils() bool {
+	if tr.root != nil {
+		return tr.sanenilsnode(tr.root)
+	}
+	return true
+}
+
+func (tr *bTree) saneorder() bool {
+	var last kind
+	var count int
+	var bad bool
+	tr.Walk(func(items []kind) bool {
+		for _, item := range items {
+			if count > 0 {
+				if !less(last, item, tr.ctx) {
+					bad = true
+					return false
+				}
+			}
+			last = item
+			count++
+		}
+		return true
+	})
+	return !bad && count == tr.count
+}
+
+func TestIter(t *testing.T) {
+	N := 100_000
+	tr := testNewBTree()
+	var all []kind
+	for i := 0; i < N; i++ {
+		tr.Load(testMakeItem(i))
+		all = append(all, testMakeItem(i))
+	}
+	var count int
+	var i int
+	iter := tr.Iter()
+	for ok := iter.First(); ok; ok = iter.Next() {
+		if !eq(all[i], iter.Item()) {
+			panic("!")
+		}
+		count++
+		i++
+	}
+	if count != N {
+		t.Fatalf("expected %v, got %v", N, count)
+	}
+	iter.Release()
+	count = 0
+	i = len(all) - 1
+	iter = tr.Iter()
+	for ok := iter.Last(); ok; ok = iter.Prev() {
+		if !eq(all[i], iter.Item()) {
+			panic("!")
+		}
+		i--
+		count++
+	}
+	if count != N {
+		t.Fatalf("expected %v, got %v", N, count)
+	}
+	iter.Release()
+	i = 0
+	iter = tr.Iter()
+	for ok := iter.First(); ok; ok = iter.Next() {
+		if !eq(all[i], iter.Item()) {
+			panic("!")
+		}
+		i++
+	}
+	i--
+	for ok := iter.Prev(); ok; ok = iter.Prev() {
+		i--
+		if !eq(all[i], iter.Item()) {
+			panic("!")
+		}
+
+	}
+	if i != 0 {
+		panic("!")
+	}
+
+	i++
+	for ok := iter.Next(); ok; ok = iter.Next() {
+		if !eq(all[i], iter.Item()) {
+			panic("!")
+		}
+		i++
+
+	}
+	if i != N {
+		panic("!")
+	}
+
+	i = 0
+	for ok := iter.First(); ok; ok = iter.Next() {
+		if !eq(all[i], iter.Item()) {
+			panic("!")
+		}
+		if eq(iter.Item(), testMakeItem(N/2)) {
+			for ok = iter.Prev(); ok; ok = iter.Prev() {
+				i--
+				if !eq(all[i], iter.Item()) {
+					panic("!")
+				}
+			}
+			break
+		}
+		i++
+	}
+	iter.Release()
+
+}