Package io.permazen.kv.array

package io.permazen.kv.array
A simple KVStore implementation based on a sorted array of key/value pairs.

Instances are optimized for relatively few writes and have minimal memory overhead.

Key and value data must not exceed 2GB (each separately).

File Format

There are three files: index, keys, and values.

The keys file contains all of the database keys, concatenated and in order, encoding using a special compression scheme (see below).

The values file contains all of the database values, concatenated and in order, uncompressed.

The index file contains zero or more index entries, one entry for each key/value pair, concatenated and in order. An index entry is a pair of big endian 32-bit values, where the first value describes the offset of the corresponding key in the keys file using a special encoding (see below), while the second describes the absolute offset of the corresponding value in the values file.

For index entries in a slot equal to zero mod 32, the first 32-bit value is the absolute offset of the key in the keys file; this is called a "base key". For other index entries, the first 8 bits are how many bytes of the previous base key's prefix match this key (from zero to 255), and the remaining 24 bits are the offset in bytes from the beginning of the previous base key in the keys file of the start of this key's suffix. The end of the key in the keys file is implied by where the next key starts (or end of file).

For all index entries, the second 32-bit value is the absolute offset of the value in the values file. The end of the value in the value file is implied by where the next value starts (or end of file).