Storage of tree data structures
AssigneeWestern Digital Technologies, Inc.
InventorsShay Benisty, Ishai Ilani, Tomer Geron
Life of this patent
Estimating the term…
Abstract
Disclosed herein is a computer-implemented method for storing binary tree data in memory. The binary tree data comprises parent node data, first child node data and second child node data. The computer-implemented method comprises determining a first child node memory address, the first child node memory address being less than a parent node memory address; determining a second child node memory address, the second child node memory address being greater than the parent node memory address; storing the parent node data at the parent node memory address; storing the first child node data at the first child node memory address; and storing the second child node data at the second child node memory address.
Claims20
A computer-implemented method for storing binary tree data in a random access memory comprised of memory cells associated with corresponding memory addresses, wherein the binary tree data comprises parent node data, first child node data and second child node data, the computer-implemented method comprising:
- determining a first child node memory address using a processor to execute a memory assignment function based on a first node position vector for a first child node, the first child node memory address being less than a parent node memory address;
- determining a second child node memory address using the processor to execute the memory assignment function based on a second node position vector for a second child node, the second child node memory address being greater than the parent node memory address;
- storing the parent node data in at least one memory cell at the parent node memory address;
- storing the first child node data in at least one memory cell at the first child node memory address;
- and
- storing the second child node data in at least one memory cell at the second child node memory address, wherein the first node position vector and the second node position vector are each represented by [i1, i2, . . . , ik−1, ik], where:
- i1 is a layer position of a direct relative of that node in a first layer of the binary tree;
- i2 is a layer position of a direct relative of that node in a second layer of the binary tree;
- ik−1 is a layer position of a parent node;
- and
- ik is a layer position of that node.
An apparatus for storing binary tree data, the apparatus comprising:
- a random access memory comprised of memory cells associated with corresponding memory addresses, wherein the binary tree data comprises parent node data, first child node data and second child node data;
- and
- a processor configured to:
- determine, using a memory assignment function and based on a first node position vector for a first child node, a first child node memory address, the first child node memory address being less than a parent node memory address;
- determine, using the memory assignment function and based on a second node position vector for a second child node, a second child node memory address, the second child node memory address being greater than the parent node memory address;
- store the parent node data in at least one memory cell at the parent node memory address;
- store the first child node data in at least one memory cell at the first child node memory address;
- and
- store the second child node data in at least one memory cell at the second child node memory address, wherein the first node position vector and the second node position vector are each represented by [i1, i2, . . . , ik−1, ik], where:
- i1 is a layer position of a direct relative of that node in a first layer of the binary tree;
- i2 is a layer position of a direct relative of that node in a second layer of the binary tree;
- ik−1 is a layer position of a parent node;
- and
- ik is a layer position of that node.
An apparatus for storing binary tree data, the apparatus comprising:
- a random access memory comprised of memory cells associated with corresponding memory addresses, wherein the binary tree data comprising parent node data, first child node data and second child node data;
- means for determining, using a memory assignment function and based on a first node position vector for a first child node, a first child node memory address, the first child node memory address being less than a parent node memory address;
- means for determining, using the memory assignment function and based on a second node position vector for a second child node, a second child node memory address, the second child node memory address being greater than the parent node memory address;
- means for storing the parent node data in at least one memory cell at the parent node memory address;
- means for storing the first child node data in at least one memory cell at the first child node memory address;
- and
- means for storing the second child node data in at least one memory cell at the second child node memory address, wherein the first node position vector and the second node position vector are each represented by [i1, i2, . . . , ik−1, ik], where:
- i1 is a layer position of a direct relative of that node in a first layer of the binary tree;
- i2 is a layer position of a direct relative of that node in a second layer of the binary tree;
- ik−1 is a layer position of a parent node;
- and
- ik is a layer position of that node.
Dependencies are inferred from the claim text.