Concurrent reads and inserts into a data structure without latching or waiting by readers

A computer program product for concurrent read and write operations for hierarchical data structure elements, the computer program product comprising a non-transitory_computer readable storage medium having program code embodied therewith, the program code executable by a processor to:

• perform, by the processor, concurrent read and write operations into a hierarchical data structure that comprises a mutable tier including extendible hashing, a hash table, and an immutable tier including a concise hash table (CHT) bitmap;
• acquire, by writers, latches on the hierarchical data structure elements that the writers modify;
• directly access, by the processor, the hierarchical data structure elements by readers without acquiring latches;
• execute, by the processor, a modify operation by a writer for one or more levels of the hierarchical data structure;
• and
• track, by the processor, when removed portions of the hierarchical data structure are no longer referenced by use of a combination of a global state value and a copied local state value.

An apparatus comprising:

• a memory storing instructions;
• and
• at least one processor configured to execute the instructions to:
• perform concurrent read and write operations into a hierarchical data structure that comprises a mutable tier including extendible hashing, a hash table, and an immutable tier including a concise hash table (CHT) bitmap;
• acquire latches, by writers, on the hierarchical data structure elements that the writers modify;
• directly access the hierarchical data structure elements by readers without acquiring latches;
• execute a modify operation by a writer for one or more levels of the hierarchical data structure;
• and
• track when removed portions of the hierarchical data structure are no longer referenced by use of a combination of a global state value and a local copy of the global state value.