Method and apparatus for storing tree data structures among and within multiple memory channels

An apparatus for storing a subtree in memory, the subtree including one or more leaf arrays and a plurality of tree arrays, a path of tree arrays includes a sequence of tree arrays along any route from the root of the subtree to any leaf of the subtree, the apparatus comprising:

• means for storing said one or more leaf arrays in a first set of memory channels of N+1 sets of memory channels, said N+1 sets of memory channels including N sets of memory channels plus the first set of memory channels;
• and
• means for storing paths of the plurality of tree arrays in said N sets of memory channels, wherein for each particular path of tree arrays:
• a constrain that each tree array of the plurality of tree arrays associated with said particular path is stored in a different one of said N sets of memory channels;
• and wherein said tree arrays at a same level of tree arrays in the subtree are distributed among said N sets of memory channels that are available for a particular tree array given said constraint that each tree array of the plurality of tree arrays associated with a specific path is stored in a different one of said N sets of memory channels.

A method for storing a subtree in memory, the subtree including one or more leaf arrays and a plurality of tree arrays, a path of tree arrays includes a sequence of tree arrays along any route from the root of the subtree to any leaf of the subtree, the method comprising:

• storing said one or more leaf arrays in a first set of memory channels of N+1 sets of memory channels, said N+1 sets of memory channels including N sets of memory channels plus the first set of memory channels;
• and
• storing paths of the plurality of tree arrays in said N sets of memory channels, wherein each tree array of the plurality of tree arrays associated with one of said paths is stored in a different one of said N sets of memory channels;
• wherein said storing one or more leaf arrays includes:
• identifying that there is no block of memory indicated as available in an unused block data structure;
• and allocating a new memory page in the first memory channel.

A method for storing a subtree in memory, the subtree including one or more leaf arrays and a plurality of tree arrays, a path of tree arrays includes a sequence of tree arrays along any route from the root of the subtree to any leaf of the subtree, the method comprising:

• storing said one or more leaf arrays in a first set of memory channels of N+1 sets of memory channels, said N+1 sets of memory channels including N sets of memory channels plus the first set of memory channels;
• and
• storing paths of the plurality of tree arrays in said N sets of memory channels, wherein each tree array of the plurality of tree arrays associated with one of said paths is stored in a different one of said N sets of memory channels;
• wherein said storing said paths of the plurality of tree arrays includes:
• identifying that there is no block of memory indicated as available in an unused block data structure;
• and allocating a new memory page in one of said N sets of memory channels.

A method for storing a subtree in memory, the subtree including one or more leaf arrays and a plurality of tree arrays, a path of tree arrays includes a sequence of tree arrays along any route from the root of the subtree to any leaf of the subtree, the method comprising:

• storing said one or more leaf arrays in a first set of memory channels of N+1 sets of memory channels, said N+1 sets of memory channels including N sets of memory channels plus the first set of memory channels;
• storing paths of the plurality of tree arrays in said N sets of memory channels, wherein each tree array of the plurality of tree arrays associated with one of said paths is stored in a different one of said N sets of memory channels;
• and
• initiating a memory compaction operation in response to an occupancy or a fragmentation level of at least one of said N sets of memory channels;
• wherein said memory compaction operation includes storing a group of all said tree arrays stored in a single one of said N sets of memory channels which requires a largest storage space of that required by groups of all said leaf arrays stored in any one of the N sets of memory channels in a particular one of said N sets of memory channels having a greatest amount of storage space available for storing tree arrays.

A method for storing a subtree in memory, the subtree including one or more leaf arrays and a plurality of tree arrays, a path of tree arrays includes a sequence of tree arrays along any route from the root of the subtree to any leaf of the subtree, the method comprising:

• storing said one or more leaf arrays in a first set of memory channels of N+1 sets of memory channels, said N+1 sets of memory channels including N sets of memory channels plus the first set of memory channels;
• storing paths of the plurality of tree arrays in said N sets of memory channels, wherein each tree array of the plurality of tree arrays associated with one of said paths is stored in a different one of said N sets of memory channels;
• and
• initiating a memory compaction operation in response to an occupancy or a fragmentation level of at least one of said N sets of memory channels;
• wherein said memory compaction operation includes:
• identifying an available space ordering based on an occupancy level of each of said N sets of memory channels;
• identifying a storage requirement ordering based on the storage requirement of each of the plurality of tree arrays;
• and storing the plurality of tree arrays in said N sets of memory channels based on the available space and storage requirement orderings.

A method for storing a subtree in memory, the subtree including one or more leaf arrays and a plurality of tree arrays, a path of tree arrays includes a sequence of tree arrays along any route from the root of the subtree to any leaf of the subtree, the method comprising:

• storing said one or more leaf arrays in a first set of memory channels of N+1 sets of memory channels, said N+1 sets of memory channels including N sets of memory channels plus the first set of memory channels;
• storing paths of the plurality of tree arrays in said N sets of memory channels, wherein each tree array of the plurality of tree arrays associated with one of said paths is stored in a different one of said N sets of memory channels;
• and
• initiating a memory compaction operation in response to an occupancy or a fragmentation level of at least one of said N+1 sets of memory channels;
• wherein said memory compaction operation includes:
• identifying whether (1) a tree array storage requirement for a group of all said tree arrays stored in a single one of said N sets of memory channels which requires a largest storage space of that required by groups of all said leaf arrays stored in any one of the N sets of memory channels or (2) a leaf array storage requirement for said one or more leaf arrays requires more storage space;
• and storing the groups of said one or more leaf arrays identified as requiring more storage space in a particular one of said N+1 sets of memory channels having a greatest amount of storage space available.

A method for storing a subtree in memory, the subtree including one or more leaf arrays and a plurality of tree arrays, a path of tree arrays includes a sequence of tree arrays along any route from the root of the subtree to any leaf of the subtree, the method comprising:

• storing said one or more leaf arrays in a first set of memory channels of N+1 sets of memory channels, said N+1 sets of memory channels including N sets of memory channels plus the first set of memory channels;
• storing paths of the plurality of tree arrays in said N sets of memory channels, wherein each tree array of the plurality of tree arrays associated with one of said paths is stored in a different one of said N sets of memory channels;
• and
• initiating a memory compaction operation in response to an occupancy or a fragmentation level of at least one of said N+1 sets of memory channels;
• wherein said memory compaction operation includes:
• identifying an available space ordering based on an occupancy level of each of said N+1 sets of memory channels;
• identifying a storage requirement ordering based on the storage requirement of each of the plurality of tree arrays and said one or more leaf arrays;
• and storing the plurality of tree arrays and said one or more leaf arrays in said N+1 sets of memory channels based on the available space and storage requirement orderings.