index-maxheap.c File Reference

MaxHeap - A binary maximum heap index for flash memory.

More...

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "cfs/cfs.h"
#include "cfs/cfs-coffee.h"
#include "lib/memb.h"
#include "lib/random.h"
#include "db-options.h"
#include "index.h"
#include "result.h"
#include "storage.h"
#include "net/ip/uip-debug.h"

Go to the source code of this file.

Detailed Description

MaxHeap - A binary maximum heap index for flash memory.

The idea behind the MaxHeap index is to write entries sequentially 
into small buckets, which are indexed in a binary maximum heap. 
Although sequential writes make the entries unsorted within a 
bucket, the time to load and scan a single bucket is small. The 
sequential write is important for flash memories, which are 
unable to handle multiple rewrites of the same page without doing 
an expensive erase operation between the rewrites.

Each bucket specifies a range (a,b) of values that it accepts. 
Once a bucket fills up, two buckets are created with the ranges 
(a,mean) and (mean+1, b), respectively. The entries from the 
original bucket are then copied into the appropriate new bucket 
before the old bucket gets deleted.

Author

Nicolas Tsiftes nvt@s.nosp@m.ics..nosp@m.se

Definition in file index-maxheap.c.