iTunes Search Algorithm/Data Structure?

[Bill Mill]

Hello all,

What data structure would you use to implement something analogous to
the iTunes search? I imagine that it must be a tree of some sort, but I
can't figure out an easy structure for it.

Requirements (in case you haven't used it):

You are given 4 rows in a list view:
[["alpha, "beta"], ["delta", "gamma"], ["foo", "bar"], ["etc", "etc"]]

and a search text box.

Typing "a" in the list box leaves rows 0, 1 and 2 in the list box,
because some element in each of those rows has an "a" in it. Typing
"am" leaves only row 1, since "gamma" has the substring "am" in it.

The key here is that this works instantaneously as you type, even with
very large lists with many elements per row. I'd like the employee list
in my current application to be similarly filtered, but I don't quite
see how.

Thoughts?

-Bill Mill
bill.mill at gmail.com
billmill.org