What Are Indexes? B-Trees Explained

The data structure under everything

Without indexes, every WHERE col = ? is a full table scan: SQLite reads every row, checks the predicate, returns matches. That's O(n). On 10 million rows it's many seconds; on 10 thousand it's invisible.

An index is a separate B-tree data structure that stores the indexed column(s) in sorted order with pointers back to the row. With an index, WHERE col = ? becomes O(log n) — a few page reads regardless of table size.

Three kinds of B-tree access SQLite uses:

Equality — WHERE col = ? walks the tree to the matching key.
Range — WHERE col BETWEEN a AND b walks to the first match then scans forward.
Prefix on TEXT — WHERE col LIKE 'pre%' uses the index because 'pre%' has a known starting prefix; '%suf' does not.

Principle: Every INTEGER PRIMARY KEY is already an index — that's why SQLite can find a row by id instantly without you doing anything. Foreign keys are NOT automatically indexed; you must create the index yourself, and almost always should.

Code

Watch a query change behavior with and without an index·sql

CREATE TABLE big(id INTEGER PRIMARY KEY, email TEXT, name TEXT) STRICT;

-- Insert 100k rows (one transaction!)
WITH RECURSIVE cnt(x) AS (SELECT 1 UNION ALL SELECT x+1 FROM cnt WHERE x<100000)
INSERT INTO big(email, name)
SELECT 'user'||x||'@x.com', 'User '||x FROM cnt;

.timer on
SELECT * FROM big WHERE email = 'user99999@x.com';
-- Run Time: real 0.045 user 0.040 ...   (full scan)

CREATE INDEX idx_big_email ON big(email);
SELECT * FROM big WHERE email = 'user99999@x.com';
-- Run Time: real 0.000 user 0.000 ...   (index used)

What Are Indexes? B-Trees Explained

The data structure under everything

Code

External links

Exercise

Progress

Comments 0