Storage Engine Internals | Relational Databases

In this chapter

The table itself turns out to be a B-Tree too, sorted by rowid — we look underneath SQLite's page-based storage, then run ANALYZE and discover its statistics are real, but based on averages that can hide the exact kind of skew Chapter 3 uncovered.

12–15 min

The Problem in Real Life

Mike has one more question before he lets this Act go. "Every time you say 'B-Tree,' I picture the index. But what about the table itself? Where do all the actual rows live?"

Sarah smiles. "Same idea, actually. The table isn't some separate pile of rows sitting off to the side — it's a B-Tree too, just one sorted by row ID instead of whatever column we pick."

It's the one piece that ties every earlier chapter in this Act together — indexes, plans, optimization — all of it sits on top of this same underlying structure.

An index isn't a separate world from the table. It's the same kind of structure, just sorted by something else.

Sarah

What an Index Sits On Top Of

A table is a B-Tree too

Sorted by rowid instead of a chosen column — the same structure this Act has been calling an index, just applied to the table itself.

Everything on disk is pages

Both table B-Trees and index B-Trees are built from the same fixed-size pages — PRAGMA page_size/page_count reveal this directly.

ANALYZE replaces guesses with real numbers

sqlite_stat1 records actual row counts and average values-per-row for every index, so the planner isn't working from a default assumption.

Even real statistics can hide the truth

Basic statistics store an average, not a true distribution — a column with a rare and a common value can still look uniform to the planner.

What's Actually Underneath a Table

Everything in this Act has been about indexes — but a table itself is stored the exact same way. SQLite keeps every table as its own B-Tree, sorted by rowid (the row's internal identifier), and every index as a separate B-Tree, sorted by whatever column(s) it was built on. An index doesn't replace the table's structure; it adds another, differently-sorted path to the same data.

Below the B-Tree level, a SQLite database file is really just a sequence of fixed-size pages — the unit SQLite reads and writes at a time, whether it's loading a row, an index entry, or anything else on disk.

OrderID is declared INTEGER PRIMARY KEY, which SQLite treats as an alias for the table's own rowid — meaning the table's B-Tree is already sorted by exactly this value. Looking a row up by it needs nothing extra.

A Rowid Lookup Needs No Separate Index

EXPLAIN QUERY PLAN
SELECT * FROM AllOrders WHERE OrderID = 5000;

SEARCH AllOrders USING INTEGER PRIMARY KEY (rowid=?) — the fastest possible lookup, using a structure that already existed.

A SQLite database file is divided into fixed-size pages — here, 4,096 bytes each. Every table B-Tree and every index B-Tree is built out of these same pages; page_count shows how many currently exist in this database.

The Database File, in Pages

PRAGMA page_size;
PRAGMA page_count;

page_size: 4096. page_count: 78 — this entire 10,000-row table (plus its schema) fits in 78 pages.

ANALYZE walks every table and index and records real statistics — row counts and how spread out each indexed column's values are — into a table called sqlite_stat1, so the query planner can make decisions based on actual numbers instead of a rough default guess.

ANALYZE: Turning Guesses Into Real Numbers

CREATE INDEX idx_allorders_customerid ON AllOrders (CustomerID);
CREATE INDEX idx_allorders_status ON AllOrders (Status);

ANALYZE;

SELECT * FROM sqlite_stat1;

idx_allorders_customerid: 10000 rows, ~20 per distinct value. idx_allorders_status: 10000 rows, ~5000 per distinct value — notice this is just an average, and doesn't capture Chapter 3's real skew (100 Cancelled vs. 9,900 Delivered).

The Planner, Now Backed by Real Numbers

EXPLAIN QUERY PLAN
SELECT * FROM AllOrders WHERE CustomerID = 250 AND Status = 'Cancelled';

SEARCH AllOrders USING INDEX idx_allorders_customerid (CustomerID=?) — with ANALYZE's numbers in hand (20 avg rows/value vs. 5,000), the planner has a real, evidence-based reason to prefer this index, not just a default assumption.

This is also where a real limitation shows up honestly: sqlite_stat1's basic statistics only record an average rows-per-value, not the actual distribution. It has no way to know that 'Cancelled' is rare and 'Delivered' is common — both get treated as roughly 5,000 rows each. On a real production database, this is exactly the kind of gap that occasionally leads a well-informed planner to still make a suboptimal choice.

None of this changes what to write in a query — it changes what's actually happening underneath one. A table is a B-Tree by rowid, an index is a B-Tree by something else, both live in the same fixed-size pages, and the planner's decisions are only as good as the statistics it's been given.

Key Takeaway

A table is stored the exact same way an index is — a B-Tree sorted by rowid instead of a chosen column — and the query planner's every decision in this Act has been built on real, but sometimes incomplete, statistics about that underlying structure.

Why This Matters

Understanding that tables and indexes are the same kind of structure — just sorted differently — is what makes concepts like covering indexes, rowid lookups, and ANALYZE's role click together as one coherent system, instead of a list of disconnected tricks.

GreenMart's team now understands what every earlier chapter in this Act was actually built on top of. The checkpoint ahead puts all of it together on a genuinely slow report.