In this lesson, you will learn why traditional B-tree indexes struggle with complex text searches and how inverted indexes solve this by mapping words to their locations.
The Limitation of B-Trees
So far, we have looked extensively at B-tree indexes. These are excellent for range queries (e.g., WHERE price BETWEEN 10 AND 50) or finding exact matches. However, B-trees store data based on the entire value of a column. If you have a column named review_text containing the sentence "The database performance is excellent," a B-tree index stores that entire string as a single entry.
If you search for WHERE review_text LIKE '%performance%', the B-tree cannot use its internal structure to find the word "performance." It is forced to perform a full table scan because the index is only ordered by the start of the string, not by the individual words contained within it.
The Inverted Index Solution
To search through massive amounts of text efficiently, we use an inverted index. Imagine the index at the back of a textbook: it lists keywords alphabetically and provides a list of page numbers where those words appear.
A database inverted index does the same:
- Tokenization: It breaks the text into individual words (tokens).
- Mapping: It creates a table where each token points to the primary keys (or row IDs) of the rows containing that word.
-- Conceptual View of an Inverted Index
| Token | Row_ID |
|-------------|--------|
| database | 1, 5 |
| performance | 1, 8 |
| excellent | 1 |
When you search for "performance," the database doesn't scan the whole table; it jumps straight to the "performance" entry in the inverted index, sees that it exists in Row_ID 1 and 8, and fetches only those specific records.
Why not B-trees?
If you tried to force a B-tree to do this, you would need an index for every possible word position, which would consume massive amounts of disk space and make updates incredibly slow. Inverted indexes are purpose-built for the "needle in a haystack" problem, allowing for lightning-fast keyword lookups that B-trees simply weren't designed to handle.
Key Takeaway: While B-tree indexes are optimized for ordering and range lookups on complete values, inverted indexes are optimized for locating individual words within large blocks of unstructured text.