LRU Page Cache for B-Tree Nodes

Buffer Hot Tree Pages in RAM

Every 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.

LRU Cache Operations

On read, return cached page or load from disk, insert at MRU side. On eviction, drop LRU entry when capacity exceeded.

c
Loading…

Pin pages during split/merge so they are not evicted mid-operation
Clock sweep approximates LRU cheaply in kernels
Measure cache hit ratio on repeated searches
Dirty pages must be written back before eviction

Working Through the Exercise

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.

Trace first: walk one failing input step by step
Read the manual: skim the official doc for the mechanism named in this task
Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

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.

Write a C program that implements an LRU page cache for B-tree nodes.

Requirements:

Define a CacheEntry struct: page_id, is_dirty, last_access_time, data (a simple int representing the page)
Define a PageCache struct: entries array, capacity, count, current_time
Implement cache_get(cache, page_id): return the page data or -1 if miss. On hit, update last_access_time.
Implement cache_put(cache, page_id, data, is_dirty): add to cache, evict LRU if full
Implement cache_evict_lru(cache): remove the entry with smallest last_access_time
Simulate a workload:
1. Access pages: 1, 2, 3, 4, 5 (all miss, cache capacity=3, so pages 1,2,3 loaded, then 4 evicts 1, 5 evicts 2)
2. Access page 3 (hit)
3. Access page 1 (miss, evicts LRU)
4. Write page 6 (dirty)
After each access, print cache state: page IDs in cache, hits/misses so far
Print final dirty pages that need flush
Calculate and print the hit rate
Include a note about why write-back caching is used with WAL for durability

Buffer Hot Tree Pages in RAM

LRU Cache Operations

On read, return cached page or load from disk, insert at MRU side. On eviction, drop LRU entry when capacity exceeded.

c
Loading…

Pin pages during split/merge so they are not evicted mid-operation
Clock sweep approximates LRU cheaply in kernels
Measure cache hit ratio on repeated searches
Dirty pages must be written back before eviction

Working Through the Exercise

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.

Trace first: walk one failing input step by step
Read the manual: skim the official doc for the mechanism named in this task
Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

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.

Write a C program that implements an LRU page cache for B-tree nodes.

Requirements:

Define a CacheEntry struct: page_id, is_dirty, last_access_time, data (a simple int representing the page)
Define a PageCache struct: entries array, capacity, count, current_time
Implement cache_get(cache, page_id): return the page data or -1 if miss. On hit, update last_access_time.
Implement cache_put(cache, page_id, data, is_dirty): add to cache, evict LRU if full
Implement cache_evict_lru(cache): remove the entry with smallest last_access_time
Simulate a workload:
1. Access pages: 1, 2, 3, 4, 5 (all miss, cache capacity=3, so pages 1,2,3 loaded, then 4 evicts 1, 5 evicts 2)
2. Access page 3 (hit)
3. Access page 1 (miss, evicts LRU)
4. Write page 6 (dirty)
After each access, print cache state: page IDs in cache, hits/misses so far
Print final dirty pages that need flush
Calculate and print the hit rate
Include a note about why write-back caching is used with WAL for durability

Topic Overview

Buffer Hot Tree Pages in RAM

LRU Cache Operations

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source

LRU Page Cache for B-Tree Nodes

Topic Overview

Buffer Hot Tree Pages in RAM

LRU Cache Operations

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source