O2-tree: a shared memory resident index in multicore architectures
Date
2013-02-06
Authors
Ohene-Kwofie, Daniel
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Shared memory multicore computer architectures are now commonplace in computing.
These can be found in modern desktops and workstation computers and also in High
Performance Computing (HPC) systems. Recent advances in memory architecture and
in 64-bit addressing, allow such systems to have memory sizes of the order of hundreds of
gigabytes and beyond. This now allows for realistic development of main memory resident
database systems. This still requires the use of a memory resident index such as T-Tree,
and the B+-Tree for fast access to the data items.
This thesis proposes a new indexing structure, called the O2-Tree, which is essentially
an augmented Red-Black Tree in which the leaf nodes are index data blocks that store
multiple pairs of key and value referred to as \key-value" pairs. The value is either the
entire record associated with the key or a pointer to the location of the record. The
internal nodes contain copies of the keys that split blocks of the leaf nodes in a manner
similar to the B+-Tree. O2-Tree structure has the advantage that: it can be easily
reconstructed by reading only the lowest value of the key of each leaf node page. The size
is su ciently small and thus can be dumped and restored much faster.
Analysis and comparative experimental study show that the performance of the O2-Tree
is superior to other tree-based index structures with respect to various query operations
for large datasets. We also present results which indicate that the O2-Tree outperforms
popular key-value stores such as BerkelyDB and TreeDB of Kyoto Cabinet for various
workloads. The thesis addresses various concurrent access techniques for the O2-Tree for
shared memory multicore architecture and gives analysis of the O2-Tree with respect to
query operations, storage utilization, failover and recovery.