What is the easiest way to simulate a database table with an index in a key value store?

Question

What is the easiest way to simulate a database table with an index in a key value store? The key value store has NO ranged queries and NO ordered keys.

The things I want to simulate (in order of priority):

1. Create tables
2. Add columns
3. Create indexes
4. Query based on primary key
5. Query based on arbitrary columns

Answer 1

Use a hashtable or dictionary. If you want unique key values you could use a GUID or hashcode.

Answer 2

The key-value store should support ordering the keys and ranged access to the keys.

Then you should create two dictionaries:

id -> payload

and

col1, id -> NULL

, where payload should contain all the data the database table would contain, and the keys of the second dictionary should contain the values of (col1, id) from each entry of the first dictionary.

Answer 3

If you use Redis (an advanced key-value store that supports strings, lists, sets, etc.) Then this is quite easy. I have already developed a C# redis client that has native support for storing POCO's data models. These exact same POCO's can be used by OrmLite to store it in a RDBMS.

By the way Redis is fast, I have a benchmark that stores and retrieves the entire Northwind Database (3202 records) in under 1.2 seconds (running inside a UnitTest on a 3yo iMac).

I store entities in two ways

• Distinct entities, where I combine the Class type name and Primary Key to create a unique key e.g. urn:user:1
  • I then maintain a separate set of primary keys (in a Redis Set) to keep track of all my entities, using a key like: ids:user
• In a Redis server side list - which acts very much like a table with support for paging, using a key like: lists:user