In LevelDB, are all the keys loaded in memory?

user_8990219 0
Viewed 195

So, I have been reading about the implementation of LevelDB and other key-value stores which use the Log Structured Merge Tree in their implementation. I had a couple of questions on this:

  • Are all the keys loaded in memory in LevelDB even in case of large datasets?
  • If not, how is a key searched for, is it through binary search or any other algorithm?
leveldb implementation key-value-store
2 Answers

So, I did find out that there is a memtable which holds the keys and values in memory and when this memtable becomes more than some specific size - the compaction process occurs. And so the memtable is written to a SST and emptied. So, it appears that all the keys are not stored in memory and LevelDB does use binary search on files using a concept of restart points in the SST file.

user_89902190

  1. No. Only a subset of keys are kept in memory. Recently read and written usually are in memory

  2. First the memtable is chekded - then the key is searched for in each of the sstable files from the highest to the lowest level

user_41543020
Related