Buffer Pool and LRU Eviction

The problem: disk is slow, RAM is fast

Reading a 4KB page from disk — even an SSD — costs orders of magnitude more time than reading the same bytes from RAM. If every PAGE GET or B-tree traversal step re-read its page from disk, a database would be unusably slow. Every real database engine sits a buffer pool (a.k.a. page cache) between the storage layer and the disk: a fixed-size, in-memory table of recently-used pages, so that "hot" pages — the root of a B-tree, frequently queried rows — get served from RAM almost every time.

This is exactly the same problem your OS solves with its page cache and your CPU solves with L1/L2/L3 cache: a small fast layer in front of a large slow one, and an eviction policy to decide what stays in the small layer when it's full.

The data structure: hash map + ordering for eviction

A buffer pool needs two things simultaneously:

1. O(1) lookup by page ID — "is this page currently cached, and if so, give me its data." A hash map (page_id → data) does this.
2. An eviction order — when the cache is full and a new page must come in, which cached page gets kicked out? That's what LRU (Least Recently Used) answers: evict whichever page was accessed longest ago, on the theory that pages used recently are likely to be used again soon (temporal locality).

The classic combination that gives you both in O(1) is a hash map + doubly linked list:

map:  page_id -> node in linked list
list: most-recently-used <-> ... <-> least-recently-used

• On a cache hit (CACHE READ on a page already present): look it up via the map, then unlink its list node and move it to the front (most-recently-used end).
• On a cache write to a page not present, or a miss that then loads the page: if the cache is at capacity, evict the node at the back of the list (least-recently-used), remove it from the map, then insert the new page at the front.

If you don't need strict O(1) and your n (cache size) is small, an ordered map / array with a "last used" counter or timestamp works too — pick whichever your language makes easiest, but understand why the linked-list version is the standard answer, since it's a very common systems-interview structure.

Commands, mapped to the structure

CACHE SIZE <n>            -> set capacity; if shrinking below current count, evict LRU pages now
CACHE WRITE <page_id> <d> -> insert-or-update page_id -> d, mark most-recently-used, evict if over capacity
CACHE READ <page_id>      -> hit: return data, mark most-recently-used, hits++
                              miss: return MISS, misses++   (this exercise doesn't fetch from a real disk backing store)
CACHE STATS               -> hits:<n>,misses:<n>,evictions:<n>

Track three counters (hits, misses, evictions) as plain integers updated at the point where each event actually happens — don't derive them after the fact, since a WRITE that triggers an eviction and a READ that's a hit both need to update exactly one counter each.

Edge cases

• CACHE SIZE set smaller than the current number of cached pages — you must evict down to the new capacity immediately, incrementing evictions for each page removed, not just cap future inserts.
• Re-writing a page already in the cache — this should update its data and refresh its recency, but must not count as an eviction of itself, and shouldn't change the cache's occupied count.
• CACHE SIZE 0 or a degenerate cache — every write should immediately evict (or simply refuse to cache), and every read should miss.
• Ties in recency — LRU only needs a strict "least recently used" order; as long as your structure consistently picks some correct least-recently-used entry (not an arbitrary one when multiple entries were touched "simultaneously" within a single command), your eviction count and eviction choices will match expected output.

Why this matters for the bigger project

Once you wire the B-tree (search/insert/delete) to route its page reads and writes through this cache instead of talking to storage directly, repeated traversals down the same hot path — like the root and its immediate children, visited on every single search — become nearly free, and only genuinely cold pages pay the simulated "disk" cost. This is the same mechanism that makes real databases fast under repeated, skewed access patterns.