Chapter 36 of 41

Indexing in DBMS

On this page

Think about a 900-page textbook. If you want the page that explains "deadlock", you do not read the book from page 1. You open the index at the back, find "Deadlock ... 412", and jump straight to page 412.

A database does exactly the same thing. A table with a few million rows is stored across thousands of disk blocks. Reading every block to find one row is slow. An index is a small, separate structure that tells the DBMS where the wanted rows live, so it can jump straight to them.

In the previous chapter, File Organization, we saw how records are placed into blocks (heap files, sequential files, hashed files). In this chapter we add a second structure on top of the file: the index.

An index is an auxiliary data structure that maps values of a search key to the locations (blocks or records) where rows with those values are stored, so that the DBMS can find them without scanning the whole file.


Why Do We Need Indexes?

The slow part of a database query is usually not the CPU. It is moving blocks (also called pages) between disk and memory. So in DBMS theory we measure the cost of a search by the number of block accesses.

Suppose a table has 6,000 blocks and is stored as a heap (unordered) file. To find the student with roll number 1042:

  • Without an index: the DBMS must scan blocks one by one. On average it reads half the file (3,000 blocks); in the worst case, all 6,000.

  • With a good index: it reads a handful of index blocks plus one data block, often 3 to 4 block accesses in total.

That difference (thousands of reads versus four) is why indexes exist. We will compute these exact numbers later in the chapter.


Basic Terms

Term

Meaning

Search key

The attribute (or set of attributes) used to look up rows through the index. It does not have to be a primary key or even unique.

Index entry

A pair (search-key value, pointer). The pointer is either a block address or a record address.

Index file

The file that stores the index entries, kept sorted by search key (for ordered indexes).

Data file

The file that stores the actual table rows.

Index entries are much smaller than full rows (a key plus a pointer, maybe 16 bytes, versus a 100+ byte row). So many more entries fit in one block, which makes the index file far smaller than the data file. Searching a small, sorted file is cheap.

There are two big families of indexes:

  • Ordered indexes: entries are kept sorted by the search key (this chapter, and B-trees/B+ trees in the next chapter).

  • Hash indexes: entries are placed into buckets using a hash function (covered in Hashing in DBMS).


How Do We Judge an Index?

No single index is best for everything. Textbooks usually compare indexing techniques on these factors:

  • Access types supported: equality search (roll = 1042), range search (marks BETWEEN 60 AND 80), or both.

  • Access time: block accesses needed to find the data.

  • Insertion time and deletion time: every INSERT/DELETE must also update every index on the table.

  • Space overhead: the extra disk space the index occupies.

Keep these in mind. Almost every design decision about indexes is a trade-off between faster reads and slower writes plus extra space.


Dense Index vs Sparse Index

Dense Index

A dense index has an index entry for every search-key value in the data file (for a unique key, that means one entry per record).

Dense index on roll_no          Data file (sorted by roll_no)

 roll_no | ptr                  Block 1:  101 Asha    CSE
 --------+----                            102 Bilal   ECE
   101   | --> Block 1                    103 Chitra  CSE
   102   | --> Block 1          Block 2:  104 Dev     ME
   103   | --> Block 1                    105 Esha    CSE
   104   | --> Block 2                    106 Farhan  IT
   105   | --> Block 2          Block 3:  107 Gauri   ECE
   106   | --> Block 2                    108 Harsh   CSE
   107   | --> Block 3
   108   | --> Block 3

To find roll 105, the DBMS searches the index for 105 and follows the pointer directly to the record.

Sparse Index

A sparse (non-dense) index has entries for only some search-key values, typically one entry per data block (the first key in each block, called the anchor record or block anchor).

Sparse index on roll_no         Data file (sorted by roll_no)

 roll_no | ptr                  Block 1:  101 Asha    CSE
 --------+----                            102 Bilal   ECE
   101   | --> Block 1                    103 Chitra  CSE
   104   | --> Block 2          Block 2:  104 Dev     ME
   107   | --> Block 3                    105 Esha    CSE
                                          106 Farhan  IT
                                Block 3:  107 Gauri   ECE
                                          108 Harsh   CSE

