The RABTree and RAB-Tree: Lean Index Structures for Snapshot Access in Transaction-time Databases

In this work we introduce two lean temporal index structures to efficiently support snapshot access (i.e., timeslice queries) in a transaction-time database. The two proposed structures, the RABTree and its RAB-Tree variant, are conceptually simple, easy to implement and efficient index solutions. In particular, the RABTree index guarantees optimal performances for transaction-time data which are naturally clustered according to their insertion time without redundancy. A theoretical and experimental evaluation of the two indexes, in comparison with their previously proposed competitors, is also provided.