Method for balancing of distributed tree file structures in parallel computing systems to enable recovery after a failure

摘要

A distributed network is described which contains a plurality of interconnected nodes each node including a processor and data storage apparatus. A plurality of key-index data identifiers are distributed among the nodes, with each node including a tree data structure in non- volatile storage defining locations of the key-index data identifiers. The tree data structure includes a ROOT data structure comprising two lists, "NEW ROOT" and "OLD ROOT", each comprised of an ordered array of boundaries assigned nodes for the top level of the tree. A method is described for balancing the tree data structure which comprises the steps of:PPa. a providing in each of the nodes across which the key-index data identifiers are distributed, at least copies of the two lists, "NEW ROOT" and "OLD ROOT", of the ROOT data structure;P Pb. determining when a first node contains an excess of key-index data identifiers;PPc. moving the excess of key-index data identifiers to a second node;PPd. updating the first node/second node boundary value in "NEW ROOT" of the ROOT data structure and the copies of "NEW ROOT" in the first and second nodes to note the movement of the data file identifiers, whereby in the event of a malfunction of one of the nodes, a record exists in both of the nodes of both an updated and non-updated ROOT data structure to enable data recovery.