Patent EP0453193A2 successfully refreshed from Google Patents.
EP0453193A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
A method of balancing tree structures in parallel computer systems
Assignee: International Business Machines Corp
•
Filing: 1991-04-12
•
Granted: —
•
Expires: 2011-04-12
Abstract
Abstract A distributed network contains a plurality of interconnected nodes 10, each node including a processor 16 and data storage apparatus 26. 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 31 for the top level of the tree, comprising two lists, "NEW ROOT" and "OLD ROOT", each comprised of an ordered array of boundaries assigned to the nodes. The tree data structure is balanced by determining when a first node contains an excess of key-index data identifiers, and moving the excess of key-index data identifiers to a second node. The first node/second node boundary value in "NEW ROOT" of the ROOT data structure is updated to record the movement of the data file identifiers, so that 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.
Inventors
- 👤 Alexander H. Frey, Jr.
- 👤 Richard C. Mosteller
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-02 23:57
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/14; G06F11/1402; G06F16/00; G06F16/10; G06F16/13
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
200 words
In a distributed computing network containing a plurality of interconnected nodes (10), each node having a processor (16) and non-volatile data storage means (26), a method for balancing between said nodes a tree structure containing key-index data identifiers, wherein a top level of the tree structure forms a ROOT (31), said method comprising the steps of: a. providing (50) the ROOT in a data file in non-volatile storage, wherein said ROOT comprises first and second lists, each of which contains key boundary values describing the distribution amongst said nodes of the key-index data identifiers; b. providing (50) in each of the nodes across which the key-index data identifiers are distributed, files containing copies of said ROOT; c. determining (52) when a first node contains an excess of the key-index data identifiers in comparison to a second node; d. moving (60) the excess key-index data identifiers to non-volatile storage in said second node; and e. updating (72) the files containing copies of said ROOT in said first and second nodes by providing information concerning the movement of the key index data identifiers in sufficient detail to thereby enable system recovery in the event of a malfunction of one of said nodes.
Claim 2
Dependent Claim
42 words
The method of Claim 1, further comprising, between steps c and d, the step of: establishing (56) a new boundary value for the first node in the second list of said ROOT to determine the key-index data identifiers to be moved therefrom.
Claim 3
Dependent Claim
59 words
The method of Claim 2 wherein step (e) includes the steps of: in said first node, establishing a pointer to indicate a next key-index data identifier to be moved; and establishing a pointer in said second node, indicating the key-index data identifier boundary after each movement of a key-index data identifier from said first node into said second node.
Claim 4
Dependent Claim
71 words
The method of Claim 3, further comprising the steps of: deleting (66) a key-index data identifier from the first node when said first node receives from the second node an acknowledgement of receipt of said key-index data identifier thereby; and moving (68) the pointer in the first node to a new next key-index data identifier to be moved, repeating steps d and e until said pointer reaches said new boundary value.
Claim 5
Independent Claim
50 words
The method of any preceding claim, wherein said moving step (d) includes the step of: retaining in said first node a copy of each key-index data identifier moved to said second node until acknowledgement of receipt and storage of the moved key-index data identifier in said second node is received.
Claim 6
Dependent Claim
44 words
The method of Claim 5, further comprising the step of: after all the excess key-index data identifiers have been moved to the second node, writing (72) the updated second list in place of said first list to the ROOT data file in non-volatile storage.
Claim 7
Dependent Claim
23 words
The method of Claim 6, further comprising the step of: propagating (74) to all nodes an updated copy of the ROOT data structure.
Claim 8
Independent Claim
65 words
The method of any preceding claim, further comprising the step of: said first node responding to any command from a third node to move one or more key-index data identifiers, by determining (110) if the portion of the data structure referred to by the command has been moved to said second node and, if so, redirecting said key-index data identifier command to the second node.
Claim 9
Independent Claim
62 words
The method of any preceding claim, further comprising the step of: f. in the event of a malfunction in a node, recopying said ROOT data structure from non-volatile storage, and determining if a rebalancing was in process between nodes by comparing (100) in both said first and second nodes said first and second lists to see whether or not they are identical.
Claim 10
Dependent Claim
43 words
The method as defined in Claim 9, further comprising the step of: g. if said first and second lists are not identical, continuing with steps d and e, starting with a. non-identical key-index data identifier in said second list found in step f.
Claim 11
Dependent Claim
39 words
The method as defined in Claim 10 as dependent on claim 2, further comprising the step of: i. terminating said step g after said pointer reaches the key-index data identifier boundary value established in the step of claim 2.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.