1. A method for storing one or more data records in a B link -tree data structure comprising at least two nodes, said nodes comprising at least one index node and at least one leaf node, where each of said data records is associated with a key, the method comprising: storing at least one delete state, where said at least one delete state is associated with one or more of said nodes; performing a node operation on a target node from among said nodes; and updating said at least one delete state if necessitated by said node operation.