Intro to Database Systems (CMU 15-445)
My notes working through CMU's Intro to Database Systems lecture series by the CMU Database Group, from the relational model up through distributed databases.
About this series
Notes and takeaways from the CMU's Database Systems course(15-445/645). One post per lecture. Reference to series youtube: here
Why am I learning this? I believe the computer science have a way of repeating itself, and the the way of thinking on how DBMS was designed and some parts of how DBMS interfaces were defined will be applicable to other projects I'll have a chance to work throughout my life. Also! More of low-level OS stuff, which is fun!
#03 - Database Storage: Files, Pages, Tuples
How a DBMS stores data on disk: why it works around the OS, the page abstraction and page sizing and other fun shenanigans
#04 - Memory Management & Buffer Pools
What interface did DBMS people come up with for loading from memory - eg. Buffer pools, page tables, and frames. Another lesson on why a DBMS manages memory instead of using hihg-level OS functions, plus low-level details on memory management - buffer replacement strategies/dirty-page eviction.
#05 - Log-Structured Database Storage
Storage interface stays the same - but there are different ways to implement its core functionality. This lectures touches on Log-structured storage, its drawbacks, benefits - and low-level design decisions and considerations
#06 - Column-Store Databases
Log vs Tuple storage is one way to differente storage; However there exists a 3rd alternatve - a column-oriented storage. This stuff is powerful for big analytics, BigQuery and Parquet use it; These notes focus on its advantages/drawbacks and low-level design of it
#07 - Database Hash Tables
Learnt a lot about low-level design of specific hashing implementations; The other half of the lecture focused on how these hashing ties into DBMS
#08 - B+Trees: The Best Data Structure in the World
B+Trees, the workhorse index of databases: how they stay balanced, why they're built for disk-based storage, and how they power range scans and point lookups.
#09 - Vector Indexes + Inverted Indexes + Skip Lists + Bloom Filters
Beyond B+Trees: vector indexes for similarity search, inverted indexes for full-text, skip lists for probabilistic ordering, and bloom filters for fast set membership.
#10 - Latching in Data Structures
Latches vs locks, and how databases keep shared data structures like B+Trees correct under concurrent access using techniques such as latch crabbing.
#11 - Sorting & Aggregation Algorithms
Sorting data that doesn't fit in memory with external merge sort, plus how databases execute aggregations using sorting and hashing.