B-Tree Index

Intermediate

Indexes

InnoDB's default B-tree index supports equality, range, prefix, and ORDER BY operations; the leftmost prefix rule governs which queries benefit from a composite index.

Overview

The B-Tree (Balanced Tree) index is InnoDB's default and most widely used index structure. It organises values in a sorted tree of fixed-depth pages, allowing MySQL to locate a row with O(log n) disk reads instead of a full O(n) table scan. Every InnoDB table has a clustered index — the primary key B-Tree stores the actual row data at its leaf nodes. Secondary (non-clustered) B-Tree indexes store the indexed column values plus the primary key value at their leaf nodes; MySQL then performs a second lookup (bookmark lookup) into the clustered index to fetch the full row. Understanding how B-Trees work — and specifically the leftmost prefix rule for composite indexes — is essential for writing queries that actually use your indexes.

Clustered vs Secondary Indexes

InnoDB tables always have a clustered index. If you define a PRIMARY KEY, that is the clustered index — the table's rows are physically stored in primary key order. If not, InnoDB uses the first unique NOT NULL column; otherwise it creates a hidden 6-byte row ID.

Secondary indexes are separate B-Tree structures. Their leaf nodes contain the indexed column(s) and the primary key value. A lookup on a secondary index first traverses the secondary B-Tree, then uses the retrieved primary key to look up the full row in the clustered index — this double traversal is the "bookmark lookup" or "key lookup".

SQL — MySQL Index Internals

-- Clustered index = PRIMARY KEY
-- Row data is physically ordered by customer_id
CREATE TABLE customers (
    customer_id INT        NOT NULL AUTO_INCREMENT,
    email       VARCHAR(255) NOT NULL,
    name        VARCHAR(100),
    city        VARCHAR(50),
    PRIMARY KEY (customer_id)          -- clustered index
);

-- Secondary index on email
CREATE INDEX idx_email ON customers (email);

-- When MySQL uses idx_email to find a row:
-- 1. Traverse idx_email B-Tree to find leaf with email value → gets customer_id
-- 2. Traverse PRIMARY KEY B-Tree with that customer_id → gets full row
-- This is the "bookmark lookup" — 2 B-Tree traversals

-- Avoid it with a covering index (include all needed columns):
CREATE INDEX idx_email_name ON customers (email, name);
-- SELECT name FROM customers WHERE email = '...'
-- → satisfied entirely from the secondary index, no bookmark lookup needed

Leftmost Prefix Rule for Composite Indexes

A composite (multi-column) index on (a, b, c) can be used by queries that filter on: • a alone • a and b • a, b, and c

But NOT on b alone, or c alone, or b and c — because the index is sorted by a first. This is the leftmost prefix rule. It also applies to range queries: once a range condition is applied to a column, the optimizer cannot use the index for subsequent columns in the index.

SQL — MySQL

-- Composite index on (city, status, created_at)
CREATE INDEX idx_city_status_date ON orders (city, status, created_at);

-- ✅ Uses the full index (city + status + range on created_at)
SELECT * FROM orders
WHERE  city = 'Mumbai'
  AND  status = 'SHIPPED'
  AND  created_at >= '2025-01-01';

-- ✅ Uses first two columns of the index
SELECT * FROM orders
WHERE  city = 'Mumbai' AND status = 'PENDING';

-- ✅ Uses only the first column
SELECT * FROM orders WHERE city = 'Delhi';

-- ❌ Index NOT used — skips the first column (city)
SELECT * FROM orders WHERE status = 'PENDING';

-- ❌ After a range on city, status cannot use the index
SELECT * FROM orders
WHERE  city > 'L'    -- range condition — index can only help filter city
  AND  status = 'SHIPPED';  -- status cannot use the index here

-- EXPLAIN confirms which index is chosen
EXPLAIN SELECT * FROM orders WHERE city = 'Mumbai' AND status = 'SHIPPED';
-- key: idx_city_status_date   key_len: X   ref: const,const   type: ref

Index Selectivity & Choosing the Right Columns

Index selectivity = distinct values / total rows. A value near 1.0 (e.g., email, UUID) means the index eliminates almost all rows — very effective. A value near 0 (e.g., boolean, gender) means the index barely narrows things down — often the optimizer skips it and does a full scan.

Composite index column order tip: put high-selectivity equality columns first, then lower-selectivity equality columns, then the range column last. Never index columns you always filter with a function (e.g., YEAR(created_at)) — use generated columns or range queries instead.

SQL — MySQL

-- Check index selectivity
SELECT
    index_name,
    cardinality,
    cardinality / (SELECT COUNT(*) FROM orders) AS selectivity
FROM information_schema.statistics
WHERE table_schema = 'mydb'
  AND table_name   = 'orders';

-- ❌ Function on indexed column disables the index
SELECT * FROM orders WHERE YEAR(created_at) = 2025;
-- Optimizer cannot use an index on created_at because of the function wrapper

-- ✅ Rewrite as a range — index on created_at is used
SELECT * FROM orders
WHERE  created_at >= '2025-01-01'
  AND  created_at <  '2026-01-01';

-- Generated column trick for function-based index equivalent
ALTER TABLE orders ADD COLUMN order_year SMALLINT
    GENERATED ALWAYS AS (YEAR(created_at)) STORED;
CREATE INDEX idx_order_year ON orders (order_year);

Key Points to Remember

1Every InnoDB table has a clustered B-Tree index (the PRIMARY KEY) — row data is physically stored at its leaf nodes in PK order.
2Secondary index leaf nodes store the indexed column(s) + primary key; MySQL does a second lookup (bookmark lookup) to fetch the full row.
3A covering index includes all columns needed by a query, eliminating the bookmark lookup — EXPLAIN shows "Using index".
4The leftmost prefix rule: a composite index on (a, b, c) is usable for queries that start with a; skipping the first column means the index is not used.
5After a range condition on a column in a composite index, subsequent columns in the index cannot be used for filtering.
6Avoid applying functions on indexed columns in WHERE clauses (YEAR(created_at)); use range conditions instead to keep the index usable.

Interview Questions

What is the difference between a clustered and a non-clustered index in MySQL InnoDB?

MediumAmazon

Explain the leftmost prefix rule with an example of a composite index.

MediumUber

You have an index on (city, status). Will the query WHERE status = 'ACTIVE' use this index?

EasyFlipkart

What is a covering index and how does it improve query performance?

MediumGoogle

Why does WHERE YEAR(created_at) = 2025 not use an index on created_at? How do you rewrite it?

MediumInfosys

Ask Aria about B-Tree Index

Your personal AI tutor — ask anything about this concept

Revision Status

Personal Notes

Discussion

Loading discussion…

Indexes Overview

Composite Index