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.