I read the paper "The Adaptive Radix Tree" and immediately thought it would be a good fit for our versioned flash-based / in-memory hybrid data store #1
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 :+1:
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 :+1:
Kind regards Johannes