A B+Tree index can accelerate a pattern match anchored at the start of a string, such as matching 'abc' followed by anything, but not one that searches for 'abc' anywhere inside the value. Why, and what are the options when you genuinely need infix search?

## Why prefix works A B+Tree orders keys lexicographically: comparison proceeds character by character from the left. Every value beginning with 'abc' therefore sits together in the leaf level, between the first key at or after 'abc' and the first key at or after 'abd'. The engine descends the tree once, lands on the start of that run, and walks the linked leaves until it passes the end. Work is proportional to matches, not to table size. This is the same property that makes composite indexes usable only from their leading column onward. ## Why an unanchored pattern does not If the requested fragment can begin at any offset, matching values are scattered throughout key order: 'xabc', 'abcx', 'zzabcz' sort nowhere near each other. There is no lower bound to seek to and no point at which the engine can stop early, so correctness requires examining every value. The optimizer will either scan the table or, if the index contains everything the query needs and is much smaller than the table, scan the *index* end to end. Seeing an index in the plan therefore does not mean a seek happened - check whether the plan reports a seek with bounds or a full index scan. A middle case is worth knowing: some patterns have a *usable* prefix even though they also contain wildcards later, for example 'abc%def'. The engine can seek on the 'abc' prefix and apply the rest as a filter on the smaller candidate set. Only a wildcard in the very first position removes the bound entirely. ## Options for genuine infix search 1. **Fragment or n-gram indexes.** Index every three-character substring of each value; a search for 'abc' becomes a lookup for the trigrams of the search term, intersecting posting lists. Costs are a much larger index and heavier writes, and short search terms below the fragment length degrade to scans. 2. **Inverted full-text index.** If the real requirement is *word* search rather than arbitrary substrings, tokenize into words with stemming and index the tokens. This is dramatically better than substring matching for natural-language fields, but it will not find a fragment inside a word or inside an identifier. 3. **Reversed-value column.** When only *suffix* search is needed - matching the end of a string - store the reversed string in a maintained column and index it. A suffix search becomes a prefix search on the reversed column. 4. **Reduce the candidate set first.** Very often the infix search is combined with another filter such as tenant, status, or a date range. If that filter is selective and indexed, scanning a few thousand candidate rows for the fragment is perfectly fast, and no exotic index is needed. Always check this before reaching for heavier machinery. 5. **External search service.** When the product needs relevance ranking, typo tolerance, highlighting, or faceting, that is a search engine's job, and the tradeoff becomes an operational and consistency one: a second store to keep in sync, with lag. 6. **Structure the data instead.** Frequently the fragment being searched is really a field embedded in a formatted string - a region code inside an order reference, a domain inside an email. Splitting it into its own column turns an infix search into an equality predicate, which is the cheapest fix of all. ## How to talk about it The strong answer names the ordering property first, then states the tradeoff for each alternative rather than reciting one favourite. Interviewers listen for whether you check the combined-filter option before proposing a new index type, and whether you know that an index appearing in a plan is not proof of a seek.