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, 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 each of N contiguous levels of the plurality of tree arrays in a different one of said N sets of memory channels, wherein each of the plurality of tree arrays at a same level of said N contiguous levels is stored in the same memory channel set of said N sets of memory channels;
• wherein which of said N sets of memory channels to store which of said N contiguous levels of the plurality of tree arrays is determined based on one or more occupancy levels of one or more of said N sets of memory channels, where said one or more occupancy levels correspond to an amount of free space in said one or more of said N sets of memory channels.

An apparatus for storing items, the apparatus comprising:

• a first memory channel for storing one or more first level internal nodes of a subtree;
• a second memory channel for storing one or more second level internal nodes of the subtree, wherein said one or more second level internal nodes are child of said one or more first level internal nodes;
• a third memory channel for storing one or more third level internal nodes of the subtree, wherein said one or more third level internal nodes are child of said one or more second level internal nodes;
• a fourth memory channel for storing one or more fourth level internal nodes of the subtree, wherein said one or more fourth level internal nodes are child of said one or more third level internal nodes;
• a fifth memory channel for storing one or more leaf arrays of the subtree;
• and
• a memory manager coupled to the first memory channel, the second memory channel, the third memory channel, the fourth memory channel, and the fifth memory channel;
• wherein the memory manager stores said one or more leaf arrays of the subtree in the fifth memory channel and stores N contiguous levels of internal nodes in the first, second, third, and fourth memory channels, wherein each internal node at a same level of said N contiguous levels is stored in the same one of the first, second, third, and fourth memory channels;
• and wherein which of said first, second, third, and fourth memory channels to store which of said N contiguous levels of internal nodes is determined based on one or more occupancy levels of said first, second, third, and fourth memory channels, where said one or more occupancy levels correspond to an amount of free space in one or more of said first, second, third, and fourth memory channels.