The hash table data structure can be easily spread across multiple machines with a simple algorithm to distribute the keys:machine_to_query = item_key % machine_countWhen you want to read and write key value pairs, you use the key to work out which machine stores the data, then you talk to that machine.  If you want a count of the total number of items, you'd need to request the count from each server and add them up.What algorithms exist for efficiently managing data structures where the data is partitioned across multiple machines?  Distributed algorithms, not parallel algorithms.How might something like a sorted array work in a distributed fashion?  Efficiently.
Algorithms for data structures in distributed system
algorithms;data structures;big data
Here's a link to a similar question on SO:https://stackoverflow.com/questions/3927537/how-do-you-implement-sorting-and-paging-on-distributed-dataAlso the last article from T-79.4001 Seminar on Theoretical Computer Science looks useful:http://www.tcs.hut.fi/Studies/T-79.4001/2007SPR/Some books on the subject:Distributed Algorithms - KaufmannDesign and Analysis of Distributed Algorithms - Wiley