GWT "database" (client-side)

XBSDB seems to be good library for client-side db plus indexing solution.

You may take a look at itemscript, it has an in memory "database" which you can query using REST-like URL fragments. I haven't tried it but it looks promising. I have to agree with tdavies that if you like Taffy, writing JSNI wrapper around it is quite trivial task.

Some time ago I created simple in-memory database-like system in GWT, where I leveraged existing Comparator interface for sorting, created simple Filter interface, and simple Query used to store any number of Comparators and Filters. Simple generic ModelManager class which stored model objects in one of collection classes and was running my Queries. It worked pretty well even without any support for indexing.

You won't find any existing solutions for your problem, I spent huge amount of time looking for one. Apart of that, why not give HTML5 a try?

Have you looked at Dojo's Data Store?

I'm not sure how well it fits your specific needs, but it's a pure JavaScript solution. Like much of Dojo, the documentation can be a bit difficult to sort through, but there's an article about using Dojo Grid and the basic MVC pattern on developerWorks that may interest you.

http://www.ibm.com/developerworks/web/library/wa-aj-dojogrid/index.html

Cheers.