Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Cache Oblivious Lookahead Arrays
C Objective-C
branch: master
Failed to load latest commit information.
include Implement PIO paths for k-way merge
.gitignore Track .gitignore
COPYING
Makefile k-way merge in to buffers
README.md
cola.c
coladb.c Implement PIO paths for k-way merge
minheap.c Include minheap implementation
os.c Initialize eof in fd_read()

README.md

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.

Something went wrong with that request. Please try again.