Improve the iterate seek to O(logN) (#25)
* improve the iterate seek to O(logN)
* add benchmark
diff --git a/btree.go b/btree.go
index 7e4551d..6ff062f 100644
--- a/btree.go
+++ b/btree.go
@@ -500,13 +500,14 @@
// thus creating a "greaterOrEqual" or "lessThanEqual" rather than just a
// "greaterThan" or "lessThan" queries.
func (n *node) iterate(dir direction, start, stop Item, includeStart bool, hit bool, iter ItemIterator) (bool, bool) {
- var ok bool
+ var ok, found bool
+ var index int
switch dir {
case ascend:
- for i := 0; i < len(n.items); i++ {
- if start != nil && n.items[i].Less(start) {
- continue
- }
+ if start != nil {
+ index, _ = n.items.find(start)
+ }
+ for i := index; i < len(n.items); i++ {
if len(n.children) > 0 {
if hit, ok = n.children[i].iterate(dir, start, stop, includeStart, hit, iter); !ok {
return hit, false
@@ -530,7 +531,15 @@
}
}
case descend:
- for i := len(n.items) - 1; i >= 0; i-- {
+ if start != nil {
+ index, found = n.items.find(start)
+ if !found {
+ index = index - 1
+ }
+ } else {
+ index = len(n.items) - 1
+ }
+ for i := index; i >= 0; i-- {
if start != nil && !n.items[i].Less(start) {
if !includeStart || hit || start.Less(n.items[i]) {
continue
diff --git a/btree_test.go b/btree_test.go
index 9eeb136..78a90cd 100644
--- a/btree_test.go
+++ b/btree_test.go
@@ -361,6 +361,21 @@
}
}
+func BenchmarkSeek(b *testing.B) {
+ b.StopTimer()
+ size := 100000
+ insertP := perm(size)
+ tr := New(*btreeDegree)
+ for _, item := range insertP {
+ tr.ReplaceOrInsert(item)
+ }
+ b.StartTimer()
+
+ for i := 0; i < b.N; i++ {
+ tr.AscendGreaterOrEqual(Int(i%size), func(i Item) bool { return false })
+ }
+}
+
func BenchmarkDeleteInsert(b *testing.B) {
b.StopTimer()
insertP := perm(benchmarkTreeSize)
