Where do you exactly use data structures?

Question

I know what data structures is, How it works & importance of it. I just have some doubts on where do we actually use it.

When database can do filtering, fetching, sorting efficiently, Why we need to use data structures in db data?

I was working on a project which uses Cassandra database. In that I'd to filter data based on two fields. The two fields are indexed. But I can't filter it as it will force me to use Allow filtering but It's not a recommended one.

In this case I thought to fetch rows filtered by one indexed column & rest by our program (Java/Python etc) so we need to use better data structure here. Is this a correct approach? If not what's the solution for these kind of problems?

Let's assume I've billions of list of string data in a db table, I want to use it for autocomplete for that it's better to use tries data structure, How can I do this? fetch all data into memory and process?

If my approach is wrong, Are data structures mainly used for in memory data?

Answer 1

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.