When you begin learning about databases, one of the most important performance concepts you will encounter is indexing. To truly understand why indexing is necessary, it helps to begin with a few real-life analogies.

1. Why Do We Need Indexing?

Imagine your home is extremely disorganized. Your watch is in one place, your socks somewhere else, your laptop who-knows-where, and your phone lost under a pile of clothes. If someone asks you to find a small item—say, the key to your bike—it might take a long time. You search randomly because everything is scattered. This is what an unorganized dataset feels like.

Now, compare this with a medical store. If you ask the shopkeeper for Vitamin D capsules, he hands them over immediately. He knows exactly where everything is because the medicines are organized and categorized properly. This organization is the real-world equivalent of indexing.

In an unorganized home, searching takes time. In an organized medical store, searching is instant. Databases behave the same way.

2. How Searching Works Without Indexing

Consider a simple array of numbers arranged randomly. If you are asked to find whether the number 9 exists in the list, you have no choice except to scan each element one by one. This is called a linear search, and its time complexity is:

Time Complexity = O(n)

(You may need to scan all n elements.)

If the array contains 1 million elements and the number you want is at the end, you must check nearly all 1 million items. That is slow.

However, if the array is sorted, you can apply binary search, which cuts the data in half repeatedly. In that case, the time complexity becomes:

Time Complexity = O(log n)

This is significantly faster.

What Does This Have to Do With Indexing?
Indexing is essentially a way to allow a database to use binary search instead of linear search when executing queries—especially those with a WHERE clause.

3. SQL Example

To make the concept concrete, let’s use a real SQL structure with, employees table search

CREATE TABLE employees (
    emp_id INT PRIMARY KEY,
    name VARCHAR(100),
    salary INT
);

INSERT INTO employees (emp_id, name, salary) VALUES
(1, 'Ramesh Thapa', 55000),
(2, 'Sita Karki', 45000),
(3, 'Bikash Gurung', 120000),
(4, 'Mina Magar', 30000),
(5, 'Kamal Lama', 75000),
(6, 'Laxmi BK', 40000),
(7, 'Prakash Bista', 90000),
(8, 'Sarita Rai', 45000),
(9, 'Nirmal Shahi', 150000),
(10, 'Bhabana Kunwar', 45000);
--- This example contains 1050 rows in total.

Imagine this table grows to 10 million employees, with salary values arranged in no particular order.

Suppose we run this query:

SELECT name FROM employees
WHERE salary = 45000;

Output:

+----------------------+
| name                 |
+----------------------+
| Bikash Gurung        |
| Nirmal Shahi         |
| Rajan Kunwar         |
| Bijay Rana           |
| Sabitri Tamang       |
|......................|
|......................|
|......................|
|......................|
| Jeevan Magar         |
| Dipesh Shrestha      |
| Kedar Koirala        |
| Sushil Pandey        |
+----------------------+
408 rows in set (0.013 sec)

What happens internally?
Since the salary column has no index:

  • The database checks every row one-by-one.
  • For a large table (like 10 million rows), this is extremely slow.
  • Time complexity = O(n).

This is the equivalent of searching for your lost items in a messy, unorganized house.

How Indexing Improves This
To optimize the query, we create an index on the salary column:

CREATE INDEX idx_salary ON employees (salary);

Now execute the same query:

SELECT name FROM employees
WHERE salary >= 100000;

Output:

+----------------------+
| name                 |
+----------------------+
| Bikash Gurung        |
| Nirmal Shahi         |
| Rajan Kunwar         |
| Bijay Rana           |
| Sabitri Tamang       |
|......................|
|......................|
|......................|
|......................|
| Jeevan Magar         |
| Dipesh Shrestha      |
| Kedar Koirala        |
| Sushil Pandey        |
+----------------------+
408 rows in set (0.013 sec)

What happens now?

  • The database does not scan the entire employees table.
  • It looks into the separate sorted index structure on salary.
  • It performs binary search on this sorted list.
  • Then uses stored pointers to retrieve the exact rows.

Time complexity becomes: O(log n)

This is drastically faster, even with millions of records.

How Indexes Are Implemented
Most relational databases use B-Tree (or variations like B+Tree) structures to store index data. These are optimized for balanced, fast searches and for disk-based storage.

So, when asked in interviews:

What data structure does indexing use?
Answer: Usually B-Tree or B+Tree.

4. When Should You Use Indexing?

Indexing is powerful, but you must use it wisely. You do not blindly apply indexing everywhere.

Use indexing when the database is read-intensive.

If your system performs many read operations (SELECT queries), indexing will:

  • Improve query speed
  • Reduce response time
  • Decrease CPU usage

2. Avoid indexing: when not to use indexing

1. in write-intensive/write-heavy systems
If your application has many:

  • INSERTs,
  • UPDATEs,
  • DELETEs

Then indexing can slow down performance. Why?
Because every time you modify data:

  1. The table must be updated
  2. The index must also be updated
  3. The index may need re-sorting or rebalancing

This adds overhead.

2. in small tables
Small tables can be scanned very quickly; indexing adds unnecessary complexity.

Conclusion
Indexing is a crucial optimization technique that transforms slow, linear searches into fast, logarithmic searches. By storing sorted values and pointers in a separate memory structure (usually a B-tree), indexes dramatically improve query performance for large datasets.

But remember:
Indexing is most beneficial in read-intensive environments and should be used thoughtfully—not blindly.