/cola

Cache Oblivious Lookahead Arrays

Primary LanguageCGNU General Public License v3.0GPL-3.0

cola - Cache Oblivious Lookahead Array

Copyright (c) 2013 Gianni Tedesco

INTRODUCTION

This implements the COLA structure described in the paper "Cache Oblivious Streaming B-Trees" by Bender, Farach-Colton, et al.

We use mmap where possible and do k-way merges using a binary min-heap instead of binary merges.

NOT IMPLEMENTED

  1. Values are not stored yet.
  2. No fractional cascading or any other optimisation of queries.
  3. Deamortisation (via background write thread) is also not implemented.

BUILDING

$ make

RUNNING

$ ./cola help

If you like and use this software then press to donate towards its development progress and email me to say what features you would like added.