OB-tree: a new write optimisation index on out-of-core column-store databases. (2018)

• Record Type: Journal Article
• Authors: Yu, Feng; Matacic, Tyler J.; Latronica, Brandon J.; Hou, Wen-Chi
• Is Part Of: International journal of intelligent information and database systems. Volume 11:Number 1(2018)
• Page Start: 46
• Page End: 66
• Publication Date: 2018
• Subjects: column-store database -- write optimisation -- index -- B+-tree; Database management -- Computer programs -- Periodicals; Information retrieval -- Computer programs -- Periodicals; Information storage and retrieval systems -- Computer programs -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Intelligent agents (Computer software) -- Periodicals; 006.33
• Languages: English
• ISSNs: 1751-5858

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.