An adaptive split policy for the Time Split B-Tree

摘要

The Time Split-B Tree is an efficient storage and access structure proposed by Lomet and Salzberg for transaction-time temporal data. This structure forces strong data duplication, due to storage space splits along the time dimension, to improve selectivity for temporal queries. However, redundancy increases storage space requirements and, as a consequence, can be considered as a weakness for a large class of transaction-time database applications. From this viewpoint, almost all the merit figures of the Time Split B-Tree suffer from the high redundancy degree usually reached by the structure during its lifetime. An improvement of the Time Split B-Tree is presented in this work. It is based on a new adaptive split policy which aims to dynamically limit data duplication within given bounds. An evaluation of the Time Split B--Tree with the adaptive split policy has been done via extensive simulations in comparison with the previous Time Split B-Tree performance. The Time Split B--Tree with the new split policy proved to have a better and more uniform behaviour.