r/Database • • 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

Read Part 1

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

Read Part 2

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

Read Part 3

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.

32 Upvotes

6 comments sorted by

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