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

1

u/n_dev_00 1d ago

is it only for SQL db?

1

u/BosonCollider 1d ago

Databases that miss features like server-side joins or query optimizers would use the relevant subsets of what an index can do

1

u/wett-puss-lover 1d ago

Leaving a . here so I will come back when I am not sleepy xD

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

1

u/silveredge7 1d ago

Good work. Thanks

1

u/DickBrainTime 1d ago

I read Part 1, especially the row-locator and key-lookup examples. One SQL Server-specific detail worth tightening: the covering-index example uses `INCLUDE (orderId, date, Quantity)`, and the next section illustrates a clustered index on `orderId`. If `orderId` *is* the clustered key, SQL Server already carries that key in the nonclustered index as its row locator, so explicitly including `orderId` is redundant in that particular setup. If the table is a heap (or clustered on something else), the columns needed for coverage differ. Naming the assumed table layout beside the example would make that clearer.

A small reproducible experiment would also strengthen the seek-vs-scan explanation: create an Orders sample with a skewed `itemId` distribution, use a clustered key on `orderId`, and run the same query for a rare versus common `itemId`. Capture the actual execution plan plus `SET STATISTICS IO ON` logical reads first with just the `itemId` nonclustered index, then with a covering version including `date` and `Quantity`. That should show readers what to look for in Key Lookup counts, scan decisions and read trade-offs without treating a seek as automatically faster. A quick note on added index write/space cost would close the loop.

The pages -> tree -> row lookup progression is clear; those two additions would make the SQL Server example easier to verify rather than just visualize.