Generational garbage collector for trees under multi-version concurrency control

A method of implementing generational garbage collection for a plurality of trees under multi-version concurrency control, comprising:

• detecting live objects in a plurality of normal trees,
• wherein the plurality of trees include the plurality of normal trees and a plurality of frozen trees,
• wherein objects include tree nodes and tree leaves and are alive when the objects are reachable from a tree root of at least one tree, wherein tree elements include objects and tree roots;
• identifying poorly-filled young chunks of hard-drive memory and poorly-filled old chunks of the hard-drive memory,
• wherein the hard-drive memory includes a plurality chunks that are fixed-sized blocks of the hard-drive memory,
• wherein the chunks include young chunks that store young elements, old chunks that store old elements, and immortal chunks that store immortal elements;
• opening for writes one or more old chunks;
• copying elements from the poorly-filled young chunks and the poorly-filled old chunks to the one or more opened old chunks;
• updating elements above the elements from the poorly-filled young chunks and the poorly-filled old chunks in the normal trees and storing the updated elements in the young chunks;
• opening for writes one or more immortal chunks;
• copying the tree leaves of the frozen trees from the young chunks and from the old chunks to the one or more opened immortal chunks;
• and
• updating and storing all nodes of the frozen trees in the immortal chunks.

A computer-readable medium having stored thereon instructions, when executed by a processor, causes the processor to perform a method of implementing generational garbage collection for a plurality of trees under multi-version concurrency control, comprising:

• detecting live objects in a plurality of normal trees,
• wherein the plurality of trees include the plurality of normal trees and a plurality of frozen trees,
• wherein objects include tree nodes and tree leaves and are alive when the objects are reachable from a tree root of at least one tree, wherein tree elements include objects and tree roots;
• identifying poorly-filled young chunks of hard-drive memory and poorly-filled old chunks of the hard-drive memory,
• wherein the hard-drive memory includes a plurality chunks that are fixed-sized blocks of the hard-drive memory,
• wherein the chunks include young chunks that store young elements, old chunks that store old elements, and immortal chunks that store immortal elements;
• opening for writes one or more old chunks;
• copying elements from the poorly-filled young chunks and the poorly-filled old chunks to the one or more opened old chunks;
• updating elements above the elements from the poorly-filled young chunks and the poorly-filled old chunks in the normal trees and storing the updated elements in the young chunks;
• opening for writes one or more immortal chunks;
• copying the tree leaves of the frozen trees from the young chunks and from the old chunks to the one or more opened immortal chunks;
• and
• updating and storing all nodes of the frozen trees in the immortal chunks.