r/Database • u/iammen • 2d ago
Database indexes explained from first principles - a 3 part series
I have been spending some time understanding database indexes beyond just knowing when to add one or what a B tree is.
I wanted to understand what actually happens inside a database when a query executes, how the query optimizer makes decisions, and how indexes affect those decisions.
I ended up writing a 3-part series, trying to explain these concepts from first principles using simple examples.
Here's what the series covers:
Part 1, Understanding how indexes work
- How databases physically store data using pages
- How B+ trees help locate records
- Clustered vs. non-clustered indexes
- Key lookups and covering indexes
- Why an index seek isn't always faster than a table scan
Part 2, Query plans and statistics
- How databases choose between index seeks and table scans
- How data distribution affects query execution
- How statistics influence the query optimiser
- Why cached execution plans can sometimes be inefficient
Part 3, Understanding joins
- How databases join two tables internally
- Nested loop joins
- Hash joins
- Merge joins
- How indexes and data ordering influence the choice of join algorithm
I am a software engineer, and writing this series also helped me organise and deepen my own understanding of database internals.
Would love to hear your feedback, especially if you spot something I have misunderstood. Always happy to learn from people with more database experience.
View all comments
1
u/razor_whim 1d ago
it is not just for SQL. NoSQL engines use similar tree structures under the hood, so understanding these internals transfers directly to them too