The dictionary will do the job. However, if you perform quick partial matches (for example, searching by user type), you can get better performance by creating multiple keys that point to the same element. For example, the word “Apple” may be located with “Ap,” “App,” “Appl,” and “Apple.”
I used this approach for a similar number of records with very good results. I turned 10K source articles into 50K unique keys. Each of these dictionary entries points to a list containing links to all matches for that term. You can then search more efficiently in this smaller list. Despite the large number of lists it creates, the amount of memory is quite reasonable.
You can also create your own keys if you want to redirect common spelling errors or point out related items. It also fixes most problems with unique keys, as each key points to a list. Each element can be classified by each of the words in its name; this is extremely useful if you have long product names with a few words in it. When classifying your positions, each word in the name can be mapped to one or more keys.
I should also point out that creating and classifying 10K elements should not take long if everything is done correctly (a couple of hundred milliseconds is reasonable). Results can be cached as long as you want to use Application , Cache or static elements.
To summarize, the resulting structure is a Dictionary<string, List<T>> , where the string is short (2-6 characters work well), but a unique key. Each key points to a List<T> (or other collection, if you are so inclined) of elements that match that key. When the search is done, you will find a key that matches the term provided by the user. Depending on the length of your keys, you can truncate the user's search to the maximum key length. After determining the correct child collection, you then look at this collection for a complete or partial match, using any methodology you want.
Finally, you can create a lightweight structure for each item in the list so that you can store additional information about the item. For example, you can create a small product class that stores the name, price, department, and popularity of a product. This can help you refine the results that you show to the user.
All in one, you can perform intelligent, detailed, fuzzy queries in real time.
The above structures should provide functionality roughly equivalent to trie .