To find roll 105:

  1. Find the largest index key that is ≤ 105. That is 104.

  2. Follow its pointer to Block 2.

  3. Search inside Block 2 for 105.

Why does this work? Only because the data file is sorted on the same key. If the file were not sorted by roll_no, roll 105 could be in any block, and knowing that block 2 starts at 104 would tell us nothing. That is the most important rule to remember:

A sparse index is possible only when the data file is physically ordered on the search key.

Point

Dense Index

Sparse Index

Entries

One per search-key value

One per block (typically)

Size

Larger

Much smaller

Lookup

Usually a bit faster (points straight at the record)

Needs a search inside the data block

Data file must be sorted on key?

No

Yes

Insert/delete maintenance

More work (more entries)

Less work (changes only when a block's first key changes)

Can answer "does key exist?" from the index alone

Yes

No, must read the data block


Types of Single-Level Ordered Indexes

Classic DBMS textbooks (and GATE questions) divide single-level ordered indexes into three types, depending on whether the data file is sorted on the indexed field and whether that field is a key.

Field is a key (unique)

Field is a non-key (duplicates allowed)

Data file sorted on this field

Primary index

Clustering index

Data file not sorted on this field

Secondary index (on a key)

Secondary index (on a non-key)

1. Primary Index

A primary index is built on the ordering key field of a sorted file: the file is physically sorted on this field and the field is unique.

  • It is sparse: one entry per data block, holding the block's first key (anchor) and the block pointer.

  • Number of index entries = number of data blocks.

The roll_no example above is a primary index.

2. Clustering Index

A clustering index is built when the file is physically sorted on a non-key field, so many records can share the same value (for example, a student file sorted by dept).

  • There is one entry per distinct value of the field.

  • The pointer goes to the first block containing that value. Records with the same value are stored next to each other ("clustered"), so the DBMS just keeps reading forward.

Clustering index on dept        Data file (sorted by dept)

 dept | ptr                     Block 1:  CSE  Asha
 -----+----                               CSE  Chitra
 CSE  | --> Block 1                       CSE  Esha
 ECE  | --> Block 2             Block 2:  CSE  Harsh
 IT   | --> Block 3                       ECE  Bilal
 ME   | --> Block 3                       ECE  Gauri
                                Block 3:  IT   Farhan
                                          ME   Dev

Notice that ECE points to Block 2 even though Block 2 starts with a CSE record. The pointer goes to the first block where that value appears.

3. Secondary Index

A secondary index is built on a field that is not the ordering field of the file. Since the file is not sorted on this field, matching records can be anywhere, so a secondary index must be dense.

  • On a key field (e.g., email in a file sorted by roll_no): one entry per record, pointing to the block or record.

  • On a non-key field (e.g., city): one value may appear in many records spread over many blocks. The common solution is an extra level of indirection: the index entry for Pune points to a small block (a "bucket") that lists the pointers to all Pune records.

Secondary index on city (non-key) with indirection

 city      | ptr                 pointer block          data file (sorted by roll_no)
 ----------+----                 for "Pune"
 Chennai   | --> [..]
 Pune      | --> [ r3 , r7 , r12 ]  -->  records scattered in blocks 1, 3 and 5
 Mumbai    | --> [..]

(Elmasri & Navathe classify this indirection version as nondense, because it has one entry per distinct value rather than one per record. Under the definition used in this chapter, an entry for every search-key value, it counts as dense. Either way, every value of the field appears in the index, which is the point that matters.)

Secondary indexes give a big improvement over a linear scan because, without them, a search on a non-ordering field must read the whole file.

How Many of Each Can a Table Have?

  • A file can be physically sorted on only one field. So a file can have at most one primary index OR one clustering index, not both.

  • A file can have many secondary indexes.

A Note on Terminology

Different books use different words, which confuses many students:

  • Some books (for example, Silberschatz) use clustering index (or primary index) for any index whose search key matches the file's sort order, and non-clustering index for secondary indexes.

  • Others (for example, Elmasri & Navathe, and most GATE questions) use the three-way split shown above.

  • In real systems, "primary index" usually just means "the index on the PRIMARY KEY". These are not the same idea, so read questions carefully.


Worked Example: Counting Block Accesses

This is the classic exam calculation. Let us do it step by step.

Given:

  • Number of records r = 60,000

  • Record size R = 100 bytes

  • Block size B = 1024 bytes, records are unspanned (a record never crosses a block boundary)

  • Search key size V = 10 bytes, block pointer size P = 6 bytes

Step 1: The Data File

Blocking factor  bfr = floor(B / R) = floor(1024 / 100) = 10 records per block
Number of blocks b   = ceil(r / bfr) = ceil(60000 / 10)  = 6000 blocks
  • Linear search (no index, unsorted file): 3000 block accesses on average, 6000 in the worst case.

  • Binary search (file sorted on the key): ceil(log2 6000) = 13 block accesses.

Step 2: A Primary Index (Sparse)

Index entry size        = V + P = 10 + 6 = 16 bytes
Index blocking factor   = floor(1024 / 16) = 64 entries per block   (this is the fan-out)
Index entries           = one per data block = 6000
Index blocks            = ceil(6000 / 64) = 94 blocks
Binary search on index  = ceil(log2 94) = 7 block accesses
Plus 1 data block       = 7 + 1 = 8 block accesses

The index is only 94 blocks, compared to 6000 data blocks. Binary search on the small index plus one data-block read costs 8 accesses instead of 13.

Step 3: A Secondary Index (Dense) on a Key Field

Now suppose the file is not sorted on the field we want to search, so without an index we need a linear scan (3000 accesses on average).

Index entries           = one per record = 60000
Index blocks            = ceil(60000 / 64) = 938 blocks
Binary search on index  = ceil(log2 938) = 10 block accesses
Plus 1 data block       = 10 + 1 = 11 block accesses

From 3000 average accesses down to 11. The dense index is bigger than the sparse one (938 vs 94 blocks), but it is still a huge win.


Multilevel Indexes

Binary search on a 938-block index still needs about log2 938 ≈ 10 reads. Can we do better?

Yes. The index file is itself a sorted file. So we can build a sparse index on the index, and then an index on that, until the top level fits in one block. This is a multilevel index.

The key insight: binary search cuts the search space by a factor of 2 per read, but each index block lets us choose among fo (the fan-out, here 64) children. So each read cuts the search space by a factor of 64.

Level 1 (the dense secondary index) : 938 blocks
Level 2 (sparse index on level 1)   : ceil(938 / 64) = 15 blocks
Level 3 (sparse index on level 2)   : ceil(15 / 64)  = 1 block   <-- top level

Search cost = one block per level + one data block = 3 + 1 = 4 block accesses
                  [ top level: 1 block ]
                 /          |           \
       [15 second-level index blocks]
         /    |    \
 [938 first-level index blocks]  -->  data blocks

In general, a multilevel index needs about logfo(number of first-level blocks) levels. With fan-out 64, a three-level index can hold up to 64 × 64 × 64 = 262,144 first-level entries (the top block points to 64 second-level blocks, which point to 4,096 first-level blocks of 64 entries each). Our 60,000 entries fit comfortably.

Method (same 60,000-record file)

Block accesses

Linear search, unsorted file

3000 average, 6000 worst

Binary search, sorted file

13

Primary (sparse) index + binary search

8

Secondary (dense) index + binary search

11

Multilevel index over the secondary index

4

A static multilevel index has one big problem: inserting and deleting records means shifting entries in sorted blocks at every level. The fix is a dynamic multilevel index that leaves free space in nodes and splits/merges them as needed. That structure is the B+ tree, the subject of the next chapter, B-Tree & B+ Tree. Almost every real relational database uses B+ trees as its default index.


Single-Column, Composite and Covering Indexes

Composite (Multi-Column) Index

A composite index uses more than one column as the search key, for example (city, salary). Entries are sorted by city first, and by salary within the same city, just like names in a phone book are sorted by surname, then by first name.

This gives the leftmost-prefix rule: an index on (city, salary) can efficiently look up by city alone, or by city and salary together, but not by salary alone. A phone book does not help you find everyone named "Rahul" regardless of surname.

Covering Index

If an index contains every column a query needs, the DBMS can answer the query from the index alone without touching the table rows. Such an index "covers" the query. This saves the extra lookup into the data file.


Seeing Indexes in a Real DBMS (MySQL 8)

Theory is easier to trust when you see it. The examples below use the company_db sample database from our SQL tutorial (tables departments, employees, customers, orders). EXPLAIN shows the plan MySQL chooses for a query. The two columns to watch are type (how rows are accessed) and key (which index is used).

Indexes MySQL Created Automatically

SELECT INDEX_NAME, COLUMN_NAME, NON_UNIQUE, INDEX_TYPE
FROM information_schema.STATISTICS
WHERE TABLE_SCHEMA = 'company_db' AND TABLE_NAME = 'employees'
ORDER BY INDEX_NAME, SEQ_IN_INDEX;
+------------+-------------+------------+------------+
| INDEX_NAME | COLUMN_NAME | NON_UNIQUE | INDEX_TYPE |
+------------+-------------+------------+------------+
| dept_id    | dept_id     |          1 | BTREE      |
| email      | email       |          0 | BTREE      |
| manager_id | manager_id  |          1 | BTREE      |
| PRIMARY    | emp_id      |          0 | BTREE      |
+------------+-------------+------------+------------+

We never wrote CREATE INDEX, yet there are four indexes. MySQL created them for the PRIMARY KEY, the UNIQUE constraint on email, and the two FOREIGN KEY columns (InnoDB requires an index on foreign key columns so that constraint checks are fast). All are B+ trees (MySQL reports them as BTREE).

Before and After Creating an Index

EXPLAIN SELECT name, salary FROM employees WHERE city = 'Mumbai';
+----+-------------+-----------+------------+------+---------------+------+---------+------+------+----------+-------------+
| id | select_type | table     | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra       |
+----+-------------+-----------+------------+------+---------------+------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | employees | NULL       | ALL  | NULL          | NULL | NULL    | NULL |   10 |    10.00 | Using where |
+----+-------------+-----------+------------+------+---------------+------+---------+------+------+----------+-------------+

type = ALL means a full table scan: every row is read and checked. Now add a secondary index on city:

CREATE INDEX idx_city ON employees(city);
EXPLAIN SELECT name, salary FROM employees WHERE city = 'Mumbai';
+----+-------------+-----------+------------+------+---------------+----------+---------+-------+------+----------+-------+
| id | select_type | table     | partitions | type | possible_keys | key      | key_len | ref   | rows | filtered | Extra |
+----+-------------+-----------+------------+------+---------------+----------+---------+-------+------+----------+-------+
|  1 | SIMPLE      | employees | NULL       | ref  | idx_city      | idx_city | 203     | const |    2 |   100.00 | NULL  |
+----+-------------+-----------+------------+------+---------------+----------+---------+-------+------+----------+-------+

Now type = ref and key = idx_city: MySQL looks up 'Mumbai' in the index and reads only the 2 matching rows instead of all 10. (The query returns Sneha Kapoor and Vikram Singh.) On a 10-row table this hardly matters, but on 10 million rows it is the difference between milliseconds and minutes.

A lookup on the primary key is even better: type = const, because at most one row can match.

EXPLAIN SELECT name FROM employees WHERE emp_id = 5;
+----+-------------+-----------+------------+-------+---------------+---------+---------+-------+------+----------+-------+
| id | select_type | table     | partitions | type  | possible_keys | key     | key_len | ref   | rows | filtered | Extra |
+----+-------------+-----------+------------+-------+---------------+---------+---------+-------+------+----------+-------+
|  1 | SIMPLE      | employees | NULL       | const | PRIMARY       | PRIMARY | 4       | const |    1 |   100.00 | NULL  |
+----+-------------+-----------+------------+-------+---------------+---------+---------+-------+------+----------+-------+

Wrapping the Column in a Function Hides the Index

CREATE INDEX idx_hire ON employees(hire_date);
EXPLAIN SELECT name FROM employees WHERE YEAR(hire_date) = 2020;
+----+-------------+-----------+------------+------+---------------+------+---------+------+------+----------+-------------+
| id | select_type | table     | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra       |
+----+-------------+-----------+------------+------+---------------+------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | employees | NULL       | ALL  | NULL          | NULL | NULL    | NULL |   10 |   100.00 | Using where |
+----+-------------+-----------+------------+------+---------------+------+---------+------+------+----------+-------------+

The index on hire_date is ignored (possible_keys = NULL). Why? The index is sorted by hire_date, not by YEAR(hire_date). The DBMS cannot search a sorted list of dates for "year = 2020" without computing the function for every entry. Rewrite the condition as a range on the bare column:

EXPLAIN SELECT name FROM employees
WHERE hire_date >= '2020-01-01' AND hire_date < '2021-01-01';
+----+-------------+-----------+------------+-------+---------------+----------+---------+------+------+----------+-----------------------+
| id | select_type | table     | partitions | type  | possible_keys | key      | key_len | ref  | rows | filtered | Extra                 |
+----+-------------+-----------+------------+-------+---------------+----------+---------+------+------+----------+-----------------------+
|  1 | SIMPLE      | employees | NULL       | range | idx_hire      | idx_hire | 3       | NULL |    2 |   100.00 | Using index condition |
+----+-------------+-----------+------------+-------+---------------+----------+---------+------+------+----------+-----------------------+

type = range: an index range scan, exactly what an ordered index is good at. (MySQL 8.0.13 and later can also index an expression directly, e.g. CREATE INDEX idx_hire_year ON employees ((YEAR(hire_date)));, after which the first query uses that functional index.)

The Leftmost-Prefix Rule in Action

CREATE INDEX idx_city_salary ON employees(city, salary);

EXPLAIN SELECT name FROM employees WHERE salary > 90000;
+----+-------------+-----------+------------+------+---------------+------+---------+------+------+----------+-------------+
| id | select_type | table     | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra       |
+----+-------------+-----------+------------+------+---------------+------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | employees | NULL       | ALL  | NULL          | NULL | NULL    | NULL |   10 |    33.33 | Using where |
+----+-------------+-----------+------------+------+---------------+------+---------+------+------+----------+-------------+

salary is the second column of the index, so the index cannot be used to search by salary alone. Now use the leading column:

EXPLAIN SELECT city, salary FROM employees WHERE city = 'Mumbai' AND salary > 60000;
+----+-------------+-----------+------------+-------+--------------------------+-----------------+---------+------+------+----------+--------------------------+
| id | select_type | table     | partitions | type  | possible_keys            | key             | key_len | ref  | rows | filtered | Extra                    |
+----+-------------+-----------+------------+-------+--------------------------+-----------------+---------+------+------+----------+--------------------------+
|  1 | SIMPLE      | employees | NULL       | range | idx_city,idx_city_salary | idx_city_salary | 208     | NULL |    2 |   100.00 | Using where; Using index |
+----+-------------+-----------+------------+-------+--------------------------+-----------------+---------+------+------+----------+--------------------------+

Two things to notice:

  • type = range on idx_city_salary: MySQL jumps to city = 'Mumbai' and scans the salary range inside it.

  • Extra: Using index: this is a covering index. The query only needs city and salary, both stored in the index, so the table rows are never read.

One more interesting case: if the query needs only indexed columns but filters on the second column, MySQL may scan the whole index (smaller than the table) instead of the table:

EXPLAIN SELECT city, salary FROM employees WHERE salary > 90000;
+----+-------------+-----------+------------+-------+-----------------+-----------------+---------+------+------+----------+--------------------------+
| id | select_type | table     | partitions | type  | possible_keys   | key             | key_len | ref  | rows | filtered | Extra                    |
+----+-------------+-----------+------------+-------+-----------------+-----------------+---------+------+------+----------+--------------------------+
|  1 | SIMPLE      | employees | NULL       | index | idx_city_salary | idx_city_salary | 208     | NULL |   10 |    33.33 | Using where; Using index |
+----+-------------+-----------+------------+-------+-----------------+-----------------+---------+------+------+----------+--------------------------+

type = index is a full index scan, not a search: all 10 index entries are read. Students often mistake it for "the index is being used efficiently". It is better than reading the table, but it is still a scan.

How InnoDB Maps These Ideas

  • Every InnoDB table is stored inside the B+ tree of its primary key. This is called the clustered index: the leaf level holds the full rows, sorted by primary key. It plays the role of the textbook primary index (the file is ordered on the key).

  • All other indexes are secondary indexes. Their leaf entries store the indexed columns plus the primary key value (not a physical address). A secondary-index lookup therefore finds the primary key first and then searches the clustered index to fetch the row, unless the index covers the query.

  • This is one practical reason to keep primary keys short: every secondary index entry carries a copy of the primary key.


The Cost of Indexes: When Not to Index

If indexes are so fast, why not index every column? Because every index has a price:

  • Slower writes: each INSERT, DELETE, and UPDATE of an indexed column must also update every affected index. A table with 8 indexes does roughly 9 structure updates per inserted row.

  • Extra storage: indexes occupy disk and buffer-pool memory.

  • Low selectivity columns gain little: on a column like gender or status with only a few distinct values, a lookup matches a large fraction of the table. Jumping between index and table for 40% of the rows can be slower than a single sequential scan, so the optimizer often ignores such an index.

  • Tiny tables: if the whole table fits in a block or two, a scan is already cheap.

Good candidates for indexes:

  • Columns used often in WHERE conditions with high selectivity (IDs, emails, phone numbers).

  • Join columns (especially foreign keys).

  • Columns used in ORDER BY or range conditions (an ordered index returns rows already sorted).


Common Mistakes

  • Saying a sparse index works on any file. It needs the data file to be sorted on the search key.

  • Saying a secondary index can skip values like a sparse primary index. The file is not ordered on that field, so every value must appear in the index.

  • Thinking a table can have two clustering/primary indexes. A file has only one physical order.

  • Forgetting the +1. Index search cost counts the index blocks plus one access to the data block.

  • Using floor instead of ceil (or vice versa). Blocking factor uses floor (a partial record does not fit); number of blocks uses ceil (a partial block still occupies a block).

  • Applying functions to indexed columns in WHERE conditions, which hides the index.

  • Ignoring column order in composite indexes. (a, b) is not the same as (b, a).


Interview Questions

1. What is an index and why does it speed up queries?

An index is a separate structure that maps search-key values to record locations. Because index entries are small and sorted (or hashed), the DBMS can find the right block with a few block accesses instead of scanning the whole table.

2. Difference between a dense and a sparse index?

A dense index has an entry for every search-key value; a sparse index has entries for only some values (usually one per block). Sparse indexes are smaller but require the data file to be sorted on the search key.

3. Primary vs clustering vs secondary index?

Primary: file sorted on a unique key field, sparse, one entry per block. Clustering: file sorted on a non-key field, one entry per distinct value pointing to the first block with that value. Secondary: on a field the file is not sorted by, always dense, and a table can have many.

4. Why can a table have only one clustered index?

A clustered index determines the physical order of rows, and rows can be stored in only one order.

5. What is a multilevel index and why is it useful?

It is an index on an index, built until the top level fits in one block. Each level narrows the search by the fan-out (often hundreds) instead of by 2 as in binary search, so lookups need only a few block accesses. B+ trees are dynamic multilevel indexes.

6. What is a covering index?

An index that contains all the columns a query needs, so the query is answered from the index alone without reading table rows.

7. An index exists on (last_name, first_name). Will WHERE first_name = 'Ravi' use it for searching?

No. By the leftmost-prefix rule, the index is sorted by last_name first, so it cannot be used to seek on first_name alone (the DBMS might still do a full index scan).

8. Why not create an index on every column?

Every index slows down inserts, updates and deletes, consumes space, and may not help low-selectivity columns. Indexes should match the actual query workload.


Summary

  • An index maps search-key values to record locations, reducing the number of block accesses.

  • Dense index: entry for every key value. Sparse index: entry per block, only possible when the file is sorted on the key.

  • Primary index: sorted file, unique key, sparse. Clustering index: sorted file, non-key, one entry per distinct value. Secondary index: unsorted field, dense, many allowed.

  • A file can have at most one primary or clustering index, but many secondary indexes.

  • Cost = index block accesses + 1 data block. Use floor for blocking factor, ceil for block counts.

  • Multilevel indexes reduce search cost to about logfan-out(index blocks). B+ trees make them dynamic.

  • Composite indexes follow the leftmost-prefix rule; covering indexes avoid table reads.

  • Indexes speed up reads but cost space and slow down writes, so choose them based on the queries you actually run.

An index trades a little space and write speed for a lot of read speed.