Index Types

An index is a data structure that speeds up data retrieval. Without an index, the database must scan the entire table (full table scan) to find matching rows.

Different query patterns require different index types. Choosing the right index is one of the most impactful performance optimizations.

---

Learning Objectives

After completing this chapter, you will be able to:

• Differentiate between clustered and non-clustered indexes.
• Understand composite, covering, and unique indexes.
• Know when to use hash, bitmap, partial, and spatial indexes.
• Explain index-only scans (covering indexes).
• Choose the right index type for a given query pattern.
• Answer index-related interview questions.

---

Index Classification

Indexes can be classified by multiple dimensions:

Dimension	Types
Structure	B+ Tree, Hash, Bitmap, GiST
Clustering	Clustered, Non-Clustered
Uniqueness	Unique, Non-Unique
Columns	Single-Column, Composite (Multi-Column)
Coverage	Covering (Included Columns)
Filtering	Full, Partial (Filtered), Sparse

---

Clustered Index

A clustered index determines the physical order of data in the table.

Characteristics

• The leaf nodes contain the actual data rows.
• There can be only one clustered index per table.
• Data is physically sorted by the clustered key.
• Creating a clustered index rearranges how data is stored on disk.

How It Works (B+ Tree)

Internal: [101 | 201 | 301]
              ↓     ↓     ↓
Leaf:     [101, row_data] → [201, row_data] → [301, row_data]
         (physically ordered on disk)

In Practice

• MySQL/InnoDB: The PRIMARY KEY is always a clustered index.
• SQL Server: Clustered index is created explicitly (or defaults to heap).
• PostgreSQL: Does not have true clustered indexes — uses non-clustered indexes with heap storage. CLUSTER command reorders the table physically.

When to Use

• Primary key lookups: SELECT * FROM Users WHERE User_ID = 101.
• Range queries on the primary key: WHERE User_ID BETWEEN 101 AND 200.
• Queries that return many columns from the same table (no extra lookup needed).

---

Non-Clustered Index

A non-clustered index is a separate structure from the data table.

Characteristics

• Leaf nodes contain pointers to the data (row ID or clustered key).
• You can have many non-clustered indexes per table.
• The index is ordered logically, but the data is not physically reordered.
• A lookup requires: index search → pointer → data fetch.

How It Works

For a heap-organized table:

Index Leaf: [101 | RID_1] → [201 | RID_2] → [301 | RID_3]
                 ↓              ↓              ↓
Data Pages:  [RID_1: row_101] [RID_2: row_201] [RID_3: row_301]

Clustered vs Non-Clustered

Aspect	Clustered	Non-Clustered
Data storage	Data in leaf nodes	Pointer in leaf nodes
Count per table	1	Many (up to 999 in some DBs)
Physical order	Matches index order	Does not change table order
Lookup speed	Fastest (data found in index)	Slower (may need extra lookup)
Insert/Update cost	Higher (may reorganize data)	Lower

---

Composite Index (Multi-Column Index)

A composite index indexes multiple columns together.

Rules

• The index is built on (col1, col2, col3).
• Queries can use the index for conditions on col1, or col1+col2, or col1+col2+col3.
• This is the leftmost prefix rule.

Example

CREATE INDEX idx_name_city_age ON Users (Name, City, Age);

Query	Uses Index?	Reason
WHERE Name = 'Rahul'	Yes	Leftmost column is Name
WHERE Name = 'Rahul' AND City = 'Mumbai'	Yes	Name + City prefix
WHERE Name = 'Rahul' AND City = 'Mumbai' AND Age = 25	Yes	Full prefix match
WHERE City = 'Mumbai'	No	City is not the leftmost column
WHERE Age = 25	No	Age is not the leftmost column
WHERE Name = 'Rahul' AND Age = 25	Partial	Name is used, Age cannot use index (City is missing)

Column Order Matters

Place the most selective column first (the column with the most unique values).

-- Better: Name first (likely more selective than City)
CREATE INDEX idx_name_city ON Users (Name, City);

-- Worse: City first (many users in one city)
CREATE INDEX idx_city_name ON Users (City, Name);

---

Covering Index (Index-Only Scan)

A covering index contains all columns required by a query, so the database never needs to access the actual table.

Example

