Indexing Internals

Reviewed & published by Brayan K

By the end of this lesson you'll know what actually happens inside an index — how a B-tree turns a million-row scan into a handful of hops, when a hash or bitmap index wins, the difference between clustered and non-clustered storage, why a covering index can skip the table entirely, and the leftmost-prefix rule that decides whether your composite index gets used at all.

Part of the free SQL course at LearnCodingFast — hands-on lessons with examples you run in your browser, plus practice exercises and a quick quiz.

What You'll Learn

• How a B-tree/B+tree gives O(log n) lookups, range scans, and free sorting
• Why hash indexes are equality-only and bitmap indexes suit low-cardinality columns
• Clustered vs non-clustered indexes — physical order vs pointers
• Covering indexes and the index-only scan that never touches the table
• The leftmost-prefix rule for composite (multi-column) indexes
• How to read an EXPLAIN plan to confirm an index is actually used

Our Sample Table: employees

Picture this employees table with 1,000,000 rows. Without an index, finding one salary means reading all million rows. The examples below build indexes on it and watch the plan change.

1. B-Tree Indexes — The Workhorse

An index is a separate data structure the database keeps next to your table to find rows quickly — like the index at the back of a book. The default everywhere (PostgreSQL, MySQL, SQLite, SQL Server) is the B-tree (technically a B+tree: only the leaf level holds the data, and the leaves are chained together).

A B-tree is a sorted phone book. The values are kept in order, so you never read it cover to cover. You open near the middle, see you've gone too far, jump back — a few hops and you're there. Each hop roughly halves what's left, which is why lookups are logarithmic: 1,000,000 rows take only about 20 comparisons (log₂ 1,000,000 ≈ 20), not a million.

How it works under the hood: internal nodes are signposts ("salaries from 50k–60k are down this branch"); the bottom leaf nodes hold the actual entries in sorted order and are linked left-to-right in a chain. That structure gives you three wins for free:

• Equality (= 75000): walk down the tree to one leaf.
• Range (BETWEEN 50000 AND 80000): find the first matching leaf, then follow the leaf chain until you pass the upper bound.
• Sorting (ORDER BY salary): the leaves are already sorted, so no separate sort step is needed.

-- The table this lesson uses. Every later block queries it, and the
-- "Try it Yourself" button carries this setup along so each snippet runs.
-- manager_id points at another row's id; the CEO's is NULL, which is what
-- makes the org chart walkable.
CREATE TABLE employees (
    id         INTEGER PRIMARY KEY,
    name       TEXT,
    title      TEXT,
    manager_id INTEGER,
    salary     INTEGER,
    hire_date  TEXT,
    email      TEXT
);

INSERT INTO employees (id, name, title, manager_id, salary, hire_date, email) VALUES
    (1, 'Ada',   'Chief Executive',  NULL, 180000, '2019-02-11', '[email protected]'),
    (2, 'Brian', 'VP Engineering',      1, 140000, '2020-06-01', '[email protected]'),
    (3, 'Carla', 'VP Sales',            1, 135000, '2021-09-20', '[email protected]'),
    (4, 'Dan',   'Engineer',            2,  75000, '2024-01-15', '[email protected]'),
    (5, 'Eve',   'Junior Engineer',     4,  62000, '2024-07-08', '[email protected]');

-- This lesson also queries an orders table, so it is created here too.
CREATE TABLE orders (
    id          INTEGER PRIMARY KEY,
    customer_id INTEGER,
    product_id  INTEGER,
    order_date  TEXT,
    quantity    INTEGER,
    total       REAL,
    status      TEXT
);

INSERT INTO orders (id, customer_id, product_id, order_date, quantity, total, status) VALUES
    (1, 101, 1, '2026-01-14', 2,  49.98, 'shipped'),
    (2, 102, 3, '2026-01-22', 1,  79.00, 'shipped'),
    (3, 101, 4, '2026-02-03', 5,  16.25, 'pending'),
    (4, 103, 5, '2026-02-17', 1,  32.00, 'shipped'),
    (5, 104, 6, '2026-02-28', 3,  38.97, 'cancelled'),
    (6, 102, 2, '2026-03-05', 4,  38.00, 'pending'),
    (7, 105, 3, '2026-03-19', 2, 158.00, 'shipped'),
    (8, 101, 6, '2026-03-30', 1,  12.99, 'shipped');


-- A B-tree index keeps the indexed values in SORTED order,
-- so the database can binary-search them instead of reading
-- every row. This is the default in PostgreSQL, MySQL, SQLite...
CREATE INDEX idx_employees_salary
ON employees (salary);

-- Now an equality lookup walks down the tree (a few hops),
-- instead of scanning all 1,000,000 rows:
SELECT id, name, salary
FROM employees
WHERE salary = 75000;

