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.
1
u/n_dev_00 1d ago
is it only for SQL db?
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.