Genuine iterators, reverse iterators

[martinsumner]

Many KV stores offer an iterator feature which allows calls to next or prev to move forward and back across the store.

Leveled as a backend had a requirement to support folds over ranges of keys (or keys and metadata). To implement such folds, it can take a snapshot copy of a penciller. The penciller has keys and metadata in memory (level -1) and keys and metadata in sst files (level 0 +), and the snapshot will be a process containing only the in-memory keys/metadata in the required range, and pointers to the SST files at each level that cover the range. When the fold is started, the sst files are asked to expand out the range into lists of actual keys (up to a maximum size), and the penciller then scans up and down the levels trying to determine what the next key is and when the next key is determined the fold function is applied, and continues to be applied to the next key until either the end of the range is reached or an exception is thrown by the fold function to exit out.

There is sort of a next function possible, in that you could have a range with only a start key, and state the maximum number of keys the fold function wishes to apply to 1 - and therefore the function can return just the next key after the start key. However, this is more expensive than finding a single key, and the full cost would need to be faced again to find the next key after that.

So is there a better way of doing next and prev, and also virtually first and last?