15

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?

Lu4
  • 14,873
  • 15
  • 79
  • 132

2 Answers2

10

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.

Andy Dent
  • 17,578
  • 6
  • 88
  • 115
5

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.

Matt Warren
  • 10,279
  • 7
  • 48
  • 63
  • 3
    you wouldn't need to use a B-tree on top on leveldb, instead you should create another leveldb to serve as an index for each field. (in effect mimic-ing what a relational database does when you add indexes to a table) but when i looked at leveldb, i didn't see cross db transactions. – Dan D. Jan 28 '12 at 21:45
  • @DanD. I second that! +1 for the comment! I would add one more thing: [yes, there are no transactions, but you do have batch writes](http://stackoverflow.com/questions/9022691/what-constitutes-a-transaction-layer-when-talking-about-database-systems) and you do have a lot of other features which come close to an ACID transaction. – Kiril Feb 01 '12 at 17:47
  • 1
    @Lirik What i meant by "cross db transaction" was _atomic actions involving multiple leveldb instances_ which leveldb doesn't have support. Although leveldb does support atomic actions on a single leveldb instance, you can't build atomic operations on multiple leveldb instances out of that. – Dan D. Feb 01 '12 at 18:16
  • @DanD. ah, yep... that's correct, I didn't see the "cross" in "cross db transactions." – Kiril Feb 01 '12 at 18:18
  • 12
    Why do you need a separate leveldb? Just mix the "index" pairs along with the "record" pairs. – Andy Dent May 25 '12 at 23:34