# cmu-db/bustub architecture

> Architecture diagram of the GitHub repository cmu-db/bustub, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2026-10-05). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/cmu-db/bustub
- Repository: https://github.com/cmu-db/bustub

## Overview

BusTub is an educational relational database with basic SQL and an interactive shell. The principal workflow accepts SQL, binds it, plans and optimizes it, then executes it against catalog-managed tables and indexes; transaction and storage components support that work. The tree and excerpts establish the major subsystems, but many planner/executor connections were not sampled, so those links are shown as unverified rather than asserted. The README also identifies the shell as a product capability; build, grading, and development tooling are omitted.

Main entry points: [`src/concurrency/transaction_manager.cpp`](https://github.com/cmu-db/bustub/blob/master/src/concurrency/transaction_manager.cpp) (Transaction manager), [`src/include/catalog/catalog.h`](https://github.com/cmu-db/bustub/blob/master/src/include/catalog/catalog.h) (Catalog and indexes), [`src/storage/table/table_heap.cpp`](https://github.com/cmu-db/bustub/blob/master/src/storage/table/table_heap.cpp) (Tables and tuples), [`tools/shell/shell.cpp`](https://github.com/cmu-db/bustub/blob/master/tools/shell/shell.cpp) (Interactive shell)

## Diagram (Mermaid)

```mermaid
flowchart TD

subgraph group_sql["SQL processing"]
  node_shell["Interactive shell<br/>[shell.cpp]"]
  node_instance["Database instance"]
  node_binder["SQL binder<br/>[bind_select.cpp]"]
  node_planner["Query planner<br/>[planner.cpp]"]
  node_optimizer["Plan optimizer<br/>[optimizer.cpp]"]
end

subgraph group_runtime["Query runtime"]
  node_engine["Execution engine<br/>[execution_engine.h]"]
  node_executors["Query operators"]
end

subgraph group_data["Data and storage"]
  node_catalog[("Catalog and indexes<br/>[catalog.h]")]
  node_tables[("Tables and tuples<br/>[table_heap.cpp]")]
  node_buffer["Buffer pool"]
  node_disk[("Disk manager<br/>[disk_manager.cpp]")]
end

subgraph group_tx["Transactions and recovery"]
  node_transactions["Transaction manager"]
  node_locks["Lock manager<br/>[lock_manager.cpp]"]
  node_logging["Log manager<br/>[log_manager.cpp]"]
end

subgraph group_types["Data types"]
  node_values["Types and values<br/>[value.cpp]"]
end

node_user(("SQL user"))

node_user -->|"enters SQL"| node_shell
node_shell -.->|"submits queries"| node_instance
node_instance -->|"binds SQL"| node_binder
node_binder -.->|"produces bound statements"| node_planner
node_planner -.->|"builds plans"| node_optimizer
node_optimizer -.->|"supplies optimized plan"| node_engine
node_engine -->|"creates operators"| node_executors
node_executors -.->|"accesses metadata"| node_catalog
node_catalog -->|"owns table heaps"| node_tables
node_catalog -->|"uses buffer pool"| node_buffer
node_buffer -.->|"loads and flushes pages"| node_disk
node_transactions -->|"uses catalog"| node_catalog
node_transactions -->|"tracks tuple versions"| node_tables
node_transactions -.->|"coordinates locking"| node_locks
node_transactions -->|"uses log manager"| node_logging
node_tables -.->|"stores typed tuples"| node_values

click node_shell "https://github.com/cmu-db/bustub/blob/master/tools/shell/shell.cpp"
click node_instance "https://github.com/cmu-db/bustub/blob/master/src/common/bustub_instance.cpp"
click node_binder "https://github.com/cmu-db/bustub/blob/master/src/binder/bind_select.cpp"
click node_planner "https://github.com/cmu-db/bustub/blob/master/src/planner/planner.cpp"
click node_optimizer "https://github.com/cmu-db/bustub/blob/master/src/optimizer/optimizer.cpp"
click node_engine "https://github.com/cmu-db/bustub/blob/master/src/include/execution/execution_engine.h"
click node_executors "https://github.com/cmu-db/bustub/tree/master/src/execution"
click node_catalog "https://github.com/cmu-db/bustub/blob/master/src/include/catalog/catalog.h"
click node_tables "https://github.com/cmu-db/bustub/blob/master/src/storage/table/table_heap.cpp"
click node_buffer "https://github.com/cmu-db/bustub/blob/master/src/buffer/buffer_pool_manager.cpp"
click node_disk "https://github.com/cmu-db/bustub/blob/master/src/storage/disk/disk_manager.cpp"
click node_transactions "https://github.com/cmu-db/bustub/blob/master/src/concurrency/transaction_manager.cpp"
click node_locks "https://github.com/cmu-db/bustub/blob/master/src/concurrency/lock_manager.cpp"
click node_logging "https://github.com/cmu-db/bustub/blob/master/src/recovery/log_manager.cpp"
click node_values "https://github.com/cmu-db/bustub/blob/master/src/type/value.cpp"

classDef toneNeutral fill:#f8fafc,stroke:#334155,stroke-width:1.5px,color:#0f172a
classDef toneBlue fill:#dbeafe,stroke:#2563eb,stroke-width:1.5px,color:#172554
classDef toneAmber fill:#fef3c7,stroke:#d97706,stroke-width:1.5px,color:#78350f
classDef toneMint fill:#dcfce7,stroke:#16a34a,stroke-width:1.5px,color:#14532d
classDef toneRose fill:#ffe4e6,stroke:#e11d48,stroke-width:1.5px,color:#881337
classDef toneIndigo fill:#e0e7ff,stroke:#4f46e5,stroke-width:1.5px,color:#312e81
classDef toneTeal fill:#ccfbf1,stroke:#0f766e,stroke-width:1.5px,color:#134e4a
class node_shell,node_instance,node_binder,node_planner,node_optimizer,node_user toneBlue
class node_engine,node_executors toneAmber
class node_catalog,node_tables,node_buffer,node_disk toneMint
class node_transactions,node_locks,node_logging toneRose
class node_values toneIndigo
```

## Components

### SQL processing

- [Interactive shell](https://github.com/cmu-db/bustub/blob/master/tools/shell/shell.cpp): `tools/shell/shell.cpp`
- [Database instance](https://github.com/cmu-db/bustub/blob/master/src/common/bustub_instance.cpp): `src/common/bustub_instance.cpp`
- [SQL binder](https://github.com/cmu-db/bustub/blob/master/src/binder/bind_select.cpp): `src/binder/bind_select.cpp`
- [Query planner](https://github.com/cmu-db/bustub/blob/master/src/planner/planner.cpp): `src/planner/planner.cpp`
- [Plan optimizer](https://github.com/cmu-db/bustub/blob/master/src/optimizer/optimizer.cpp): `src/optimizer/optimizer.cpp`

### Query runtime

- [Execution engine](https://github.com/cmu-db/bustub/blob/master/src/include/execution/execution_engine.h): `src/include/execution/execution_engine.h`
- [Query operators](https://github.com/cmu-db/bustub/tree/master/src/execution): `src/execution`

### Data and storage

- [Catalog and indexes](https://github.com/cmu-db/bustub/blob/master/src/include/catalog/catalog.h): `src/include/catalog/catalog.h`
- [Tables and tuples](https://github.com/cmu-db/bustub/blob/master/src/storage/table/table_heap.cpp): `src/storage/table/table_heap.cpp`
- [Buffer pool](https://github.com/cmu-db/bustub/blob/master/src/buffer/buffer_pool_manager.cpp): `src/buffer/buffer_pool_manager.cpp`
- [Disk manager](https://github.com/cmu-db/bustub/blob/master/src/storage/disk/disk_manager.cpp): `src/storage/disk/disk_manager.cpp`

### Transactions and recovery

- [Transaction manager](https://github.com/cmu-db/bustub/blob/master/src/concurrency/transaction_manager.cpp): `src/concurrency/transaction_manager.cpp`
- [Lock manager](https://github.com/cmu-db/bustub/blob/master/src/concurrency/lock_manager.cpp): `src/concurrency/lock_manager.cpp`
- [Log manager](https://github.com/cmu-db/bustub/blob/master/src/recovery/log_manager.cpp): `src/recovery/log_manager.cpp`

### Data types

- [Types and values](https://github.com/cmu-db/bustub/blob/master/src/type/value.cpp): `src/type/value.cpp`

### Other components

- **SQL user**

## Connections

- SQL user → Interactive shell: enters SQL
- Interactive shell → Database instance: submits queries
- Database instance → SQL binder: binds SQL (evidence: `src/common/bustub_instance.cpp`)
- SQL binder → Query planner: produces bound statements
- Query planner → Plan optimizer: builds plans
- Plan optimizer → Execution engine: supplies optimized plan
- Execution engine → Query operators: creates operators (evidence: `src/include/execution/execution_engine.h`)
- Query operators → Catalog and indexes: accesses metadata
- Catalog and indexes → Tables and tuples: owns table heaps (evidence: `src/include/catalog/catalog.h`)
- Catalog and indexes → Buffer pool: uses buffer pool (evidence: `src/include/catalog/catalog.h`)
- Buffer pool → Disk manager: loads and flushes pages
- Transaction manager → Catalog and indexes: uses catalog (evidence: `src/concurrency/transaction_manager.cpp`)
- Transaction manager → Tables and tuples: tracks tuple versions (evidence: `src/concurrency/transaction_manager.cpp`)
- Transaction manager → Lock manager: coordinates locking
- Transaction manager → Log manager: uses log manager
- Tables and tuples → Types and values: stores typed tuples
