ProductPromotion
Logo

Go.Lang

made by https://0x3d.site

GitHub - plar/go-adaptive-radix-tree: Adaptive Radix Trees implemented in Go
Adaptive Radix Trees implemented in Go. Contribute to plar/go-adaptive-radix-tree development by creating an account on GitHub.
Visit Site

GitHub - plar/go-adaptive-radix-tree: Adaptive Radix Trees implemented in Go

GitHub - plar/go-adaptive-radix-tree: Adaptive Radix Trees implemented in Go

An Adaptive Radix Tree Implementation in Go

Coverage Status Go Report Card GoDoc

This library provides a Go implementation of the Adaptive Radix Tree (ART).

Features:

  • Lookup performance surpasses highly tuned alternatives
  • Support for highly efficient insertions and deletions
  • Space efficient
  • Performance is comparable to hash tables
  • Maintains the data in sorted order, which enables additional operations like range scan and prefix lookup
  • O(k) search/insert/delete operations, where k is the length of the key
  • Minimum / Maximum value lookups
  • Ordered iteration
  • Prefix-based iteration
  • Support for keys with null bytes, any byte array could be a key

Usage

package main

import (
    "fmt"
    "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")
    value, found := tree.Search(art.Key("Hi, I'm Key"))
    if found {
        fmt.Printf("Search value=%v\n", value)
    }

    tree.ForEach(func(node art.Node) bool {
        fmt.Printf("Callback value=%v\n", node.Value())
        return true
    })

    for it := tree.Iterator(); it.HasNext(); {
        value, _ := it.Next()
        fmt.Printf("Iterator value=%v\n", value.Value())
    }
}

// Output:
// Search value=Nice to meet you, I'm Value
// Callback value=Nice to meet you, I'm Value
// Iterator value=Nice to meet you, I'm Value

Documentation

Check out the documentation on godoc.org

Performance

plar/go-adaptive-radix-tree outperforms kellydunn/go-art by avoiding memory allocations during search operations. It also provides prefix based iteration over the tree.

Benchmarks were performed on datasets extracted from different projects:

  • The "Words" dataset contains a list of 235,886 english words. [2]
  • The "UUIDs" dataset contains 100,000 uuids. [2]
  • The "HSK Words" dataset contains 4,995 words. [4]
go-adaptive-radix-tree # Average time Bytes per operation Allocs per operation
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
go-art
Tree Insert Words 5 272,047,975 ns/op 81,628,987 B/op 2,547,316 allocs/op
Tree Search Words 10 129,011,177 ns/op 13,272,278 B/op 1,659,033 allocs/op
Tree Insert UUIDs 10 140,309,246 ns/op 33,678,160 B/op 874,561 allocs/op
Tree Search UUIDs 20 82,120,943 ns/op 3,883,131 B/op 485,391 allocs/op

To see more benchmarks just run

$ ./make qa/benchmarks

References

[1] The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases (Specification)

[2] C99 implementation of the Adaptive Radix Tree

[3] Another Adaptive Radix Tree implementation in Go

[4] HSK Words. HSK(Hanyu Shuiping Kaoshi) - Standardized test of Standard Mandarin Chinese proficiency.

Articles
to learn more about the golang concepts.

Resources
which are currently available to browse on.

mail [email protected] to add your project or resources here ๐Ÿ”ฅ.

FAQ's
to know more about the topic.

mail [email protected] to add your project or resources here ๐Ÿ”ฅ.

Queries
or most google FAQ's about GoLang.

mail [email protected] to add more queries here ๐Ÿ”.

More Sites
to check out once you're finished browsing here.

0x3d
https://www.0x3d.site/
0x3d is designed for aggregating information.
NodeJS
https://nodejs.0x3d.site/
NodeJS Online Directory
Cross Platform
https://cross-platform.0x3d.site/
Cross Platform Online Directory
Open Source
https://open-source.0x3d.site/
Open Source Online Directory
Analytics
https://analytics.0x3d.site/
Analytics Online Directory
JavaScript
https://javascript.0x3d.site/
JavaScript Online Directory
GoLang
https://golang.0x3d.site/
GoLang Online Directory
Python
https://python.0x3d.site/
Python Online Directory
Swift
https://swift.0x3d.site/
Swift Online Directory
Rust
https://rust.0x3d.site/
Rust Online Directory
Scala
https://scala.0x3d.site/
Scala Online Directory
Ruby
https://ruby.0x3d.site/
Ruby Online Directory
Clojure
https://clojure.0x3d.site/
Clojure Online Directory
Elixir
https://elixir.0x3d.site/
Elixir Online Directory
Elm
https://elm.0x3d.site/
Elm Online Directory
Lua
https://lua.0x3d.site/
Lua Online Directory
C Programming
https://c-programming.0x3d.site/
C Programming Online Directory
C++ Programming
https://cpp-programming.0x3d.site/
C++ Programming Online Directory
R Programming
https://r-programming.0x3d.site/
R Programming Online Directory
Perl
https://perl.0x3d.site/
Perl Online Directory
Java
https://java.0x3d.site/
Java Online Directory
Kotlin
https://kotlin.0x3d.site/
Kotlin Online Directory
PHP
https://php.0x3d.site/
PHP Online Directory
React JS
https://react.0x3d.site/
React JS Online Directory
Angular
https://angular.0x3d.site/
Angular JS Online Directory