What is an Index in SQL? B-Tree Indexes Explained

Without an index, finding a specific row in a table means MySQL must check every single row one by one — a full table scan. An index is a separate, specially organized data structure that lets MySQL jump almost directly to the matching rows instead, the same way a book's index lets you jump straight to a topic's page instead of reading the entire book cover to cover.

Key Definitions

• Index: A separate, ordered data structure that MySQL maintains alongside a table, allowing it to quickly locate rows matching a given condition without scanning the entire table.
• Full table scan: A search strategy where MySQL examines every single row in a table one by one, used when no suitable index exists for a query's condition.
• B-Tree (Balanced Tree): A self-balancing, ordered tree data structure that most SQL database indexes use internally, allowing lookups, insertions, and range searches in logarithmic time.

What You'll Learn

• Define a database index and the problem it solves.
• Understand the B-Tree data structure that underlies most SQL indexes.
• Explain why an index dramatically speeds up equality and range lookups.
• Understand the tradeoff an index introduces for write operations.

Detailed Explanation

Imagine searching for 'Dr. Sen' in a doctors table with a million rows and no index on doctor_name. MySQL has no choice but to check every single row's doctor_name column one at a time until it either finds a match or exhausts the entire table — a full table scan, whose cost grows directly with table size.

An index on doctor_name changes this completely. Internally, MySQL's default storage engine, InnoDB, organizes most indexes as a B-Tree: a balanced, ordered tree structure where each node contains sorted key values pointing either to further nodes (narrowing the search) or, at the leaf level, to the actual row's location. Searching a B-Tree for 'Dr. Sen' means starting at the tree's root and following a small number of comparisons down through the tree's structure — for a million-row table, a B-Tree lookup might take roughly 20 comparisons instead of up to a million, because a balanced tree's depth grows logarithmically with the number of entries, not linearly.

This same B-Tree structure is also naturally efficient for range queries (like WHERE salary BETWEEN 80000 AND 100000) and sorting (ORDER BY doctor_name), since B-Tree indexes keep their keys stored in sorted order, letting MySQL walk sequentially through a relevant range rather than needing to sort the entire table from scratch.

Indexes aren't free, however. Every INSERT, UPDATE, or DELETE on an indexed column must also update the index structure itself, which adds write overhead — a genuine tradeoff between faster reads and slightly slower writes, explored further in Lesson 9.11.

Visual Summary

A B-Tree diagram: a root node at the top containing a few sorted key ranges, branching down into several child nodes, each further narrowing the range, down to leaf nodes at the bottom containing actual sorted key values with pointers to row locations. An arrow traces a search path for 'Dr. Sen' from root to leaf in just 3 hops, labeled 'Logarithmic search — a fraction of the comparisons a full scan would need'.

Quick Reference

Search Method	How It Works	Cost as Table Grows
Full table scan (no index)	Check every row one by one	Grows linearly — doubles as rows double
B-Tree index lookup	Navigate a balanced tree structure to the match	Grows logarithmically — barely increases as rows grow

SQL Example

CREATE TABLE departments (
  department_id   INT PRIMARY KEY AUTO_INCREMENT,
  department_name VARCHAR(100) NOT NULL
);

CREATE TABLE doctors (
  doctor_id       INT PRIMARY KEY AUTO_INCREMENT,
  doctor_name     VARCHAR(100) NOT NULL,
  department_id   INT,
  salary          INT,
  FOREIGN KEY (department_id) REFERENCES departments(department_id)
);

CREATE TABLE patients (
  patient_id      INT PRIMARY KEY AUTO_INCREMENT,
  patient_name    VARCHAR(100) NOT NULL,
  city            VARCHAR(80)
);

CREATE TABLE appointments (
  appointment_id    INT PRIMARY KEY AUTO_INCREMENT,
  patient_id        INT,
  doctor_id         INT,
  appointment_date  DATE,
  status            VARCHAR(20),
  FOREIGN KEY (patient_id) REFERENCES patients(patient_id),
  FOREIGN KEY (doctor_id)  REFERENCES doctors(doctor_id)
);

CREATE TABLE bills (
  bill_id         INT PRIMARY KEY AUTO_INCREMENT,
  appointment_id  INT,
  amount          DECIMAL(10,2),
  paid            BOOLEAN DEFAULT FALSE,
  FOREIGN KEY (appointment_id) REFERENCES appointments(appointment_id)
);

INSERT INTO departments VALUES
  (1, 'Cardiology'), (2, 'Orthopedics'), (3, 'Neurology'), (4, 'Dermatology');

INSERT INTO doctors (doctor_id, doctor_name, department_id, salary) VALUES
  (101, 'Dr. Verma', 1, 95000), (102, 'Dr. Iyer', 2, 78000),
  (103, 'Dr. Sen', 3, 120000), (104, 'Dr. Khan', 1, 88000);

