In one embodiment, two-phase mutation of an ordered tree data structure is performed, wherein a lock can be acquired on a first node in an ordered tree data structure, and an identifier for the first node can be added to a lock path data structure. A second node can also be locked, and an identifier for the second node can be added to the lock path data structure. Subsequently, a set of operations to perform on the ordered tree responsive to a modification of the second node can be determined for each node affected by the modification, and the operation for each node can be stored in the lock path data structure. Once the operations for the nodes have been determined, the operations listed in the lock path can be performed.