Inside a database engine: storage, indexes and logs
You understand database internals by studying pages, the buffer pool, B+trees, write-ahead logging and MVCC and writing a small key-value store in Python.
Level 501 · 15 lessons · 12 practice labs
Lessons
Storage
- Pages and files on disk
- Row layout and page structure
- The buffer pool and page replacement
- Looking at a real page with pageinspect
- Short task: a heap file with fixed-size pages
Index structures
- B+tree: search, insert and split
- LSM trees and compaction
- Hash indexes
- Short task: a small B+tree in Python
Recovery and concurrency
- The write-ahead logging principle
- Checkpoints and crash recovery
- How MVCC is implemented
- Two-phase locking
- The query executor: the iterator model
- Capstone: a logged, crash-safe key-value store
Practice labs
- Read inside a page with pageinspect: Insert rows into a small table and inspect the page's line pointers and free space with pageinspect.
- Measure how row size affects page count: Store the same data with different column orders and calculate the space taken by alignment padding.
- Write an LRU buffer pool in Python: Write a small LRU buffer pool over a fixed page file that reports its hit ratio.
- Trace a key's path in a B+tree: Write the pages read to find a key in a given B+tree diagram and measure the index depth on a real table.
- Simulate a page split: Insert sequential and random keys into a small-capacity B+tree and compare the number of splits.
- Implement compaction in a mini LSM tree: Write an LSM sketch that flushes a memtable to disk, merges two files and drops deleted keys.
- Match WAL records to a transaction: Find the WAL records produced by an INSERT and an UPDATE and match them to their transaction.
- Measure the effect of checkpoint frequency: Change the checkpoint interval and compare write volume and post-crash recovery time.
- Add recovery to a logged key-value store: Write a small log-first key-value store, kill it midway and replay the log on restart.
- See row versions through hidden columns: Update a row three times and explain with xmin and xmax which version is visible to whom.
- Show two-phase locking on a schedule: Decide which of three transaction schedules follows two-phase locking and try them in the database.
- Write a mini executor with the iterator model: Write scan, filter and join operators with an open-next-close interface in Python and run a query plan.
About this course
You understand database internals by studying pages, the buffer pool, B+trees, write-ahead logging and MVCC and writing a small key-value store in Python.
What you will learn
- Storage
- Index structures
- Recovery and concurrency
Prerequisites
You should be experienced in the topics of the same path up to level 401.
Lab environment
Lessons run in your own Kali Linux terminal in the browser, connected to a private lab network. Nothing to install.
Frequently asked questions
- Is this course right for my level?
- The course is at level 501; it assumes you know the topics of the lower-level courses.
- Is there anything to install?
- No. Every lesson runs in your own lab environment that opens in the browser.
- How do lessons work?
- Each lesson has 8 to 10 steps and a short quiz. Early steps show the command to type, later steps give less help; if two attempts fail, the solution opens.
- Can I try it for free?
- Yes. The first three lessons of every course are free.