Contiki-NG
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/ipv6/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.