Du skal opsætte et indeks ved hjælp af sæt eller sorterede sæt, som du skriver til, når du gemmer noget.
Der er et godt indlæg på http://web.archive.org/web/20121013063245/http://playnice.ly/blog/2010/05/05/a-fast-fuzzy-full-text-index-using-redis det er ret tæt på det, jeg selv bruger.