6

I have searched for key value stores that support integer keys and integer values. LevelDB seems a good option, though I can't find any information on whether integer values/keys are supported

amirouche
  • 7,682
  • 6
  • 40
  • 94
Rosh Cherian
  • 61
  • 1
  • 2

4 Answers4

11

You can store pretty much anything in LevelDB. You provide opaque slices of data into LevelDB via the Slice structure. Here is an example:

int intKey = 256;
int intValue = 256*256;

Slice key((char*)&intKey, sizeof(int));
Slice value((char*)&intValue, sizeof(int));

db->Put(leveldb::WriteOptions(), key, value);

And that's pretty much it!

However, one thing to note is that while it's generally fine to store integers in LevelDB (as both keys and values), they will be order via the BytewiseComparator so your key has to support bytewise comparison. This also means that if you rely on specific ordering of the keys, then you have to be mindful of the endian-ness on the system.

You can also write your own comparator via the Comparator interface which will allow you to replace the default BytewiseComparator.

Kiril
  • 39,672
  • 31
  • 167
  • 226
  • But the Get doesnt give me slice right? If the data is not '0' padded how will it work? Or am i missing something here? – vinothkr Oct 16 '13 at 09:48
  • Get returns a std::string which can contain an arbitrary byte array. You can also use an Iterator and seek with it, to be able to get a Slice pointing to the value without any copying required. This is the recommended approach for very large values. – Andy Dent Dec 11 '13 at 12:26
1

In many cases a more elaborate encoding scheme for integer keys is a better choice. Packing an int into its two-complement representation in a char* (as suggested in another answer to this question) is one option; varint encoding is another one (saves space for small integers, can store arbitrary numbers without an upper bound).

wouter bolsterlee
  • 3,879
  • 22
  • 30
  • Isn't varint an optimisation of the two-complement method ? – amirouche Aug 21 '15 at 21:18
  • 1
    no. varints (which has multiple variants) use a variable size, while two-complement numbers use a fixed size. this means varints are theoretically unbounded (but not in practical implementations), while two-complement numbers have a range of -2^n to 2^n-1. also, varints need zigzag encoding for negative numbers, while 2 complement reserves a sign bit for that. – wouter bolsterlee Aug 25 '15 at 11:05
0

To enlarge on Link's answer, partly because I've just been playing with this exact thing as part of the book I'm writing, you can see the BytewiseComparator results he/she talks about below.

Another approach is to flip your binary integers to big endian format so they will sort OK with the default comparator. This makes it easier to compose keys. long flippedI = htonl(i);

Note that LevelDB is very fast. I've done tests on an iPhone4 with 50,000 text-keyed records with secondary keys, so about 100,000 key/value pairs and it screams along.

It is very easy to write a custom Comparator which is used by your database forevermore and still uses ByteWiseComparator for keys other than your numbers. The biggest issue is deciding which keys are covered by your custom rules or not.

A trivial way would be to say that all non-integer keys are more than 4 characters long so you assume a 4 byte key is an integer. That means you just need to ensure you add trailing spaces or something else to push that. It's all very arbitrary and up to you but remember the only two pieces of information you have are the key content and its length. There's no other metadata for a given key.

Part of the results from a sample for standard comparator with int keys starting at 1 and going up by 1 to 1000, using a database with standard BytewiseComparator

Listing the keys in decimal and hex
 256 ( 100)
 512 ( 200)
 768 ( 300)
   1 (   1)
 257 ( 101)
 513 ( 201)
 769 ( 301)
   2 (   2)
 258 ( 102)
 514 ( 202)
 770 ( 302)
   3 (   3)
 259 ( 103)
 515 ( 203)
 771 ( 303)
...
 254 (  fe)
 510 ( 1fe)
 766 ( 2fe)
 255 (  ff)
 511 ( 1ff)
 767 ( 2ff)
Andy Dent
  • 17,578
  • 6
  • 88
  • 115
  • You mean flip into big-endian order, not little-endian. You used "htonl" in your example which means "host to network" and network byte order is big-endian. LevelDB may be fast compared to other older databases, but it's quite slow compared to LMDB. – hyc Dec 09 '13 at 20:26
-1

LMDB has explicit support for integer keys (and values, if you're using sorted duplicates). http://symas.com/mdb

When a DB is configured for integer keys, the key comparison functions are also much faster since they can compare word-at-a-time instead of just byte-at-a-time as the default string-oriented compare does.

Disclaimer: I am the author of LMDB. Of course, that doesn't make the facts any different.

hyc
  • 1,387
  • 8
  • 22
  • 3
    The question was about LevelDB. Please stop spamming other questions trying to promote LMDB. – Andy Dent Dec 10 '13 at 16:10
  • 2
    The question says "I have searched" which means he's still looking for options. And LevelDB is a provably inferior option, and LMDB is a provably superior option. – hyc Dec 11 '13 at 23:02
  • @hyc that rather depends on your requirements. I've just reviewed LMDB and found it utterly unsuitable, yet LevelDB appears to do just what I need. – Alnitak Jan 27 '15 at 12:12
  • 1
    Sure, "depends on your requirements" is a fair statement. Most people who use a database have "must reliably retrieve data that was previously stored" as a requirement. They also require "must store data with predictable latency." LevelDB fails on both counts. https://www.usenix.org/conference/osdi14/technical-sessions/presentation/pillai http://riak-users.197444.n3.nabble.com/Riak-stalls-leveldb-backend-td4032349.html So unless you're writing another lossy data store like MongoDB where you don't actually care about retrieving your data, LevelDB is generally unsuitable as a key value store. – hyc Jan 29 '15 at 15:08
  • 1
    It would be courteous to disclose your role in LMDB's development, speaking as someone searching my options. – Michael Theriot Aug 23 '16 at 02:59
  • Disclaimer added. I added it on various posts but did not use it consistently on all posts. Nevertheless, the facts are the facts: https://twitter.com/brokencodebot/status/723504249037008896 – hyc Aug 25 '16 at 00:51