-- A range scan finds the FIRST matching leaf, then walks the
-- sorted leaves left-to-right until it passes the upper bound:
SELECT id, name, salary
FROM employees
WHERE salary BETWEEN 50000 AND 80000;

-- Because the leaves are already sorted, the same index also
-- powers ORDER BY salary with NO extra sort step.

-- ✅ Expected result:
-- id | name | salary
-- 5 | Eve | 62000
-- 4 | Dan | 75000

2. Reading the EXPLAIN Plan

How do you prove the index is being used? Ask the planner with EXPLAIN. It prints the plan — the steps the database will take, as text. The two lines you care about most:

• Seq Scan — a full table scan; every row read. The index was not used.
• Index Scan — it jumped through the index. That's what you want.

-- Ask the planner what it would do (this text is the EXPLAIN
-- "plan" — read it bottom-up; the deepest node runs first):
EXPLAIN
SELECT id, name, salary FROM employees WHERE salary = 75000;

-- ✅ Expected plan (uses the index we just created):
--   Index Scan using idx_employees_salary on employees
--     Index Cond: (salary = 75000)
--
-- "Index Scan" = good — it jumped straight to the rows.
-- If you instead see "Seq Scan on employees", the index was
-- NOT used and every row was read one by one.

Your Turn: pick the index type

Choose B-tree vs hash vs bitmap for the described column and justify it. The expected answer is in the comments so you can check yourself.

-- 🎯 YOUR TURN — fill in the blanks and justify your choice.
-- Scenario: the "orders" table has a "status" column with just
-- 4 possible values (pending, shipped, delivered, cancelled).
-- It is ONLY ever filtered with status = '...' and the table is
-- read far more often than it is written.

-- 1) Which index TYPE fits a low-cardinality, read-heavy,
--    equality-only column?  (btree / hash / bitmap)
-- 👉 Replace ___ with one of those three words:
CREATE ___ INDEX idx_orders_status ON orders (status);

-- 2) 👉 In one line, say WHY a plain B-tree is a poor fit here:
-- Because ___

-- ✅ Expected: BITMAP — only ~4 distinct values means a B-tree
--    is barely more selective than a full scan, while a bitmap
--    AND/ORs tiny bit-strings and is cheap to combine. A B-tree
--    is a poor fit because low cardinality gives it almost no
--    filtering power (each value points at ~25% of all rows).

3. Hash Indexes — Equality Only

A hash index runs each value through a hash function and stores it in a bucket. Looking up an exact value is O(1) on average — jump straight to the bucket. The catch: hashing scrambles order, so there is no "next" value. That means equality only — no ranges, no ORDER BY, no prefix LIKE.

Think of a hash index as a coat check: hand over your ticket number and you get the exact coat instantly — but you can't ask for "all coats with tickets between 40 and 80", because the rack isn't in number order.

-- A HASH index stores hash(value) -> row location in buckets.
-- Lookup is O(1) average for EQUALITY, but the hash destroys
-- ordering, so it can do = and nothing else.
CREATE INDEX idx_users_email_hash
ON users USING hash (email);

-- ✅ Great — exact match jumps to one bucket:
SELECT * FROM users WHERE email = '[email protected]';

-- ❌ A hash index CANNOT serve any of these (no order exists):
--   WHERE email > 'a'          -- no range scan
--   WHERE email LIKE 'alice%'  -- no prefix search
--   ORDER BY email             -- no sorted output
-- For range/sort/LIKE you must fall back to a B-tree.

4. Bitmap Indexes — Low Cardinality

Cardinality means "how many distinct values a column has". email is high-cardinality (nearly unique); status with four values is low-cardinality. A bitmap index stores one bit-string per distinct value — a row of 1s and 0s where bit position N means "row N has this value". To find "shipped AND west", the database just bitwise-ANDs two bit-strings, which is blazingly fast.

Imagine a wall of light switches, one per row. The "shipped" bitmap flips on every shipped order; the "west" bitmap flips on every western order. Overlay the two and the switches still on are exactly the rows you want.

Oracle creates bitmap indexes explicitly; PostgreSQL builds equivalent bitmap scans on the fly to combine several B-tree indexes. The downside is writes: every insert or update must flip bits across whole bit-strings, so bitmaps belong on read-heavy tables (reporting, data warehouses), not busy transactional tables.

-- A BITMAP index shines on LOW-CARDINALITY columns — ones with
-- only a handful of distinct values (status, is_active, region).
-- It stores one bit-string per distinct value; bit position N
-- means "row N has this value":
--   status='shipped'   -> 1 0 0 1 1 0 ...
--   status='pending'   -> 0 1 1 0 0 1 ...
-- (Oracle creates these explicitly; PostgreSQL builds them
--  on the fly when combining several B-tree indexes.)
CREATE BITMAP INDEX idx_orders_status ON orders (status);

-- The magic: combine filters with cheap bitwise AND / OR.
-- "shipped AND west" = bitwise-AND the two bit-strings, then
-- fetch only the rows whose result bit is 1:
SELECT * FROM orders
WHERE status = 'shipped'
  AND region = 'west';

-- ⚠️ Each write must flip bits across whole bit-strings, so
-- bitmaps are for read-heavy tables (data warehouses), not
-- busy OLTP tables that update constantly.

5. Clustered vs Non-Clustered

A clustered index decides the physical order of the rows on disk — the table is the index, with full rows living in the leaves. Because rows can only be stored one way, a table can have exactly one clustered index (usually the primary key). A non-clustered index is a separate sorted structure whose leaves hold the indexed value plus a pointer back to the row; you can have many of these, but each lookup pays for a pointer hop to fetch the rest of the row.

A clustered index is a dictionary: the words and their definitions are physically printed in sorted order. A non-clustered index is the index at the back of a textbook: it lists terms with page numbers you must flip to.

-- CLUSTERED index = the table rows are PHYSICALLY stored in the
-- index's order. There can be only ONE per table (rows can only
-- be sorted one way). The primary key is usually the cluster key.
-- A "leaf" of the clustered index IS the full row.
--   (SQL Server: CREATE CLUSTERED INDEX; MySQL/InnoDB clusters
--    on the PRIMARY KEY automatically.)
CREATE CLUSTERED INDEX idx_orders_pk ON orders (order_id);

-- NON-CLUSTERED index = a separate sorted structure whose leaves
-- hold the indexed value + a POINTER back to the row. You can
-- have many of these. The pointer hop to fetch the rest of the
-- row is the cost.
CREATE INDEX idx_orders_customer ON orders (customer_id);

-- Reading customer 42's orders: walk idx_orders_customer to find
-- the matching keys, then follow each pointer into the clustered
-- table to get the full rows.
SELECT * FROM orders WHERE customer_id = 42;

6. Covering Indexes — Skip the Table

A covering index includes every column a query touches, so the database answers it from the index alone and never visits the table — an index-only scan. You keep the filter/sort columns as the index keys and tack on the columns you only need to return as the payload (via INCLUDE in PostgreSQL/SQL Server, or just by listing them in MySQL).

-- A COVERING index contains EVERY column a query needs, so the
-- database answers the query from the index alone and never
-- touches the table — an "index-only scan".

-- This query needs customer_id (to filter) and total (to return):
SELECT total FROM orders WHERE customer_id = 42;

-- Put the filter column first, then INCLUDE the payload column:
CREATE INDEX idx_orders_cust_total
ON orders (customer_id) INCLUDE (total);
-- (PostgreSQL/SQL Server use INCLUDE; MySQL just lists both
--  columns: ON orders (customer_id, total).)

-- ✅ Expected plan — note "Index Only Scan", no table fetch:
--   Index Only Scan using idx_orders_cust_total on orders
--     Index Cond: (customer_id = 42)

7. Composite Indexes & the Leftmost-Prefix Rule

A composite (multi-column) index on (A, B, C) is sorted by A first, ties broken by B, then C — exactly like a phone book sorted by (last name, then first name). The leftmost-prefix rule follows directly: the index can seek only on a prefix of its columns with no gaps. It serves filters on A, on A+B, or on A+B+C — but not on B alone or C alone, because without the leading column the entries are scattered all over the index.

💡 Rule of thumb — column order is everything

Put the columns you filter with = first, the column you range/sort on next, and payload-only columns last. Get the order wrong and the index sits unused while your query falls back to a Seq Scan.

Your Turn: which queries does it serve?

Given the composite index below, mark each query ✅ (index helps) or ❌ (it can't) using the leftmost-prefix rule.

-- 🎯 YOUR TURN — leftmost-prefix rule.
-- A composite B-tree index is sorted by its FIRST column, then
-- ties broken by the second, then the third — like a phone book
-- sorted by (last_name, first_name). You can only use it from
-- the LEFT with no gaps.
CREATE INDEX idx_emp ON employees (department_id, hire_date, salary);

-- For EACH query, mark ✅ if the index helps or ❌ if it cannot,
-- 👉 by replacing each ___ :

-- a) WHERE department_id = 5
--    ___   (leftmost column present)

-- b) WHERE department_id = 5 AND hire_date > '2023-01-01'
--    ___   (leftmost + next, no gap)

