An Adaptive Radix Tree implementation.

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:

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.
Simple, automatic, and customizable tree pretty-printing in Rust.

display_tree Simple, automatic, and customizable tree pretty-printing in Rust. This crate provides tools to easily pretty-print data as a tree, includ

Use rust programming language to create a b+ tree.
Use rust programming language to create a b+ tree.

Use rust programming language to create a b+ tree.

Purplecoin Core integration/staging tree

ℙurplecoin Official implementation of Purplecoin, the first stateless cryptocurrency. Requires Rust Nightly =v1.63.0. WARNING The source code is stil

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

indexset A pure-rust(with zero dependencies, no-std) fenwick tree, for the efficient computation of dynamic prefix sums. Background Did you ever have

A tree-backed slab allocator

beton A tree-backed slab allocator API Docs | Releases | Contributing Installation $ cargo add beton Memory Safety This crate uses unsafe operations i

Experimental Quantum Computer Simulator + Quantum Chess Implementation
Experimental Quantum Computer Simulator + Quantum Chess Implementation

Quantum Chess A somewhat hacky implementation of this paper (made in a week over a holiday). It's not heavily tested and probably has some bugs still

Ray Tracing: The Next Week implementation in Rust
Ray Tracing: The Next Week implementation in Rust

rttnw Ray Tracing: The Next Week implementation in Rust How to run Install Rust: Link here. Run project git clone https://github.com/luliic2/rttnw cd

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

µKanren-rs This is a Rust implementation of µKanren, a featherweight relational programming language. See the original Scheme implementation here for

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

RustZX for ESP32 - experimental version Goal of the project: Run ZX Spectrum on ESP32 HW: ESP32 OTG USB with ST7789 display References Rust code for E

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

    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
Owner
Ryan Daum
A crusty old porcupine.
Ryan Daum
A radix tree implementation for router, and provides CRUD operations.

radixtree A radix tree implementation for router, and provides CRUD operations. Radixtree is part of treemux, on top of which updates and removes are

Zhenwei Guo 2 Dec 19, 2022
A Rust implementation of generic prefix tree (trie) map with wildcard capture support

prefix_tree_map A Rust implementation of generic prefix tree (trie) map with wildcard capture support. Design Trie is a good data structure for storin

EAimTY 3 Dec 6, 2022
Serialize & deserialize device tree binary using serde

serde_device_tree Use serde framework to deserialize Device Tree Blob binary files; no_std compatible. Use this library Run example: cargo run --examp

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

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

Nouzan 1 Dec 5, 2021
A cargo plugin for showing a tree-like overview of a crate's modules.

cargo-modules Synopsis A cargo plugin for showing an overview of a crate's modules. Motivation With time, as your Rust projects grow bigger and bigger

Vincent Esche 445 Jan 3, 2023
A minimal `syn` syntax tree pretty-printer

prettyplease::unparse A minimal syn syntax tree pretty-printer. Overview This is a pretty-printer to turn a syn syntax tree into a String of well-form

David Tolnay 429 Dec 28, 2022
Embeddable tree-walk interpreter for a "mostly lazy" Lisp-like scripting language.

ceceio Embeddable tree-walk interpreter for a "mostly lazy" Lisp-like scripting language. Just a work-in-progress testbed for now. Sample usage us

Vinícius Miguel 7 Aug 18, 2022
Key-value store for embedded systems, for raw NOR flash, using an LSM-Tree.

ekv Key-value store for embedded systems, for raw NOR flash, using an LSM-Tree. Features None yet TODO Everything Minimum supported Rust version (MSRV

Dario Nieuwenhuis 16 Nov 22, 2022
A tutorial of building an LSM-Tree storage engine in a week! (WIP)

LSM in a Week Build a simple key-value storage engine in a week! Tutorial The tutorial is available at https://skyzh.github.io/mini-lsm. You can use t

Alex Chi 870 Jan 3, 2023
Purplecoin Core integration/staging tree

ℙurplecoin Official implementation of Purplecoin, the first stateless cryptocurrency. Requires Rust Nightly >=v1.63.0. WARNING The source code is stil

Purplecoin 5 Dec 31, 2022