rdaum / rart-rs Goto Github PK

Inner nodes that have shrunk down to only 1 child which is a leaf should be pruned out, their prefix modified, and replaced with a leaf node.

The Self-Tuning Adaptive Radix Tree paper (https://db.in.tum.de/~leis/papers/artsync.pdf) adds some new concepts, which I might attempt to add to the existing implementation.

• A "tuning" pass
• A version of Node4 which is "multilevel"
• "Rewired" nodes via kernel page remapping

I want to look into see how much of this can be pulled into this existing implementation.

C++ implementation here for reference: https://github.com/jungmair/START

Before I publish to crates.io, I need to write all the rustdoc and generally improve the comments thrroughout.

Once that is done, publish a version to crates.io

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)?;

Thanks for this excellent librarry!

I noticed that the iter and range methods don't work currently because only the leaf nodes are being iterated over, and not the inner nodes. Just curious if you plan to resolve this

As per the https://db.in.tum.de/~leis/papers/artsync.pdf paper, implement a form of the tree using optimistic lock coupling.

I started down this path at one point but never finished. I have a draft of a versioned, coupled lock implemented elsewhere, but it's relatively untested and I will need to return to it.

I go back and forth on how much existing code can be shared.

Testing for correctness is perhaps the most challenging part here.

Problems with the current range & iteration implementation:

• Not currently performance tested / benched.
• Not currently in the fuzz tests.
• Copies: In order to return full keys (for the first half of the entry tuple), the entire key needs to be reconstructed from the partial, which means performing (likely slow) copies during iteration.
• Missing separate iteration of values and keys. Having .values iteration would take no copies.
• Source code could be cleaned up.