-- c) WHERE hire_date > '2023-01-01'
--    ___   (starts at the 2nd column — gap at the front)

-- d) WHERE department_id = 5 AND salary > 90000
--    ___   (uses dept for seeking; salary can't be seeked
--           because hire_date in the middle is skipped)

-- ✅ Expected: a) ✅   b) ✅   c) ❌   d) ✅ (partial — it seeks
--    on department_id only, then filters salary while scanning).

Common Errors (and the fix)

• Hash index for a range query: you build USING hash (price) then run WHERE price > 100 and the plan shows a Seq Scan. Hashing has no order — use a B-tree for anything but exact equality.
• Wrong composite column order: an index on (hire_date, department_id) won't help WHERE department_id = 5 because department_id isn't the leftmost column. Reorder to put the most-filtered (usually the =) column first.
• Over-indexing a write-heavy table: every INSERT/UPDATE/DELETE must update every index, so piling indexes onto an OLTP table makes writes crawl. Index the queries that matter, then drop unused ones (check idx_scan = 0 in pg_stat_user_indexes).
• Low-selectivity B-tree index: indexing is_active (only true/false) rarely helps — when a value matches ~half the rows the planner ignores the index because a scan is cheaper. Index high-selectivity columns; consider a bitmap for low-cardinality reporting.
• Function on the indexed column: WHERE LOWER(email) = '[email protected]' can't use a plain index on email — the function hides the raw value. Index the expression (CREATE INDEX ... (LOWER(email))) or store it normalized.

Frequently Asked Questions

Q: If indexes make reads so fast, why not index every column?

Because every index must be kept up to date on every write, and each one eats storage and memory. More indexes mean slower INSERT/UPDATE/DELETE and a bigger database. Index for the queries you actually run, then drop the ones the stats show are unused.

Q: What's the difference between a B-tree and a B+tree?

In a B+tree only the leaf level stores data, and the leaves are linked in a chain — which is what makes range scans and ordered reads fast. Databases say "B-tree" but almost all of them actually implement B+trees.

Q: My index exists but the query still does a Seq Scan — why?

Common causes: the filter doesn't match the leftmost prefix of a composite index; a function wraps the column (LOWER(col)); the column has low selectivity so a scan is genuinely cheaper; or table statistics are stale (run ANALYZE). Read the EXPLAIN plan to see which.

Q: Does the order of columns in a composite index matter?

Hugely. (A, B) and (B, A) are different indexes that serve different queries. Lead with the column(s) you filter by equality, then the range/sort column. The leftmost-prefix rule means only the leading columns can be seeked.

Mini-Challenge: Design the Optimal Index

Put it all together — equality first, sort column next, payload via INCLUDE. Write the CREATE INDEX, then check it against the expected idea in the comments.

-- 🎯 MINI-CHALLENGE: design the optimal index for this workload.
-- This ONE query runs thousands of times per minute on a huge,
-- read-heavy "events" table:
--
--   SELECT event_time, payload
--   FROM   events
--   WHERE  tenant_id = ?
--     AND  event_type = 'click'
--   ORDER BY event_time DESC
--   LIMIT 50;
--
-- Design a single index that:
--   1. Seeks on the two equality columns (think leftmost-prefix
--      order: which columns are matched with = ?)
--   2. Returns rows already in ORDER BY order (so no sort step)
--   3. COVERS the query so it never touches the table
--
-- ✅ Expected idea: lead with the equality columns, then the
--    sort column, then INCLUDE the payload, e.g.
--    (tenant_id, event_type, event_time) INCLUDE (payload).
--    Equality columns first → seek; event_time next → ordered
--    scan that satisfies ORDER BY; INCLUDE(payload) → index-only.

-- your CREATE INDEX here

🎉 Lesson Complete

• ✅ A B-tree/B+tree keeps values sorted for O(log n) lookups, range scans, and free ordering
• ✅ Hash indexes are equality-only; bitmap indexes suit low-cardinality, read-heavy columns
• ✅ Clustered = physical row order (one per table); non-clustered = a sorted structure of pointers
• ✅ A covering index answers a query from the index alone (index-only scan)
• ✅ The leftmost-prefix rule decides which queries a composite index serves — column order is everything
• ✅ Read the EXPLAIN plan: Index Scan good, Seq Scan means your index was skipped
• ✅ Next: Query Optimization — turn these plans into faster queries

Practice quiz

Continue this course

• Previous: Advanced Relational Database Theory & Normalization (BCNF, 4NF, 5NF)
• Next: Query Optimization Deep Dive: Execution Plans, Cost Estimation & Hints — Read EXPLAIN plans, understand cost estimation, and apply optimiser hints
• Quick reference: SQL cheat sheet
• From the blog: Database Indexing Strategies