tidwall/btree

B-tree implementation for Go

btree's Issues

Seek does not initialize iter item

Seek() does not initialize the internal item field in the iterator even when an item is found (i.e. Seek() returns true). This causes the call to Item() to return a zero value for the first item.

To reproduce:

$ go version
go version go1.18rc1 linux/amd64
$ cat go.mod
module repro

go 1.18

require github.com/tidwall/btree v1.1.1-0.20220220161908-7bec22d8e3fa // indirect
$ cat repro.go
package main

import (
	"fmt"

	"github.com/tidwall/btree"
)

func main() {
	t := btree.NewGeneric[string](func(a, b string) bool {
		return a < b
	})

	t.Set("a")
	t.Set("b")
	t.Set("c")
	t.Set("d")
	t.Set("e")

	iter := t.Iter()
	for ok := iter.Seek("b"); ok; ok = iter.Next() {
		fmt.Println(iter.Item())
	}
	iter.Release()
}
$ go run repro.go

c
d
e

Expected output

b
c
d
e

MapIter[K,V] Seek method does not initialize the item

There are two paths in Seek that return true, indicating that an item was found equal to or greater than the key. Neither set the item internally before returning causing subsequent calls to Item() to return the zero value.

Map for pre-generics version of Go

Why there is no map for non generic versions of Go?

add put method to set kvpairs , if old value exists, return val

how about "add put method to set kvpairs , if old value exists, return val", thinkabout this:
a position can only hold one element, but if the element return to user, then the position may be used for other element.
so, if user want to know the position situation, user must retrieve if the position is used

Does btree.Map use concurrency locks?

Just a general question, noticed NewMap does not have the option to turn locks on or off like btree.New does.

Generics

I saw you have a few commits planning to use generics. Do you have a work in progress for this? I would be willing to try it out in anacrolix/torrent, where I'm dealing with a lot of heap allocation overhead due to stuffing things into google/btree's Item interface.

Do we need a rebalancing process for the btree?

I was wondering if we need a rebalancing process for the tree.
Is there any case it grows imbalanced? If yes how should we manage it?

Nice. Does it come with a disk backed version one?

Basically wanting to use btree on disk but these are too large. for empty db creation, it uses 1mb. Can you create one that uses less than 100b with yours? Just looking for a disk backed version. Thx in advance.

    "github.com/timtadh/fs2/bptree"
    "github.com/timtadh/fs2/fmap"

How does copy-on-write actually work?

is b+ tree surport?

b++

b plus tree

Investigate if we can re-use allocated memory after `Map.Clear()`

In btree.Map, when we do btree.Map.Clear(), we are removing references to all old internal memory, which will cause it to be garbage collected.

If you then proceeded to build a similarly sized tree again, you'd have to re-allocate memory. If you use Clear() you should be expecting that the caller will at minimum, have to re-allocate the root. (Though to me the use case reads as wanting to preserve memory, vs instantiating a new map)

I feel like it'd be worth while to investigate if we can keep "spare allocated map nodes" around, for ability to re-use after Clear().

My intuition for an architecture here, is to have an MapNodeMemoryPool field in Map, and we move map nodes to there during a clear.

This lets us:

• Re-use memory after a clear
• Potentially re-use for MapNodes that get unallocated during normal operation
• Ensure theres never cross-thread dependencies if multiple maps are used in parallel. (As all memory pooling is done on a per-struct basis)

Please say if this is deemed as a not-desired complexity tradeoff!

Use of interface{} and constant type/length keys

When using this table with predictable constant-size binary keys(32 bytes), would this library still use interface{} or does it adjust to constant column/data sizes?

Would be great if the extra overhead can be avoided.

With go1.18rc1 getting error: constraints: package constraints is not in GOROOT

