Patent ID: 7730101

Claim:
A computer implemented method of implementing tree data storage structure in a distributed computing environment, comprising: implementing in memory on a first computer a first tree data storage structure comprising a first node in memory and at least one other node in memory associated with the first tree data storage structure, said first computer comprising program code associated with the first tree data storage structure and first tree node information for the first tree data storage structure; implementing in memory on a second computer a second tree data storage structure comprising a second node in memory and at least one other node in memory associated with the second tree data storage structure, said second computer comprising program code associated with the second tree data storage structure and second tree node information for the second tree data storage structure, said second tree node information different than the first tree node information, the second computer being communicatively coupled to the first computer; at the second computer, receiving a request to place a lock on the first node in memory; at the second computer, obtaining information associated with the first node in memory from the first tree data storage structure; at the second computer, determining using the information associated with the first node in memory whether an existing lock on the first node in memory has previously been acquired; and at the second computer, upon determining an existing lock on the first node in memory has previously been acquired: at the second computer, when the existing lock is shared and the requested lock is for a shared lock, placing a shared lock on the first node in memory and reading information from the first node; at the second computer, when the existing lock is exclusive and the requested lock is for a shared lock, waiting for information to be written to the first node in memory by at least one of the first computer and a third computer and providing access to the first node in memory as existed prior to the exclusive lock while waiting for any ongoing writes to the first node in memory to be completed, and upon any ongoing writes to the first node in memory being completed, changing the existing exclusive lock to a shared lock, providing a shared lock to a current version of the node in memory, and reading the information from the node in memory; and at the second computer, when the existing lock is exclusive and the requested lock is for an exclusive lock, waiting for any ongoing writes to the first node in memory to be complete, removing the existing lock, and placing an exclusive lock on the first node, wherein removing the exclusive lock comprises transmitting a revocation request to the holder of the exclusive lock, wherein at least one of the first and second data tree storage structures is a B-link tree.