---

🚌 CMU 15-445 (Fall 2022) - Database System Implementation

My implementation of the BusTub relational database management system for CMU 15-445/645 (Intro to Database Systems).

This project demonstrates deep understanding of DBMS internals, including memory management, indexing, and concurrency control.

🛠️ Key Features Implemented

1. Buffer Pool Manager (Memory Management)

• LRU-K Replacement Policy: Implemented a sophisticated page eviction algorithm (LRU-K) that tracks history of page accesses to better estimate page temperature compared to traditional LRU.
• Thread Safety: Secured internal data structures with std::mutex to support concurrent page fetching and eviction.
• Instance Management: Managed the lifecycle of pages, handling dirty flags and disk write-backs.

2. B+ Tree Index (Storage Engine)

• Data Structure: Implemented an on-disk B+ Tree to support efficient range scans and point lookups.
• Concurrency Control (Latch Crabbing):
  • Applied Latch Crabbing protocol to ensure thread safety during tree traversals.
  • Used Read/Write Latches (PageGuard) to maximize concurrency, allowing multiple readers while blocking writers only when necessary.
• Dynamic Resizing: handled Split and Merge/Redistribute operations for internal and leaf nodes to maintain tree balance.

3. Query Execution (Iterator Model)

• Implemented Volcano Model executors (SeqScan, Insert, Delete, IndexScan).
• Supported optimization rules for query planning.

📂 Project Structure

src/
├── buffer/
│   ├── lru_k_replacer.cpp         # LRU-K Eviction Algorithm
│   └── buffer_pool_manager.cpp    # Buffer Pool Management
├── storage/
│   ├── index/
│   │   └── b_plus_tree.cpp        # B+ Tree Implementation (The Core)
│   └── page/
│       └── b_plus_tree_page.cpp   # Node Layout
└── concurrency/
    └── lock_manager.cpp           # 2PL (Two-Phase Locking)