rohansuri / adaptive-radix-tree Goto Github PK

For instance according to the papers:

HOT: A Height Optimized Trie Index for Main-Memory Database Systems
START — Self-Tuning Adaptive Radix Tree

Hi,

I want to port your Adaptive Radix Trie to my little database project (https://github.com/sirixdb/sirix) and make it a persistent datastructure + write it to and read it from disk :-)

Currently some tests fail, as attached because of missing default constructors. I have to admit it's not obvious to me how they can be run at all.

Another thing is that the system needs fine granular, fast, random reads to read the variable sized nodes (so, hopefully Optane Memory will be the thing). Furthermore the leaf nodes of the trie can be versioned (storing from the parent node/page a bunch of references to retrieve partial nodes or page-fragments in the SirixDB terminology. I maybe will try to store them within the last InnerNode and version the InnerNodes which then have embedded leaf nodes.This way, only changed records will be stored + some records which are outside of a sliding window (so, if only one value, that is record has been added, it will only store this one and fetch others from previous revisions).

I'm also in contact with Robert Binna for a HOT version, but I think I won't have that much time to start completely from scratch and I'm not really familiar with C++, so reading his Open Source version is not easy for me.

Kind regards and thanks for the great work.

Have a great weekend
Johannes

Hi,

I came up with the idea to further reduce storage space in SirixDB (https://sirix.io, which I'm developing in my spare time) through prefix-compression of basically a dictionary of all names in JSON or XML resources. Currently I'm storing entry-records of a HashMap in SirixDBs trie based structure which versions basically on a record-level.

However, now I stumbled across this paper and immediately thought it would be a way better fit than my rather simple lock and latch-free AVL-tree implementation for secondary in-memory indexes. Basically, I'm however not even sure if the (variable sized nodes) are really that bad for cache-lines, as they basically store the name, two pointers to the on-disk nodes which are read once the tree is re-built in-memory and a bunch of delta-encoded variable sized 64 bit integer/long node-IDs.

But the paper of course suggests, that this adaptive radix-tree is even a better fit than B+-trees (which I thought are rather common also in in-memory database systems).

As I've already read many times, that in general binary-trees don't seem to be a good fit due to the cache-line mismatches and so on for modern hardware anymore I think it would be a good fit to have this index-structure. Also, contributions are of course more than welcome ;-)

So, I guess what I wanted to say is I'd love to port your index-structure and incorporate it 👍

Kind regards
Johannes

Hello @rohansuri, this is more a question than a issue.
I tried using you ART implementation for a personal project, but I soon realized that the only release available is compiled using Java 12 as per this message:
Caused by: java.lang.UnsupportedClassVersionError: com/github/rohansuri/art/BinaryComparable has been compiled by a more recent version of the Java Runtime (class file version 56.0), this version of the Java Runtime only recognizes class file versions up to 52.0

I'm curious, is there a specific reason for this? Like maybe, GC reasons, etc...
Thanks btw, awesome work.

Any plans of improving the Adaptive Radix Trie implementation with SIMD operations? The new incubating Vector API might be useful, also in terms of feedback for the JDK guys :-)

Furthermore a height optimized trie (Paper and Ph.D. thesis of Robert Binna) would probably also be an improvement.

JDK11 is the LTS version. Could you please upload artifact in that version?

Hi,

do you have any idea why range scans for 64Bit Integers are faster in Red/Black trees (TreeMap)?

BTW: Regarding the height they improved their trie with HOT, which especially should address the issue to reduce the height. I think they now use tries within the trie, basically.

Kind regards
Johannes