Where do you exactly use data structures?
This is a broad question but will attempt to answer.

From my understanding of your question, you have billions of strings which you want to use for autocomplete.

The way most typical autocomplete examples work is you load the entire set of strings into memory and build a trie. That works well for small datasets like the list of countries, or a small list of tags.

Searching for how google implements its autocomplete doesn't return any results, but that would be sort of what you're asking I'd think.

What I imagine is slow in your current implementation is, you have billions of rows in your database, with a column containing the string of interest. Then you are just doing a LIKE search to match substrings. So it has to scan every string in the billions of records, which is very slow.

The (typical relational) database won't offer you much support here.

One solution to this problem is to use a "full text search database" such as Lucene. The problem this solves is indexing. Another related index that might help is an inverted index. An inverted index might use a B+tree for indexing the terms (words perhaps) in documents (or strings in your case). But this just means it will match individual terms/words, not complete sentences or exact substring matches like the LIKE query will do.

So you have to decide how you want your autocomplete to work. If they can search for exact strings in the text, then the best solution is probably to create a gigantic trie for all the strings. If the trie doesn't fit into main memory, as probably is your case, then you could potentially try creating a string b-tree data structure instead of a trie. This is better as an on-disk data structure. If instead they can search for tokens/terms/words like a keyword search, then you can use an inverted index B-tree, such as with Lucene. Either way you will need another data structure on top of the relational database, and probably one that efficiently works with a file system.