Full-text indexes in MySQL - Time & Space Complexity

Time Complexity: Full-text indexes

O(k)

Understanding Time Complexity

When searching text in a database, speed matters a lot. Full-text indexes help find words quickly in large text columns.

We want to understand how the search time changes as the text data grows.

Scenario Under Consideration

Analyze the time complexity of the following full-text search query.

SELECT * FROM articles
WHERE MATCH(content) AGAINST('database');
    

This query searches the word 'database' in the content column using a full-text index.

Identify Repeating Operations

Look at what repeats when the query runs.

• Primary operation: Searching the full-text index for matching words.
• How many times: The search scans index entries related to the search word, not the whole table rows.

How Execution Grows With Input

As the number of rows and text size grows, the full-text index helps keep search fast.

Input Size (n)	Approx. Operations
10	Few index lookups
100	More index lookups but still quick
1000	More index entries checked but not all rows scanned

Pattern observation: The search time grows slowly because it uses the index, not scanning all text.

Final Time Complexity

Time Complexity: O(k)

This means the search time grows slowly as the data grows, thanks to the index structure.

Common Mistake

[X] Wrong: "Full-text search scans every row every time, so it's slow for big data."

[OK] Correct: Full-text indexes let the database jump directly to matching words, avoiding scanning all rows.

Interview Connect

Understanding how full-text indexes speed up searches shows you know how databases handle big text data efficiently. This skill helps you explain and design fast search features.

Self-Check

"What if we searched multiple words instead of one? How would the time complexity change?"