StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POUsing key-value databases as a set with persistent indices
text
Body
copied!<p>Since the below got a bit long: Here's the tl;dr; version: Is there an existing key/value best-practice for fast key <em>and</em> value lookup, something like a hash-based set with persistent indices?</p> <p>I'm interested in the world of key-value databases and have so far failed to figure out how one would efficiently implement the following use-case:</p> <p>Assume we want to serialize some data and reference them somewhere else by a persistent, unique integer index. Thus e.g.: Key = unsigned int, Value = MyData.</p> <p>The database should have fast key lookup and ensure that MyData is unique.</p> <p>Now, when I insert a new value into my the database, I could assign it a new index key, e.g. the current size of the database or to prevent clashes after removing items, I could keep some counter externally.</p> <p>But how would I ensure that I do not insert the same MyData value into my database? So far, it looks to me as if this is not efficiently possible with key-value databases - is this correct? I.e. I do <em>not</em> want to iterate over the whole database just to ensure MyData value is not in there already...</p> <p>What is the best pratice to implement this, then?</p> <p>For background: I work on KDevelop where we use the above for our code analysis cache. We actually have a custom implementation of the above use-case <a href="https://projects.kde.org/projects/extragear/kdevelop/kdevplatform/repository/revisions/master/entry/language/duchain/repositories/itemrepository.h">1</a>. Search for Bucket and ItemRepository if you are interested in the internals, and see <a href="https://projects.kde.org/projects/extragear/kdevelop/kdevplatform/repository/revisions/master/entry/language/duchain/indexedstring.cpp">2</a> for an examplatory usage of the ItemRepository.</p> <p>But you will probably agree, that this code is quite hard to understand and thus hard to maintain. I want to compare its performance to alternative solutions which might result in simpler code - but only if it does not incur a severe performance penalty. Considering the hype around the performance of key-value storages such as OpenLDAP MDB, Kyoto Cabinet and LevelDB, this is where I wanted to start.</p> <p>What we have in KDevelop - as far as I figured out - is basically a sort of hybrid on-disk/in-memory hash map which gets saved to disk periodically (which of course can result in major data corruption in case of crashes etc.). Items are stored in a location based on their hash value which then of course also allows relatively fast value lookups as long as the hash function is fast. The added twist is that you also get some sort of persistent database index which can be used to lookup the items quite efficiently.</p> <p>So - long story short - how would one do that with a key/value database such as LevelDB, Kyoto Cabinet, OpenLDAP MDB - you name it?</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload