Indexes — B-Tree Intuition, When to Add

Runtime contract: This review executed the bounded fixtures with Python’s SQLite 3.45.1. The safe executable lab uses 10,000 deterministic rows in an in-memory SQLite database and checks results/plans, not elapsed-time performance. PostgreSQL 16 index types, MVCC visibility and concurrent-build instructions are primary-source-reviewed references. No Docker container, PostgreSQL server, production DDL or benchmark is run.

Why this session exists

An index trades storage and maintenance work for additional access paths. Whether it helps depends on a query's predicates, output, ordering, cardinality and runtime conditions. A sequential scan can be correct and efficient; an index scan can still do excessive work.

You will explain the page-oriented B-tree model, read scan/search and PostgreSQL plan nodes, assess point/range/sort queries, design composite/expression/partial/covering indexes, measure predicate selectivity correctly, and plan a PostgreSQL concurrent build with validity checks. None of those objectives requires believing a universal “1000× speedup” story.

Prerequisites

Read SQL basics, joins and aggregations. An index changes how rows are found, not which rows SQL means to return; ORDER BY is still necessary even if a particular scan happens to look sorted.

The book index and page-oriented search

A cookbook's alphabetical index maps a rare ingredient to page references. A B-tree similarly organises keys so a search can discard most candidate branches at each level. Its nodes pack multiple keys/pointers into pages; balanced height keeps search-path growth logarithmic. Database page I/O, CPU comparisons and result-row retrieval are distinct costs.

The schematic contains twelve leaf keys, not fifteen table rows; root separator values are routing metadata here. For key 50, visit root then leaf C, then potentially fetch the referenced table tuple. That is two index-page visits, not necessarily two total disk reads. Cached pages may require no physical read; a heap fetch or visibility check can add work.

With an illustrative fanout 200, 200^4 = 1.6 billion describes how rapidly routing capacity grows. It is not a promise of four reads at any table size: leaf capacity, key width, fill, tree shape, cache residency and output cardinality affect the count. A balanced binary search tree and a B-tree both offer logarithmic lookup in key count; B-trees improve page utilisation/fanout rather than winning by a different big-O class. Binary nodes can also share pages, so “one binary-tree level always equals one physical disk read” is too rigid.

Search plus k matching entries is roughly O(log_b n + k) in a simplified ordered-tree model, with additional table-fetch costs. A range scan follows ordered entries; an index-compatible ORDER BY/LIMIT can avoid a separate sort and stop early. Hash indexes are equality-only in PostgreSQL and do not provide order/ranges, but O(1)-style expected probing alone does not prove they are faster than a well-cached B-tree.

The historical lesson is enduring page-oriented ordered search and later specialised access methods, not the original unsourced release-year timeline. PostgreSQL 16's documented method contracts below are the version used for this review.

Index types and appropriate questions

BRIN need not require perfectly sorted or append-only data, but weak correlation reduces pruning. It has no guaranteed 1/1000 size ratio or B-tree-like speed. PostgreSQL pg_trgm supplies GiST/GIN trigram support for suitable LIKE/ILIKE/regex searches, including some non-prefix patterns; it is not the same as a reverse-string B-tree or a complete search-engine inverted-index architecture.

Selectivity is a predicate's matching fraction

Let a table contain 10,000 rows, 9,900 shipped and 100 pending. status='pending' matches 1%; shipped matches 99%. COUNT(DISTINCT status)/COUNT(*) = 2/10000 is a distinctness ratio, not either predicate's selectivity. A low-cardinality column can be useful for a rare value.

SELECT COUNT(*) AS total,
       SUM(CASE WHEN status='pending' THEN 1 ELSE 0 END) AS matching,
       1.0*SUM(CASE WHEN status='pending' THEN 1 ELSE 0 END)/NULLIF(COUNT(*),0) AS match_fraction
FROM orders;

There is no universal “filters out 95%” threshold or “under 10K rows always scan” rule. Table width, clustering/correlation, cache, random-versus-sequential costs, selected columns, LIMIT, index-only opportunities and statistics all matter. A query selecting 90% of a wide table may favour a sequential scan; a count over a small covering index may use that index even for most rows.

When a normal base-column index does not provide the desired seek

• UPPER(email)='X' does not generally obtain an equality seek from an index keyed on raw email; an expression index on UPPER(email) can support that expression. Some casts/rewrites can preserve indexability, so “any function/cast makes every index unusable” is false.
• email LIKE '%example.com' has no fixed leading prefix for a normal email B-tree range seek. A full index scan may still be possible; a suffix/domain column, suitable reversed representation or pg_trgm index solves different search contracts.
• DATE(created_at)=... can often be rewritten to a half-open timestamp interval. Define the timezone first: a local calendar day around daylight-saving changes is not always 24 elapsed hours.
• Prefix LIKE can require a matching operator class/collation in PostgreSQL. Use the deployed collation, not a guessed lexical rule.
• A broad predicate or unfiltered SELECT can legitimately scan. An ORDER BY/LIMIT or covering projection can still make an index useful without a selective WHERE.

Composite indexes: order bounds work, not absolute usability

PostgreSQL 16 explicitly allows a multicolumn B-tree to be used with conditions on any subset of its columns. Leading equalities plus the first following inequality most effectively bound the scanned range. Conditions further right can be checked in the index and save heap visits without necessarily narrowing that range.

For (a,b,c):

For country='DE' AND created_at>=cutoff ORDER BY created_at DESC LIMIT 100, (country,created_at DESC) is a strong candidate because equality fixes country and the remaining range/order align. A workload querying timestamps alone may favour a separate timestamp-first index. “Most selective column first” is not a complete design rule: equality/range/order patterns, reuse, key widths and actual plans matter. Do not import newer PostgreSQL skip-scan behaviour into a version-16 guarantee.

PostgreSQL can combine separate indexes through bitmap plans, with their own costs and loss of index ordering. Composite indexes suit measured common combinations; indexing every possible five-column filter combination is combinatorially expensive. Columnar analytical stores may instead use partition/row-group pruning and clustering. That layout still costs write/recluster/compaction work; skipping is not literally free.

Maintenance, covering and visibility

An inserted row may need entries in several indexes, page splits, WAL records, storage and cache residency. The overhead is not exactly N times total write latency or WAL volume for N indexes. Partial indexes omit nonmatching rows, and PostgreSQL HOT updates can avoid some index maintenance under applicable conditions. Deletes and vacuum cleanup also have different timing from immediate insert maintenance.

A covering index has the values a query needs. PostgreSQL 16 index-only scans additionally need a supported access method and MVCC visibility information: if a heap page's all-visible bit is not set, the executor still visits the heap. INCLUDE can store non-key payload columns without using them for search bounds or unique-key enforcement. Wide payloads increase cost; “covering means never touches the heap and halves I/O” is not a guarantee.

A long-lived snapshot can delay removal of old versions; vacuum maintains visibility/reclamation information. Adding indexes without considering write traffic, memory and vacuum pressure may move rather than solve the bottleneck.

Hands-on: exact local access-path experiment

Save as indexes_lab.py. Data and timestamps are deterministic: created_tick ranges from 1 to 10000, rather than every inserted row receiving the same transaction-start now(). It checks result preservation before/after indexes, expression lookup, composite ordering, common/rare counts and suffix matches. Plan observations are printed with the local SQLite version. No timings are advertised.

"""Access-path observations, not a benchmark or PostgreSQL simulation."""
import sqlite3
 
conn = sqlite3.connect(':memory:')
conn.execute('CREATE TABLE users(id INTEGER PRIMARY KEY,email TEXT NOT NULL,'
             'country TEXT NOT NULL,created_tick INTEGER NOT NULL,status TEXT NOT NULL)')
countries = ['US','IN','DE','JP','BR']
conn.executemany('INSERT INTO users VALUES(?,?,?,?,?)', (
    (i,f'user_{i}@example.com',countries[i%5],i,'pending' if i%100==0 else 'shipped')
    for i in range(1,10001)
))
conn.commit()
conn.execute('ANALYZE')
print('SQLite',sqlite3.sqlite_version)
 
def observe(label, sql, params=()):
    rows = conn.execute(sql,params).fetchall()
    plan = conn.execute('EXPLAIN QUERY PLAN '+sql,params).fetchall()
    print(label, 'result=',rows,'plan=',plan)
    return rows
 
point = 'SELECT id,email FROM users WHERE email=?'
expected = [(9876,'user_9876@example.com')]
assert observe('Before email index',point,('user_9876@example.com',))==expected
conn.execute('CREATE INDEX ix_email ON users(email)')
assert observe('After email index',point,('user_9876@example.com',))==expected
upper = 'SELECT id FROM users WHERE upper(email)=?'
assert observe('Before expression index',upper,('USER_5000@EXAMPLE.COM',))==[(5000,)]
conn.execute('CREATE INDEX ix_upper ON users(upper(email))')
assert observe('After expression index',upper,('USER_5000@EXAMPLE.COM',))==[(5000,)]
 
