log-structured-merge-tree/, which trades write amplification for range query supportDate: 2026-05-29
Time: 08:38
Both engines are append-only log-structured stores, but they make fundamentally different choices about what to keep in memory and how data is organized on disk.
The hash index in hash-index-storage/bitcask.py keeps a complete in-memory dictionary mapping every key to its disk location:
# bitcask.py:37 — the entire keydir lives in RAM
self.keydir: dict[str, KeyEntry] = {}
A get() (line 155) is a dictionary lookup followed by a single disk seek — constant time regardless of dataset size. A put() (line 150) appends to the active file and updates the hash map. There's no ordering of keys anywhere — the keys() method (line 167) just dumps the dictionary.
The second Bitcask variant in log-structured-hash-table/bitcask.py is structurally identical but adds CRC32 integrity checks (HEADER_FMT = "!III", line 13) and a CorruptionError (line 19). Both variants share the same fundamental limitation: every key must fit in memory, and there is no way to answer "give me all keys between A and D" without scanning the entire hash map.
The LSM-tree in log-structured-merge-tree/lsm.py uses a SortedDict as its memtable (line 8: from sortedcontainers import SortedDict). When the memtable fills up, it's flushed as a sorted SSTable — an on-disk file where keys are in lexicographic order with a sparse index for binary search.
This sorted structure enables rangescan(), which the test at testlsm.py:150-153 exercises:
results = db.range_scan("a", "e")
assert results == [("a", "1"), ("b", "updated"), ("c", "3"), ("d", "4")]
Range scans merge results from the memtable and all SSTables using a heap-based merge (the heapq import at lsm.py:5). The hash index has no equivalent operation — grep for range|scan|iterator across hash-index-storage/ returned zero matches.
| Dimension | Hash Index (Bitcask) | LSM-Tree |
|-----------|---------------------|----------|
| Read path | Hash lookup → 1 disk seek (O(1)) | Memtable → SSTables newest-first (O(log N) per level) |
| Write path | Append + update hash map | Append to WAL + insert into sorted memtable |
| Range queries | Not supported | Native via sorted merge across memtable + SSTables |
| Memory requirement | All keys must fit in RAM | Only memtable + sparse indexes in RAM |
| Crash recovery | Scan all data files or load hint files (rebuildindex, bitcask.py:107) | Replay WAL (WAL.replay(), lsm.py:31) — only unflushed writes |
| Write amplification | Low — compaction rewrites each live value once | Higher — values may be rewritten across multiple compaction levels |
The Bitcask recovery at bitcask.py:107-114 must scan every data file on startup unless hint files exist. Hint files (writehint_file, line 141) are an optimization written during compaction that store just the key-to-offset mappings, avoiding a full data scan.
The LSM-tree uses a WAL (lsm.py:11-60) that's replayed on startup. Only unflushed memtable entries need recovery — everything already flushed to SSTables is durable by construction. The test at test_lsm.py:96-103 verifies this: it opens a new LSMTree without closing the first, and the WAL replay restores x and y.
The sstable-and-compaction/sstable.py module provides a more production-grade SSTable implementation with magic bytes (MAGIC = b"SSTB", line 10), explicit tombstone markers (line 12), and both writer/reader classes. This is the same sorted-file concept the LSM-tree depends on, but extracted as a reusable component with block-level sparse indexes (block_size=64, line 48) for efficient binary search within files.
The hash index wins when your workload is all point lookups and updates — think session stores, caches, or sensor readings keyed by device ID. The LSM-tree wins when you need range queries or can't guarantee all keys fit in RAM — time-series data, ordered event logs, or anything where you query by key prefix or range.