Storage Engines & Recovery

class BufferPool:
    def __init__(self, size_mb):
        self.pages = {}  # page_id -> page_data
        self.lru = OrderedDict()  # for eviction
        self.max_pages = size_mb * 1024 // 8  # 8KB pages
    
    def get_page(self, page_id):
        if page_id in self.pages:
            # Cache hit! Move to end (most recently used)
            self.lru.move_to_end(page_id)
            return self.pages[page_id]
        else:
            # Cache miss - read from disk
            page = read_page_from_disk(page_id)
            self.add_to_cache(page_id, page)
            return page

# Finding "John" in a B+ tree index on names
1. Root: "John" < "M", go left
2. Level 2: "John" > "G", go to middle child  
3. Leaf: Scan "G-I" page, find "John" -> row location
4. Fetch actual row from heap file

def insert(tree, key, value):
    leaf = find_leaf(tree.root, key)
    
    if leaf.has_space():
        leaf.insert(key, value)
    else:
        # Split leaf into two
        new_leaf = leaf.split()
        middle_key = new_leaf.keys[0]
        
        # Propagate split up the tree
        insert_into_parent(leaf.parent, middle_key, new_leaf)

class LSMTree:
    def write(self, key, value):
        # 1. Log for crash recovery
        self.wal.append(f"SET {key} = {value}")
        
        # 2. Add to in-memory table
        self.memtable[key] = value
        
        # 3. Flush when full
        if self.memtable.size() > THRESHOLD:
            self.flush_to_disk()
    
    def flush_to_disk(self):
        # Sort and write to new SSTable file
        sorted_data = sorted(self.memtable.items())
        sstable = create_sstable(sorted_data)
        self.sstables[0].append(sstable)
        self.memtable.clear()

class WriteAheadLog:
    def __init__(self):
        self.log_file = open("database.wal", "ab")  # Append, binary
        self.lsn = 0  # Log Sequence Number
    
    def log_update(self, tx_id, table, row_id, old_value, new_value):
        entry = {
            "lsn": self.lsn,
            "tx_id": tx_id,
            "type": "UPDATE",
            "table": table,
            "row_id": row_id,
            "old_value": old_value,  # For undo
            "new_value": new_value   # For redo
        }
        self.log_file.write(serialize(entry))
        self.log_file.flush()  # Force to disk
        self.lsn += 1
        
        # Only now safe to update actual data
        return self.lsn

def recover():
    # Phase 1: Analysis - What was happening?
    committed_txns = set()
    active_txns = set()
    
    for entry in read_log_from_checkpoint():
        if entry.type == "BEGIN":
            active_txns.add(entry.tx_id)
        elif entry.type == "COMMIT":
            active_txns.remove(entry.tx_id)
            committed_txns.add(entry.tx_id)
    
    # Phase 2: Redo - Replay committed transactions
    for entry in read_log_from_checkpoint():
        if entry.tx_id in committed_txns:
            apply_change(entry)
    
    # Phase 3: Undo - Rollback incomplete transactions
    for entry in reversed(read_log_from_checkpoint()):
        if entry.tx_id in active_txns:
            undo_change(entry)

# Configure connection pooling properly
pool = psycopg2.pool.ThreadedConnectionPool(
    minconn=5,    # Keep some connections ready
    maxconn=20,   # Limit maximum connections
    host="localhost",
    database="mydb"
)

# Use context managers to ensure cleanup
from contextlib import contextmanager

@contextmanager
def get_db_connection():
    conn = pool.getconn()
    try:
        yield conn
        conn.commit()
    except:
        conn.rollback()
        raise
    finally:
        pool.putconn(conn)