Client-side caching/paging of *Large Hierarchical Data* (Large Tree Data)

Question

Background: I am developing a client-server based WPF application which displays large result sets (millions of rows) from related ad-hoc SQL Server queries in a custom UI Tree/Grid View.

The ad-hoc SQL queries, which are generated on the client through the user interface, are essentially nested 'master-detail' (related) queries which end up providing hierarchical (related) result data such as the following (pseudo results):

Item
Index  Nodes
-----  -----
1   -  Group Level 1 + Aggregate Summary Data       (e.g. Country)
2       -  Group Level 2 + Aggregate Summary Data   (e.g. City)
3             Item Detail                           (e.g. Sales Data)  
4             Item Detail                           (e.g. Sales Data)  
5             Item Detail                           (e.g. Sales Data)  
6             Item Detail                           (e.g. Sales Data)  
7   -  Group Level 1 + Aggregate Summary Data       (e.g. Country)
8       +  Group Level 2 + Aggregate Summary Data   (e.g. City)
9   +  Group Level 1 + Aggregate Summary Data       (e.g. Country)

+ = Can be expanded
- = Is Expanded

Requirements/Constraints:

1. All groupings are initially collapsed - i.e. you see only the root items in the UI initially.
2. The SQL queries are related in that the results of the queries closer to the root provide the keys/filter criteria for the query the next level up as in a typical master-detail relationship (Group Level 1 Query provides criteria for Group Leve 2 query and so on).
3. Users can scroll up or down though the entire hierarchy (millions of items) at will. While the Item Detail (non-group) data may not be available immediately upon scrolling, the hierarchy/tree structure should at least be available for the UI to organize itself.
4. Only the tree structure need be cached client-side (together with key/filter criteria that will be used to query for the full data from SQL Server).
5. Item access is performance critical so approaching O(n) access would be ideal.

Essentially, due to memory and performance constraints the tree structure needs to be cached client-side (and possibly paged in/out of memory as the structure itself could be large) where it can grow as users scroll and expand nodes.

Questions:

1. What structure would be best suited for holding the tree structure locally?
2. What is the best way to cache that tree structure client-side bearing in mind that it will change as nodes are expanded/collapsed by the user as they scroll through the hierarchy?

I'm not looking for a definitive answer (unless someone has one) but rather some less than general pointers for a solid implementation strategy in c#.

Thanks in advance for any help!