go get github.com/tidwall/btree@generics
go: downloading github.com/tidwall/btree v1.1.1-0.20220103194347-7411d3930522
github.com/tidwall/btree imports
constraints: package constraints is not in GOROOT (/Users//sdk/go1.18rc1/src/constraints)

The Map[K, V].find() API design discussion

can you export

func (tr *Map[K, V]) find(n *mapNode[K, V], key K) (index int, found bool)

to public domain, like:

func (tr *Map[K, V]) Find(n *mapNode[K, V], key K) (index int, found bool)

for method to use:

func (tr *Map[K, V]) GetAt(index int) (K, V, bool)

question about crash during iteration (probably because of mutation during iteration)

Hello @tidwall,

thank you a lot for this very nice module, it was very handy to me several times.

I'm trying to debug a crash in one of my applications:

runtime error: index out of range [44] with length 31 - trace:

/usr/lib/go/src/runtime/panic.go:914 +0x244
github.com/tidwall/btree.(*MapIter[...]).Next(0x1488618)
    .../github.com/tidwall/btree@v1.7.0/map.go:1051 +0x258
github.com/sahib/timeq/index.(*Iter).Next(0x3993ca0)
    .../github.com/sahib/timeq@v0.0.0-20231205120808-c044c518c189/index/index.go:152 +0x7c

The respective program has roughly the following structure and is single-threaded (so we can rule out data races):

var m *btree.Map[string,string]
for m := m.Iter(); iter.Next(); {   // crash in Next() sometimes
    // ...
    if someCondition {
        m.Set("foo", "bar")
    }
   // ...
}

If I'm reading the code for map iteration right, then mutation during iteration does not seem to be supported as Set() does not seem to update the current iterators' stack. Is this correct and is this missing from the documentation? If yes, adding it would be great. I could do a PR if you want.

possible panic when writing from multiple goroutines

This code immediately panics on my system:

package main

import (
	"math/rand"
	"sync"
	"time"

	"github.com/tidwall/btree"
)

func main() {
	var s btree.Map[int, int]
	numGoroutines := 1000
	numInsertsPerGoroutine := 1_000_000 / numGoroutines

	//var l sync.Mutex
	var wg sync.WaitGroup

	for i := 0; i < numGoroutines; i++ {
		wg.Add(1)
		go func(goroutineIndex int) {
			s1 := rand.NewSource(time.Now().UnixNano())
			r1 := rand.New(s1)
			defer wg.Done()
			for j := 0; j < numInsertsPerGoroutine; j++ {
				key := r1.Intn(100_000_000_000)
				//l.Lock()
				s.Set(key, j)
				//l.Unlock()
			}
		}(i)
	}

	wg.Wait()
}

panic: runtime error: index out of range [9] with length 9

goroutine 8 [running]:
github.com/tidwall/btree.(*Map[...]).nodeSet(0x48b160, 0x0, {0xc00005d6b0?, 0x408cf8?})
        /home/rene/go/pkg/mod/github.com/tidwall/[email protected]/map.go:234 +0x6f1
github.com/tidwall/btree.(*Map[...]).Set(0x48b160, 0x13220dc334, 0xb)
        /home/rene/go/pkg/mod/github.com/tidwall/[email protected]/map.go:169 +0x6f
main.main.func1(0x0?)
        /home/rene/Code/btree/main.go:28 +0x1a5
created by main.main
        /home/rene/Code/btree/main.go:21 +0x4d
exit status 2

Documentation for Get() is inaccurate

Docs say Get(key, value) instead of Get(key).

I'll submit a pull request if I can make a moment. Thanks, this b-tree is hot.

ADMIN

ADMIN

#- [ ] ____New on here```

Breaking changes in switching from uint64 to atomic.Uint64

Using go version <1.19 leads to compiler error:

/github.com/tidwall/[email protected]/btreeg.go:41:17: undefined: atomic.Uint64

I suggest to switch to 1.19 in go.mod and to explicitly say to the users that this package is not backward compatible.

Found this issue using buntDB where there is no go 1.19 requirements either.

PathHint on Map/Set?

I noticed the Hinting was not exposed on Map && Set. Is there a reason behind this or is it worth exploring creating a PR?

What is the purpose of path hints?

I am trying to understand how exactly I can use path hint methods. Could you please give some examples in the Readme. That would be helpful.

Delete during Ascend in thread-safe tree

Thanks for publishing this library!

I have a case where I want to delete some items in a range, which would be something like

bt.Ascend(start, func(item interface{}) {
  if filter(item) {
    bt.Delete(item)
  }
})

But since sync.Mutex isn't re-entrant, it deadlocks.

• Is it safe to do delete inside an Ascend with the non-safe version (provided outside locking)?
• If so, could Ascend unlock while the callback is running?

If not, would I have to do something like

delitem := start
for {
  bt.Ascend(delitem, func(item interface{}) {
    if filter(item) {
      delitem = item
      return false
    }
  })
  if isEnd(delitem) {
    break
  }
  bt.Delete(delitem)
}

In that case, it seems like there should be an AscendHint to complement DeleteHint.