Comparative analysis of the O2-tree with alternative main-memory DBMS index structures
In today's computing world, in-memory databases are increasingly being used to increase transactional throughput and cache query results in distributed systems. One component of in-memory databases that is crecial in determining their performance is their index structure. In 2013, Ohene-Kwofie, Otoo et al. proposed the O2-Tree, and the associated O2-Tree-KV as a index structure for main memory databases and an associated key-value store, respectively. Initial tests demonstrated that the O2-Tree was a promising structure. Still, results obtained from testing the performance of the O2-Tree-KV with leading NoSQL data stores were not as conclusive, as only a small set of alternative structures were employed during testing. In this study, we demonstrate, by way of experimentation, the viability of the O2-Tree as a comparative database index by testing its performance alongside other leading index structures. We achieve this by demonstrating that the O2-Tree is competitive in two critical domains of database index-structure comparison; the ability to build index structures quickly and thus recover from unexpected and sometimes inevitable crashes; the ability to execute query sets with varying update ratios at relatively fast speeds.
Undergraduate thesis submitted to the Department of Computer Science and Information Systems, Ashesi University, in partial fulfilment of the requirements for the award of Bachelor of Science degree in Computer Science, May 2022