queries = {
 'A country only': ("SELECT count(*) FROM users WHERE country='DE'",[(2000,)]),
 'B tick only': ('SELECT id FROM users WHERE created_tick>9900 ORDER BY created_tick DESC LIMIT 3',
                 [(10000,),(9999,),(9998,)]),
 'C equality + range/order': ("SELECT id FROM users WHERE country='DE' AND created_tick>9900 "
                            'ORDER BY created_tick DESC LIMIT 3',[(9997,),(9992,),(9987,)])
}
# Owned, disposable in-memory index only; neither production nor repository schema.
for name,definition in [('country_tick','country,created_tick DESC'),
                        ('tick_country','created_tick DESC,country')]:
    conn.execute(f'CREATE INDEX ix_test ON users({definition})')
    conn.execute('ANALYZE')
    for label,(sql,want) in queries.items():
        assert observe(name+' '+label,sql)==want
    conn.execute('DROP INDEX ix_test')
 
conn.execute('CREATE INDEX ix_status ON users(status)')
assert observe('Rare',"SELECT count(*) FROM users WHERE status='pending'")==[(100,)]
assert observe('Common',"SELECT count(*) FROM users WHERE status='shipped'")==[(9900,)]
assert observe('Suffix',"SELECT count(*) FROM users WHERE email LIKE '%example.com'")==[(10000,)]
ratio = conn.execute("SELECT 1.0*sum(status='pending')/count(*),"
                     '1.0*count(DISTINCT status)/count(*) FROM users').fetchone()
assert ratio == (0.01,0.0002)
print('Predicate fraction versus distinctness ratio',ratio)
conn.close()
print('Index result-preservation checks passed; no timing claim')

Worked results and interpretation

• Email user_9876@example.com identifies row 9876 before and after the index.
• Country DE corresponds to id % 5 = 2: there are 2000 DE rows. With created_tick>9900, the newest three are 9997,9992,9987.
• UPPER(email)='USER_5000@EXAMPLE.COM' identifies 5000; the expression index changes the eligible access path, not that answer.
• Status counts are pending 100, shipped 9900. The fixture makes distinctness versus predicate selectivity observable.
• Every email ends with example.com, so that suffix query matches all 10000 rows. A LIMIT 5 merely bounds output; it does not make the predicate selective.

Compare query A (country only), B (tick only) and C (both) under each composite column order on a fresh local fixture. Record SEARCH/SCAN, covering use and temporary-sort indications. Do not force the planner to use an index merely to “prove” a left-prefix slogan. The automated check compares answers and captures plans without treating SQLite choices as PostgreSQL predictions.

Read the access node before interpreting its cost

For the exact local lab on SQLite 3.45.1, the no-index email query reports SCAN users; after ix_email, it reports a SEARCH using a covering email index. In this rowid table, INTEGER PRIMARY KEY aliases the rowid carried by the index, so selecting id and email needs no other table column. Adding country to that SELECT changes the covering requirement. These are fixture observations, not a promise for another schema/version.

Plain EXPLAIN estimates work and rows; it does not measure a successful run. In EXPLAIN ANALYZE, actual rows/time on repeatedly executed nodes are per-loop averages, so multiply by loops when reasoning about total row work. Parent-node times include child work: summing every displayed time double-counts. A bad estimate can be a statistics/correlation issue rather than evidence that the B-tree itself is broken.

A partial index is a predicate contract

This small SQLite fixture exposes eligibility and maintenance without timing claims:

CREATE TABLE partial_orders(id INTEGER PRIMARY KEY,customer_id INTEGER,status TEXT);
INSERT INTO partial_orders VALUES (1,7,'paid'),(2,7,'pending'),(3,8,NULL),(4,8,'paid');
CREATE INDEX ix_paid_customer ON partial_orders(customer_id) WHERE status='paid';
SELECT id FROM partial_orders WHERE status='paid' AND customer_id=7 ORDER BY id;
UPDATE partial_orders SET status='paid' WHERE id=2;
SELECT id FROM partial_orders WHERE status='paid' AND customer_id=7 ORDER BY id;

