remove bptree

18 files changed, 0 insertions, 3421 deletions

diff --git a/weed/util/bptree/Makefile b/weed/util/bptree/Makefile
deleted file mode 100644
index a98f39a08..000000000
--- a/weed/util/bptree/Makefile
+++ /dev/null
@@ -1,6 +0,0 @@
-all: gen
-
-.PHONY : gen
-
-gen:
-	protoc bptree.proto --go_out=plugins=grpc:. --go_opt=paths=source_relative
diff --git a/weed/util/bptree/README.md b/weed/util/bptree/README.md
deleted file mode 100644
index 1dddae940..000000000
--- a/weed/util/bptree/README.md
+++ /dev/null
@@ -1,60 +0,0 @@
-This adapts one b+ tree implementation
-https://sourcegraph.com/github.com/timtadh/data-structures@master/-/tree/tree/bptree
-to persist changes to on disk.
-
-# When a node needs to persist itself?
-
-* A node changed its key or value
-    * When an item is added.
-    * When an item is updated.
-    * When an item is deleted.
-
-* When a node is split.
-    * 2 new nodes are created (they shoud persist themselves). 
-    * Parent node need to point to the new nodes. 
-
-* When a node is merged.
-    * delete one node
-    * persist the merged node
-
-
-In general, if one node is returned from a function, the node should have already been persisted.
-The parent node may need to delete the old node.
-
-BpTree
-  Add(key ItemKey, value ItemValue)
-    new_root = self.getRoot().put(key,value)
-      a, b, err := self.insert(key, value)
-        self.internal_insert(key, value)
-          self.internal_split(q.keys[0], q)
-            persist(a,b)
-          self.persist() // child add q node
-          self.maybePersist(child == p)
-        self.leaf_insert(key, value)
-          self.persist() // if dedup
-          self.leaf_split(key, value)
-            self.pure_leaf_split(key, value)
-              persist(a,b)
-              a.persist()
-              persist(a,b)
-            self.put_kv(key, value)
-      new_root.persist()
-    self.setRoot(new_root)
-      oldroot.destroy()
-    // maybe persist BpTree new root
-
-  Replace(key ItemKey, where WhereFunc, value ItemValue)
-    leaf.persist()
-  RemoveWhere(key ItemKey, where WhereFunc)
-    self.getRoot().remove(key, where)
-      self.internal_remove(key, nil, where)
-        child.leaf_remove(key, nil, where)
-        child.leaf_remove(key, sibling.keys[0], where)
-          l.destroy() // when the node is empty
-          a.maybePersist(hasChange)
-        self.destroy() // when no keys left
-        self.persist() // when some keys are left
-      self.leaf_remove(key, self.keys[len(self.keys)-1], where)
-    new_root.persist() // when new root is added
-    // maybe persist BpTree new root
-  
\ No newline at end of file
diff --git a/weed/util/bptree/bpmap.go b/weed/util/bptree/bpmap.go
deleted file mode 100644
index 0c13a132f..000000000
--- a/weed/util/bptree/bpmap.go
+++ /dev/null
@@ -1,69 +0,0 @@
-package bptree
-
-import (
-	"fmt"
-)
-
-/* A BpMap is a B+Tree with support for duplicate keys disabled. This makes it
- * behave like a regular Map rather than a MultiMap.
- */
-type BpMap BpTree
-
-func NewBpMap(node_size int, nodeStore NodeStore) *BpMap {
-	return &BpMap{
-		root: NewLeaf(node_size, nodeStore),
-	}
-}
-
-func (self *BpMap) Has(key ItemKey) bool {
-	return (*BpTree)(self).Has(key)
-}
-
-func (self *BpMap) Put(key ItemKey, value ItemValue) (err error) {
-	new_root, err := self.getRoot().put(key, value)
-	if err != nil {
-		return err
-	}
-	self.setRoot(new_root)
-	return nil
-}
-
-func (self *BpMap) Get(key ItemKey) (value ItemValue, err error) {
-	j, l := self.getRoot().get_start(key)
-	if l.keys[j].Equals(key) {
-		return l.values[j], nil
-	}
-	return nil, fmt.Errorf("key not found: %s", key)
-}
-
-func (self *BpMap) Remove(key ItemKey) (value ItemValue, err error) {
-	value, err = self.Get(key)
-	if err != nil {
-		return nil, err
-	}
-	ns := self.getRoot().Capacity()
-	new_root, err := self.getRoot().remove(key, func(value ItemValue) bool { return true })
-	if err != nil {
-		return nil, err
-	}
-	if new_root == nil {
-		new_root = NewLeaf(ns, self.root.nodeStore)
-		err = new_root.persist()
-		self.setRoot(new_root)
-	} else {
-		self.setRoot(new_root)
-	}
-	return value, nil
-}
-
-func (self *BpMap) Keys() (ki KIterator) {
-	return (*BpTree)(self).Keys()
-}
-
-func (self *BpMap) Values() (vi Iterator) {
-	return (*BpTree)(self).Values()
-}
-
-func (self *BpMap) Iterate() (kvi KVIterator) {
-	return (*BpTree)(self).Iterate()
-}
diff --git a/weed/util/bptree/bptree.go b/weed/util/bptree/bptree.go
deleted file mode 100644
index 141c595f3..000000000
--- a/weed/util/bptree/bptree.go
+++ /dev/null
@@ -1,158 +0,0 @@
-package bptree
-
-// started by copying from https://sourcegraph.com/github.com/timtadh/data-structures@master/-/tree/tree/bptree
-
-/* A BpTree is a B+Tree with support for duplicate keys. This makes it behave as
- * a MultiMap. Additionally you can use the Range operator to select k/v in a
- * range. If from > to it will iterate backwards.
- */
-type BpTree struct {
-	root *BpNode
-}
-
-type loc_iterator func() (i int, leaf *BpNode, li loc_iterator)
-
-func NewBpTree(node_size int, nodeStore NodeStore) *BpTree {
-	return &BpTree{
-		root: NewLeaf(node_size, nodeStore),
-	}
-}
-
-func (self *BpTree) Has(key ItemKey) bool {
-	if len(self.getRoot().keys) == 0 {
-		return false
-	}
-	j, l := self.getRoot().get_start(key)
-	return l.keys[j].Equals(key)
-}
-
-func (self *BpTree) Count(key ItemKey) int {
-	if len(self.root.keys) == 0 {
-		return 0
-	}
-	j, l := self.root.get_start(key)
-	count := 0
-	end := false
-	for !end && l.keys[j].Equals(key) {
-		count++
-		j, l, end = next_location(j, l)
-	}
-	return count
-}
-
-func (self *BpTree) Add(key ItemKey, value ItemValue) (err error) {
-	new_root, err := self.getRoot().put(key, value)
-	if err != nil {
-		return err
-	}
-	self.setRoot(new_root)
-	return nil
-}
-
-func (self *BpTree) Replace(key ItemKey, where WhereFunc, value ItemValue) (err error) {
-	li := self.getRoot().forward(key, key)
-	for i, leaf, next := li(); next != nil; i, leaf, next = next() {
-		if where(leaf.values[i]) {
-			leaf.values[i] = value
-			if persistErr := leaf.persist(); persistErr != nil && err == nil {
-				err = persistErr
-				break
-			}
-		}
-	}
-	return err
-}
-
-func (self *BpTree) Find(key ItemKey) (kvi KVIterator) {
-	return self.Range(key, key)
-}
-
-func (self *BpTree) Range(from, to ItemKey) (kvi KVIterator) {
-	var li loc_iterator
-	if !to.Less(from) {
-		li = self.getRoot().forward(from, to)
-	} else {
-		li = self.getRoot().backward(from, to)
-	}
-	kvi = func() (key ItemKey, value ItemValue, next KVIterator) {
-		var i int
-		var leaf *BpNode
-		i, leaf, li = li()
-		if li == nil {
-			return nil, nil, nil
-		}
-		return leaf.keys[i], leaf.values[i], kvi
-	}
-	return kvi
-}
-
-func (self *BpTree) RemoveWhere(key ItemKey, where WhereFunc) (err error) {
-	ns := self.getRoot().Capacity()
-	new_root, err := self.getRoot().remove(key, where)
-	if err != nil {
-		return err
-	}
-	if new_root == nil {
-		new_root = NewLeaf(ns, self.root.nodeStore)
-		err = new_root.persist()
-		self.setRoot(new_root)
-	} else {
-		self.setRoot(new_root)
-	}
-	return err
-}
-
-func (self *BpTree) Keys() (ki KIterator) {
-	li := self.getRoot().all()
-	var prev Equatable
-	ki = func() (key ItemKey, next KIterator) {
-		var i int
-		var leaf *BpNode
-		i, leaf, li = li()
-		if li == nil {
-			return nil, nil
-		}
-		if leaf.keys[i].Equals(prev) {
-			return ki()
-		}
-		prev = leaf.keys[i]
-		return leaf.keys[i], ki
-	}
-	return ki
-}
-
-func (self *BpTree) Values() (vi Iterator) {
-	return MakeValuesIterator(self)
-}
-
-func (self *BpTree) Items() (vi KIterator) {
-	return MakeItemsIterator(self)
-}
-
-func (self *BpTree) Iterate() (kvi KVIterator) {
-	li := self.getRoot().all()
-	kvi = func() (key ItemKey, value ItemValue, next KVIterator) {
-		var i int
-		var leaf *BpNode
-		i, leaf, li = li()
-		if li == nil {
-			return nil, nil, nil
-		}
-		return leaf.keys[i], leaf.values[i], kvi
-	}
-	return kvi
-}
-
-func (self *BpTree) Backward() (kvi KVIterator) {
-	li := self.getRoot().all_backward()
-	kvi = func() (key ItemKey, value ItemValue, next KVIterator) {
-		var i int
-		var leaf *BpNode
-		i, leaf, li = li()
-		if li == nil {
-			return nil, nil, nil
-		}
-		return leaf.keys[i], leaf.values[i], kvi
-	}
-	return kvi
-}
diff --git a/weed/util/bptree/bptree.pb.go b/weed/util/bptree/bptree.pb.go
deleted file mode 100644
index 078a54717..000000000
--- a/weed/util/bptree/bptree.pb.go
+++ /dev/null
@@ -1,195 +0,0 @@
-// Code generated by protoc-gen-go. DO NOT EDIT.
-// versions:
-// 	protoc-gen-go v1.25.0
-// 	protoc        v3.12.3
-// source: bptree.proto
-
-package bptree
-
-import (
-	proto "github.com/golang/protobuf/proto"
-	protoreflect "google.golang.org/protobuf/reflect/protoreflect"
-	protoimpl "google.golang.org/protobuf/runtime/protoimpl"
-	reflect "reflect"
-	sync "sync"
-)
-
-const (
-	// Verify that this generated code is sufficiently up-to-date.
-	_ = protoimpl.EnforceVersion(20 - protoimpl.MinVersion)
-	// Verify that runtime/protoimpl is sufficiently up-to-date.
-	_ = protoimpl.EnforceVersion(protoimpl.MaxVersion - 20)
-)
-
-// This is a compile-time assertion that a sufficiently up-to-date version
-// of the legacy proto package is being used.
-const _ = proto.ProtoPackageIsVersion4
-
-type ProtoNode struct {
-	state         protoimpl.MessageState
-	sizeCache     protoimpl.SizeCache
-	unknownFields protoimpl.UnknownFields
-
-	Keys     [][]byte `protobuf:"bytes,1,rep,name=keys,proto3" json:"keys,omitempty"`
-	Values   [][]byte `protobuf:"bytes,2,rep,name=values,proto3" json:"values,omitempty"`
-	Pointers []int64  `protobuf:"varint,3,rep,packed,name=pointers,proto3" json:"pointers,omitempty"`
-	Next     int64    `protobuf:"varint,4,opt,name=next,proto3" json:"next,omitempty"`
-	Prev     int64    `protobuf:"varint,5,opt,name=prev,proto3" json:"prev,omitempty"`
-	Id       int64    `protobuf:"varint,6,opt,name=id,proto3" json:"id,omitempty"`
-}
-
-func (x *ProtoNode) Reset() {
-	*x = ProtoNode{}
-	if protoimpl.UnsafeEnabled {
-		mi := &file_bptree_proto_msgTypes[0]
-		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
-		ms.StoreMessageInfo(mi)
-	}
-}
-
-func (x *ProtoNode) String() string {
-	return protoimpl.X.MessageStringOf(x)
-}
-
-func (*ProtoNode) ProtoMessage() {}
-
-func (x *ProtoNode) ProtoReflect() protoreflect.Message {
-	mi := &file_bptree_proto_msgTypes[0]
-	if protoimpl.UnsafeEnabled && x != nil {
-		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
-		if ms.LoadMessageInfo() == nil {
-			ms.StoreMessageInfo(mi)
-		}
-		return ms
-	}
-	return mi.MessageOf(x)
-}
-
-// Deprecated: Use ProtoNode.ProtoReflect.Descriptor instead.
-func (*ProtoNode) Descriptor() ([]byte, []int) {
-	return file_bptree_proto_rawDescGZIP(), []int{0}
-}
-
-func (x *ProtoNode) GetKeys() [][]byte {
-	if x != nil {
-		return x.Keys
-	}
-	return nil
-}
-
-func (x *ProtoNode) GetValues() [][]byte {
-	if x != nil {
-		return x.Values
-	}
-	return nil
-}
-
-func (x *ProtoNode) GetPointers() []int64 {
-	if x != nil {
-		return x.Pointers
-	}
-	return nil
-}
-
-func (x *ProtoNode) GetNext() int64 {
-	if x != nil {
-		return x.Next
-	}
-	return 0
-}
-
-func (x *ProtoNode) GetPrev() int64 {
-	if x != nil {
-		return x.Prev
-	}
-	return 0
-}
-
-func (x *ProtoNode) GetId() int64 {
-	if x != nil {
-		return x.Id
-	}
-	return 0
-}
-
-var File_bptree_proto protoreflect.FileDescriptor
-
-var file_bptree_proto_rawDesc = []byte{
-	0x0a, 0x0c, 0x62, 0x70, 0x74, 0x72, 0x65, 0x65, 0x2e, 0x70, 0x72, 0x6f, 0x74, 0x6f, 0x12, 0x06,
-	0x62, 0x70, 0x74, 0x72, 0x65, 0x65, 0x22, 0x8b, 0x01, 0x0a, 0x09, 0x50, 0x72, 0x6f, 0x74, 0x6f,
-	0x4e, 0x6f, 0x64, 0x65, 0x12, 0x12, 0x0a, 0x04, 0x6b, 0x65, 0x79, 0x73, 0x18, 0x01, 0x20, 0x03,
-	0x28, 0x0c, 0x52, 0x04, 0x6b, 0x65, 0x79, 0x73, 0x12, 0x16, 0x0a, 0x06, 0x76, 0x61, 0x6c, 0x75,
-	0x65, 0x73, 0x18, 0x02, 0x20, 0x03, 0x28, 0x0c, 0x52, 0x06, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x73,
-	0x12, 0x1a, 0x0a, 0x08, 0x70, 0x6f, 0x69, 0x6e, 0x74, 0x65, 0x72, 0x73, 0x18, 0x03, 0x20, 0x03,
-	0x28, 0x03, 0x52, 0x08, 0x70, 0x6f, 0x69, 0x6e, 0x74, 0x65, 0x72, 0x73, 0x12, 0x12, 0x0a, 0x04,
-	0x6e, 0x65, 0x78, 0x74, 0x18, 0x04, 0x20, 0x01, 0x28, 0x03, 0x52, 0x04, 0x6e, 0x65, 0x78, 0x74,
-	0x12, 0x12, 0x0a, 0x04, 0x70, 0x72, 0x65, 0x76, 0x18, 0x05, 0x20, 0x01, 0x28, 0x03, 0x52, 0x04,
-	0x70, 0x72, 0x65, 0x76, 0x12, 0x0e, 0x0a, 0x02, 0x69, 0x64, 0x18, 0x06, 0x20, 0x01, 0x28, 0x03,
-	0x52, 0x02, 0x69, 0x64, 0x42, 0x31, 0x5a, 0x2f, 0x67, 0x69, 0x74, 0x68, 0x75, 0x62, 0x2e, 0x63,
-	0x6f, 0x6d, 0x2f, 0x63, 0x68, 0x72, 0x69, 0x73, 0x6c, 0x75, 0x73, 0x66, 0x2f, 0x73, 0x65, 0x61,
-	0x77, 0x65, 0x65, 0x64, 0x66, 0x73, 0x2f, 0x77, 0x65, 0x65, 0x64, 0x2f, 0x75, 0x74, 0x69, 0x6c,
-	0x2f, 0x62, 0x70, 0x74, 0x72, 0x65, 0x65, 0x62, 0x06, 0x70, 0x72, 0x6f, 0x74, 0x6f, 0x33,
-}
-
-var (
-	file_bptree_proto_rawDescOnce sync.Once
-	file_bptree_proto_rawDescData = file_bptree_proto_rawDesc
-)
-
-func file_bptree_proto_rawDescGZIP() []byte {
-	file_bptree_proto_rawDescOnce.Do(func() {
-		file_bptree_proto_rawDescData = protoimpl.X.CompressGZIP(file_bptree_proto_rawDescData)
-	})
-	return file_bptree_proto_rawDescData
-}
-
-var file_bptree_proto_msgTypes = make([]protoimpl.MessageInfo, 1)
-var file_bptree_proto_goTypes = []interface{}{
-	(*ProtoNode)(nil), // 0: bptree.ProtoNode
-}
-var file_bptree_proto_depIdxs = []int32{
-	0, // [0:0] is the sub-list for method output_type
-	0, // [0:0] is the sub-list for method input_type
-	0, // [0:0] is the sub-list for extension type_name
-	0, // [0:0] is the sub-list for extension extendee
-	0, // [0:0] is the sub-list for field type_name
-}
-
-func init() { file_bptree_proto_init() }
-func file_bptree_proto_init() {
-	if File_bptree_proto != nil {
-		return
-	}
-	if !protoimpl.UnsafeEnabled {
-		file_bptree_proto_msgTypes[0].Exporter = func(v interface{}, i int) interface{} {
-			switch v := v.(*ProtoNode); i {
-			case 0:
-				return &v.state
-			case 1:
-				return &v.sizeCache
-			case 2:
-				return &v.unknownFields
-			default:
-				return nil
-			}
-		}
-	}
-	type x struct{}
-	out := protoimpl.TypeBuilder{
-		File: protoimpl.DescBuilder{
-			GoPackagePath: reflect.TypeOf(x{}).PkgPath(),
-			RawDescriptor: file_bptree_proto_rawDesc,
-			NumEnums:      0,
-			NumMessages:   1,
-			NumExtensions: 0,
-			NumServices:   0,
-		},
-		GoTypes:           file_bptree_proto_goTypes,
-		DependencyIndexes: file_bptree_proto_depIdxs,
-		MessageInfos:      file_bptree_proto_msgTypes,
-	}.Build()
-	File_bptree_proto = out.File
-	file_bptree_proto_rawDesc = nil
-	file_bptree_proto_goTypes = nil
-	file_bptree_proto_depIdxs = nil
-}
diff --git a/weed/util/bptree/bptree.proto b/weed/util/bptree/bptree.proto
deleted file mode 100644
index 1d55096a2..000000000
--- a/weed/util/bptree/bptree.proto
+++ /dev/null
@@ -1,14 +0,0 @@
-syntax = "proto3";
-
-package bptree;
-
-option go_package = "github.com/chrislusf/seaweedfs/weed/util/bptree";
-
-message ProtoNode {
-  repeated bytes keys = 1;
-  repeated bytes values = 2;
-  repeated int64 pointers = 3;
-  int64 next = 4;
-  int64 prev = 5;
-  int64 id = 6;
-}
diff --git a/weed/util/bptree/bptree_node.go b/weed/util/bptree/bptree_node.go
deleted file mode 100644
index 507d9d318..000000000
--- a/weed/util/bptree/bptree_node.go
+++ /dev/null
@@ -1,767 +0,0 @@
-package bptree
-
-type ItemKey Hashable
-type ItemValue Equatable
-
-type NodeStore interface {
-	PersistFunc(node *BpNode) error
-	DestroyFunc(node *BpNode) error
-}
-
-type BpNode struct {
-	keys        []ItemKey
-	values      []ItemValue
-	pointers    []*BpNode
-	next        *BpNode
-	prev        *BpNode
-	protoNodeId int64
-	protoNode   *ProtoNode
-	nodeStore   NodeStore
-}
-
-func NewInternal(size int, nodeStore NodeStore) *BpNode {
-	if size < 0 {
-		panic(NegativeSize())
-	}
-	return &BpNode{
-		keys:        make([]ItemKey, 0, size),
-		pointers:    make([]*BpNode, 0, size),
-		protoNodeId: GetProtoNodeId(),
-		nodeStore:   nodeStore,
-	}
-}
-
-func NewLeaf(size int, nodeStore NodeStore) *BpNode {
-	if size < 0 {
-		panic(NegativeSize())
-	}
-	return &BpNode{
-		keys:        make([]ItemKey, 0, size),
-		values:      make([]ItemValue, 0, size),
-		protoNodeId: GetProtoNodeId(),
-		nodeStore:   nodeStore,
-	}
-}
-
-func (self *BpNode) Full() bool {
-	return len(self.keys) == cap(self.keys)
-}
-
-func (self *BpNode) Pure() bool {
-	if len(self.keys) == 0 {
-		return true
-	}
-	k0 := self.keys[0]
-	for _, k := range self.keys {
-		if !k0.Equals(k) {
-			return false
-		}
-	}
-	return true
-}
-
-func (self *BpNode) Internal() bool {
-	return cap(self.pointers) > 0
-}
-
-func (self *BpNode) Len() int {
-	return len(self.keys)
-}
-
-func (self *BpNode) Capacity() int {
-	return cap(self.keys)
-}
-
-func (self *BpNode) Height() int {
-	if !self.Internal() {
-		return 1
-	} else if len(self.pointers) == 0 {
-		panic(BpTreeError("Internal node has no pointers but asked for height"))
-	}
-	return self.pointers[0].Height() + 1
-}
-
-func (self *BpNode) has(key ItemKey) bool {
-	_, has := self.find(key)
-	return has
-}
-
-func (self *BpNode) left_most_leaf() *BpNode {
-	if self.Internal() {
-		return self.pointers[0].left_most_leaf()
-	}
-	return self
-}
-
-func (self *BpNode) right_most_leaf() *BpNode {
-	if self.Internal() {
-		return self.pointers[len(self.pointers)-1].right_most_leaf()
-	}
-	return self
-}
-
-/* returns the index and leaf-block of the first key greater than or equal to
- * the search key. (unless the search key is greater than all the keys in the
- * tree, in that case it will be the last key in the tree)
- */
-func (self *BpNode) get_start(key ItemKey) (i int, leaf *BpNode) {
-	if self.Internal() {
-		return self.internal_get_start(key)
-	} else {
-		return self.leaf_get_start(key)
-	}
-}
-
-func next_location(i int, leaf *BpNode) (int, *BpNode, bool) {
-	j := i + 1
-	for j >= len(leaf.keys) && leaf.getNext() != nil {
-		j = 0
-		leaf = leaf.getNext()
-	}
-	if j >= len(leaf.keys) {
-		return -1, nil, true
-	}
-	return j, leaf, false
-}
-
-func prev_location(i int, leaf *BpNode) (int, *BpNode, bool) {
-	j := i - 1
-	for j < 0 && leaf.getPrev() != nil {
-		leaf = leaf.getPrev()
-		j = len(leaf.keys) - 1
-	}
-	if j < 0 {
-		return -1, nil, true
-	}
-	return j, leaf, false
-}
-
-/* returns the index and leaf-block of the last key equal to the search key or
- * the first key greater than the search key. (unless the search key is greater
- * than all the keys in the tree, in that case it will be the last key in the
- * tree)
- */
-func (self *BpNode) get_end(key ItemKey) (i int, leaf *BpNode) {
-	end := false
-	i, leaf = self.get_start(key)
-	pi, pleaf := i, leaf
-	for !end && leaf.keys[i].Equals(key) {
-		pi, pleaf = i, leaf
-		i, leaf, end = next_location(i, leaf)
-	}
-	return pi, pleaf
-}
-
-func (self *BpNode) internal_get_start(key ItemKey) (i int, leaf *BpNode) {
-	if !self.Internal() {
-		panic(BpTreeError("Expected a internal node"))
-	}
-	i, has := self.find(key)
-	if !has && i > 0 {
-		// if it doesn't have it and the index > 0 then we have the next block
-		// so we have to subtract one from the index.
-		i--
-	}
-	child := self.pointers[i]
-	return child.get_start(key)
-}
-
-func (self *BpNode) leaf_get_start(key ItemKey) (i int, leaf *BpNode) {
-	i, has := self.find(key)
-	if i >= len(self.keys) && i > 0 {
-		i = len(self.keys) - 1
-	}
-	if !has && (len(self.keys) == 0 || self.keys[i].Less(key)) && self.getNext() != nil {
-		return self.getNext().leaf_get_start(key)
-	}
-	return i, self
-}
-
-/* This puts the k/v pair into the B+Tree rooted at this node and returns the
- * (possibly) new root of the tree.
- */
-func (self *BpNode) put(key ItemKey, value ItemValue) (root *BpNode, err error) {
-	a, b, err := self.insert(key, value)
-	if err != nil {
-		return nil, err
-	} else if b == nil {
-		return a, nil
-	}
-	// else we have root split
-	root = NewInternal(self.Capacity(), self.nodeStore)
-	root.put_kp(a.keys[0], a)
-	root.put_kp(b.keys[0], b)
-	return root, root.persist()
-}
-
-// right is only set on split
-// left is always set. When split is false left is the pointer to block
-//                     When split is true left is the pointer to the new left
-//                     block
-func (self *BpNode) insert(key ItemKey, value ItemValue) (a, b *BpNode, err error) {
-	if self.Internal() {
-		return self.internal_insert(key, value)
-	} else { // leaf node
-		return self.leaf_insert(key, value)
-	}
-}
-
-/* - first find the child to insert into
- * - do the child insert
- * - if there was a split:
- *    - if the block is full, split this block
- *    - else insert the new key/pointer into this block
- */
-func (self *BpNode) internal_insert(key ItemKey, value ItemValue) (a, b *BpNode, err error) {
-	if !self.Internal() {
-		return nil, nil, BpTreeError("Expected a internal node")
-	}
-	i, has := self.find(key)
-	if !has && i > 0 {
-		// if it doesn't have it and the index > 0 then we have the next block
-		// so we have to subtract one from the index.
-		i--
-	}
-	child := self.pointers[i]
-	p, q, err := child.insert(key, value)
-	if err != nil {
-		return nil, nil, err
-	}
-	self.keys[i] = p.keys[0]
-	self.pointers[i] = p
-	if q != nil {
-		// we had a split
-		if self.Full() {
-			return self.internal_split(q.keys[0], q)
-		} else {
-			if err := self.put_kp(q.keys[0], q); err != nil {
-				return nil, nil, err
-			}
-			return self, nil, self.persist()
-		}
-	}
-	return self, nil, self.maybePersist(child != p)
-}
-
-/* On split
- * - first assert that the key to be inserted is not already in the block.
- * - Make a new block
- * - balance the two blocks.
- * - insert the new key/pointer combo into the correct block
- */
-func (self *BpNode) internal_split(key ItemKey, ptr *BpNode) (a, b *BpNode, err error) {
-	if !self.Internal() {
-		return nil, nil, BpTreeError("Expected a internal node")
-	}
-	if self.has(key) {
-		return nil, nil, BpTreeError("Tried to split an internal block on duplicate key")
-	}
-	a = self
-	b = NewInternal(self.Capacity(), self.nodeStore)
-	balance_nodes(a, b, key)
-	if b.Len() > 0 && key.Less(b.keys[0]) {
-		if err := a.put_kp(key, ptr); err != nil {
-			return nil, nil, err
-		}
-	} else {
-		if err := b.put_kp(key, ptr); err != nil {
-			return nil, nil, err
-		}
-	}
-	return a, b, persist(a, b)
-}
-
-/* if the leaf is full then it will defer to a leaf_split
- *    (but in one case that will not actually split in the case of a insert into
- *    a pure block with a matching key)
- * else this leaf will get a new entry.
- */
-func (self *BpNode) leaf_insert(key ItemKey, value ItemValue) (a, b *BpNode, err error) {
-	if self.Internal() {
-		return nil, nil, BpTreeError("Expected a leaf node")
-	}
-	if true { // no_dup = true
-		i, has := self.find(key)
-		if has {
-			self.values[i] = value
-			return self, nil, self.persist()
-		}
-	}
-	if self.Full() {
-		return self.leaf_split(key, value)
-	} else {
-		if err := self.put_kv(key, value); err != nil {
-			return nil, nil, err
-		}
-		return self, nil, self.persist()
-	}
-}
-
-/* on leaf split if the block is pure then it will defer to pure_leaf_split
- * else
- *    - a new block will be made and inserted after this one
- *    - the two blocks will be balanced with balanced_nodes
- *    - if the key is less than b.keys[0] it will go in a else b
- */
-func (self *BpNode) leaf_split(key ItemKey, value ItemValue) (a, b *BpNode, err error) {
-	if self.Internal() {
-		return nil, nil, BpTreeError("Expected a leaf node")
-	}
-	if self.Pure() {
-		return self.pure_leaf_split(key, value)
-	}
-	a = self
-	b = NewLeaf(self.Capacity(), self.nodeStore)
-	insert_linked_list_node(b, a, a.getNext())
-	balance_nodes(a, b, key)
-	if b.Len() > 0 && key.Less(b.keys[0]) {
-		if err := a.put_kv(key, value); err != nil {
-			return nil, nil, err
-		}
-	} else {
-		if err := b.put_kv(key, value); err != nil {
-			return nil, nil, err
-		}
-	}
-	return a, b, persist(a, b)
-}
-
-/* a pure leaf split has two cases:
- *  1) the inserted key is less than the current pure block.
- *     - a new block should be created before the current block
- *     - the key should be put in it
- *  2) the inserted key is greater than or equal to the pure block.
- *     - the end of run of pure blocks should be found
- *     - if the key is equal to pure block and the last block is not full insert
- *       the new kv
- *     - else split by making a new block after the last block in the run
- *       and putting the new key there.
- *     - always return the current block as "a" and the new block as "b"
- */
-func (self *BpNode) pure_leaf_split(key ItemKey, value ItemValue) (a, b *BpNode, err error) {
-	if self.Internal() || !self.Pure() {
-		return nil, nil, BpTreeError("Expected a pure leaf node")
-	}
-	if key.Less(self.keys[0]) {
-		a = NewLeaf(self.Capacity(), self.nodeStore)
-		b = self
-		if err := a.put_kv(key, value); err != nil {
-			return nil, nil, err
-		}
-		insert_linked_list_node(a, b.getPrev(), b)
-		return a, b, persist(a, b)
-	} else {
-		a = self
-		e := self.find_end_of_pure_run()
-		if e.keys[0].Equals(key) && !e.Full() {
-			if err := e.put_kv(key, value); err != nil {
-				return nil, nil, err
-			}
-			return a, nil, a.persist()
-		} else {
-			b = NewLeaf(self.Capacity(), self.nodeStore)
-			if err := b.put_kv(key, value); err != nil {
-				return nil, nil, err
-			}
-			insert_linked_list_node(b, e, e.getNext())
-			if e.keys[0].Equals(key) {
-				return a, nil, nil
-			}
-			return a, b, persist(a, b)
-		}
-	}
-}
-
-func (self *BpNode) put_kp(key ItemKey, ptr *BpNode) error {
-	if self.Full() {
-		return BpTreeError("Block is full.")
-	}
-	if !self.Internal() {
-		return BpTreeError("Expected a internal node")
-	}
-	i, has := self.find(key)
-	if has {
-		return BpTreeError("Tried to insert a duplicate key into an internal node")
-	} else if i < 0 {
-		panic(BpTreeError("find returned a negative int"))
-	} else if i >= cap(self.keys) {
-		panic(BpTreeError("find returned a int > than cap(keys)"))
-	}
-	if err := self.put_key_at(i, key); err != nil {
-		return err
-	}
-	if err := self.put_pointer_at(i, ptr); err != nil {
-		return err
-	}
-	return nil
-}
-
-func (self *BpNode) put_kv(key ItemKey, value ItemValue) error {
-	if self.Full() {
-		return BpTreeError("Block is full.")
-	}
-	if self.Internal() {
-		return BpTreeError("Expected a leaf node")
-	}
-	i, _ := self.find(key)
-	if i < 0 {
-		panic(BpTreeError("find returned a negative int"))
-	} else if i >= cap(self.keys) {
-		panic(BpTreeError("find returned a int > than cap(keys)"))
-	}
-	if err := self.put_key_at(i, key); err != nil {
-		return err
-	}
-	if err := self.put_value_at(i, value); err != nil {
-		return err
-	}
-	return nil
-}
-
-func (self *BpNode) put_key_at(i int, key ItemKey) error {
-	if self.Full() {
-		return BpTreeError("Block is full.")
-	}
-	self.keys = self.keys[:len(self.keys)+1]
-	for j := len(self.keys) - 1; j > i; j-- {
-		self.keys[j] = self.keys[j-1]
-	}
-	self.keys[i] = key
-	return nil
-}
-
-func (self *BpNode) put_value_at(i int, value ItemValue) error {
-	if len(self.values) == cap(self.values) {
-		return BpTreeError("Block is full.")
-	}
-	if self.Internal() {
-		return BpTreeError("Expected a leaf node")
-	}
-	self.values = self.values[:len(self.values)+1]
-	for j := len(self.values) - 1; j > i; j-- {
-		self.values[j] = self.values[j-1]
-	}
-	self.values[i] = value
-	return nil
-}
-
-func (self *BpNode) put_pointer_at(i int, pointer *BpNode) error {
-	if len(self.pointers) == cap(self.pointers) {
-		return BpTreeError("Block is full.")
-	}
-	if !self.Internal() {
-		return BpTreeError("Expected a internal node")
-	}
-	self.pointers = self.pointers[:len(self.pointers)+1]
-	for j := len(self.pointers) - 1; j > i; j-- {
-		self.pointers[j] = self.pointers[j-1]
-	}
-	self.pointers[i] = pointer
-	return nil
-}
-
-func (self *BpNode) remove(key ItemKey, where WhereFunc) (a *BpNode, err error) {
-	if self.Internal() {
-		return self.internal_remove(key, nil, where)
-	} else {
-		return self.leaf_remove(key, self.keys[len(self.keys)-1], where)
-	}
-}
-
-func (self *BpNode) internal_remove(key ItemKey, sibling *BpNode, where WhereFunc) (a *BpNode, err error) {
-	if !self.Internal() {
-		panic(BpTreeError("Expected a internal node"))
-	}
-	i, has := self.find(key)
-	if !has && i > 0 {
-		// if it doesn't have it and the index > 0 then we have the next block
-		// so we have to subtract one from the index.
-		i--
-	}
-	if i+1 < len(self.keys) {
-		sibling = self.pointers[i+1]
-	} else if sibling != nil {
-		sibling = sibling.left_most_leaf()
-	}
-	child := self.pointers[i]
-	oldChild := child
-	if child.Internal() {
-		child, err = child.internal_remove(key, sibling, where)
-	} else {
-		if sibling == nil {
-			child, err = child.leaf_remove(key, nil, where)
-		} else {
-			child, err = child.leaf_remove(key, sibling.keys[0], where)
-		}
-	}
-	if err != nil {
-		return nil, err
-	}
-	if child == nil {
-		if err := self.remove_key_at(i); err != nil {
-			return nil, err
-		}
-		if err := self.remove_ptr_at(i); err != nil {
-			return nil, err
-		}
-	} else {
-		self.keys[i] = child.keys[0]
-		self.pointers[i] = child
-	}
-	if len(self.keys) == 0 {
-		return nil, self.destroy()
-	}
-	return self, self.maybePersist(oldChild != child)
-}
-
-func (self *BpNode) leaf_remove(key, stop ItemKey, where WhereFunc) (a *BpNode, err error) {
-	if self.Internal() {
-		return nil, BpTreeError("Expected a leaf node")
-	}
-	a = self
-	hasChange := false
-	for j, l, next := self.forward(key, key)(); next != nil; j, l, next = next() {
-		if where(l.values[j]) {
-			hasChange = true
-			if err := l.remove_key_at(j); err != nil {
-				return nil, err
-			}
-			if err := l.remove_value_at(j); err != nil {
-				return nil, err
-			}
-		}
-		if len(l.keys) == 0 {
-			remove_linked_list_node(l)
-			if l.getNext() == nil {
-				a = nil
-			} else if stop == nil {
-				a = nil
-			} else if !l.getNext().keys[0].Equals(stop) {
-				a = l.getNext()
-			} else {
-				a = nil
-			}
-			if err := l.destroy(); err != nil {
-				return nil, err
-			}
-		}
-	}
-	if a != nil {
-		return a, a.maybePersist(hasChange)
-	}
-	return a, nil
-}
-
-func (self *BpNode) remove_key_at(i int) error {
-	if i >= len(self.keys) || i < 0 {
-		return BpTreeError("i, %v, is out of bounds, %v, %v %v.", i, len(self.keys), len(self.values), self)
-	}
-	for j := i; j < len(self.keys)-1; j++ {
-		self.keys[j] = self.keys[j+1]
-	}
-	self.keys = self.keys[:len(self.keys)-1]
-	return nil
-}
-
-func (self *BpNode) remove_value_at(i int) error {
-	if i >= len(self.values) || i < 0 {
-		return BpTreeError("i, %v, is out of bounds, %v.", i, len(self.values))
-	}
-	for j := i; j < len(self.values)-1; j++ {
-		self.values[j] = self.values[j+1]
-	}
-	self.values = self.values[:len(self.values)-1]
-	return nil
-}
-
-func (self *BpNode) remove_ptr_at(i int) error {
-	if i >= len(self.pointers) || i < 0 {
-		return BpTreeError("i, %v, is out of bounds, %v.", i, len(self.pointers))
-	}
-	for j := i; j < len(self.pointers)-1; j++ {
-		self.pointers[j] = self.pointers[j+1]
-	}
-	self.pointers = self.pointers[:len(self.pointers)-1]
-	return nil
-}
-
-func (self *BpNode) find(key ItemKey) (int, bool) {
-	var l = 0
-	var r = len(self.keys) - 1
-	var m int
-	for l <= r {
-		m = ((r - l) >> 1) + l
-		if key.Less(self.keys[m]) {
-			r = m - 1
-		} else if key.Equals(self.keys[m]) {
-			return m, true
-		} else {
-			l = m + 1
-		}
-	}
-	return l, false
-}
-
-func (self *BpNode) find_end_of_pure_run() *BpNode {
-	k := self.keys[0]
-	p := self
-	n := self.getNext()
-	for n != nil && n.Pure() && k.Equals(n.keys[0]) {
-		p = n
-		n = n.getNext()
-	}
-	return p
-}
-
-func (self *BpNode) all() (li loc_iterator) {
-	j := -1
-	l := self.left_most_leaf()
-	end := false
-	j, l, end = next_location(j, l)
-	li = func() (i int, leaf *BpNode, next loc_iterator) {
-		if end {
-			return -1, nil, nil
-		}
-		i = j
-		leaf = l
-		j, l, end = next_location(j, l)
-		return i, leaf, li
-	}
-	return li
-}
-
-func (self *BpNode) all_backward() (li loc_iterator) {
-	l := self.right_most_leaf()
-	j := len(l.keys)
-	end := false
-	j, l, end = prev_location(j, l)
-	li = func() (i int, leaf *BpNode, next loc_iterator) {
-		if end {
-			return -1, nil, nil
-		}
-		i = j
-		leaf = l
-		j, l, end = prev_location(j, l)
-		return i, leaf, li
-	}
-	return li
-}
-
-func (self *BpNode) forward(from, to ItemKey) (li loc_iterator) {
-	j, l := self.get_start(from)
-	end := false
-	j--
-	li = func() (i int, leaf *BpNode, next loc_iterator) {
-		j, l, end = next_location(j, l)
-		if end || to.Less(l.keys[j]) {
-			return -1, nil, nil
-		}
-		return j, l, li
-	}
-	return li
-}
-
-func (self *BpNode) backward(from, to ItemKey) (li loc_iterator) {
-	j, l := self.get_end(from)
-	end := false
-	li = func() (i int, leaf *BpNode, next loc_iterator) {
-		if end || l.keys[j].Less(to) {
-			return -1, nil, nil
-		}
-		i = j
-		leaf = l
-		j, l, end = prev_location(i, l)
-		return i, leaf, li
-	}
-	return li
-}
-
-func insert_linked_list_node(n, prev, next *BpNode) {
-	if (prev != nil && prev.getNext() != next) || (next != nil && next.getPrev() != prev) {
-		panic(BpTreeError("prev and next not hooked up"))
-	}
-	n.setPrev(prev)
-	n.setNext(next)
-	if prev != nil {
-		prev.setNext(n)
-	}
-	if next != nil {
-		next.setPrev(n)
-	}
-}
-
-func remove_linked_list_node(n *BpNode) {
-	if n.getPrev() != nil {
-		n.getPrev().setNext(n.getNext())
-	}
-	if n.getNext() != nil {
-		n.getNext().setPrev(n.getPrev())
-	}
-}
-
-/**
- * a must be full and b must be empty else there will be a panic
- *
- * Different from common btree implementation, this splits the nodes by the inserted key.
- * Items less than the splitKey stays in a, or moved to b if otherwise.
- * This should help for monotonically increasing inserts.
- *
- */
-func balance_nodes(a, b *BpNode, splitKey ItemKey) {
-	if len(b.keys) != 0 {
-		panic(BpTreeError("b was not empty"))
-	}
-	if !a.Full() {
-		panic(BpTreeError("a was not full", a))
-	}
-	if cap(a.keys) != cap(b.keys) {
-		panic(BpTreeError("cap(a.keys) != cap(b.keys)"))
-	}
-	if cap(a.values) != cap(b.values) {
-		panic(BpTreeError("cap(a.values) != cap(b.values)"))
-	}
-	if cap(a.pointers) != cap(b.pointers) {
-		panic(BpTreeError("cap(a.pointers) != cap(b.pointers)"))
-	}
-
-	m := find_split_index(a, b, splitKey)
-	var lim = len(a.keys) - m
-	b.keys = b.keys[:lim]
-	if cap(a.values) > 0 {
-		if cap(a.values) != cap(a.keys) {
-			panic(BpTreeError("cap(a.values) != cap(a.keys)"))
-		}
-		b.values = b.values[:lim]
-	}
-	if cap(a.pointers) > 0 {
-		if cap(a.pointers) != cap(a.keys) {
-			panic(BpTreeError("cap(a.pointers) != cap(a.keys)"))
-		}
-		b.pointers = b.pointers[:lim]
-	}
-	for i := 0; i < lim; i++ {
-		j := m + i
-		b.keys[i] = a.keys[j]
-		if cap(a.values) > 0 {
-			b.values[i] = a.values[j]
-		}
-		if cap(a.pointers) > 0 {
-			b.pointers[i] = a.pointers[j]
-		}
-	}
-	a.keys = a.keys[:m]
-	if cap(a.values) > 0 {
-		a.values = a.values[:m]
-	}
-	if cap(a.pointers) > 0 {
-		a.pointers = a.pointers[:m]
-	}
-}
-
-func find_split_index(a, b *BpNode, splitKey ItemKey) int {
-	m := len(a.keys)
-	for m > 0 && !a.keys[m-1].Less(splitKey) {
-		m--
-	}
-	return m
-}
diff --git a/weed/util/bptree/bptree_store_test.go b/weed/util/bptree/bptree_store_test.go
deleted file mode 100644
index 2e034171c..000000000
--- a/weed/util/bptree/bptree_store_test.go
+++ /dev/null
@@ -1,53 +0,0 @@
-package bptree
-
-import (
-	"fmt"
-	"testing"
-)
-
-type nodeStorePrintlnImpl struct {
-}
-
-func (n *nodeStorePrintlnImpl) PersistFunc(node *BpNode) error {
-	println("saving node", node.protoNodeId)
-	return nil
-}
-func (n *nodeStorePrintlnImpl) DestroyFunc(node *BpNode) error {
-	println("delete node", node.protoNodeId)
-	return nil
-}
-
-func TestAddRemove(t *testing.T) {
-
-	tree := NewBpTree(3, &nodeStorePrintlnImpl{})
-	for i:=0;i<9;i++{
-		println("++++++++++", i)
-		tree.Add(String(fmt.Sprintf("%02d", i)), nil)
-		printTree(tree.root, "")
-	}
-
-	if !tree.Has(String("08")) {
-		t.Errorf("lookup error")
-	}
-	for i:=5;i<9;i++{
-		println("----------", i)
-		tree.RemoveWhere(String(fmt.Sprintf("%02d", i)), func(value ItemValue) bool {
-			return true
-		})
-		printTree(tree.root, "")
-	}
-	if tree.Has(String("08")) {
-		t.Errorf("remove error")
-	}
-}
-
-func printTree(node *BpNode, prefix string) {
-	fmt.Printf("%sNode %d\n", prefix, node.protoNodeId)
-	prefix += " "
-	for i:=0;i<len(node.keys);i++{
-		fmt.Printf("%skey %v\n", prefix, node.keys[i])
-		if i < len(node.pointers) && node.pointers[i] != nil {
-			printTree(node.pointers[i], prefix+" ")
-		}
-	}
-}
\ No newline at end of file
diff --git a/weed/util/bptree/bptree_test.go b/weed/util/bptree/bptree_test.go
deleted file mode 100644
index 1fd6d1122..000000000
--- a/weed/util/bptree/bptree_test.go
+++ /dev/null
@@ -1,1408 +0,0 @@
-package bptree
-
-import (
-	"encoding/hex"
-	"runtime/debug"
-	"sort"
-	"sync"
-	"testing"
-
-	crand "crypto/rand"
-	"encoding/binary"
-	mrand "math/rand"
-
-)
-
-var rand *mrand.Rand
-
-func init() {
-	seed := make([]byte, 8)
-	if _, err := crand.Read(seed); err == nil {
-		rand = ThreadSafeRand(int64(binary.BigEndian.Uint64(seed)))
-	} else {
-		panic(err)
-	}
-}
-
-func randslice(length int) []byte {
-	return RandSlice(length)
-}
-
-func randstr(length int) String {
-	return String(RandStr(length))
-}
-
-type Strings []String
-
-func (self Strings) Len() int {
-	return len(self)
-}
-
-func (self Strings) Less(i, j int) bool {
-	return self[i].Less(self[j])
-}
-
-func (self Strings) Swap(i, j int) {
-	self[i], self[j] = self[j], self[i]
-}
-
-type record struct {
-	key   String
-	value ItemValue
-}
-
-type records []*record
-
-func (self records) Len() int {
-	return len(self)
-}
-
-func (self records) Less(i, j int) bool {
-	return self[i].key.Less(self[j].key)
-}
-
-func (self records) Swap(i, j int) {
-	self[i], self[j] = self[j], self[i]
-}
-
-func BenchmarkBpTree(b *testing.B) {
-	b.StopTimer()
-
-	recs := make(records, 100)
-	ranrec := func() *record {
-		return &record{randstr(20), randstr(20)}
-	}
-
-	for i := range recs {
-		recs[i] = ranrec()
-	}
-
-	b.StartTimer()
-	for i := 0; i < b.N; i++ {
-		t := NewBpTree(23, nil)
-		for _, r := range recs {
-			t.Add(r.key, r.value)
-		}
-		for _, r := range recs {
-			t.RemoveWhere(r.key, func(value ItemValue) bool { return true })
-		}
-	}
-}
-
-func TestAddHasCountFindIterateRemove(t *testing.T) {
-
-	ranrec := func() *record {
-		return &record{
-			randstr(12),
-			randstr(12),
-		}
-	}
-
-	test := func(bpt *BpTree) {
-		var err error
-		recs := make(records, 128)
-		new_recs := make(records, 128)
-		for i := range recs {
-			r := ranrec()
-			recs[i] = r
-			new_recs[i] = &record{r.key, randstr(12)}
-			err = bpt.Add(r.key, r.value)
-			if err != nil {
-				t.Error(err)
-			}
-		}
-
-		for i, r := range recs {
-			if has := bpt.Has(r.key); !has {
-				t.Error(bpt, "Missing key")
-			}
-			if has := bpt.Has(randstr(10)); has {
-				t.Error("Table has extra key")
-			}
-			if count := bpt.Count(r.key); count != 1 {
-				t.Error(bpt, "Missing key")
-			}
-			if count := bpt.Count(randstr(10)); count != 0 {
-				t.Error("Table has extra key")
-			}
-			for k, v, next := bpt.Find(r.key)(); next != nil; k, v, next = next() {
-				if !k.Equals(r.key) {
-					t.Error(bpt, "Find Failed Key Error")
-				}
-				if !v.(String).Equals(r.value) {
-					t.Error(bpt, "Find Failed Value Error")
-				}
-			}
-			err = bpt.Replace(r.key, func(value ItemValue) bool { return true }, new_recs[i].value)
-			if err != nil {
-				t.Error(err)
-			}
-		}
-		sort.Sort(recs)
-		sort.Sort(new_recs)
-		i := 0
-		for k, v, next := bpt.Iterate()(); next != nil; k, v, next = next() {
-			if !recs[i].key.Equals(k) {
-				t.Error("iterate error wrong key")
-			}
-			if !new_recs[i].value.Equals(v.(String)) {
-				t.Error("iterate error wrong value")
-			}
-			i++
-		}
-		i = len(recs) - 1
-		for k, v, next := bpt.Backward()(); next != nil; k, v, next = next() {
-			if !recs[i].key.Equals(k) {
-				t.Error("iterate error wrong key")
-			}
-			if !new_recs[i].value.Equals(v.(String)) {
-				t.Error("iterate error wrong value")
-			}
-			i--
-		}
-		i = 0
-		for k, next := bpt.Keys()(); next != nil; k, next = next() {
-			if !recs[i].key.Equals(k) {
-				t.Error("iterate error wrong key")
-			}
-			i++
-		}
-		i = 7
-		for k, v, next := bpt.Range(recs[i].key, recs[i+(len(recs)/2)].key)(); next != nil; k, v, next = next() {
-			if !recs[i].key.Equals(k) {
-				t.Error("iterate error wrong key")
-			}
-			if !new_recs[i].value.Equals(v.(String)) {
-				t.Error("iterate error wrong value")
-			}
-			i++
-		}
-		for k, v, next := bpt.Range(recs[i].key, recs[7].key)(); next != nil; k, v, next = next() {
-			if !recs[i].key.Equals(k) {
-				t.Error("iterate error wrong key")
-			}
-			if !new_recs[i].value.Equals(v.(String)) {
-				t.Error("iterate error wrong value", k, v, recs[i].value, new_recs[i].value)
-			}
-			i--
-		}
-		for i, r := range recs {
-			if has := bpt.Has(r.key); !has {
-				t.Error(bpt, "Missing key")
-			}
-			if count := bpt.Count(r.key); count != 1 {
-				t.Error(bpt, "Missing key")
-			}
-			if err := bpt.RemoveWhere(r.key, func(value ItemValue) bool { return true }); err != nil {
-				t.Fatal(bpt, err)
-			}
-			if has := bpt.Has(r.key); has {
-				t.Error("Table has extra key")
-			}
-			for _, x := range recs[i+1:] {
-				if has := bpt.Has(x.key); !has {
-					t.Error(bpt, "Missing key", x.key)
-				}
-			}
-		}
-	}
-	for i := 2; i < 64; i++ {
-		test(NewBpTree(i, nil))
-	}
-}
-
-func TestBpMap(t *testing.T) {
-
-	ranrec := func() *record {
-		return &record{
-			randstr(12),
-			randstr(12),
-		}
-	}
-
-	test := func(table MapOperable) {
-		recs := make(records, 400)
-		for i := range recs {
-			r := ranrec()
-			recs[i] = r
-			err := table.Put(r.key, String(""))
-			if err != nil {
-				t.Error(err)
-			}
-			err = table.Put(r.key, r.value)
-			if err != nil {
-				t.Error(err)
-			}
-		}
-
-		for _, r := range recs {
-			if has := table.Has(r.key); !has {
-				t.Error(table, "Missing key")
-			}
-			if has := table.Has(randstr(12)); has {
-				t.Error("Table has extra key")
-			}
-			if val, err := table.Get(r.key); err != nil {
-				t.Error(err)
-			} else if !(val.(String)).Equals(r.value) {
-				t.Error("wrong value")
-			}
-		}
-
-		for i, x := range recs {
-			if val, err := table.Remove(x.key); err != nil {
-				t.Error(err)
-			} else if !(val.(String)).Equals(x.value) {
-				t.Error("wrong value")
-			}
-			for _, r := range recs[i+1:] {
-				if has := table.Has(r.key); !has {
-					t.Error("Missing key")
-				}
-				if has := table.Has(randstr(12)); has {
-					t.Error("Table has extra key")
-				}
-				if val, err := table.Get(r.key); err != nil {
-					t.Error(err)
-				} else if !(val.(String)).Equals(r.value) {
-					t.Error("wrong value")
-				}
-			}
-		}
-	}
-
-	test(NewBpMap(23, nil))
-}
-
-func Test_get_start(t *testing.T) {
-	root := NewLeaf(2, nil)
-	root, err := root.put(Int(1), Int(1))
-	if err != nil {
-		t.Error(err)
-	}
-	root, err = root.put(Int(5), Int(3))
-	if err != nil {
-		t.Error(err)
-	}
-	root, err = root.put(Int(3), Int(2))
-	if err != nil {
-		t.Error(err)
-	}
-	t.Log(root)
-	t.Log(root.pointers[0])
-	t.Log(root.pointers[1])
-	i, n := root.get_start(Int(1))
-	if n != root.pointers[0] {
-		t.Error("wrong node from get_start")
-	}
-	if i != 0 {
-		t.Error("wrong index from get_start")
-	}
-	i, n = root.get_start(Int(3))
-	if n != root.pointers[0] {
-		t.Error("wrong node from get_start")
-	}
-	if i != 1 {
-		t.Error("wrong index from get_start")
-	}
-	i, n = root.get_start(Int(5))
-	if n != root.pointers[1] {
-		t.Error("wrong node from get_start")
-	}
-	if i != 0 {
-		t.Error("wrong index from get_start")
-	}
-	i, n = root.get_start(Int(2))
-	if n != root.pointers[0] {
-		t.Error("wrong node from get_start")
-	}
-	if i != 1 {
-		t.Error("wrong index from get_start")
-	}
-	i, n = root.get_start(Int(4))
-	t.Log(n)
-	if n != root.pointers[1] {
-		t.Error("wrong node from get_start")
-	}
-	if i != 0 {
-		t.Error("wrong index from get_start")
-	}
-	i, n = root.get_start(Int(0))
-	if n != root.pointers[0] {
-		t.Error("wrong node from get_start")
-	}
-	if i != 0 {
-		t.Error("wrong index from get_start")
-	}
-	i, n = root.get_start(Int(5))
-	if n != root.pointers[1] {
-		t.Error("wrong node from get_start")
-	}
-	if i != 0 {
-		t.Error("wrong index from get_start")
-	}
-}
-
-func Test_get_end(t *testing.T) {
-	root := NewLeaf(3, nil)
-	root, err := root.put(Int(1), Int(1))
-	if err != nil {
-		t.Fatal(err)
-	}
-	root, err = root.put(Int(4), Int(4))
-	if err != nil {
-		t.Fatal(err)
-	}
-	root, err = root.put(Int(3), Int(3))
-	if err != nil {
-		t.Fatal(err)
-	}
-	root, err = root.put(Int(8), Int(8))
-	if err != nil {
-		t.Fatal(err)
-	}
-	root, err = root.put(Int(9), Int(9))
-	if err != nil {
-		t.Fatal(err)
-	}
-	root, err = root.put(Int(10), Int(10))
-	if err != nil {
-		t.Fatal(err)
-	}
-	root, err = root.put(Int(6), Int(6))
-	if err != nil {
-		t.Fatal(err)
-	}
-	root, err = root.put(Int(7), Int(7))
-	if err != nil {
-		t.Fatal(err)
-	}
-	root, err = root.put(Int(5), Int(5))
-	if err != nil {
-		t.Fatal(err)
-	}
-	t.Log(root)
-	t.Log(root.pointers[0])
-	t.Log(root.pointers[1])
-	printTree(root, "")
-}
-
-func Test_put_no_root_split(t *testing.T) {
-	a := NewLeaf(2, nil)
-	if err := a.put_kv(Int(1), Int(1)); err != nil {
-		t.Error(err)
-	}
-	p, err := a.put(Int(1), Int(2))
-	if err != nil {
-		t.Error(err)
-	} else {
-		if p != a {
-			t.Errorf("p != a")
-		}
-		if !p.has(Int(1)) {
-			t.Error("p didn't have the right keys", p)
-		}
-	}
-	p, err = a.put(Int(1), Int(3))
-
-	t.Log(a)
-	printTree(a, "")
-
-	if err != nil {
-		t.Error(err)
-	} else {
-		if p != a {
-			t.Errorf("p != a")
-		}
-		if !p.has(Int(1)) {
-			t.Error("p didn't have the right keys", p)
-		}
-		t.Log(p)
-		t.Log(p.getNext())
-	}
-}
-
-func Test_put_root_split(t *testing.T) {
-	a := NewLeaf(2, nil)
-	p, err := a.put(Int(1), Int(1))
-	if err != nil {
-		t.Error(err)
-	} else {
-		if p != a {
-			t.Errorf("p != a")
-		}
-		if !p.has(Int(1)) {
-			t.Error("p didn't have the right keys", p)
-		}
-	}
-	p, err = a.put(Int(3), Int(3))
-	if err != nil {
-		t.Error(err)
-	} else {
-		if p != a {
-			t.Errorf("p != a")
-		}
-		if !p.has(Int(1)) || !p.has(Int(3)) {
-			t.Error("p didn't have the right keys", p)
-		}
-	}
-	p, err = a.put(Int(2), Int(2))
-	if err != nil {
-		t.Error(err)
-	} else {
-		if p == a {
-			t.Errorf("p == a")
-		}
-		if !p.has(Int(1)) || !p.has(Int(3)) {
-			t.Error("p didn't have the right keys", p)
-		}
-		if len(p.pointers) != 2 {
-			t.Error("p didn't have right number of pointers", p)
-		}
-		if !p.pointers[0].has(Int(1)) || !p.pointers[0].has(Int(2)) {
-			t.Error("p.pointers[0] didn't have the right keys", p.pointers[0])
-		}
-		if !p.pointers[1].has(Int(3)) {
-			t.Error("p.pointers[1] didn't have the right keys", p.pointers[1])
-		}
-		t.Log(p)
-		t.Log(p.pointers[0])
-		t.Log(p.pointers[1])
-	}
-}
-
-func Test_internal_insert_no_split(t *testing.T) {
-	a := NewInternal(3, nil)
-	leaf := NewLeaf(1, nil)
-	if err := leaf.put_kv(Int(1), Int(1)); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kp(Int(1), leaf); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kp(Int(5), nil); err != nil {
-		t.Error(err)
-	}
-	p, q, err := a.internal_insert(Int(2), nil)
-	if err != nil {
-		t.Error(err)
-	} else {
-		if p != a {
-			t.Errorf("p != a")
-		}
-		if q != nil {
-			t.Errorf("q != nil")
-		}
-		if !p.has(Int(1)) || !p.has(Int(2)) || !p.has(Int(5)) {
-			t.Error("p didn't have the right keys", p)
-		}
-	}
-}
-
-func Test_internal_insert_split_less(t *testing.T) {
-	a := NewInternal(3, nil)
-	leaf := NewLeaf(1, nil)
-	if err := leaf.put_kv(Int(1), Int(1)); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kp(Int(1), leaf); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kp(Int(3), nil); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kp(Int(5), nil); err != nil {
-		t.Error(err)
-	}
-	p, q, err := a.internal_insert(Int(2), nil)
-	if err != nil {
-		t.Error(err)
-	} else {
-		if p != a {
-			t.Errorf("p != a")
-		}
-		if q == nil {
-			t.Errorf("q == nil")
-		}
-		if !p.has(Int(1)) || !p.has(Int(2)) {
-			t.Error("p didn't have the right keys", p)
-		}
-		if !q.has(Int(3)) || !q.has(Int(5)) {
-			t.Error("q didn't have the right keys", q)
-		}
-	}
-}
-
-func Test_internal_split_less(t *testing.T) {
-	a := NewInternal(3, nil)
-	if err := a.put_kp(Int(1), nil); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kp(Int(3), nil); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kp(Int(5), nil); err != nil {
-		t.Error(err)
-	}
-	p, q, err := a.internal_split(Int(2), nil)
-	if err != nil {
-		t.Error(err)
-	} else {
-		if p != a {
-			t.Errorf("p != a")
-		}
-		if q == nil {
-			t.Errorf("q == nil")
-		}
-		if !p.has(Int(1)) || !p.has(Int(2)) {
-			t.Error("p didn't have the right keys", p)
-		}
-		if !q.has(Int(3)) || !q.has(Int(5)) {
-			t.Error("q didn't have the right keys", q)
-		}
-	}
-}
-
-func Test_internal_split_equal(t *testing.T) {
-	a := NewInternal(3, nil)
-	if err := a.put_kp(Int(1), nil); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kp(Int(3), nil); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kp(Int(5), nil); err != nil {
-		t.Error(err)
-	}
-	p, q, err := a.internal_split(Int(3), nil)
-	if err == nil {
-		t.Error("split succeeded should have failed", p, q)
-	}
-}
-
-func Test_internal_split_greater(t *testing.T) {
-	a := NewInternal(3, nil)
-	if err := a.put_kp(Int(1), nil); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kp(Int(3), nil); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kp(Int(5), nil); err != nil {
-		t.Error(err)
-	}
-	p, q, err := a.internal_split(Int(4), nil)
-	if err != nil {
-		t.Error(err)
-	} else {
-		if p != a {
-			t.Errorf("p != a")
-		}
-		if q == nil {
-			t.Errorf("q == nil")
-		}
-		if !p.has(Int(1)) ||  !p.has(Int(3)) || !p.has(Int(4)){
-			t.Error("p didn't have the right keys", p)
-		}
-		if !q.has(Int(5)) {
-			t.Error("q didn't have the right keys", q)
-		}
-	}
-}
-
-func Test_leaf_insert_no_split(t *testing.T) {
-	a := NewLeaf(3, nil)
-	insert_linked_list_node(a, nil, nil)
-	if err := a.put_kv(Int(1), Int(1)); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kv(Int(3), Int(3)); err != nil {
-		t.Error(err)
-	}
-	p, q, err := a.leaf_insert(Int(2), Int(2))
-	if err != nil {
-		t.Error(err)
-	} else {
-		if p != a {
-			t.Errorf("p != a")
-		}
-		if q != nil {
-			t.Errorf("q != nil")
-		}
-		if !p.has(Int(1)) || !p.has(Int(2)) || !p.has(Int(3)) {
-			t.Error("p didn't have the right keys", p)
-		}
-	}
-}
-
-// tests the defer to split logic
-func Test_leaf_insert_split_less(t *testing.T) {
-	a := NewLeaf(3, nil)
-	insert_linked_list_node(a, nil, nil)
-	if err := a.put_kv(Int(1), Int(1)); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kv(Int(3), Int(3)); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kv(Int(5), Int(5)); err != nil {
-		t.Error(err)
-	}
-	p, q, err := a.leaf_insert(Int(2), Int(2))
-	if err != nil {
-		t.Error(err)
-	} else {
-		if p != a {
-			t.Errorf("p != a")
-		}
-		if q == nil {
-			t.Errorf("q == nil")
-		}
-		if !p.has(Int(1)) || !p.has(Int(2)) {
-			t.Error("p didn't have the right keys", p)
-		}
-		if !q.has(Int(3)) || !q.has(Int(5)) {
-			t.Error("q didn't have the right keys", q)
-		}
-	}
-}
-
-func Test_leaf_split_less(t *testing.T) {
-	a := NewLeaf(3, nil)
-	insert_linked_list_node(a, nil, nil)
-	if err := a.put_kv(Int(1), Int(1)); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kv(Int(3), Int(3)); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kv(Int(5), Int(5)); err != nil {
-		t.Error(err)
-	}
-	p, q, err := a.leaf_split(Int(2), Int(2))
-	if err != nil {
-		t.Error(err)
-	} else {
-		if p != a {
-			t.Errorf("p != a")
-		}
-		if q == nil {
-			t.Errorf("q == nil")
-		}
-		if !p.has(Int(1)) || !p.has(Int(2)) {
-			t.Error("p didn't have the right keys", p)
-		}
-		if !q.has(Int(3)) || !q.has(Int(5)) {
-			t.Error("q didn't have the right keys", q)
-		}
-	}
-}
-
-func Test_leaf_split_equal(t *testing.T) {
-	a := NewLeaf(3, nil)
-	insert_linked_list_node(a, nil, nil)
-	if err := a.put_kv(Int(1), Int(1)); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kv(Int(3), Int(3)); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kv(Int(5), Int(5)); err != nil {
-		t.Error(err)
-	}
-	p, q, err := a.leaf_split(Int(3), Int(2))
-	if err != nil {
-		t.Error(err)
-	} else {
-		if p != a {
-			t.Errorf("p != a")
-		}
-		if q == nil {
-			t.Errorf("q == nil")
-		}
-		if !p.has(Int(1)) {
-			t.Error("p didn't have the right keys", p)
-		}
-		if !q.has(Int(3)) || !q.has(Int(5)) {
-			t.Error("q didn't have the right keys", q)
-		}
-	}
-}
-
-func Test_leaf_split_greater(t *testing.T) {
-	a := NewLeaf(3, nil)
-	insert_linked_list_node(a, nil, nil)
-	if err := a.put_kv(Int(1), Int(1)); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kv(Int(3), Int(3)); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kv(Int(5), Int(5)); err != nil {
-		t.Error(err)
-	}
-	p, q, err := a.leaf_split(Int(4), Int(2))
-	if err != nil {
-		t.Error(err)
-	} else {
-		if p != a {
-			t.Errorf("p != a")
-		}
-		if q == nil {
-			t.Errorf("q == nil")
-		}
-		if !p.has(Int(1)) || !p.has(Int(3)) || !p.has(Int(4)) {
-			t.Error("p didn't have the right keys", p)
-		}
-		if !q.has(Int(5)) {
-			t.Error("q didn't have the right keys", q)
-		}
-	}
-}
-
-// tests the defer logic
-func Test_pure_leaf_insert_split_less(t *testing.T) {
-	a := NewLeaf(2, nil)
-	insert_linked_list_node(a, nil, nil)
-	b := NewLeaf(2, nil)
-	insert_linked_list_node(b, a, nil)
-	c := NewLeaf(2, nil)
-	insert_linked_list_node(c, b, nil)
-	d := NewLeaf(2, nil)
-	insert_linked_list_node(d, c, nil)
-	if err := a.put_kv(Int(3), Int(1)); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kv(Int(3), Int(2)); err != nil {
-		t.Error(err)
-	}
-	if err := b.put_kv(Int(3), Int(3)); err != nil {
-		t.Error(err)
-	}
-	if err := b.put_kv(Int(3), Int(4)); err != nil {
-		t.Error(err)
-	}
-	if err := c.put_kv(Int(3), Int(5)); err != nil {
-		t.Error(err)
-	}
-	if err := c.put_kv(Int(3), Int(6)); err != nil {
-		t.Error(err)
-	}
-	if err := d.put_kv(Int(4), Int(6)); err != nil {
-		t.Error(err)
-	}
-	p, q, err := a.leaf_insert(Int(2), Int(1))
-	if err != nil {
-		t.Error(err)
-	} else {
-		if q != a {
-			t.Errorf("q != a")
-		}
-		if p == nil || len(p.keys) != 1 || !p.keys[0].Equals(Int(2)) {
-			t.Errorf("p did not contain the right key")
-		}
-		if p.getPrev() != nil {
-			t.Errorf("expected p.prev == nil")
-		}
-		if p.getNext() != a {
-			t.Errorf("expected p.next == a")
-		}
-		if a.getPrev() != p {
-			t.Errorf("expected a.prev == p")
-		}
-		if a.getNext() != b {
-			t.Errorf("expected a.next == b")
-		}
-		if b.getPrev() != a {
-			t.Errorf("expected b.prev == a")
-		}
-		if b.getNext() != c {
-			t.Errorf("expected b.next == c")
-		}
-		if c.getPrev() != b {
-			t.Errorf("expected c.prev == b")
-		}
-		if c.getNext() != d {
-			t.Errorf("expected c.next == d")
-		}
-		if d.getPrev() != c {
-			t.Errorf("expected d.prev == c")
-		}
-		if d.getNext() != nil {
-			t.Errorf("expected d.next == nil")
-		}
-	}
-}
-
-func Test_pure_leaf_split_less(t *testing.T) {
-	a := NewLeaf(2, nil)
-	insert_linked_list_node(a, nil, nil)
-	b := NewLeaf(2, nil)
-	insert_linked_list_node(b, a, nil)
-	c := NewLeaf(2, nil)
-	insert_linked_list_node(c, b, nil)
-	d := NewLeaf(2, nil)
-	insert_linked_list_node(d, c, nil)
-	if err := a.put_kv(Int(3), Int(1)); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kv(Int(3), Int(2)); err != nil {
-		t.Error(err)
-	}
-	if err := b.put_kv(Int(3), Int(3)); err != nil {
-		t.Error(err)
-	}
-	if err := b.put_kv(Int(3), Int(4)); err != nil {
-		t.Error(err)
-	}
-	if err := c.put_kv(Int(3), Int(5)); err != nil {
-		t.Error(err)
-	}
-	if err := c.put_kv(Int(3), Int(6)); err != nil {
-		t.Error(err)
-	}
-	if err := d.put_kv(Int(4), Int(6)); err != nil {
-		t.Error(err)
-	}
-	p, q, err := a.pure_leaf_split(Int(2), Int(1))
-	if err != nil {
-		t.Error(err)
-	} else {
-		if q != a {
-			t.Errorf("q != a")
-		}
-		if p == nil || len(p.keys) != 1 || !p.keys[0].Equals(Int(2)) {
-			t.Errorf("p did not contain the right key")
-		}
-		if p.getPrev() != nil {
-			t.Errorf("expected p.prev == nil")
-		}
-		if p.getNext() != a {
-			t.Errorf("expected p.next == a")
-		}
-		if a.getPrev() != p {
-			t.Errorf("expected a.prev == p")
-		}
-		if a.getNext() != b {
-			t.Errorf("expected a.next == b")
-		}
-		if b.getPrev() != a {
-			t.Errorf("expected b.prev == a")
-		}
-		if b.getNext() != c {
-			t.Errorf("expected b.next == c")
-		}
-		if c.getPrev() != b {
-			t.Errorf("expected c.prev == b")
-		}
-		if c.getNext() != d {
-			t.Errorf("expected c.next == d")
-		}
-		if d.getPrev() != c {
-			t.Errorf("expected d.prev == c")
-		}
-		if d.getNext() != nil {
-			t.Errorf("expected d.next == nil")
-		}
-	}
-}
-
-func Test_pure_leaf_split_equal(t *testing.T) {
-	a := NewLeaf(2, nil)
-	insert_linked_list_node(a, nil, nil)
-	b := NewLeaf(2, nil)
-	insert_linked_list_node(b, a, nil)
-	c := NewLeaf(2, nil)
-	insert_linked_list_node(c, b, nil)
-	d := NewLeaf(2, nil)
-	insert_linked_list_node(d, c, nil)
-	if err := a.put_kv(Int(3), Int(1)); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kv(Int(3), Int(2)); err != nil {
-		t.Error(err)
-	}
-	if err := b.put_kv(Int(3), Int(3)); err != nil {
-		t.Error(err)
-	}
-	if err := b.put_kv(Int(3), Int(4)); err != nil {
-		t.Error(err)
-	}
-	if err := c.put_kv(Int(3), Int(5)); err != nil {
-		t.Error(err)
-	}
-	if err := d.put_kv(Int(4), Int(6)); err != nil {
-		t.Error(err)
-	}
-	p, q, err := a.pure_leaf_split(Int(3), Int(1))
-	if err != nil {
-		t.Error(err)
-	} else {
-		if p != a {
-			t.Errorf("p != a")
-		}
-		if q != nil {
-			t.Errorf("q != nil")
-		}
-		if a.getPrev() != nil {
-			t.Errorf("expected a.prev == nil")
-		}
-		if a.getNext() != b {
-			t.Errorf("expected a.next == b")
-		}
-		if b.getPrev() != a {
-			t.Errorf("expected b.prev == a")
-		}
-		if b.getNext() != c {
-			t.Errorf("expected b.next == c")
-		}
-		if c.getPrev() != b {
-			t.Errorf("expected c.prev == b")
-		}
-		if c.getNext() != d {
-			t.Errorf("expected c.next == d")
-		}
-		if d.getPrev() != c {
-			t.Errorf("expected d.prev == c")
-		}
-		if d.getNext() != nil {
-			t.Errorf("expected d.next == nil")
-		}
-	}
-}
-
-func Test_pure_leaf_split_greater(t *testing.T) {
-	a := NewLeaf(2, nil)
-	insert_linked_list_node(a, nil, nil)
-	b := NewLeaf(2, nil)
-	insert_linked_list_node(b, a, nil)
-	c := NewLeaf(2, nil)
-	insert_linked_list_node(c, b, nil)
-	d := NewLeaf(2, nil)
-	insert_linked_list_node(d, c, nil)
-	if err := a.put_kv(Int(3), Int(1)); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kv(Int(3), Int(2)); err != nil {
-		t.Error(err)
-	}
-	if err := b.put_kv(Int(3), Int(3)); err != nil {
-		t.Error(err)
-	}
-	if err := b.put_kv(Int(3), Int(4)); err != nil {
-		t.Error(err)
-	}
-	if err := c.put_kv(Int(3), Int(5)); err != nil {
-		t.Error(err)
-	}
-	if err := d.put_kv(Int(5), Int(6)); err != nil {
-		t.Error(err)
-	}
-	p, q, err := a.pure_leaf_split(Int(4), Int(1))
-	if err != nil {
-		t.Error(err)
-	} else {
-		if p != a {
-			t.Errorf("p != a")
-		}
-		if q == nil || len(q.keys) != 1 || !q.keys[0].Equals(Int(4)) {
-			t.Errorf("q != nil")
-		}
-		if a.getPrev() != nil {
-			t.Errorf("expected a.prev == nil")
-		}
-		if a.getNext() != b {
-			t.Errorf("expected a.next == b")
-		}
-		if b.getPrev() != a {
-			t.Errorf("expected b.prev == a")
-		}
-		if b.getNext() != c {
-			t.Errorf("expected b.next == c")
-		}
-		if c.getPrev() != b {
-			t.Errorf("expected c.prev == b")
-		}
-		if c.getNext() != q {
-			t.Errorf("expected c.next == q")
-		}
-		if q.getPrev() != c {
-			t.Errorf("expected q.prev == c")
-		}
-		if q.getNext() != d {
-			t.Errorf("expected q.next == d")
-		}
-		if d.getPrev() != q {
-			t.Errorf("expected d.prev == q")
-		}
-		if d.getNext() != nil {
-			t.Errorf("expected d.next == nil")
-		}
-	}
-}
-
-func Test_find_end_of_pure_run(t *testing.T) {
-	a := NewLeaf(2, nil)
-	insert_linked_list_node(a, nil, nil)
-	b := NewLeaf(2, nil)
-	insert_linked_list_node(b, a, nil)
-	c := NewLeaf(2, nil)
-	insert_linked_list_node(c, b, nil)
-	d := NewLeaf(2, nil)
-	insert_linked_list_node(d, c, nil)
-	if err := a.put_kv(Int(3), Int(1)); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kv(Int(3), Int(2)); err != nil {
-		t.Error(err)
-	}
-	if err := b.put_kv(Int(3), Int(3)); err != nil {
-		t.Error(err)
-	}
-	if err := b.put_kv(Int(3), Int(4)); err != nil {
-		t.Error(err)
-	}
-	if err := c.put_kv(Int(3), Int(5)); err != nil {
-		t.Error(err)
-	}
-	if err := c.put_kv(Int(3), Int(6)); err != nil {
-		t.Error(err)
-	}
-	if err := d.put_kv(Int(4), Int(6)); err != nil {
-		t.Error(err)
-	}
-	e := a.find_end_of_pure_run()
-	if e != c {
-		t.Errorf("end of run should have been block c %v %v", e, c)
-	}
-}
-
-func Test_insert_linked_list_node(t *testing.T) {
-	a := NewLeaf(1, nil)
-	insert_linked_list_node(a, nil, nil)
-	b := NewLeaf(2, nil)
-	insert_linked_list_node(b, a, nil)
-	c := NewLeaf(3, nil)
-	insert_linked_list_node(c, b, nil)
-	d := NewLeaf(4, nil)
-	insert_linked_list_node(d, a, b)
-	if a.getPrev() != nil {
-		t.Errorf("expected a.prev == nil")
-	}
-	if a.getNext() != d {
-		t.Errorf("expected a.next == d")
-	}
-	if d.getPrev() != a {
-		t.Errorf("expected d.prev == a")
-	}
-	if d.getNext() != b {
-		t.Errorf("expected d.next == b")
-	}
-	if b.getPrev() != d {
-		t.Errorf("expected b.prev == d")
-	}
-	if b.getNext() != c {
-		t.Errorf("expected b.next == c")
-	}
-	if c.getPrev() != b {
-		t.Errorf("expected c.prev == b")
-	}
-	if c.getNext() != nil {
-		t.Errorf("expected c.next == nil")
-	}
-}
-
-func Test_remove_linked_list_node(t *testing.T) {
-	a := NewLeaf(1, nil)
-	insert_linked_list_node(a, nil, nil)
-	b := NewLeaf(2, nil)
-	insert_linked_list_node(b, a, nil)
-	c := NewLeaf(3, nil)
-	insert_linked_list_node(c, b, nil)
-	d := NewLeaf(4, nil)
-	insert_linked_list_node(d, a, b)
-	if a.getPrev() != nil {
-		t.Errorf("expected a.prev == nil")
-	}
-	if a.getNext() != d {
-		t.Errorf("expected a.next == d")
-	}
-	if d.getPrev() != a {
-		t.Errorf("expected d.prev == a")
-	}
-	if d.getNext() != b {
-		t.Errorf("expected d.next == b")
-	}
-	if b.getPrev() != d {
-		t.Errorf("expected b.prev == d")
-	}
-	if b.getNext() != c {
-		t.Errorf("expected b.next == c")
-	}
-	if c.getPrev() != b {
-		t.Errorf("expected c.prev == b")
-	}
-	if c.getNext() != nil {
-		t.Errorf("expected c.next == nil")
-	}
-	remove_linked_list_node(d)
-	if a.getPrev() != nil {
-		t.Errorf("expected a.prev == nil")
-	}
-	if a.getNext() != b {
-		t.Errorf("expected a.next == b")
-	}
-	if b.getPrev() != a {
-		t.Errorf("expected b.prev == a")
-	}
-	if b.getNext() != c {
-		t.Errorf("expected b.next == c")
-	}
-	if c.getPrev() != b {
-		t.Errorf("expected c.prev == b")
-	}
-	if c.getNext() != nil {
-		t.Errorf("expected c.next == nil")
-	}
-	remove_linked_list_node(a)
-	if b.getPrev() != nil {
-		t.Errorf("expected b.prev == nil")
-	}
-	if b.getNext() != c {
-		t.Errorf("expected b.next == c")
-	}
-	if c.getPrev() != b {
-		t.Errorf("expected c.prev == b")
-	}
-	if c.getNext() != nil {
-		t.Errorf("expected c.next == nil")
-	}
-	remove_linked_list_node(c)
-	if b.getPrev() != nil {
-		t.Errorf("expected b.prev == nil")
-	}
-	if b.getNext() != nil {
-		t.Errorf("expected b.next == nil")
-	}
-	remove_linked_list_node(b)
-}
-
-func Test_balance_leaf_nodes_with_dup(t *testing.T) {
-	a := NewLeaf(3, nil)
-	b := NewLeaf(3, nil)
-	if err := a.put_kv(Int(1), Int(1)); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kv(Int(1), Int(1)); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kv(Int(2), Int(1)); err != nil {
-		t.Error(err)
-	}
-	balance_nodes(a, b, Int(2))
-	if !a.has(Int(1)) || a.has(Int(2)) {
-		t.Error("a had wrong items", a)
-	}
-	if !b.has(Int(2)) || b.has(Int(1)) {
-		t.Error("a had wrong items", b)
-	}
-}
-
-func Test_balance_leaf_nodes(t *testing.T) {
-	a := NewLeaf(7, nil)
-	b := NewLeaf(7, nil)
-	if err := a.put_kv(Int(1), Int(1)); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kv(Int(2), Int(2)); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kv(Int(3), Int(3)); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kv(Int(4), Int(4)); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kv(Int(5), Int(5)); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kv(Int(6), Int(6)); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kv(Int(7), Int(7)); err != nil {
-		t.Error(err)
-	}
-	balance_nodes(a, b, Int(5))
-	for i, k := range a.keys {
-		if int(k.(Int)) != i+1 {
-			t.Errorf("k != %d", i+1)
-		}
-	}
-	for i, k := range b.keys {
-		if int(k.(Int)) != 5+i {
-			t.Errorf("k != %d", 5+i)
-		}
-	}
-	for i, v := range a.values {
-		if int(v.(Int)) != i+1 {
-			t.Errorf("k != %d", i+1)
-		}
-	}
-	for i, v := range b.values {
-		if int(v.(Int)) != 5+i {
-			t.Errorf("v != %d", 5+i)
-		}
-	}
-	t.Log(a)
-	t.Log(b)
-}
-
-func Test_balance_internal_nodes(t *testing.T) {
-	a := NewInternal(6, nil)
-	b := NewInternal(6, nil)
-	if err := a.put_kp(Int(1), nil); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kp(Int(2), nil); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kp(Int(3), nil); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kp(Int(4), nil); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kp(Int(5), nil); err != nil {
-		t.Error(err)
-	}
-	if err := a.put_kp(Int(6), nil); err != nil {
-		t.Error(err)
-	}
-	balance_nodes(a, b, Int(4))
-	for i, k := range a.keys {
-		if int(k.(Int)) != i+1 {
-			t.Errorf("k != %d", i+1)
-		}
-	}
-	for i, k := range b.keys {
-		if int(k.(Int)) != 3+i+1 {
-			t.Errorf("k != %d", 3+i+1)
-		}
-	}
-	t.Log(a)
-	t.Log(b)
-}
-
-
-// copied from
-
-// ThreadSafeRand provides a thread safe version of math/rand.Rand using
-// the same technique used in the math/rand package to make the top level
-// functions thread safe.
-func ThreadSafeRand(seed int64) *mrand.Rand {
-	return mrand.New(&lockedSource{src: mrand.NewSource(seed).(mrand.Source64)})
-}
-
-// from: https://golang.org/src/math/rand/rand.go?s=8161:8175#L317
-type lockedSource struct {
-	lk  sync.Mutex
-	src mrand.Source64
-}
-
-func (r *lockedSource) Int63() (n int64) {
-	r.lk.Lock()
-	n = r.src.Int63()
-	r.lk.Unlock()
-	return
-}
-
-func (r *lockedSource) Uint64() (n uint64) {
-	r.lk.Lock()
-	n = r.src.Uint64()
-	r.lk.Unlock()
-	return
-}
-
-func (r *lockedSource) Seed(seed int64) {
-	r.lk.Lock()
-	r.src.Seed(seed)
-	r.lk.Unlock()
-}
-
-// seedPos implements Seed for a lockedSource without a race condiiton.
-func (r *lockedSource) seedPos(seed int64, readPos *int8) {
-	r.lk.Lock()
-	r.src.Seed(seed)
-	*readPos = 0
-	r.lk.Unlock()
-}
-
-// read implements Read for a lockedSource without a race condition.
-func (r *lockedSource) read(p []byte, readVal *int64, readPos *int8) (n int, err error) {
-	r.lk.Lock()
-	n, err = read(p, r.src.Int63, readVal, readPos)
-	r.lk.Unlock()
-	return
-}
-
-func read(p []byte, int63 func() int64, readVal *int64, readPos *int8) (n int, err error) {
-	pos := *readPos
-	val := *readVal
-	for n = 0; n < len(p); n++ {
-		if pos == 0 {
-			val = int63()
-			pos = 7
-		}
-		p[n] = byte(val)
-		val >>= 8
-		pos--
-	}
-	*readPos = pos
-	*readVal = val
-	return
-}
-
-// copied from https://sourcegraph.com/github.com/timtadh/data-structures@master/-/blob/test/support.go
-
-type T testing.T
-
-func (t *T) Assert(ok bool, msg string, vars ...ItemValue) {
-	if !ok {
-		t.Log("\n" + string(debug.Stack()))
-		var objects []interface{}
-		for _, t := range vars {
-			objects = append(objects, t)
-		}
-		t.Fatalf(msg, objects...)
-	}
-}
-
-func (t *T) AssertNil(errors ...error) {
-	any := false
-	for _, err := range errors {
-		if err != nil {
-			any = true
-			t.Log("\n" + string(debug.Stack()))
-			t.Error(err)
-		}
-	}
-	if any {
-		t.Fatal("assert failed")
-	}
-}
-
-func RandSlice(length int) []byte {
-	slice := make([]byte, length)
-	if _, err := crand.Read(slice); err != nil {
-		panic(err)
-	}
-	return slice
-}
-
-func RandHex(length int) string {
-	return hex.EncodeToString(RandSlice(length / 2))
-}
-
-func RandStr(length int) string {
-	return string(RandSlice(length))
-}
\ No newline at end of file
diff --git a/weed/util/bptree/getter_setter.go b/weed/util/bptree/getter_setter.go
deleted file mode 100644
index dcaa7a0b6..000000000
--- a/weed/util/bptree/getter_setter.go
+++ /dev/null
@@ -1,72 +0,0 @@
-package bptree
-
-var (
-	protoNodeId = int64(0)
-)
-func GetProtoNodeId() int64 {
-	protoNodeId++
-	return protoNodeId
-}
-
-func (self *BpMap) getRoot() *BpNode {
-	return self.root
-}
-func (self *BpMap) setRoot(root *BpNode) {
-	self.root = root
-}
-
-func (self *BpTree) getRoot() *BpNode {
-	return self.root
-}
-func (self *BpTree) setRoot(root *BpNode) {
-	self.root = root
-}
-
-func (self *BpNode) getNext() *BpNode {
-	return self.next
-}
-func (self *BpNode) setNext(next *BpNode) {
-	self.next = next
-}
-func (self *BpNode) getPrev() *BpNode {
-	return self.prev
-}
-func (self *BpNode) setPrev(prev *BpNode) {
-	self.prev = prev
-}
-func (self *BpNode) getNode(x int)(*BpNode) {
-	return self.pointers[x]
-}
-
-func (self *BpNode) maybePersist(shouldPersist bool) error {
-	if !shouldPersist {
-		return nil
-	}
-	return self.persist()
-}
-func (self *BpNode) persist() error {
-	if self.nodeStore != nil {
-		return self.nodeStore.PersistFunc(self)
-	}
-	return nil
-}
-func (self *BpNode) destroy() error {
-	if self.nodeStore != nil {
-		return self.nodeStore.DestroyFunc(self)
-	}
-	return nil
-}
-
-func persist(a, b *BpNode) error {
-	if a != nil {
-		if err := a.persist(); err != nil {
-			return err
-		}
-	}
-	if b != nil {
-		if err := b.persist(); err != nil {
-			return err
-		}
-	}
-	return nil
-}
\ No newline at end of file
diff --git a/weed/util/bptree/int.go b/weed/util/bptree/int.go
deleted file mode 100644
index e8fd9511c..000000000
--- a/weed/util/bptree/int.go
+++ /dev/null
@@ -1,357 +0,0 @@
-package bptree
-
-import (
-	"encoding/binary"
-	"fmt"
-)
-
-type Int8 int8
-type UInt8 uint8
-type Int16 int16
-type UInt16 uint16
-type Int32 int32
-type UInt32 uint32
-type Int64 int64
-type UInt64 uint64
-type Int int
-type UInt uint
-
-func (self *Int8) MarshalBinary() ([]byte, error) {
-	bytes := make([]byte, 0)
-	bytes[0] = uint8(*self)
-	return bytes, nil
-}
-
-func (self *Int8) UnmarshalBinary(data []byte) error {
-	if len(data) != 1 {
-		return fmt.Errorf("data wrong size")
-	}
-	*self = Int8(data[0])
-	return nil
-}
-
-func (self Int8) Equals(other Equatable) bool {
-	if o, ok := other.(Int8); ok {
-		return self == o
-	} else {
-		return false
-	}
-}
-
-func (self Int8) Less(other Sortable) bool {
-	if o, ok := other.(Int8); ok {
-		return self < o
-	} else {
-		return false
-	}
-}
-
-func (self Int8) Hash() int {
-	return int(self)
-}
-
-func (self *UInt8) MarshalBinary() ([]byte, error) {
-	bytes := make([]byte, 0)
-	bytes[0] = uint8(*self)
-	return bytes, nil
-}
-
-func (self *UInt8) UnmarshalBinary(data []byte) error {
-	if len(data) != 1 {
-		return fmt.Errorf("data wrong size")
-	}
-	*self = UInt8(data[0])
-	return nil
-}
-
-func (self UInt8) Equals(other Equatable) bool {
-	if o, ok := other.(UInt8); ok {
-		return self == o
-	} else {
-		return false
-	}
-}
-
-func (self UInt8) Less(other Sortable) bool {
-	if o, ok := other.(UInt8); ok {
-		return self < o
-	} else {
-		return false
-	}
-}
-
-func (self UInt8) Hash() int {
-	return int(self)
-}
-
-func (self *Int16) MarshalBinary() ([]byte, error) {
-	bytes := make([]byte, 2)
-	binary.BigEndian.PutUint16(bytes, uint16(*self))
-	return bytes, nil
-}
-
-func (self *Int16) UnmarshalBinary(data []byte) error {
-	if len(data) != 2 {
-		return fmt.Errorf("data wrong size")
-	}
-	*self = Int16(binary.BigEndian.Uint16(data))
-	return nil
-}
-
-func (self Int16) Equals(other Equatable) bool {
-	if o, ok := other.(Int16); ok {
-		return self == o
-	} else {
-		return false
-	}
-}
-
-func (self Int16) Less(other Sortable) bool {
-	if o, ok := other.(Int16); ok {
-		return self < o
-	} else {
-		return false
-	}
-}
-
-func (self Int16) Hash() int {
-	return int(self)
-}
-
-func (self *UInt16) MarshalBinary() ([]byte, error) {
-	bytes := make([]byte, 2)
-	binary.BigEndian.PutUint16(bytes, uint16(*self))
-	return bytes, nil
-}
-
-func (self *UInt16) UnmarshalBinary(data []byte) error {
-	if len(data) != 2 {
-		return fmt.Errorf("data wrong size")
-	}
-	*self = UInt16(binary.BigEndian.Uint16(data))
-	return nil
-}
-
-func (self UInt16) Equals(other Equatable) bool {
-	if o, ok := other.(UInt16); ok {
-		return self == o
-	} else {
-		return false
-	}
-}
-
-func (self UInt16) Less(other Sortable) bool {
-	if o, ok := other.(UInt16); ok {
-		return self < o
-	} else {
-		return false
-	}
-}
-
-func (self UInt16) Hash() int {
-	return int(self)
-}
-
-func (self *Int32) MarshalBinary() ([]byte, error) {
-	bytes := make([]byte, 4)
-	binary.BigEndian.PutUint32(bytes, uint32(*self))
-	return bytes, nil
-}
-
-func (self *Int32) UnmarshalBinary(data []byte) error {
-	if len(data) != 4 {
-		return fmt.Errorf("data wrong size")
-	}
-	*self = Int32(binary.BigEndian.Uint32(data))
-	return nil
-}
-
-func (self Int32) Equals(other Equatable) bool {
-	if o, ok := other.(Int32); ok {
-		return self == o
-	} else {
-		return false
-	}
-}
-
-func (self Int32) Less(other Sortable) bool {
-	if o, ok := other.(Int32); ok {
-		return self < o
-	} else {
-		return false
-	}
-}
-
-func (self *UInt32) MarshalBinary() ([]byte, error) {
-	bytes := make([]byte, 4)
-	binary.BigEndian.PutUint32(bytes, uint32(*self))
-	return bytes, nil
-}
-
-func (self *UInt32) UnmarshalBinary(data []byte) error {
-	if len(data) != 4 {
-		return fmt.Errorf("data wrong size")
-	}
-	*self = UInt32(binary.BigEndian.Uint32(data))
-	return nil
-}
-
-func (self Int32) Hash() int {
-	return int(self)
-}
-
-func (self UInt32) Equals(other Equatable) bool {
-	if o, ok := other.(UInt32); ok {
-		return self == o
-	} else {
-		return false
-	}
-}
-
-func (self UInt32) Less(other Sortable) bool {
-	if o, ok := other.(UInt32); ok {
-		return self < o
-	} else {
-		return false
-	}
-}
-
-func (self UInt32) Hash() int {
-	return int(self)
-}
-
-func (self *Int64) MarshalBinary() ([]byte, error) {
-	bytes := make([]byte, 8)
-	binary.BigEndian.PutUint64(bytes, uint64(*self))
-	return bytes, nil
-}
-
-func (self *Int64) UnmarshalBinary(data []byte) error {
-	if len(data) != 8 {
-		return fmt.Errorf("data wrong size")
-	}
-	*self = Int64(binary.BigEndian.Uint64(data))
-	return nil
-}
-
-func (self Int64) Equals(other Equatable) bool {
-	if o, ok := other.(Int64); ok {
-		return self == o
-	} else {
-		return false
-	}
-}
-
-func (self Int64) Less(other Sortable) bool {
-	if o, ok := other.(Int64); ok {
-		return self < o
-	} else {
-		return false
-	}
-}
-
-func (self Int64) Hash() int {
-	return int(self>>32) ^ int(self)
-}
-
-func (self *UInt64) MarshalBinary() ([]byte, error) {
-	bytes := make([]byte, 8)
-	binary.BigEndian.PutUint64(bytes, uint64(*self))
-	return bytes, nil
-}
-
-func (self *UInt64) UnmarshalBinary(data []byte) error {
-	if len(data) != 8 {
-		return fmt.Errorf("data wrong size")
-	}
-	*self = UInt64(binary.BigEndian.Uint64(data))
-	return nil
-}
-
-func (self UInt64) Equals(other Equatable) bool {
-	if o, ok := other.(UInt64); ok {
-		return self == o
-	} else {
-		return false
-	}
-}
-
-func (self UInt64) Less(other Sortable) bool {
-	if o, ok := other.(UInt64); ok {
-		return self < o
-	} else {
-		return false
-	}
-}
-
-func (self UInt64) Hash() int {
-	return int(self>>32) ^ int(self)
-}
-
-func (self *Int) MarshalBinary() ([]byte, error) {
-	bytes := make([]byte, 4)
-	binary.BigEndian.PutUint32(bytes, uint32(*self))
-	return bytes, nil
-}
-
-func (self *Int) UnmarshalBinary(data []byte) error {
-	if len(data) != 4 {
-		return fmt.Errorf("data wrong size")
-	}
-	*self = Int(binary.BigEndian.Uint32(data))
-	return nil
-}
-
-func (self Int) Equals(other Equatable) bool {
-	if o, ok := other.(Int); ok {
-		return self == o
-	} else {
-		return false
-	}
-}
-
-func (self Int) Less(other Sortable) bool {
-	if o, ok := other.(Int); ok {
-		return self < o
-	} else {
-		return false
-	}
-}
-
-func (self Int) Hash() int {
-	return int(self)
-}
-
-func (self *UInt) MarshalBinary() ([]byte, error) {
-	bytes := make([]byte, 4)
-	binary.BigEndian.PutUint32(bytes, uint32(*self))
-	return bytes, nil
-}
-
-func (self *UInt) UnmarshalBinary(data []byte) error {
-	if len(data) != 4 {
-		return fmt.Errorf("data wrong size")
-	}
-	*self = UInt(binary.BigEndian.Uint32(data))
-	return nil
-}
-
-func (self UInt) Equals(other Equatable) bool {
-	if o, ok := other.(UInt); ok {
-		return self == o
-	} else {
-		return false
-	}
-}
-
-func (self UInt) Less(other Sortable) bool {
-	if o, ok := other.(UInt); ok {
-		return self < o
-	} else {
-		return false
-	}
-}
-
-func (self UInt) Hash() int {
-	return int(self)
-}
diff --git a/weed/util/bptree/rand.go b/weed/util/bptree/rand.go
deleted file mode 100644
index 08b2e50ab..000000000
--- a/weed/util/bptree/rand.go
+++ /dev/null
@@ -1,2 +0,0 @@
-package bptree
-
diff --git a/weed/util/bptree/serde.go b/weed/util/bptree/serde.go
deleted file mode 100644
index 2a98a774a..000000000
--- a/weed/util/bptree/serde.go
+++ /dev/null
@@ -1,10 +0,0 @@
-package bptree
-
-func (protoNode *ProtoNode) ToBpTree() *BpTree {
-	node := protoNode.ToBpNode()
-	return &BpTree{root: node}
-}
-
-func (protoNode *ProtoNode) ToBpNode() *BpNode {
-	return nil
-}
\ No newline at end of file
diff --git a/weed/util/bptree/serde_test.go b/weed/util/bptree/serde_test.go
deleted file mode 100644
index 27ccccb78..000000000
--- a/weed/util/bptree/serde_test.go
+++ /dev/null
@@ -1,46 +0,0 @@
-package bptree
-
-import (
-	"fmt"
-	"testing"
-)
-
-type nodeStoreMapImpl struct {
-	m map[int64]*ProtoNode
-}
-
-func (n *nodeStoreMapImpl) PersistFunc(node *BpNode) error {
-	println("saving node", node.protoNodeId)
-	n.m[node.protoNodeId] = node.protoNode
-	return nil
-}
-func (n *nodeStoreMapImpl) DestroyFunc(node *BpNode) error {
-	println("delete node", node.protoNodeId)
-	delete(n.m, node.protoNodeId)
-	return nil
-}
-
-func TestSerDe(t *testing.T) {
-
-	nodeStore := &nodeStoreMapImpl{
-		m: make(map[int64]*ProtoNode),
-	}
-
-	tree := NewBpTree(3, nodeStore)
-
-	for i:=0;i<32;i++{
-		println("add", i)
-		tree.Add(String(fmt.Sprintf("%02d", i)), nil)
-	}
-
-	for i:=5;i<9;i++{
-		println("----------", i)
-		tree.RemoveWhere(String(fmt.Sprintf("%02d", i)), func(value ItemValue) bool {
-			return true
-		})
-		printTree(tree.root, "")
-	}
-
-
-
-}
\ No newline at end of file
diff --git a/weed/util/bptree/string.go b/weed/util/bptree/string.go
deleted file mode 100644
index 262220878..000000000
--- a/weed/util/bptree/string.go
+++ /dev/null
@@ -1,71 +0,0 @@
-package bptree
-
-import (
-	"bytes"
-	"hash/fnv"
-)
-
-type String string
-type ByteSlice []byte
-
-func (self *String) MarshalBinary() ([]byte, error) {
-	return []byte(*self), nil
-}
-
-func (self *String) UnmarshalBinary(data []byte) error {
-	*self = String(data)
-	return nil
-}
-
-func (self String) Equals(other Equatable) bool {
-	if o, ok := other.(String); ok {
-		return self == o
-	} else {
-		return false
-	}
-}
-
-func (self String) Less(other Sortable) bool {
-	if o, ok := other.(String); ok {
-		return self < o
-	} else {
-		return false
-	}
-}
-
-func (self String) Hash() int {
-	h := fnv.New32a()
-	h.Write([]byte(string(self)))
-	return int(h.Sum32())
-}
-
-func (self *ByteSlice) MarshalBinary() ([]byte, error) {
-	return []byte(*self), nil
-}
-
-func (self *ByteSlice) UnmarshalBinary(data []byte) error {
-	*self = ByteSlice(data)
-	return nil
-}
-
-func (self ByteSlice) Equals(other Equatable) bool {
-	if o, ok := other.(ByteSlice); ok {
-		return bytes.Equal(self, o)
-	} else {
-		return false
-	}
-}
-
-func (self ByteSlice) Less(other Sortable) bool {
-	if o, ok := other.(ByteSlice); ok {
-		return bytes.Compare(self, o) < 0 // -1 if a < b
-	} else {
-		return false
-	}
-}
-
-func (self ByteSlice) Hash() int {
-	h := fnv.New32a()
-	h.Write([]byte(self))
-	return int(h.Sum32())
-}
diff --git a/weed/util/bptree/tree_store/memory_store.go b/weed/util/bptree/tree_store/memory_store.go
deleted file mode 100644
index 467455664..000000000
--- a/weed/util/bptree/tree_store/memory_store.go
+++ /dev/null
@@ -1,29 +0,0 @@
-package tree_store
-
-import "errors"
-
-var (
-	NotFound = errors.New("not found")
-)
-
-type MemoryTreeStore struct {
-	m map[int64][]byte
-}
-
-func NewMemoryTreeStore() *MemoryTreeStore{
-	return &MemoryTreeStore{
-		m: make(map[int64][]byte),
-	}
-}
-
-func (m *MemoryTreeStore) Put(k int64, v []byte) error {
-	m.m[k] = v
-	return nil
-}
-
-func (m *MemoryTreeStore) Get(k int64) ([]byte, error) {
-	if v, found := m.m[k]; found {
-		return v, nil
-	}
-	return nil, NotFound
-}
diff --git a/weed/util/bptree/tree_store/tree_store.go.go b/weed/util/bptree/tree_store/tree_store.go.go
deleted file mode 100644
index 6a0af6ae6..000000000
--- a/weed/util/bptree/tree_store/tree_store.go.go
+++ /dev/null
@@ -1,6 +0,0 @@
-package tree_store
-
-type TreeStore interface {
-	Put(k int64, v []byte) error
-	Get(k int64) ([]byte, error)
-}
diff --git a/weed/util/bptree/types.go b/weed/util/bptree/types.go
deleted file mode 100644
index f987e0419..000000000
--- a/weed/util/bptree/types.go
+++ /dev/null
@@ -1,98 +0,0 @@
-package bptree
-
-import (
-	"errors"
-	"fmt"
-)
-
-type Equatable interface {
-	Equals(b Equatable) bool
-}
-
-type Sortable interface {
-	Equatable
-	Less(b Sortable) bool
-}
-
-type Hashable interface {
-	Sortable
-	Hash() int
-}
-
-var BpTreeError = fmt.Errorf
-
-func NegativeSize() error {
-	return errors.New("negative size")
-}
-
-type Iterator func() (item ItemValue, next Iterator)
-type KIterator func() (key ItemKey, next KIterator)
-type KVIterator func() (key ItemKey, value ItemValue, next KVIterator)
-type KVIterable interface {
-	Iterate() KVIterator
-}
-
-type MapOperable interface {
-	Has(key ItemKey) bool
-	Put(key ItemKey, value ItemValue) (err error)
-	Get(key ItemKey) (value ItemValue, err error)
-	Remove(key ItemKey) (value ItemValue, err error)
-}
-
-type WhereFunc func(value ItemValue) bool
-
-func MakeValuesIterator(obj KVIterable) Iterator {
-	kv_iterator := obj.Iterate()
-	var v_iterator Iterator
-	v_iterator = func() (value ItemValue, next Iterator) {
-		_, value, kv_iterator = kv_iterator()
-		if kv_iterator == nil {
-			return nil, nil
-		}
-		return value, v_iterator
-	}
-	return v_iterator
-}
-
-func MakeItemsIterator(obj KVIterable) (kit KIterator) {
-	kv_iterator := obj.Iterate()
-	kit = func() (item ItemKey, next KIterator) {
-		var key ItemKey
-		var value ItemValue
-		key, value, kv_iterator = kv_iterator()
-		if kv_iterator == nil {
-			return nil, nil
-		}
-		return &MapEntry{key, value}, kit
-	}
-	return kit
-}
-
-type MapEntry struct {
-	Key   ItemKey
-	Value ItemValue
-}
-
-func (m *MapEntry) Equals(other Equatable) bool {
-	if o, ok := other.(*MapEntry); ok {
-		return m.Key.Equals(o.Key)
-	} else {
-		return m.Key.Equals(other)
-	}
-}
-
-func (m *MapEntry) Less(other Sortable) bool {
-	if o, ok := other.(*MapEntry); ok {
-		return m.Key.Less(o.Key)
-	} else {
-		return m.Key.Less(other)
-	}
-}
-
-func (m *MapEntry) Hash() int {
-	return m.Key.Hash()
-}
-
-func (m *MapEntry) String() string {
-	return fmt.Sprintf("<MapEntry %v: %v>", m.Key, m.Value)
-}