Optimistic, version number based concurrency control for index structures with atomic, non-versioned pointer updates

摘要

Methods, systems and computer program products for traversing a level in a search path in a tree data structure by recording a version number of a node on the search path, finding a child pointer in the node on the search path, recording a version number of a child node corresponding to the child pointer, reading a version number of the node on the search path, comparing the recorded version number of the node to the read version number of the node, reading at least one child pointer in the node and comparing the read child pointer to an address of the child node.

主权项

1. A computer implemented method for traversing a level in a search path in a tree structure, comprising:
recording a version number of a node on the search path; finding a child pointer in the node on the search path, wherein the node includes a plurality of child pointers each forming a path to a corresponding child node; reading a version number of the node on the search path; comparing the recorded version number of the node to the read version number of the node; reading the child pointer in the node and comparing the read child pointer to an address of the corresponding child node; performing an update to change a selected child pointer of the node without changing the version number of the node to invalidate the path formed by the selected child pointer being updated and enable paths formed by other child pointers of the node to remain valid, wherein the update is performed in response to the corresponding child node of the selected child pointer having a new location in memory and the updated child pointer forms a path to the corresponding child node in the new location; proceeding to another level in the search path from the updated node along the valid path formed by one of the other child pointers in response to determining that the version number of the updated node remains unchanged and the search path including that valid path based on determining that the address of the corresponding child node of the one other child pointer remains unchanged; and restarting the traversal of the search path in response to the search path including the invalidated path based on the read child pointer not being equal to the address of the corresponding child node.