Answer: first ID 1, then IDs 1 and 2. The update makes row 2 newly eligible for the index. NULL status does not satisfy status='paid'. A query on customer alone cannot use this partial index as the sole source of every customer's order: it omits pending/unknown rows. SQLite and PostgreSQL have their own predicate-implication rules; neither arbitrary logical equivalence nor every bound parameter is guaranteed recognised. A partial index reduces maintained entries for excluded rows, not all work for every future update.

PostgreSQL 16 reference lab, without a bootstrap footgun

In a dedicated disposable PostgreSQL database created by its owner, the following reference-only setup offers varied timestamps and no embedded credentials. It does not DROP any existing table; the fresh table name must not already exist. Run baseline queries before adding indexes and keep identical query text afterward.

CREATE TABLE batch2_index_users (
    id bigint PRIMARY KEY,
    email text NOT NULL,
    country text NOT NULL,
    created_at timestamptz NOT NULL
);
INSERT INTO batch2_index_users
SELECT g,'user_'||g||'@example.com',
       (ARRAY['US','IN','DE','JP','BR'])[1+(g%5)::integer],
       TIMESTAMPTZ '2026-01-01 00:00:00+00' + g*INTERVAL '1 minute'
FROM generate_series(1,10000) AS s(g);
ANALYZE batch2_index_users;
EXPLAIN (ANALYZE,BUFFERS)
SELECT id,email FROM batch2_index_users WHERE email='user_9876@example.com';
CREATE INDEX batch2_index_users_email ON batch2_index_users(email);
CREATE INDEX batch2_index_users_country_ts ON batch2_index_users(country,created_at DESC);
CREATE INDEX batch2_index_users_upper ON batch2_index_users(upper(email));
ANALYZE batch2_index_users;
EXPLAIN (ANALYZE,BUFFERS)
SELECT id,email FROM batch2_index_users WHERE email='user_9876@example.com';
EXPLAIN (ANALYZE,BUFFERS)
SELECT id FROM batch2_index_users
WHERE country='DE' AND created_at >= TIMESTAMPTZ '2026-01-07 00:00:00+00'
ORDER BY created_at DESC,id LIMIT 3;

These are SELECT execution references, not recorded PostgreSQL results or latency claims. Compare rows, loops, buffers, heap fetches and sort nodes. cost is the planner's arbitrary cost scale, not milliseconds. actual time under ANALYZE is measured execution with instrumentation and that run's cache/concurrency state; repeatable benchmark design would require much more control.

Concurrent builds: locks, invalid indexes and rollout

In PostgreSQL 16 ordinary CREATE INDEX acquires a SHARE table lock: normal reads can continue but ordinary writes conflict. It is not ACCESS EXCLUSIVE, and the original quiz incorrectly said it blocks all reads. CREATE INDEX CONCURRENTLY uses a weaker SHARE UPDATE EXCLUSIVE lock and multiple phases/scans; it allows ordinary DML during the build but can wait on transactions, contend with maintenance/DDL and consume significant CPU/I/O. It is not “no locks” or guaranteed zero downtime.

For an owner-approved hot-table migration:

1. Inspect the exact query, existing indexes, table/partition size, long transactions, space and I/O budget. Choose a maintenance window or concurrent build according to workload; offline builds can be appropriate when writes are intentionally stopped.
2. Run CREATE INDEX CONCURRENTLY ... as a top-level statement, not inside a transaction block. PostgreSQL 16 has restrictions for concurrent builds on partitioned parent indexes; plan per-partition attachment separately rather than applying a blanket recipe.
3. Monitor progress/waits and handle failure. A failed concurrent build can leave an invalid index that still consumes update work; a failed concurrent unique build can even continue enforcing uniqueness in documented cases.
4. Verify catalogue flags and the intended definition, not just command completion or presence in pg_indexes. Recheck the target query plan. Choose owner-approved drop/rebuild/reindex recovery if invalid; do not auto-delete from a report.

-- PostgreSQL 16 reference only, in the owner-created disposable database.
-- Run this as a top-level statement, not inside BEGIN/COMMIT.
CREATE INDEX CONCURRENTLY batch2_index_users_created
    ON batch2_index_users(created_at DESC,id);
 
SELECT i.indexrelid::regclass AS index_name,
       i.indisvalid,i.indisready,i.indisunique,
       pg_get_indexdef(i.indexrelid) AS definition
FROM pg_index i
WHERE i.indrelid='batch2_index_users'::regclass;
 
SELECT indexrelname,idx_scan,
       pg_size_pretty(pg_relation_size(indexrelid)) AS index_size
