Key-Value Store Structures
Hash Table
Balanced BST
Skip List
B-Tree
LSM-Tree
Key:
Insert
Search
Reset
Table size: 7, h(k) = k mod 7
Key:
Insert
Search
Reset
Balanced BST (AVL)
Key:
Insert
Search
Reset
Skip list, p = 0.5
Key:
Insert
Search
Reset
B-tree of order 4 (max 3 keys/node)
Write
Flush
Compact
Reset
Memtable: empty | L0: 0 SSTs | L1: 0 SSTs