Loading page…
Master the fundamental concepts of b-trees through this focused micro-challenge.
You have read the whole brief, and the concepts above stay free on every task. Writing and running the code needs a plan.
Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.
Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.
How it worksEvery B-tree lookup touches one page per level. A page cache (buffer pool) keeps recently used pages in memory keyed by page id. PostgreSQL shared buffers and InnoDB buffer pool are industrial-scale versions of the LRU cache you will write.
On read, return cached page or load from disk, insert at MRU side. On eviction, drop LRU entry when capacity exceeded.
cLoading…
Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.
You will implement an LRU page cache over fixed B-tree pages and report hits versus misses on a workload. This exercise asks you to show improved lookup time when the working set fits cache.
A database keeps B-tree pages in a fixed-size buffer pool. Build an LRU page cache with room for 3 pages and write-back of dirty pages.
last_access).put is a write: it marks the page dirty, whether it was a hit or a miss. get leaves the dirty flag as it was.Dirty pages are only written when evicted or flushed at the end. That is write-back caching. It is safe because the WAL already holds every change durably.
get P or put P commands, one per line.
For each access, first, if a page was evicted, evict 1 or evict 6 (dirty: write back first), then
cLoading…
with HIT or MISS and the cached pages from least to most recently used, a dirty page marked * (cache=[3,1,6*]). At the end:
cLoading…
The hit rate has one decimal, and the dirty pages are listed in cache-slot order (or none).