Crate art_tree

Adaptive Radix Tree

The radix tree based on (The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases).

Examples

use art_tree::ByteString;
use art_tree::KeyBuilder;
use art_tree::Art;

let mut art = Art::<u16, u16>::new();
for i in 0..u8::MAX as u16 {
    assert!(art.insert(i, i), "{}", i);
    assert!(matches!(art.get(&i), Some(val) if val == &i));
}
for i in 0..u8::MAX as u16 {
    assert!(matches!(art.remove(&i), Some(val) if val == i));
}

let mut art = Art::<ByteString, u16>::new();
for i in 0..u8::MAX as u16 {
    let key = KeyBuilder::new().append(i).append(ByteString::new("abc".to_string().as_bytes())).build();
    art.upsert(key.clone(), i + 1);
    assert!(matches!(art.get(&key), Some(val) if val == &(i + 1)));
}

let from_key = KeyBuilder::new().append(16u16).append(ByteString::new("abc".to_string().as_bytes())).build();
let until_key = KeyBuilder::new().append(20u16).append(ByteString::new("abc".to_string().as_bytes())).build();
assert_eq!(art.range(from_key..=until_key).count(), 5);
assert_eq!(art.iter().count(), u8::MAX as usize);

Structs

Art

Adaptive Radix Tree.

ByteString

Implementation of Key which wraps bytes slice. It can be used to represent strings as comparable byte sequence.

Float32

Float64

KeyBuilder

Builder to create keys based on several other keys. For instance, we have a structure:

Traits

Key

Trait represent [Art] key. Trait define method which convert key into byte comparable sequence. This sequence will be used to order keys inside tree.