An Adaptive Radix Tree implementation.

Ryan Daum

Last update: Jun 16, 2023

Related tags

Learning Resources rart-rs

Overview

Ryan's Adaptive Radix Tree

This is yet another implementation of an Adaptive Radix Tree (ART) in Rust. ARTs are an ordered associative (key-value) structure that outperform BTrees for many use cases.

The implementation is based on the paper The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases by Viktor Leis, Alfons Kemper, and Thomas Neumann.

I have not (yet) implemented the concurrent form described in later papers.

During implementation I looked at the following implementations, and borrowed some flow and ideas from them:

https://github.com/armon/libart/ A C implementation
https://github.com/rafaelkallis/adaptive-radix-tree C++ implementation
https://github.com/Lagrang/art-rs Another implementation in Rust. (The criterion benches I have were on the whole borrowed from here originally)

Performance boost can be gained through fixed sized keys and partials. There are a selection of key types and partials provided under the partials module.

I believe my implementation to be competitive, performance wise. The included benches compare against BTreeMap, HashMap, and art-rs and show what you'd expect: performance between a hashtable and a btree for random inserts and retrievals, but sequential inserts and retrievals are much faster than either.

Some notes:

Minimal external dependencies.
Compiles for stable Rust.
There are some bits of compartmentalized unsafe code for performance reasons, but the public API is safe.
Uses explicit SIMD optimizations for x86 SSE for the 16-child inner keyed node; an implementation for ARM NEON is also there, but doesn't really provide much performance benefit.

More documentation to come. Still working at smoothing the rough corners. Contributions welcome.

You might also like...

Simple, automatic, and customizable tree pretty-printing in Rust.

Comments

Code suggestion: remove redundant `?` and `unwrap`

Thanks for the work on this project!

I see a couple of instances where unwrap can be removed and replaced with only ?. As a general advice, unwrap can often be avoided and it is usually preferable to do so as a stylistic thing.

Two examples:

pub fn get<K: Key>(&self, key: &K) -> Option<&V> {
    self.root.as_ref()?;

    let root = self.root.as_ref().unwrap();
    AdaptiveRadixTree::get_iterate(root, key)
}

Could be written as

pub fn get<K: Key>(&self, key: &K) -> Option<&V> {
    AdaptiveRadixTree::get_iterate(self.root.as_ref()?, key)
}

        let next_node = cur_node.seek_child(k);
        next_node?;
        depth += cur_node.prefix.length();
        cur_node = next_node.unwrap();

Could be written as

        depth += cur_node.prefix.length()
        cur_node = cur_node.seek_child(k)?;

opened by jtroo 1

An Adaptive Radix Tree implementation.

Related tags

Overview

Ryan's Adaptive Radix Tree

You might also like...

Simple, automatic, and customizable tree pretty-printing in Rust.

Use rust programming language to create a b+ tree.

Purplecoin Core integration/staging tree

A pure-rust(with zero dependencies) fenwick tree, for the efficient computation of dynamic prefix sums.

A tree-backed slab allocator

Experimental Quantum Computer Simulator + Quantum Chess Implementation

Ray Tracing: The Next Week implementation in Rust

Rust implementation of µKanren, a featherweight relational programming language.

ESP32 implementation of RustZX Spectrum emulator for ESP32-USB-OTG

Comments

Code suggestion: remove redundant `?` and `unwrap`

Owner

Ryan Daum

A radix tree implementation for router, and provides CRUD operations.

A Rust implementation of generic prefix tree (trie) map with wildcard capture support

Serialize & deserialize device tree binary using serde

An embedded key-value storage for learning purpose, which is based on the idea of SSTable / LSM-tree.

A cargo plugin for showing a tree-like overview of a crate's modules.

A minimal `syn` syntax tree pretty-printer

Embeddable tree-walk interpreter for a "mostly lazy" Lisp-like scripting language.

Key-value store for embedded systems, for raw NOR flash, using an LSM-Tree.

A tutorial of building an LSM-Tree storage engine in a week! (WIP)

Purplecoin Core integration/staging tree