go-adaptive-radix-tree
A high-performance, memory-efficient Go implementation of Adaptive Radix Trees with zero-allocation searches and ordered iteration.
What is go-adaptive-radix-tree?
go-adaptive-radix-tree is a Go implementation of the Adaptive Radix Tree (ART), a data structure designed for efficient in-memory indexing of keys. It provides high-performance search, insertion, and deletion operations while maintaining keys in sorted order, enabling additional operations like range scans and prefix lookups that hash tables cannot support.
Go developers building systems requiring fast in-memory indexing with ordered data access patterns, such as databases, search engines, or applications needing prefix-based autocomplete functionality.
Developers choose this library for its combination of hash-table-like performance with the ordered iteration capabilities of trees, plus its specific optimization of zero memory allocations during searches, which outperforms other Go ART implementations.
Overview
Adaptive Radix Trees implemented in Go
Use Cases
Best For
- Implementing in-memory indexes for databases or search engines
- Building autocomplete systems with prefix-based lookup
- Applications requiring range queries over string or byte array keys
- Systems needing ordered iteration over large key sets
- Memory-constrained environments requiring space-efficient data structures
- High-performance applications where zero-allocation searches are critical
Not Ideal For
- Applications requiring persistent storage out-of-the-box without additional disk I/O code
- Projects where unordered hash tables suffice and sorted operations like range scans are never needed
- Systems needing built-in thread-safe concurrent read-write access without manual synchronization
- Scenarios with datasets larger than available RAM, as this is an in-memory structure
Pros & Cons
Pros
Search operations incur zero memory allocations, as benchmarked against go-art, reducing garbage collection overhead and improving lookup performance.
Keys are stored lexicographically, enabling efficient range scans, prefix lookups, and ordered iteration—features hash tables lack.
Uses adaptive node sizes to minimize memory overhead, making it space-optimized compared to other tree implementations.
Accepts any byte array as keys, including those with null bytes, allowing for versatile data encoding without restrictions.
Cons
Insert operations involve memory allocations, as shown in benchmarks (e.g., 1.2M allocs for 235K words), which can impact write-heavy workloads.
The library does not provide thread-safe operations, requiring developers to implement external synchronization for concurrent access, adding complexity.
Specialized for in-memory indexing with sorted access; not suitable for persistent storage or as a general-purpose replacement for all map scenarios.
Frequently Asked Questions
Related Projects
bleveA modern text/numeric/geo-spatial/vector indexing library for go
trieData structure and relevant algorithms for extremely fast prefix/fuzzy string searching.
go-edlib📚 String comparison and edit distance algorithms library, featuring : Levenshtein, LCS, Hamming, Damerau levenshtein (OSA and Adjacent transpositions algorithms), Jaro-Winkler, Cosine, etc...
levenshteinGo implementation to calculate Levenshtein Distance.
Found a gem we're missing?
Open-Awesome is built by the community, for the community. Submit a project, suggest an awesome list, or help improve the catalog on GitHub.