search

sirixdb / sirix

SirixDB is an an embeddable, bitemporal, append-only database system and event store, storing immutable lightweight snapshots. It keeps the full history of each resource. Every commit stores a space-efficient snapshot through structural sharing. It is log-structured and never overwrites data. SirixDB uses a novel page-level versioning approach.
https://sirix.io
BSD 3-Clause "New" or "Revised" License
1.13k stars 253 forks source link

Implementation of a form of Adaptive Radix Trie for secondary index structures #306

Open JohannesLichtenberger opened 4 years ago

JohannesLichtenberger commented 4 years ago

We should either enhance our PageReadOnlyTrx and PageTrx interfaces to replace our trie structure for secondary indexes or simply store the ART in leaf pages of a wide branching IndirectPage and fully read it in-memory. The second version is simpler to implement, but users need more main memory.

RedBlack trees are currently stored in leaf nodes and should be read entirely in main memory, just for simplicity and to reuse our trie data structure. RedBlack-trees are however not very cache friendly and shouldn't be used in database systems (might have a major impact with inline types in the future, when Java supports these).

JohannesLichtenberger commented 4 years ago

One important aspect is, that we can cache the pages by their offsets into the file if we enhance the interfaces and implement the ART as an "on-disk" data structure. This means, that the pages can be shared between revisions, also once read into main memory.

JohannesLichtenberger commented 4 years ago

An evolution to reduce the tree height for sparse data sets is the HOT: https://dbis-informatik.uibk.ac.at/sites/default/files/2018-06/hot-height-optimized.pdf it adapts node sizes such that sparsely populated nodes have a heigher span. Reducing storage space of the "compound nodes" can be done as in ART and Hash Array Mapped Tries (like we also do in our simple trie for dense ascending IDs).