Performing a deletion of a node in a tree data storage structure

A computer-readable storage medium having program code stored thereon and executed by a computer system, causes the computer system to:

• provide an operational layer between a tree data storage structure and a persistent storage,
• wherein the tree data storage structure communicates with the persistent storage via the operational layer, wherein the operational layer is configured to:
• generate an identifier and allocate the identifier to a node in the tree data storage structure;
• associate the identifier with the node of the tree data storage structure, the tree data storage structure being configured to satisfy concurrent operations;
• determine location information that indicates a location in the persistent storage, wherein the location information comprises identification of a disk and an offset on the disk;
• associate the identifier with the location information, wherein node information associated with the node is stored at the location in the persistent storage;
• and
• when a node is deleted from the tree data storage structure, disassociate the identifier from the location information, the program code further causing the computer system to:
• determine that the identifier is not associated with the location information;
• and send an exception in response to the request for the operation.

A computer system, comprising:

• a processing unit;
• a memory that stores a tree data storage structure configured to satisfy concurrent operations;
• a persistent storage for storing information associated with each of a plurality of nodes of the tree data storage structure;
• and
• a means for establishing an operational layer for enabling the tree data storage structure to communicate with the persistent storage, the operational layer further comprising:
• means executing on the processor for generating and associating an identifier with a node of the tree data storage structure,
• means executing on the processor for determining location information that indicates a location in the persistent storage, wherein said location information comprises identification of a disk and an offset on the disk;
• means executing on the processor for associating the identifier with the location information, wherein node information associated with the node is stored at the location in the persistent storage;
• and
• means for disassociating the identifier from the storage location when a node is deleted from the tree data storage structure, the persistent storage further comprising:
• means executing on the processor for determining that the identifier is not associated with the location information;
• and
• means executing on the processor for sending an exception in response to the request for the operation.

A computer implemented method for deleting a node from a tree data storage structure, the method comprising:

• on a computing device, establishing an operational layer between a tree data storage structure and a persistent storage, wherein the tree data storage structure communicates with the persistent storage via the operational layer, the operational layer being configured to:
• generate an identifier and allocate the identifier to a node in the tree data storage structure;
• associate the identifier with the node of the tree data storage structure, the tree data storage structure being configured to satisfy concurrent operations;
• determine location information that indicates a location in the persistent storage, wherein the location information comprises identification of a disk and an offset on the disk;
• associate the identifier with the location information, wherein node information associated with the node is stored at the location in the persistent storage;
• and
• when a node is deleted from the tree data storage structure, disassociate the identifier from the location information,
• wherein being configured to satisfy concurrent operations includes being configured to either:
• performing an insertion operation concurrently with a deletion operation, wherein the deletion operation includes deleting the node and removing any mapping to the node;
• or
• performing an insertion operation concurrently with a lookup operation, wherein the lookup operation includes reading the identifier associated with the node, reading the mapping of the identifier and determining whether the identifier is allocated to a location in persistent storage, and wherein the lookup operation further includes:
• raising an exception and sending the exception back in lieu of satisfying the lookup request, when no persistent storage location is allocated to the identifier, or
• reading the data at the persistent storage location, when a persistent storage location is allocated to the identifier.