r/Database • u/iammen • 4d 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
1
u/razor_whim 4d 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
1
u/DickBrainTime 3d 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.
1
u/n_dev_00 4d ago
is it only for SQL db?