Title: OB-tree: a new write optimisation index on out-of-core column-store databases

Authors: Feng Yu; Tyler J. Matacic; Brandon J. Latronica; Wen-Chi Hou

Addresses: Department of Computer Science and Information Systems, Youngstown State University, Youngstown, OH, USA ' Department of Computer Science and Information Systems, Youngstown State University, Youngstown, OH, USA ' Department of Computer Science and Information Systems, Youngstown State University, Youngstown, OH, USA ' Department of Computer Science, Southern Illinois University, Carbondale, IL, USA

Abstract: The column-store database is a representative of next generation databases featuring a high reading speed. Write optimisation in the out-of-core column-store database remains a well-known challenge. Timestamped binary association table (or TBAT) and asynchronous out-of-core update (or AOC update) have shown improvements in write performance. However, a common restriction shared by the timestamp-based approaches is that, after a time period of updates, the searching performance will gradually decrease. In this work, we introduce a new index, called Offset B⁺-tree (or OB-tree), to further improve the data retrieval speed after many updates have taken place. OB-tree is a flexible and robust index that employs a special pointer elimination strategy to reduce the storage costs. Succinctly designed, OB-tree can be easily integrated into existing timestamp-based column-store databases. Extensive experiments show that OB-tree can be efficiently constructed and significantly improves the data retrieval speed on the TBAT even when a large number of updates occurred.

Keywords: column-store database; write optimisation; index; B⁺-tree.

DOI: 10.1504/IJIIDS.2018.091604

International Journal of Intelligent Information and Database Systems, 2018 Vol.11 No.1, pp.46 - 66

Received: 31 Mar 2017
Accepted: 24 Aug 2017
Published online: 08 May 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article