Issue 013: Build It Yourself #1 — Part 2: Adding a hash index
In Part 1 we built a crash-safe key-value store. get(”user:42”) worked correctly and survived process kills. It was also catastrophically slow — O(n) for every lookup. Today we fix that with a 12-line structural change that makes reads O(1). No new disk format. No new files. Just a dict.
Part 1 ended with a working, crash-safe key-value store that stored records in an append-only log and recovered from crashes by scanning for the last valid CRC. The correctness story was solid. The performance story was not. To look up a single key in a 20,000-record log, the store read every record from the beginning to find the latest match. 500 random lookups took 15.5 seconds.
The fix is embarrassingly simple in hindsight, which is exactly why it’s worth implementing yourself before reading about it: keep a dictionary in memory that maps every live key to the byte offset where its value lives in the log. A lookup becomes offset, length = index[key] followed by one file.seek(offset) and one file.read(length). No scan. No iteration. One dict lookup and one seek.
