CONCURRENT READS AND INSERTS INTO A DATA STRUCTURE WITHOUT LATCHING OR WAITING BY READERS

A method includes performing, by a data structure processor, concurrent read and write operations into a hierarchical data structure. Writers acquire latches on the hierarchical data structure elements that the latches modify. The hierarchical data structure elements are directly accessed by readers without acquiring latches. A modify operation is executed by a writer for one or more levels of the hierarchical data structure. When removed portions of the hierarchical data structure are no longer referenced, tracking is performed by use of a combination of a global state value and a copied local state value. The global state value transitions through a non-repeating sequence of values. No longer referenced portions of the hierarchical data structure are tagged with the current global state value.