CREATE INDEX idx_covering ON Users (City) INCLUDE (Name, Email);
-- PostgreSQL: ... INCLUDE (Name, Email)
-- SQL Server: ... INCLUDE (Name, Email)
-- MySQL: CREATE INDEX idx_covering ON Users (City, Name, Email);

Query:

SELECT Name, Email FROM Users WHERE City = 'Mumbai';

The database finds the City in the index, reads Name and Email directly from the index leaf, and returns the result — without touching the table.

Benefits

• Eliminates the extra lookup (bookmark lookup / key lookup).
• Dramatically faster for frequently executed queries.
• Especially useful when only a few columns are needed.

---

Unique Index

A unique index ensures that all values in the indexed column(s) are distinct.

Behavior

• Prevents duplicate values.
• Automatically created when you define a UNIQUE constraint or PRIMARY KEY.
• Improves query performance (the database knows there is at most one matching row).

CREATE UNIQUE INDEX idx_unique_email ON Users (Email);

When to Use

• Email addresses, usernames, phone numbers.
• Natural keys that must be unique.
• Any column with UNIQUE constraint.

---

Hash Index

A hash index uses a hash table instead of a B+ Tree.

Characteristics

• O(1) lookup for equality conditions (WHERE key = 'value').
• Not suitable for range queries (WHERE key > 100 or LIKE patterns).
• Used internally by some databases (PostgreSQL hash indexes, MySQL MEMORY engine).

Example

-- PostgreSQL
CREATE INDEX idx_hash ON Users USING HASH (Email);

Query	Uses Hash Index?
WHERE Email = 'rahul@mail.com'	Yes (O(1))
WHERE Email LIKE 'rahul%'	No (hash cannot do pattern matching)

When to Use

• Equality lookups on a high-cardinality column.
• When B+ Tree overhead is noticeable and range queries are not needed.

---

Bitmap Index

A bitmap index stores a bitmap (array of bits) for each distinct value.

Characteristics

• Each bit represents a row (1 = matches, 0 = does not match).
• Queries combine bitmaps with AND, OR, NOT operations.
• Excellent for low-cardinality columns (male/female, status flags).
• Compresses very well.

Example

-- Oracle
CREATE BITMAP INDEX idx_gender ON Users (Gender);

Row_ID	Gender = Male	Gender = Female
1	1	0
2	0	1
3	1	0

Query: SELECT * FROM Users WHERE Gender = 'Male' → Fetch rows where Male bitmap = 1.

When to Use

• Data warehouse / OLAP queries.
• Columns with few distinct values (＜ 1% of row count).
• Complex boolean combinations of multiple low-cardinality columns.

Not suitable for: OLTP with frequent updates (bitmap indexes have high update cost).

---

Partial (Filtered) Index

A partial index indexes only a subset of rows.

Example

-- PostgreSQL, SQL Server
CREATE INDEX idx_active_users ON Users (Email) WHERE Status = 'Active';

• The index contains only Active users.
• Smaller index → faster scans.
• Queries with WHERE Status = 'Active' AND Email = '...' use this index.

When to Use

• When queries consistently filter on a specific value (e.g., WHERE Status = 'Active').
• Archival tables where you query recent data more frequently.
• Soft-delete tables where you often filter WHERE deleted_at IS NULL.

---

Index Selection Guidelines

Query Pattern	Best Index Type
WHERE id = 101	Clustered (PK) or Unique
WHERE city = 'Mumbai' AND name = 'Rahul'	Composite (city, name)
WHERE name LIKE 'Rah%'	B+ Tree (supports prefix search)
WHERE status IN ('A', 'B', 'C')	Bitmap (for low-cardinality)
SELECT name, email WHERE city = 'Mumbai'	Covering (includes name, email)
WHERE email = 'user@mail.com'	Hash or Unique
WHERE status = 'Active'	Partial (filtered)

---

Interview Deep Dive

---

Key Takeaways

• Clustered indexes store data in order; non-clustered indexes store pointers.
• Only one clustered index per table; many non-clustered indexes.
• Composite indexes follow the leftmost prefix rule.
• Covering indexes enable index-only scans (no table access).
• Hash indexes are O(1) for equality but cannot do range queries.
• Bitmap indexes are for low-cardinality columns in OLAP systems.
• Partial indexes reduce size by indexing only relevant rows.
• Choose index types based on query patterns, not table structure.