# Basic Compaction
Data written to the database is initially written to an in-memory store
called the memtable. The memtable is flushed to disk when the amount of data
crosses a threshold. The data flushed to disk is written as an SSTable.
As more data is written, he number of tables on disk will keep increasing.
Since the search performance depends on the number of SSTables to be searched,
we need to limit the number of SSTables.
We do this by running the compaction service as the number of SSTables grow.
When the number of SSTables grows equals a configurable limit, we merge
them into a single table. On every SSTable flush, we check to see if the
number of tables equals the limit, if so block till the tables are merged
into a single table.
In workloads where data is frequently updated, the merged SSTable size may be
far lower than the number of SStables * size of SStable. For now, we will
move forward without taking this case into consideration.
## Handling updates to the live index
`get` operation involve identifying the correct SSTable to query and then
searching for the existence of a value in it.
To speed up `get` operation, an in-memory sparse index of key to the SSTable, and
the offset within it is maintained in memory.
```rustc
struct TableAddress {
// the idx of the SSTable housing the data
table: usize,
// the offset within the SSTable at which the key can be found
offset: usize
}
let key: L = /** A key in the table **/
let index = HashMap<K, TableAddress>::new();
// ...
// ...
// populate index
// ..
// ...
let address = index.get(key);
```
The `TableAddress` corresponding to a key is used to seek to the correct
offset within an SSTable and begin searching for a key. Having this offset
avoids us having to search all SSTables / the entire SSTable.
To full-fill, a get request the index is queried to find the key or the
largest value less than the queried key. The `TableAddress` corresponding to
that key is used to read the SSTable.
The Sparse Index needs to kept in sync with the state of SSTables on disk.
As a result, every compaction is returns a new Sparse Index that can replace
the existing index.
## Updates to Sparse Index on Memtable Flush
When the memtable is flushed, it leads to creation of another SSTable on disk.
The data from this table has not yet been incorporated into the Sparse Index
so, searching for a key would require a linear pass over all new SSTables.
To avoid this, when a memtable is flushed to disk, the keys that have been
overwritten are updated in the Sparse Index to point to the new `TableAddress`.
Also, new keys are sampled and corresponding entries are added to the Sparse
Index as well. Eventually, these newly flushed tables are compacted into a
single table, and the sparse index is updated.