Indexing in a Database
Lecture 8 · indexing is a technique used in a database to make data searching faster. An index works like the index of a book: instead of scanning the whole table, the DBMS uses the index to directly find the required rows.
The problem — tables are unsorted
A table usually stores data in an unsorted manner and is not optimized for fast searching. Notice that Emp_ID is not sorted here:
| Row Location | Emp_ID | Name | Dept |
|---|---|---|---|
| R1 | 101 | Rahim | CSE |
| R2 | 105 | Rony | CSE |
| R3 | 103 | Karim | EEE |
| R4 | 110 | Nila | BBA |
| R5 | 102 | Hasan | CSE |
the query
SELECT *
FROM Employee
WHERE Emp_ID = 105;Without an index the DBMS may check rows like this:
R1 → R2 → R3 → R4 → R5. It searches the table row by row — a full table scan, O(n). The fix — create an index
create index
CREATE INDEX idx_emp_id
ON Employee(Emp_ID);The index stores the values of the selected column in a sorted / searchable structure, along with pointers to the actual table rows:
| Emp_ID | Row Pointer |
|---|---|
| 101 | R1 |
| 102 | R5 |
| 103 | R3 |
| 105 | R2 |
| 110 | R4 |
Notice that the index is sorted by Emp_ID, not by table row order.
Step 1 — search the smaller SORTED index
binary search finds Emp_ID 105
Get the actual row pointer R2
Step 2 — go directly to row R2 in the actual table
The DBMS does not scan the full table
Uses / benefits of indexing
| Benefit | Example |
|---|---|
| To search records quickly | SELECT * FROM Student WHERE Student_ID = 105; |
| To speed up sorting | SELECT * FROM Student ORDER BY CGPA DESC; |
| To improve join performance | SELECT Student.Name, Enrolls.Course_ID FROM Student, Enrolls WHERE Student.Student_ID = Enrolls.Student_ID; — if Student_ID is indexed in both tables, the join becomes faster. |
| To enforce uniqueness | CREATE UNIQUE INDEX idx_email ON Student(Email); — ensures duplicate emails are not allowed. |
| Reduces disk I/O | Instead of reading the whole table, the DBMS reads only the required index pages and data pages. |
Demerits of indexing
| Demerit | Explanation |
|---|---|
| Extra storage is required | Indexes need additional disk space; a table with many indexes makes the database bigger. |
| Insert becomes slower | INSERT INTO Employee VALUES (106,'Sakib','CSE',52000); — the DBMS inserts the row and also updates the index. |
| Update becomes slower | If an indexed column is updated, the index must also be modified. |
| Delete becomes slower | When a row is deleted, the related index entry must also be deleted. |
| Too many indexes reduce performance | Indexes improve read performance, but too many of them reduce write performance. |
| Not useful for small tables | If a table has very few rows, a full table scan may be faster than using an index. |
The one-sentence trade-off: an index buys read speed with storage and write speed. Index the columns you search, join and sort on — and nothing else.
Next: Evaluation metrics →