Method for balancing of distributed tree file structures in parallel computing systems to enable recovery after a failure
US5230047A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Apr 16, 1990 |
| Grant date | Jul 20, 1993 |
| Priority date | — |
| Expiry date | Apr 16, 2010 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/13
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
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: PA0 a. 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; PA0 b. determining when a first node contains an excess of key-index data identifiers; PA0 c. moving the excess of key-index data identifiers to a second node; PA0 d. 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, whereb…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.