RocksDB Iterator

Interface: Iterator

DBIter is a wrapper around an InternalIterator (In this case a MergingIterator).DBIter's job is to parse InternalKeys exposed by the underlying InternalIterator and expose them as user keys.

Example:

The underlying InternalIterator exposed

But what DBIter will expose to the user is

The MergingIterator is composed of many child iterators, MergingIterator is basically a heap for Iterators.In MergingIterator we put all child Iterators in a heap and expose them as one sorted stream.

Example:

The underlying child Iterators exposed

The will keep all child Iterators in a heap and expose them as one sorted stream

Implementation:

Interface: InternalIterator

This is a wrapper around MemtableRep::Iterator, Every memtable representation implement it's own Iterator to expose the keys/values in the memtable as a sorted stream

Interface:

This Iterator is used to read blocks from SST file, whether these blocks were index blocks or data blocks.Since SST file blocks are sorted and immutable, we load the block in memory and create a BlockIter for this sorted data.

Implementation: table/two_level_iterator.cc

A TwoLevelIterator is composed of 2 Iterators

• First level Iterator (firstlevel_iter)
• Second level Iterator (secondlevel_iter)firstlevel_iter is used to figure out the secondlevel_iter to use, and secondlevel_iter points to the actual data that we are reading.

Example:

RocksDB uses TwoLevelIterator to read SST files, firstlevel_iter is a BlockIter on the SST file Index block and is a BlockIter on a Data block.

Let's look at this simplified representation of an SST file, we have 4 Data blocks and 1 Index Block

• firstlevel_iter => BlockIter over Index block