Indexing — Introduction | DBMS Notes

An index is a data structure that improves the speed of data retrieval operations on a database table. It works like the index at the back of a book — instead of scanning

What is an Index?

An index is a data structure that improves the speed of data retrieval operations on a database table. It works like the index at the back of a book — instead of scanning every page, you jump directly to the relevant location.

An index is built on one or more columns of a table and stores the column values along with pointers to the actual data rows.

Why Indexing?

Code exampleWoHoTech

  Without Index:
  SELECT * FROM Employee WHERE emp_id = 105;
  → Scan EVERY row in the table (full table scan)
  → If table has 1,000,000 rows → 1,000,000 comparisons
  → Very slow for large tables

  With Index on emp_id:
  → Use B+ tree to find emp_id = 105
  → Only 3-4 comparisons (log₂ of 1,000,000 ≈ 20, but B+ tree is wider)
  → Jump directly to the row
  → Extremely fast

Index Structure (Concept)

Index	Data File:
│EmpID │ Pointer │ │ Page 1	E101, E102, E103 │
├──────┼─────────┤ │ Page 2	E104, E105, E106 │
│ 101 │	Page1 │─────────┤ Page 3: E107, E108, E109 │
│ 102 │	Page1 │ └──────────────────────────┘
│ 103 │	Page1 │
│ 104 │	Page2 │
│ 105 │	Page2 │──────► {Page 2, Slot 2}
│ 106 │	Page2 │

Types of Indexes — Overview

Indexes ├── By Data Coverage │ ├── Dense Index — entry for every record │ └── Sparse Index — entry for some records (one per block) │ ├── By Key Type │ ├── Primary Index — on ordering key of ordered file │ ├── Clustering Index — on non-key ordering attribute │ └── Secondary Index — on non-ordering attribute │ ├── By Structure │ ├── Single-Level — flat index file │ └── Multi-Level — index on index (B/B+ tree) │ └── By Uniqueness ├── Unique Index — no duplicate key values └── Non-Unique Index — duplicate key values allowed

Index Key vs. Search Key

Index key — the attribute(s) on which the index is built
Search key — the attribute(s) used in a query's WHERE clause

An index is useful when the index key matches (or is a prefix of) the search key.

Cost of Indexing

Indexes are not free — they have costs:

Operation	Impact
SELECT	Faster (the whole point)
INSERT	Slower — index must be updated
UPDATE	Slower — index must be updated if key column changes
DELETE	Slower — index entry must be removed
Storage	Extra disk space required

Rule of thumb: Create indexes on columns that are frequently used in WHERE, JOIN, ORDER BY, and GROUP BY clauses. Avoid over-indexing write-heavy tables.

Index in SQL

sql exampleWoHoTech

-- Create a simple index
CREATE INDEX idx_emp_salary ON Employee(salary);

-- Create a unique index
CREATE UNIQUE INDEX idx_emp_email ON Employee(email);

-- Create a composite (multi-column) index
CREATE INDEX idx_emp_dept_salary ON Employee(dept_id, salary);

-- View indexes on a table
SHOW INDEX FROM Employee;

-- Drop an index
DROP INDEX idx_emp_salary ON Employee;

Clustered vs. Non-Clustered Index

CLUSTERED INDEX

─────────────────

The physical order of rows on disk matches the index order.

Only ONE clustered index per table (it IS the table).

Very fast for range queries.

Employee Table (clustered on EmpID)

Disk: [E101][E102][E103][E104][E105]... (physically sorted)

NON-CLUSTERED INDEX

─────────────────────

A separate structure with pointers to the actual rows.

Multiple non-clustered indexes per table allowed.

Slightly slower than clustered for range queries.

Salary Index (non-clustered)

Index: 45000→{Page5,Slot3}, 52000→{Page2,Slot1}, 75000→{Page1,Slot2}...

← sorted by salary; data rows scattered on disk

What is an Index?

An index is built on one or more columns of a table and stores the column values along with pointers to the actual data rows.

Why Indexing?

Code exampleWoHoTech

  Without Index:
  SELECT * FROM Employee WHERE emp_id = 105;
  → Scan EVERY row in the table (full table scan)
  → If table has 1,000,000 rows → 1,000,000 comparisons
  → Very slow for large tables

  With Index on emp_id:
  → Use B+ tree to find emp_id = 105
  → Only 3-4 comparisons (log₂ of 1,000,000 ≈ 20, but B+ tree is wider)
  → Jump directly to the row
  → Extremely fast

Index Structure (Concept)

Index	Data File:
│EmpID │ Pointer │ │ Page 1	E101, E102, E103 │
├──────┼─────────┤ │ Page 2	E104, E105, E106 │
│ 101 │	Page1 │─────────┤ Page 3: E107, E108, E109 │
│ 102 │	Page1 │ └──────────────────────────┘
│ 103 │	Page1 │
│ 104 │	Page2 │
│ 105 │	Page2 │──────► {Page 2, Slot 2}
│ 106 │	Page2 │

Types of Indexes — Overview

Index Key vs. Search Key

Index key — the attribute(s) on which the index is built
Search key — the attribute(s) used in a query's WHERE clause

An index is useful when the index key matches (or is a prefix of) the search key.

Cost of Indexing

Indexes are not free — they have costs:

Operation	Impact
SELECT	Faster (the whole point)
INSERT	Slower — index must be updated
UPDATE	Slower — index must be updated if key column changes
DELETE	Slower — index entry must be removed
Storage	Extra disk space required

Rule of thumb: Create indexes on columns that are frequently used in WHERE, JOIN, ORDER BY, and GROUP BY clauses. Avoid over-indexing write-heavy tables.

Index in SQL

sql exampleWoHoTech

-- Create a simple index
CREATE INDEX idx_emp_salary ON Employee(salary);

-- Create a unique index
CREATE UNIQUE INDEX idx_emp_email ON Employee(email);

-- Create a composite (multi-column) index
CREATE INDEX idx_emp_dept_salary ON Employee(dept_id, salary);

-- View indexes on a table
SHOW INDEX FROM Employee;

-- Drop an index
DROP INDEX idx_emp_salary ON Employee;

Clustered vs. Non-Clustered Index

CLUSTERED INDEX

─────────────────

The physical order of rows on disk matches the index order.

Only ONE clustered index per table (it IS the table).

Very fast for range queries.

Employee Table (clustered on EmpID)

Disk: [E101][E102][E103][E104][E105]... (physically sorted)

NON-CLUSTERED INDEX

─────────────────────

A separate structure with pointers to the actual rows.

Multiple non-clustered indexes per table allowed.

Slightly slower than clustered for range queries.

Salary Index (non-clustered)

Index: 45000→{Page5,Slot3}, 52000→{Page2,Slot1}, 75000→{Page1,Slot2}...

← sorted by salary; data rows scattered on disk

Indexing — Introduction

What is an Index?

Why Indexing?

Index Structure (Concept)

Types of Indexes — Overview

Index Key vs. Search Key

Cost of Indexing

Index in SQL

Clustered vs. Non-Clustered Index

CLUSTERED INDEX

Employee Table (clustered on EmpID)

NON-CLUSTERED INDEX

Salary Index (non-clustered)

Continue learning this concept

Indexing — Introduction

What is an Index?

Why Indexing?

Index Structure (Concept)

Types of Indexes — Overview

Index Key vs. Search Key

Cost of Indexing

Index in SQL

Clustered vs. Non-Clustered Index

CLUSTERED INDEX

Employee Table (clustered on EmpID)

NON-CLUSTERED INDEX

Salary Index (non-clustered)

Continue learning this concept