A query for a single-prefix term (i.e. "yank") is technically O(log(N)+M), where N is the # of items in the sorted set, and M is the # of items returned. But since in practice we often want a small # of items, we can keep both N and M small.
One tradeoff we made is that this approach doesn't support incremental updates easily, you can always add new items, but it would take a good bit of work to remove items that have expired, or update the scores of items that change.
As for memory usage, we only store each item once (in a redis hash table), and use the unique ids as entries in the sorted sets. Which sort of approaches a trie, since instead of:
ya -> yan -> yank -> yanke -> yankee -> yankees -> [data about yankees]
we have:
ya -> 101
yan -> 101
...
101 -> [data about yankees]