I know it's taboo to post about Facebook here… but this is an interesting description of how they implemented their autocomplete (typeahead) algorithm – an extended Unicorn instance. I'd guess Google's approach isn't too different, perhaps with other libraries.
Facebook Engineerings Notizen
Facebook helps you connect and share with the people in your life.
It's an interesting story for an interesting system.
It's fairly impressive in practice, too.