Balanced binary search tree: replace the tree with a rather huge array for read-only accesses

[JohannesLichtenberger]

Meaning a more cache-line friendly variant for a static balanced binary search tree (RedBlack tree). Usually you'd use an array representation...

As an alternative to storing this search tree structure for our secondary indexes in our trie (the RedBlack tree nodes are stored in the leaf nodes of our tries) and fully reconstructing it in memory, we could add a persistent adaptive radix trie that replaces the trie and the RedBlack tree. The adaptive radix trie (ART) should be versioned in the same manner as our main document trie.

[sudip-unb]

@JohannesLichtenberger I am interested to work on this task.

[JohannesLichtenberger]

Maybe I had a crazy thought. Would it make sense to store and update a redblack tree in the single read-write trx per resource, but for read-only trx simply use another cache-friendly index structure and to build this structure from the stored redblack tree? Maybe reconstruction would be costly, hmm

[JohannesLichtenberger]

@sudip-unb still interested? Haven't heard from you...