Database Index Optimization Interview: B+ Tree and SQL Tuning

In database interviews, index optimization is a must-know core topic. Whether for campus or experienced hiring, interviewers deeply test candidates' understanding of B+ tree principles, index design capabilities, and SQL tuning experience.

Why Are Indexes So Important?

Imagine a dictionary without a table of contents or index. To find the word "database," you'd have to flip through every page—this is the efficiency of a full table scan. With an index, like a dictionary's pinyin index, you can quickly locate your target.

In databases, indexes serve the same purpose:

• Query acceleration: Optimize O(n) full table scans to O(log n) index lookups
• Sorting optimization: Use index ordering to avoid filesort
• Unique constraints: Ensure data integrity through unique indexes

B+ Tree: The Foundation of Database Indexes

Structural Features of B+ Trees

B+ Trees are the underlying data structure for most relational database indexes.

Core features of B+ Trees:

1. All data stored in leaf nodes: Non-leaf nodes only store keys and pointers
2. Leaf nodes form ordered linked lists: Facilitates range queries and sorting
3. Node size aligned with disk pages: Usually 16KB, reducing disk I/O
4. Low height: Typically 3-4 levels can store tens of millions of records

Why B+ Trees Over B Trees?

This is a classic interview question:

Better for disk storage:

• B+ tree non-leaf nodes don't store data, one page can store more keys, tree is shorter
• B tree stores data in every node, fewer keys per page, taller tree, more I/O

More efficient range queries:

• B+ tree leaf nodes form a linked list, range queries just traverse the list
• B tree requires in-order traversal of the entire tree, less efficient

Clustered vs Non-Clustered Indexes

Clustered Index

A clustered index stores data rows and index together. A table can only have one clustered index.

MySQL InnoDB clustered index features:

• Primary key automatically becomes the clustered index
• If no primary key, first non-null unique index is used
• Leaf nodes store complete row data

Non-Clustered Index (Secondary Index)

Non-clustered index leaf nodes store index key values + primary key values, requiring a "table lookup" for complete data.

Cost of table lookup: Each lookup is a random I/O. When querying large amounts of data, lookup overhead may exceed full table scan.

Covering Index: Avoid Table Lookups

When all queried fields are in the index, no table lookup is needed.

-- Create composite index
CREATE INDEX idx_email_name ON users(email, name);

-- Covering index query
SELECT email, name FROM users WHERE email = '[email protected]';
-- No table lookup needed

Index Optimization Strategies

Leftmost Prefix Principle

Composite indexes follow the leftmost prefix principle—queries must match from the leftmost column.

-- Composite index (a, b, c)
CREATE INDEX idx_abc ON table_name(a, b, c);

-- ✅ Can use index
WHERE a = 1
WHERE a = 1 AND b = 2
WHERE a = 1 AND b = 2 AND c = 3

-- ❌ Cannot use index
WHERE b = 2
WHERE c = 3

Avoid Index Invalidation

1. Using functions or operations on indexed columns

-- ❌ Index invalid
WHERE YEAR(create_time) = 2024

-- ✅ Index valid
WHERE create_time >= '2024-01-01' AND create_time < '2025-01-01'

2. Implicit type conversion

-- Assuming id is INT
-- ❌ Index invalid
WHERE id = '100'

-- ✅ Index valid
WHERE id = 100

3. LIKE starting with wildcard

-- ❌ Index invalid
WHERE name LIKE '%John'

-- ✅ Index valid
WHERE name LIKE 'John%'

High-Frequency Interview Questions

Q1: When should you create an index?

• Columns frequently used in WHERE conditions
• Columns used in JOINs
• Columns in ORDER BY or GROUP BY
• Columns with high cardinality (high uniqueness)

Q2: When should you NOT create an index?

• Small tables
• Frequently updated columns
• Low cardinality columns (like gender)
• Rarely queried columns

Q3: How to analyze slow queries?

-- Enable slow query log
SET GLOBAL slow_query_log = ON;
SET GLOBAL long_query_time = 1;

-- Use EXPLAIN to analyze
EXPLAIN SELECT * FROM users WHERE email = '[email protected]';

Summary

Database index optimization is a core backend interview topic:

• B+ Tree is the underlying index structure, understand its features
• Clustered index stores complete data, non-clustered index requires table lookup
• Covering index can avoid table lookups, improving performance
• Leftmost prefix principle is the core rule for composite indexes
• Avoid common index invalidation traps

If you're preparing for backend interviews, we recommend our Backend Engineer Interview Playbook and SQL Interview Complete Guide.

Prepare for Database Interviews with Interview AiBox!

Interview AiBox provides AI mock interviews, real-time feedback, and more. Whether it's the System Design Interview Preparation Guide or the 30-Day Coding Interview Prep, we have complete preparation plans.

Experience the Interview AiBox Features Guide now! 🚀