is there support for doing range scans?

For example:

start := []byte("foo_10")
end := []byte("foo_20")
trie.ForEachRange(start, end, func(node art.Node) bool {
    // do something with node
    return true
})

I think only prefix iteration is support currently? Would it be hard to add range iteration?

• as the base part of node, numChildren and prefixLen could be modified to uint8 to save 6 bytes each node except leaf;

type node struct { numChildren int prefixLen int prefix prefix }

• as the Kind type, int is also unnecessary, uint8 is enough too, this optimization will save 3 bytes for each art-node type Kind int

Hello,

I've been working with @prologic to try to bring bitcask up to version 1.0.

One of the things we've been struggling with is allowing a user to iterate over all keys in the tree and allow deletion by value, rather than by key (i.e. delete a key from within the ForEach callback function). The current implementation causes the ForEach to skip a node that would have been iterated over at some point after the deleted node (sometimes the next node, sometimes the one after that, etc.)

Would you consider letting us modify the iterator to pull the "next" value before the callback so that no nodes get skipped? Or would this be better done in a fork?

Sorry if my ask here is not clear, let me know if you need any further clarification.

1. possible to make this into an lru cache with fixed size? so that it can automatically remove items based on fifo

2. how does this compare with patricia trie? https://github.com/tchap/go-patricia any benchmarks on speed and mem storage size used against patricia?

great work by the way

Would it be possible to use something like flatbuffers or cap'n'proto as backing for the tree which would allow it to be persisted into disk, hence it would be loadable from disk to memory without the need to rebuild it?

Great job on building this library!

I was looking at the example in dump_tree.go and puzzled by the use of null byte "keys" for leaf nodes (since there is no extra byte in their key to pivot on). I'm not sure how that can result in a correct outcome.

I may still be missing something but this example shows why I think it's wrong unless it's a conscious decision not to allow null bytes in keys which isn't documented.

package main

import (
	"fmt"

	art "github.com/plar/go-adaptive-radix-tree"
)

func main() {
	tree := art.New()
	terms := []string{"A", "a", "aa", "aa\x00"}
	for _, term := range terms {
		tree.Insert(art.Key(term), term)
	}
	//fmt.Println(tree)

	// Should find "aa"
	fmt.Println(tree.Search(art.Key("aa")))
	// Should find "aa\x00"
	fmt.Println(tree.Search(art.Key("aa\x00")))

	// Expected Output (note the null byte doesn't print):
	// aa true
	// aa true
	//
	// Actual Output:
	// aa true
	// <nil> false

	// Dump output shows both the leaf "aa" stored with "key" of 0 as well as the
	// child with key 0:
	// ...
	//    │   ├── Node4 (0xc00000e2c0)
	//    │   │   prefix(0): [0 0 0 0 0 0 0 0 0 0] [··········]
	//    │   │   keys: [0 0 97 0] [··a·]
	//    │   │   children(3): [0xc00000e280 0xc00000e2b0 0xc00000e2e0 <nil>]
	//    │   │   ├── Leaf (0xc00000e280)
	//    │   │   │   key: [97 97] [aa]
	//    │   │   │   val: aa
	//    │   │   │
	//    │   │   ├── Leaf (0xc00000e2b0)
	//    │   │   │   key: [97 97 0] [aa·]
	//    │   │   │   val: aa
	// ...
}

Perhaps I'm missing something about the design that makes this expected behaviour? If leaves are going to be stored in this way (with an implicit null "key" indicating end of key/leaf). Then it seems to rule out null bytes in keys entirely? That seems like a limitation that's at least worth documenting.

It seems to stem from charAt returning 0 if the index is out of range of the key: https://github.com/plar/go-adaptive-radix-tree/blob/ae4b22ebc44e591df19fbc197c60b1405d52b526/node.go#L68-L70

