sis 14(3): e6

Research Article

Concurrent Operations of O2-Tree on Shared Memory Multicore Architectures

Download843 downloads
  • @ARTICLE{10.4108/sis.1.3.e6,
        author={Daniel Ohene-Kwofie and E. J. Otoo and Gideon Nimako},
        title={Concurrent Operations of O2-Tree on Shared Memory Multicore Architectures},
        journal={EAI Endorsed Transactions on Scalable Information Systems},
        volume={1},
        number={3},
        publisher={ICST},
        journal_a={SIS},
        year={2014},
        month={5},
        keywords={Pessimistic Concurrency, Indexing, In-Memory Databases,Performance, Algorithms},
        doi={10.4108/sis.1.3.e6}
    }
    
  • Daniel Ohene-Kwofie
    E. J. Otoo
    Gideon Nimako
    Year: 2014
    Concurrent Operations of O2-Tree on Shared Memory Multicore Architectures
    SIS
    ICST
    DOI: 10.4108/sis.1.3.e6
Daniel Ohene-Kwofie1,*, E. J. Otoo1, Gideon Nimako2
  • 1: School Of Electrical and Information Engineering, University Of the Witwatersrand, South Africa
  • 2: School of Public Health, University Of the Witwatersrand, South Africa
*Contact email: danielkwofie@gmail.com

Abstract

Modern computer architectures provide high performance computing capability by having multiple CPU cores. Such systems are also typically associated with very large main-memory capacities, thereby allowing them to be used for fast processing of in-memory database applications. However, most of the concurrency control mechanism associated with the index structures of these memory resident databases do not scale well, under high transaction rates. This paper presents the O2-Tree, a fast main memory resident index, which is also highly scalable and tolerant of high transaction rates in a concurrent environment using the relaxed balancing tree algorithm. The O2-Tree is a modified Red-Black tree in which the leaf nodes are formed into blocks that hold key-value pairs, while each internal node stores a single key that results from splitting leaf nodes. Multi-threaded concurrent manipulation of the O2-Tree outperforms popular NoSQL based key-value stores considered in this paper.