I'm working on a Web Application using node.js in which I'm building a partial copy of the database on the client-side to decrease the load on my server. Right now, I have a function like this (expressed as python-style pseudocode, but implemented in JavaScript):

get(table_name,primary_key):
    if primary_key in cache[table_name]:
        return cache[table_name][primary_key]
    else:
        x = get_data_from_server(table_name,primary_key) # socket.io
        return cache[table_name][primary_key] = x

While this scheme works perfectly well for caching individual rows, I'd like to extend it to support the creation of paginated tables ordered according to the primary_key, and loading additional data using the above function for only the current and possibly the adjacent pages. Now, I don't want to keep the list of primary keys on the server to be retrieved every time I need to change the page (which, for reasons beyond the scope here, will be very frequent), and keeping it on the client side, subject to real-time create/delete events from the server, doesn't seem that good an idea, even after compression (using ranges, instead of individual values).

What is the best way to calculate which items are to be displayed on a random page, minimizing the space requirements & the need for communication with the server?