README.md

Amphis

An embedded key-value store

TODO

• API

  • get()
  • put()
    • including insert and update
  • delete()

• Config

  • FPTree config
  • SSTable config

• FPTree

  • Simplified FPTree
  • Leaf file
  • Concurrency
  • Flush (converted to SSTable)
  • Recovery (flush)
  • tail header (for durable write)
  • Extended leaf page

• SSTable

  • SSTable file
  • Bloom filter/Sparse index
  • Compaction
  • Recovery

• Others

  • Error handling
  • Backgound thread

Threshold for flushing

Basically, the number of keys triggers flushing (Converting FPTree to SSTable) because the number of the root split times on the FPTree is the threshold. Where you insert K keys and the N split happens, the relation between $K$ and $N$ would be:

$$K = 8 \times (3^{N+1} + 1)$$

If you set the root_split_threshold to 6, flush would happen every 17,504 insertions.