Implementing Search Autocomplete with Spring Boot and a Trie

Search autocomplete helps users find a relevant term before they finish typing. In a Java application, it can make product searches, address fields, customer lookups, and API-driven directories feel considerably faster.

A Trie, also called a prefix tree, is well suited to this task because it stores characters by shared prefixes. A search for par can quickly locate values such as Parramatta, Parliament House, and Parkes without scanning every stored phrase.

Spring Boot provides the application layer around this data structure. It can expose a REST endpoint, validate query parameters, connect to a database for source data, and apply caching when the autocomplete service receives heavy traffic.

For an Australian application, useful examples might include suburbs such as Richmond and Parramatta, locations around Brisbane, or product searches where users type “arvo” and expect locally relevant results. Good autocomplete should also remain responsive for users on mobile networks in regional areas.

Designing The Trie For Prefix Searches

Each Trie node contains a collection of child nodes and may store completed suggestions. A boolean such as wordEnd identifies whether a complete term finishes at that node. For ranking, the node can hold a list of suggestions, frequencies, or references to records.

The basic operation converts input to a consistent form, walks through one character at a time, and returns an empty result when a required child is missing. Once the prefix node is found, a depth-first traversal collects descendants until the requested result limit is reached.

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    Set<String> suggestions = new LinkedHashSet<>();
}

Insertion and prefix lookup are approximately O(L), where L is the prefix length, excluding the cost of collecting returned suggestions. This makes the approach attractive when the dataset contains many repeated prefixes.

Loading And Normalising Suggestion Data

A service can populate the Trie during application startup from a database, CSV file, or external API. For a retail site, records may come from product names and categories; for a property platform, they might include Australian suburbs, postcodes, and street names.

Normalisation should trim whitespace, convert text to lower case using a stable locale, and decide how punctuation is treated. Keep the original display value separately so a user sees McDonald's or New South Wales rather than a transformed internal key.

Useful data preparation rules include:

• Ignore blank values and duplicate entries.
• Store a normalised key beside the display label.
• Apply a maximum suggestion length where appropriate.
• Assign popularity or business relevance scores.
• Refresh data after catalogue or location changes.

If the source contains millions of terms, loading everything into memory may be wasteful. A database-backed prefix index, Redis structure, or dedicated search engine can complement the Trie while the in-memory tree handles a smaller, high-demand vocabulary.

Exposing The Spring Boot Endpoint

A REST controller can provide an endpoint such as GET /api/search/suggestions?q=par&limit=8. The controller should reject missing or excessively long queries, cap the result count, and return a predictable JSON response.

@GetMapping("/suggestions")
List<String> suggest(
        @RequestParam String q,
        @RequestParam(defaultValue = "8") int limit) {
    return autocompleteService.find(q, Math.min(limit, 20));
}

The service should own the Trie rather than placing search logic in the controller. Marking the structure as an application-scoped component gives all requests access to the same loaded index. If updates can happen while requests are running, use a read-write lock or replace the entire Trie after rebuilding it.

For a Sydney or Melbourne customer base, a 100–200 millisecond response target is a sensible operational goal. Keep payloads small, use HTTP compression where useful, and avoid returning unnecessary product descriptions. A short response also suits users moving between Wi-Fi and mobile data.

Ranking Results And Handling Real Input

Alphabetical order is easy to implement but often produces a poor user experience. A suggestion such as Parramatta may deserve priority over a less common phrase because it is searched more frequently. Store a score with each terminal suggestion and use a bounded priority queue during traversal.

The endpoint should handle case differences, repeated spaces, accents, and harmless punctuation. Prefix matching can be extended with token-based matching when users search for terms such as new s and expect New South Wales. Fuzzy matching is useful for spelling mistakes, though it adds processing cost and should be introduced deliberately.

Practical ranking signals include:

• Search frequency over a recent time window.
• Product availability or current inventory.
• Location relevance for the selected Australian state.
• Exact phrase matches before broader matches.
• A business rule that promotes active services.

For Australian addresses, be careful with abbreviations and local conventions. “St” may mean street, while “Saint” may appear in a place name. A location-aware index should preserve authoritative forms from Australia Post or another trusted source instead of guessing from user input.

Testing, Security, And Production Operation

Unit tests should verify insertion, case handling, missing prefixes, duplicate terms, result limits, and ranking order. Controller tests can use MockMvc to confirm that invalid requests return suitable HTTP status codes and that the JSON contract remains stable.

Load tests should model bursts of short queries rather than only long searches. Monitor heap usage, endpoint latency, cache hit rates, and the time required to rebuild the index. Rate limiting can protect the service from automated clients repeatedly requesting every possible prefix.

Autocomplete input can contain sensitive terms, so avoid logging complete queries by default. Apply authentication when suggestions reveal private customer or internal catalogue data, and validate all imported values before adding them to the Trie. When publishing implementation material or adapting examples from a website, review the relevant copyright guidance before reusing code or content.

A clean Spring Boot design keeps the Trie focused on fast prefix retrieval, while separate components handle persistence, ranking, validation, and transport. That separation makes the feature easier to tune as an application grows from a small local directory to a nationwide Australian service.