Indexing Valid Time Databases Via B -trees – The MAP21 Approach
Mário A. Nascimento, Margaret H. Dunham, Michael H. Böhlen, Renato Busatto, Heidi Gregersen, Dieter Pfoser, Kristian Torp, Keun Ho Ryu · 2003
We present an approach named MAP21 which uses standard B -trees, in a multiple disks single processor architecture, to provide efficient indexing of valid time ranges. The approach is based on mapping one dimensional ranges to one dimensional points where the lexicographical order among the ranges is preserved. We compare MAP21 to the Time Index and the R -tree and we show that MAP21 is comparable to or outperforms those, depending on the number of trees utilized, the degree of parallelization among these and the type of query. The main contribution of this paper is to show that standard B -trees, available in virtually any DBMS, can be used to provide an efficient temporal index. Although our discussion is made in terms of valid time databases, MAP21 can be used (or extended to be used) within other application domains as well.