Rui Zhang
Abstract
The huge amount of temporal data generated from many important applications call for a highly efficient and scalable version index. The TSB-tree has the potential of large scalability due to its unique feature of progressive migration of data to larger mediums. However, its traditional design optimized for two levels of the memory hierarchy (the main memory and the hard disk) undermines its potential for high efficiency in face of today's advances in hardware, especially CPU/cache speed and memory size. We propose a novel version index structure called the HV-tree. Different from all previous version index structures, the HV-tree has nodes of different sizes, each optimized for a level of the memory hierarchy. As data migrates to different levels of the memory hierarchy, the HV-tree will adjust the node size automatically to exploit the best performance of all levels of the memory hierarchy. Moreover, the HV-tree has a unique chain mechanism to maximally keep recent data in higher levels of the memory hierarchy. As a result, HV-tree is several times faster than the TSB-tree for point queries (query with single key and single time value), and up to 1000 times faster than the TSB-tree for key-range and time-range queries.
- http://www.sdss.org/.Google Scholar
- C.-H. Ang and K.-P. Tan. The interval b-tree. Inf. Process. Lett., 53(2):85--89, 1995. Google ScholarDigital Library
- R. Balasubramonian, D. Albonesi, A. Buyuktosunoglu, and S. Dwarkadas. Memory hierarchy reconfiguration for energy and performance in general-purpose processor architectures. In MICRO, pages 245--257, 2000. Google ScholarDigital Library
- B. Becker, S. Gschwind, T. Ohler, B. Seeger, and P. Widmayer. An asymptotically optimal multiversion b-tree. VLDB Journal, 5(4):264--275, 1996. Google ScholarDigital Library
- P. A. Bernstein, M. L. Brodie, S. Ceri, D. J. DeWitt, M. J. Franklin, H. Garcia-Molina, J. Gray, G. Held, J. M. Hellerstein, H. V. Jagadish, M. Lesk, D. Maier, J. F. Naughton, H. Pirahesh, M. Stonebraker, and J. D. Ullman. The asilomar report on database research. SIGMOD Record, 27(4):74--80, 1998. Google ScholarDigital Library
- M. C. Easton. Key-sequence data sets on inedible storage. IBM Journal of Research and Development, 30(3):230--241, 1986. Google ScholarDigital Library
- R. Elmasri, G. T. J. Wuu, and V. Kouramajian. The time index and the monotonic b+-tree. In Temporal Databases, pages 433--456. 1993.Google Scholar
- A. Guttman. R-trees: a dynamic index structure for spatial searching. In SIGMOD, pages 47--57, 1984. Google ScholarDigital Library
- R. A. Hankins and J. M. Patel. Effect of node size on the performance of cache-conscious b+-trees. In SIGMETRICS, pages 283--294. ACM, 2003. Google ScholarDigital Library
- P.-Å. Larson. Performance analysis of linear hashing with partial expansions. TODS, 7(4):566--587, 1982. Google ScholarDigital Library
- D. B. Lomet. Partial expansions for file organizations with an index. TODS, 12(1):65--84, 1987. Google ScholarDigital Library
- D. B. Lomet, M. Hong, R. V. Nehme, and R. Zhang. Transaction time indexing with version compression. PVLDB, 1(1), 2008. Google ScholarDigital Library
- D. B. Lomet and B. Salzberg. Access methods for multiversion data. In SIGMOD Conference, pages 315--324, 1989. Google ScholarDigital Library
- D. B. Lomet and B. Salzberg. The performance of a multiversion access method. In SIGMOD Conference, pages 353--363, 1990. Google ScholarDigital Library
- J. Rao and K. A. Ross. Cache conscious indexing for decision-support in main memory. In VLDB, 1999. Google ScholarDigital Library
- J. Rao and K. A. Ross. Making b+ -trees cache conscious in main memory. In SIGMOD Conference, 2000. Google ScholarDigital Library
- A. Shatdal, C. Kant, and J. F. Naughton. Cache conscious algorithms for relational query processing. In VLDB, 1994. Google ScholarDigital Library
- Y. Tao and D. Papadias. Mv3r-tree: A spatio-temporal access method for timestamp and interval queries. In VLDB, pages 431--440, 2001. Google ScholarDigital Library
- P. Westerman. Data warehousing: using the Wal-Mart model. Morgan Kaufmann, 2001. Google ScholarDigital Library
- M. E. Wolf and M. S. Lam. A data locality optimizing algorithm. SIGPLAN Not., 26(6):30--44, 1991. Google ScholarDigital Library
Index Terms
- The HV-tree: a memory hierarchy aware version index
Recommendations
NV-Tree: reducing consistency cost for NVM-based single level systems
FAST'15: Proceedings of the 13th USENIX Conference on File and Storage TechnologiesThe non-volatile memory (NVM) has DRAM-like performance and disk-like persistency which make it possible to replace both disk and DRAM to build single level systems. To keep data consistency in such systems is non-trivial because memory writes may be ...
B3-Tree: Byte-Addressable Binary B-Tree for Persistent Memory
In this work, we propose B3-tree, a hybrid index for persistent memory that leverages the byte-addressability of the in-memory index and the page locality of B-trees. As in the byte-addressable in-memory index, B3-tree is updated by 8-byte store ...
LSB-Tree: a log-structured B-Tree index structure for NAND flash SSDs
NAND flash memory has been widely used as a storage device for embedded systems because of its fast access speed, low power consumption, and lower noise compared to a hard disk. However, due to its unique characteristics such as the lack of an in-place ...
Comments