DBHash

About

This is a disk-backed key-value store for ruby. It was developed to hold reverse index data for a corpus database project of mine, and is loosely based on levelDB’s system of tree-structured linked lists.

The data structure acts as an ordinary key-value store but is append only: items that collide are added to the end of an ordered list. Retrieving the first entry allows for fast traversal over all entries in the list by iterating a file pointer. Retrieving the last entry results in the same behaviour as any other key-value store.

The structure is implemented as a series of hash tables, written to disk in a tree structure of directories and files. Each bin holds a header to a linked list, which is appended to when data is added to that key. Entries in the linked list are interleaved within each file, making deletion slow and prone to fragmentation: this library is not intended for use with data you will re-write often.

Speed was a priority when writing this, and it is optimised for fast access to small amounts of data that are appended in random order (for example, a postings list used in a database). The library uses xxhash for bin assignment and manages file handles in append-only mode for fast writing.

Dependencies

DBHash is written in Ruby >= 2.0, and requires only xxhash as a dependency. The gem file in the repository (or below) will install this for you.

Download

DBHash is available from my git repositories page, and can be built as a gem from that or downloaded here.

Use

The API is largely similar to ruby’s stdlib Hash implementation, with a few more options to traverse the lists. Use gem serve to view the docs, or read the quick test script to help you on your way.