FROM pg_stat_user_indexes
WHERE relid='batch2_index_users'::regclass
ORDER BY pg_relation_size(indexrelid) DESC;

Use indexrelid for index size; the original script used relid and repeatedly measured the table instead. indisvalid determines planner usability; indisready concerns maintenance readiness. Statistics are observation-window-dependent, not lifetime truth.

Foreign keys, unused indexes and the design exercise

PostgreSQL automatically indexes primary/unique keys but does not automatically index referencing FK columns. Parent-key updates/deletes may need to find matching child rows, so a suitable child-key index is often important. A composite index with a useful child-key prefix may already serve the need; small or differently accessed child tables can justify another choice. Do not add redundant indexes simply because the parent is large or small.

idx_scan=0 is a candidate for investigation, not permission to drop. Check reset time, replica/workload routing, infrequent month-end queries, unique/exclusion constraints and whether the index supports required integrity or operational tasks. Index names ending in pkey are not the full list of constraint-supporting indexes. The original Airbnb percentage was not established and is not retained as a fact.

Stretch: customers filtered by country, then paid orders in the last seven days. Candidate designs include customers(country,id) and orders(customer_id,created_at); if every relevant query includes status='paid', a partial index on those order columns with that predicate can reduce indexed entries. If paid is common and the query begins with a narrow time slice, a timestamp/status-driven path may be better. Compare representative selectivity and join order; PostgreSQL must be able to establish that a query implies a partial-index predicate, which parameterised generic plans may not do. Define timestamp boundaries and include selected payload only when justified.

Recall and explain-aloud answers

1. Why logarithmic lookup? Each balanced routing level reduces the candidate range by fanout; page visits grow with height, plus output/heap work.
2. Three seek obstacles? Incompatible expression, no anchored prefix and an unselective predicate. Expression/trigram/covering indexes or scans may still be useful.
3. Selectivity threshold? Predicate matching fraction is measurable; break-even depends on workload, not a universal 5% cutoff.
4. Write cost? Extra maintained structures, WAL, page/cache and vacuum work; not exactly five times cost for five indexes.
5. CREATE INDEX locks? SHARE for normal build versus SHARE UPDATE EXCLUSIVE for concurrent build; concurrent still waits/works and can fail invalid.
6. (country,created_at) with timestamp-only? May be used but often scans a large range; not categorically impossible in PostgreSQL 16.
7. FK auto-index? Referenced eligible unique key is indexed; child FK columns are not automatically indexed in PostgreSQL. Evaluate matching existing indexes and workload.
8. No improvement? Check actual chosen path, estimates/statistics, predicate compatibility, output volume, sorting, visibility/heap fetches and contention.
9. BRIN? Block-range pruning for correlated values; lossy summaries and rechecks, not a fixed size/speed ratio.
10. 90% status query? A scan may win, while a narrow covering count can still use an index. Only representative plan/work measurements decide.

Explain-out-loud answer guide

1. What is an index? An auxiliary access structure; a B-tree stores ordered keys for balanced point/range navigation, with lookup cost plus matching-entry and possible table-fetch work. Not every index is sorted or logarithmic.

2. When use one? A measured recurring query benefits from compatible point/range predicates, ordering or covering access enough to justify storage and write maintenance; verify the actual plan.

3. When not? Do not add redundant/speculative structures or retain costs without a demonstrated need. Small tables, broad predicates and write-heavy workloads are reasons to measure, not universal bans on indexes.

Sources and next steps

Continue to transactions for visibility/locking and query planning for observed plans. Columnstores, search indexes and migration tools extend different parts of this model; no shared repository schema is changed here.

Primary documentation inspected 10 October 2026, pinned to PostgreSQL 16: multicolumn indexes, index types, index-only scans, CREATE INDEX, explicit locks, pg_index, statistics, pg_trgm, EXPLAIN. SQLite EQP is a dated mutable source. No production benchmark conclusions are drawn.

Optional archived resources

These original resource destinations are retained for continuity, not as independently verified technical evidence. Historical video labels, attribution, durations and playback were not verified in this review; search links are discovery queries, not specific lectures. Repeated links are listed once. Prefer the versioned primary sources above for dialect contracts; the archived current-version documentation may evolve.

• B-Tree Indexes — Whiteboard Explanation
• B-Trees and B+ Trees in Databases
• Database Indexing Explained (with PostgreSQL)
• Use The Index, Luke!
• Index Types — PostgreSQL Docs
• CREATE INDEX CONCURRENTLY — the safe way in prod