Du måste ställa in ett index med uppsättningar eller sorterade uppsättningar som du skriver till när du sparar något.
Det finns en bra beskrivning på http://web.archive.org/web/20121013063245/http://playnice.ly/blog/2010/05/05/a-fast-fuzzy-full-text-index-using-redis det är ganska nära det jag själv använder.