I wonder if this is a relic of the fact this code is based on libart - in C strings are generally null-terminated. I've not tested but it would seem that libart has a bug here too: https://github.com/armon/libart/blob/73c46356e6752cc8b0b774a5d0f4d2a6832a5ed3/src/art.c#L616

In the case where the key being inserted is a prefix of the existing internal node, this will attempt to create a new leaf and insert it at the key[offset+prefix_diff] index in the internal node. In the case described that it's reading off the end of the array since the leaf key is a prefix of the current node which means either a random char is used from some other bit of memory, a segfault occurs, or (possibly why it's not been noticed) if the string was allocated with a null terminator then the off-by-one read just always returns a null byte which is equivalent behaviour to this Go implementation.

I don't know how actively this library is maintained and I don't intend to use it directly but was referring to the implementation as I'm writing an immutable ART in Go and was confused by this.

If the answer is "don't use null byte" that's cool, just wanted to make sure I understood the intention!

Thanks!

Great library!

Saw the following panic in my usage:

package main

import (
	art "github.com/plar/go-adaptive-radix-tree"
)

func main() {
	tree := art.New()

	tree.Insert(art.Key("Hi, I'm Key"), "Nice to meet you, I'm Value")
	tree.Insert(art.Key(nil), "Meet you again")
	tree.Insert(art.Key(nil), "Meet you again") // panic
}

https://go.dev/play/p/G6tYWq0QzpJ

And the resulting trace:

panic: runtime error: slice bounds out of range [1:0]

goroutine 1 [running]:
github.com/plar/go-adaptive-radix-tree.(*tree).recursiveInsert(0xc00009ae60?, 0xc000106050, {0x0, 0x0, 0x0}, {0x46e6e0?, 0x496e98}, 0x1)
	/tmp/gopath331505154/pkg/mod/github.com/plar/[email protected]/tree.go:120 +0x5d7
github.com/plar/go-adaptive-radix-tree.(*tree).recursiveInsert(0xc00010a000?, 0xc00009af60, {0x0, 0x0, 0x0}, {0x46e6e0?, 0x496e98}, 0x0)
	/tmp/gopath331505154/pkg/mod/github.com/plar/[email protected]/tree.go:175 +0x293
github.com/plar/go-adaptive-radix-tree.(*tree).Insert(0xc00009af58, {0x0?, 0x404bd9?, 0x60?}, {0x46e6e0?, 0x496e98?})
	/tmp/gopath331505154/pkg/mod/github.com/plar/[email protected]/tree.go:15 +0x48
main.main()
	/tmp/sandbox249177140/prog.go:12 +0xc5

Looking to investigate further, the documentation hints that nil should be supported as a key.

1. insert words are all words? how many total?
2. search words (26) what does that mean? just search for 1 word or many many words?

| Tree Insert Words | 9 | 117,888,698 ns/op | 37,942,744 B/op | 1,214,541 allocs/op | | Tree Search Words | 26 | 44,555,608 ns/op | 0 B/op | 0 allocs/op | | Tree Insert UUIDs | 18 | 59,360,135 ns/op | 18,375,723 B/op | 485,057 allocs/op | | Tree Search UUIDs | 54 | 21,265,931 ns/op | 0 B/op | 0 allocs/op |

ART trees are useful for using with HTTP Routers, but this implementation lacks wildcards.

http.Router.Register("foo/{bar}/quz", "custom value")

That above should match a path like foo/good-day/quz. I could have made a fork which implements wildcards adding a node exclusively for the wildcards, and adding an member to identify which branch is a wildcard to fallback if none matches, but there is too much verbose code I don't know what the fuck what does what and why.

In node.go, will be keys 48 bytes long?

type node48 struct {
	node
	children [node48Max]*artNode
	// keys     [node256Max]byte
	keys    [node48Max]byte
	present [4]uint64 // need 256 bits for keys
}

Does this library use SIMD instructions as per the original ART paper? It seems Go does in fact support SIMD instructions; See for example this package