Skip to content

Search and find

Jump to bottom
Niclas Olofsson edited this page May 19, 2019 · 1 revision

A quick breakdown of the flow for searching the database during a get() operation

General flow

This is the general gist of how search happen through all layers (and levels) of the database. There are lots of important details on the way, like sequence numbers, that help keep the integrity of the search intact. But I'll cover that separately when documenting how MiNET.LevelDB does it.

  1. Call database get(key)
  2. Search memtable
  3. Search immutable memtable
  4. Delegate search to manifest (current version)
  5. Identify and delegate search to the tables that potentially hold the key.

Memtable search

First of all, there MAY exist a readonly version of the memtable waiting to be persisted as a level 0+ sorted table. So the algorithm first searches the current memtable and then also does the same search in the immutable memtable, should it exist.

Manifest and Table search

The manifest is searched like

  1. For each level, locate tables using min/max keys for each table. These are stored in the metadata that describe the current version (state) of the database, and each file has these ranges.
  2. When key is within range of a table delegate search to table

Each table search works like this

  1. Search for key in block index. If found, we get back a handle to the actual data block that MAY contain our value.
  2. Filter the key through the bloom filter (if present). Or any other strange filter that may apply. Notice that this is really an optional step since filters are really up to the implementer to define. LevelDB itself only support bloom filters, so that's what most use. Filters answer the question "Does it NOT exist in this set?".
  3. Lastly, the block data that we got from the block index is used to get the block of data that MAY contain our data. Here we do a binary search to find the proper restartpoint to scan.
  4. When we identified potential restartpoint key, we move to the index and brute force (linear) the search through each key until match is found or search key is too big (BUG: Need to check if i actually abort the search).

Clone this wiki locally