The btrtree: Path-defined version-range splitting in a branched and temporal structure

Abstract. There are applications which require the support of temporal data with branched time evolution, called branched-and-temporal data. In a branched-and-temporal database, both historic versions and current versions are allowed to be updated. We present an access method, the BTR-Tree, for branched-and-temporal databases with reasonable space and access time tradeoff. It is an index structure based on the BT-Tree [5]. The BT-Tree always splits at a current version whenever a data page or an index page is full. The BTR-Tree is able to split at a previous version while still keeping the posting property that only one parent page needs to be updated. The splitting policy of the BTR-Tree is designed to reduce data redundancy in the structure introduced by branching. Performance results show that the BTR-Tree has better space efficiency and similar query efficiency than the BT-Tree, with no overhead in search and posting algorithm complexity.