Tree data storage structures are implemented on respective computers in a distributed environment, such as on a network, so that information associated with nodes of one computer's tree data storage structure may be read or written to by another computer in the network. To promote efficiency, a cache may be employed on the computers in the network such that each computer caches information associated with nodes of tree data storage structures located on the computers in the network. A lock service may implement a caching protocol to provide efficient concurrency of caching operations while ensuring that current information associated with the nodes is available to all computers in the network.