How is it possible to build database index on top of key/value store?

Question

I was reading about LevelDB and found out that:

Upcoming versions of the Chrome browser include an implementation of the IndexedDB HTML5 API that is built on top of LevelDB

IndexedDB is also a simple key/value store that has the ability to index data.

My question is: how is it possible to build an index on top of a key/value store? I know that an index is at it's lowest level is n-ary tree and I understand the way that data is indexed in a database. But how can a key/value store like LevelDB be used for creating a database index?

Answer 1

The vital feature is not that it supports custom comparators but that it supports ordered iteration through keys and thus searches on partial keys. You can emulate fields in keys just using conventions for separating string values. The many scripting layers that sit on top of leveldb use that approach.

The dictionary view of a Key-Value store is that you can only tell if a key is present or not by exact match. It is not really feasible to use just such a KV store as a basis for a database index.

As soon as you can iterate through keys starting from a partial match, you have enough to provide the searching and sorting operations for an index.

Answer 2

Just a couple of things, LevelDB supports sorting of data using a custom comparer, from the page you linked to:

According to the project site the key features are:

• Keys and values are arbitrary byte arrays.
• Data is stored sorted by key.
• Callers can provide a custom comparison function to override the sort order.
• ....

So LevelDB can contain data this can be sorted/indexed based on 1 sort order.

If you needed several indexable fields, you could just add your own B-Tree that works on-top of LevelDB. I would imagine that this is the type of approach that the Chrome browser takes, but I'm just guessing.

You can always look through the Chrome source.