sstable: support two level indexes about pebble HOT 1 CLOSED

RocksDB includes metadata_block_size option to control the size of the first level index blocks (default 4KB). Something to pay attention to here is what happens with large keys. Consider a config with a block size of 4KB and metadata block size of 4KB. If a key is 4KB then each block will contain a single key, and each metadata block will contain a single key, and the root index block will end up containing all keys in the table.

Rather than a fixed number of index levels, perhaps we should support an arbitrary number and make the sstable act much more like an immutable btree. The leaf blocks would contain data. The index blocks would contain keys and pointers to either other index blocks or leaf blocks. We'd target the index blocks to the same size as the leaf blocks, but require them to hold at least 2 entries so that some amount of fanout is guaranteed.

Creation of this multi-level index shouldn't be too complicated. We build up the first level index blocks as that data blocks are being written. Then we loop over the first level index blocks and build up the next level. If there is more than one index block at this level we iterate building up more levels until there is a single root index block. We'd need to add a bit of sstable metadata indicating the number of levels.

Cc @ajkr

from pebble.