Ecosyste.ms: Packages
An open API service providing package, version and dependency metadata of many open source software ecosystems and registries.
proxy.golang.org : github.com/jayloop/radix
Package radix implements a memory efficient and concurrency safe adaptive radix tree (ART). The typical use case is an in-memory database index where the tree stores a pointer to where an object is stored on a permanent storage. The data structure is free of memory pointers so the overhead from garbage collection is minimal. 1. To save memory, this tree does not store the full keys in the leaves. It only stores as much information as needed to distinguish between the different keys. It is assumed the full keys are retrievable by the user. In the typical use case they would be stored on a permanent storage. 2. Max 55 bits are available for storing values associated with the inserted keys. The values could be offsets to permanent storage or compressed memory pointers. 3. The tree accepts any []byte data as keys, but in case you want to use range or min/max searches, the key data needs to be binary comparable. For uint64 all you need to do is store them in big-endian order. For int64 the sign bit also needs to be flipped. ASCII strings are trivial, but floating point numbers requires more transformations. UTF8 is rather complex (see golang.org/x/text/collate). 4. When indexing keys of variable length (like strings) the requirement is that no key may be the prefix of another key. A simple solution for this is to append a 0 byte on all keys (given 0 is not used within the keys). For improved performance unsafe operations are used in two cases: when persisting uint64 slices to a state file and when accessing []byte prefixes within the uint64 slices.
Registry
-
Source
- Documentation
- JSON
purl: pkg:golang/github.com/jayloop/radix
Keywords: concurrent, data-structures, database, go, golang, index, lock-free, prefix-search, prefix-tree, radix-tree
License: MIT
Latest release: over 3 years ago
First release: over 3 years ago
Namespace: github.com/jayloop
Stars: 1 on GitHub
Forks: 0 on GitHub
See more repository details: repos.ecosyste.ms
Last synced: 25 days ago