Single column index in SQL - Time & Space Complexity

Time Complexity: Single column index

O(log n)

Understanding Time Complexity

When we use a single column index in a database, it helps us find data faster. We want to understand how the time to find data changes as the table grows.

How does using an index affect the speed of searching through many rows?

Scenario Under Consideration

Analyze the time complexity of the following SQL query using a single column index.

SELECT *
FROM employees
WHERE employee_id = 12345;
-- Assume employee_id has a single column index

This query looks for one employee by their unique ID using an index on that column.

Identify Repeating Operations

What repeats when the database searches for the employee?

• Primary operation: The database traverses the index tree to find the matching employee_id.
• How many times: It moves through levels of the index, which grows slowly compared to the number of rows.

How Execution Grows With Input

As the number of employees grows, the search steps increase slowly.

Input Size (n)	Approx. Operations
10	About 3 steps
100	About 7 steps
1000	About 10 steps

Pattern observation: The steps grow slowly, adding only a few more as the table gets much bigger.

Final Time Complexity

Time Complexity: O(log n)

This means the search time grows slowly as the table gets bigger, making lookups efficient.

Common Mistake

[X] Wrong: "Using an index makes the search time the same no matter how big the table is."

[OK] Correct: The search time still grows as the table grows, but only slowly, not instantly or fixed.

Interview Connect

Understanding how indexes speed up searches helps you explain database efficiency clearly. This skill shows you know how data grows and how to keep queries fast.

Self-Check

"What if the index was on two columns instead of one? How would the time complexity change?"

Practice

1.

What is the main purpose of creating a single column index in a database?

easy

A. To store duplicate values in the column

B. To automatically backup the database

C. To prevent any changes to the column data

D. To speed up queries that filter or sort by that column

Solution

1. Step 1: Understand what an index does

   An index helps the database find rows faster when searching or sorting by the indexed column.

2. Step 2: Identify the purpose of a single column index

   A single column index speeds up queries that use that column in WHERE or ORDER BY clauses.

3. Final Answer:

   To speed up queries that filter or sort by that column -> Option D

4. Quick Check:

   Index speeds up queries = B [OK]

Hint: Index speeds up searches on one column [OK]

Common Mistakes:

• Thinking index stores duplicate values
• Believing index prevents data changes
• Confusing index with backup

2.

Which of the following is the correct syntax to create a single column index on the email column of a table named users?

easy

A. CREATE INDEX users ON idx_email(email);

B. CREATE INDEX idx_email ON users(email);

C. CREATE INDEX email ON users idx_email;

D. CREATE users INDEX idx_email(email);

Solution

1. Step 1: Recall the syntax for creating an index

   The correct syntax is: CREATE INDEX index_name ON table_name(column_name);

2. Step 2: Match the syntax with the options

   CREATE INDEX idx_email ON users(email); matches the correct syntax exactly.

3. Final Answer:

   CREATE INDEX idx_email ON users(email); -> Option B

4. Quick Check:

   CREATE INDEX index_name ON table(column) = A [OK]

Hint: Syntax: CREATE INDEX name ON table(column) [OK]

Common Mistakes:

• Swapping table and index names
• Missing ON keyword
• Incorrect order of keywords

3.

Given a table products with columns id, name, and category, and a single column index on category, what will the query below most likely do?

SELECT * FROM products WHERE category = 'Books';

medium

A. Use the index to quickly find rows where category is 'Books'

B. Sort the results by category before returning

C. Return an error because index cannot be used in WHERE clause

D. Scan the entire table without using the index

Solution

1. Step 1: Understand how an index affects a WHERE query

   An index on the category column helps the database quickly locate rows matching the condition category = 'Books'.

2. Step 2: Analyze the query behavior with the index

   The query will use the index to avoid scanning the whole table, speeding up the search.

3. Final Answer:

   Use the index to quickly find rows where category is 'Books' -> Option A

4. Quick Check:

   Index speeds WHERE search = D [OK]

Hint: WHERE on indexed column uses index for speed [OK]

Common Mistakes:

• Assuming index is ignored in WHERE clause
• Thinking index causes errors in queries
• Confusing index use with sorting

4.

Consider this SQL statement to create an index:

CREATE INDEX idx_price ON products price;

What is wrong with this statement?

medium

A. Table name should come after the column name

B. Index name cannot start with 'idx_'

C. Missing parentheses around the column name

D. CREATE INDEX cannot be used on numeric columns

Solution

1. Step 1: Check the syntax for CREATE INDEX

   The column name must be inside parentheses after the table name.

2. Step 2: Identify the syntax error

   The statement is missing parentheses around price. It should be ON products(price).

3. Final Answer:

   Missing parentheses around the column name -> Option C

4. Quick Check:

   Column name needs parentheses = C [OK]

Hint: Column name must be in parentheses after table [OK]

Common Mistakes:

• Omitting parentheses around column
• Misplacing table and column names
• Thinking index names have restrictions

5.

You have a table orders with columns order_id, customer_id, and order_date. You want to speed up queries that filter by customer_id and sort by order_date. Which approach is best?

hard

A. Create a composite index on customer_id and order_date

B. Create a single column index on order_date only

C. Create a single column index on customer_id only

D. Create no index to avoid slowing down inserts

Solution

1. Step 1: Understand query needs

   Queries filter by customer_id and sort by order_date, so both columns matter.

2. Step 2: Choose the best index type

   A composite index on both columns helps filter and sort efficiently, better than single column indexes.

3. Final Answer:

   Create a composite index on customer_id and order_date -> Option A

4. Quick Check:

   Composite index for filter + sort = A [OK]

Hint: Use composite index for multiple column queries [OK]

Common Mistakes:

• Using single column index when composite is better
• Avoiding indexes fearing insert slowdown
• Indexing only sort column ignoring filter