INSERT INTO patients VALUES
  (201, 'Amit Rao', 'Pune'), (202, 'Neha Joshi', 'Mumbai'),
  (203, 'Karan Mehta', 'Delhi'), (204, 'Divya Nair', 'Pune');

INSERT INTO appointments VALUES
  (301, 201, 101, '2026-05-01', 'Completed'),
  (302, 202, 102, '2026-05-02', 'Completed'),
  (303, 203, 101, '2026-05-03', 'Cancelled'),
  (304, 204, 103, '2026-05-04', 'Completed');

INSERT INTO bills (appointment_id, amount, paid) VALUES
  (301, 1500.00, TRUE), (302, 2200.00, FALSE),
  (303, 800.00, TRUE), (304, 3000.00, TRUE);

-- Without an index, MySQL must scan every row to find matches
SELECT * FROM doctors WHERE doctor_name = 'Dr. Sen';

-- Adding a B-Tree index on doctor_name (MySQL's default index type)
CREATE INDEX idx_doctors_name ON doctors(doctor_name);

-- The same query now benefits from the index for a much faster lookup
SELECT * FROM doctors WHERE doctor_name = 'Dr. Sen';

-- Use EXPLAIN to see the difference in MySQL's execution plan
EXPLAIN SELECT * FROM doctors WHERE doctor_name = 'Dr. Sen';

Before the index exists, MySQL's only option for the WHERE doctor_name = 'Dr. Sen' query is a full table scan. After CREATE INDEX idx_doctors_name builds a B-Tree structure on the doctor_name column, the identical query can instead navigate that tree directly to the matching row. Running EXPLAIN before and after creating the index reveals this difference concretely in MySQL's chosen execution plan, showing a change from a full scan to an efficient index-based lookup.

Real-World Examples

• E-commerce platforms index product SKU and customer email columns, since these are searched constantly and a full scan across millions of products or customers would be unacceptably slow.
• Banking systems heavily index account numbers and transaction dates, since instant account lookups and date-range statement queries are core, high-frequency operations.
• Search-heavy applications like job boards or real estate listings index location and category columns specifically to keep filtered search results fast even as listing volume grows.

Common Mistakes to Avoid

• Assuming indexes are free and adding them to every column without considering the write-performance tradeoff.
• Not understanding why an index dramatically improves search speed, treating it as unexplained 'magic' rather than a logical data structure benefit.
• Forgetting that an index only helps queries whose conditions can actually make use of that specific index's structure.

Interview Questions

Q1. What is a database index?

An index is a separate, specially organized data structure that MySQL maintains alongside a table, allowing it to quickly locate rows matching a given search condition without scanning every row in the table.

Q2. What data structure do most SQL indexes use internally, and why?

Most SQL indexes, including MySQL's default InnoDB indexes, use a B-Tree (Balanced Tree) structure, which allows lookups, range queries, and sorted access in logarithmic time, since the tree's depth grows very slowly even as the number of indexed entries grows large.

Q3. What is the tradeoff introduced by adding an index?

While an index significantly speeds up read queries like SELECT with WHERE conditions, it adds overhead to write operations (INSERT, UPDATE, DELETE), since the index structure itself must also be updated whenever the indexed column's data changes.

Practice MCQs

1. What happens when MySQL searches a table with no usable index for a query's condition?

1. It automatically creates an index
2. It performs a full table scan, checking every row
3. The query fails with an error
4. It returns cached results only

Answer: B. It performs a full table scan, checking every row

Explanation: Without a usable index, MySQL has no choice but to examine every row in the table one by one to find matches, a full table scan.

2. Why does a B-Tree index search remain fast even as a table grows very large?

1. B-Trees don't actually grow with the table
2. The tree's depth grows logarithmically, not linearly, with the number of entries
3. MySQL caches all B-Trees in memory permanently
4. B-Trees only work on small tables

Answer: B. The tree's depth grows logarithmically, not linearly, with the number of entries

Explanation: A balanced B-Tree's depth increases very slowly as more entries are added, meaning the number of comparisons needed for a lookup grows logarithmically rather than in direct proportion to table size.

Quick Revision Points

• An index avoids full table scans by providing a fast, structured lookup path to matching rows.
• Most SQL indexes use a B-Tree structure, offering logarithmic-time lookups, range queries, and sorted access.
• Indexes speed up reads but add overhead to writes, since the index itself must be maintained on every data change.

Conclusion

• An index is a separate data structure that avoids the need for a full table scan on every query.
• B-Tree indexes provide logarithmic-time lookups, dramatically outperforming linear full scans on large tables.
• Indexes trade improved read performance for some additional write overhead.

A database index is a separate, specially organized data structure — typically a B-Tree — that MySQL maintains alongside a table specifically to avoid full table scans, allowing it to locate matching rows through a small number of logarithmic-time comparisons instead of checking every row one by one. This same sorted, tree-based structure also naturally accelerates range queries and sorting operations. The tradeoff is that every index must be actively maintained on every INSERT, UPDATE, or DELETE affecting its column, introducing some write overhead in exchange for dramatically faster reads.