tidwall / btree Goto Github PK
View Code? Open in Web Editor NEWB-tree implementation for Go
License: MIT License
B-tree implementation for Go
License: MIT License
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.
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.
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?
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.
Ascend
with the non-safe version (provided outside locking)?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
.
I noticed the Hinting was not exposed on Map && Set. Is there a reason behind this or is it worth exploring creating a PR?
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.
ADMIN
#- [ ] ____New on here```
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)
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
Just a general question, noticed NewMap does not have the option to turn locks on or off like btree.New does.
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
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:
Please say if this is deemed as a not-desired complexity tradeoff!
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.
b++
b plus tree
Why there is no map for non generic versions of Go?
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.
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.
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.
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"
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)
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
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.