Balancing write amplification and space amplification in buffer trees

A non-transitory computer-readable storage medium having stored thereon computer executable instructions, which when executed by a computer device, cause the computer device to:

• receive a packet comprising a plurality of data elements to be stored in a target node of a buffer tree;
• store the received packet as an uncompacted packet in a first portion of a buffer associated with the target node;
• and
• perform a packet compaction operation on the target node when a compaction trigger condition exists on the target node, including the computer device:
• sorting data elements contained in uncompacted packets in the first portion of the buffer associated with the target node;
• storing the sorted data elements into one or more compacted packets in a second portion of the buffer associated with the target node, including creating the one or more compacted packets on the data storage device and writing the sorted data elements to the data storage device;
• and
• performing a data element compaction operation on one or more sets of data elements by replacing each set of data elements with a corresponding smaller set of replacement data elements, thereby reducing the number of data elements in the target node,
• wherein the compaction trigger condition on the target node is based on an amount of space used by the buffer associated with the target node and based on an amount of free space on the data storage device.

An apparatus comprising:

• one or more computer processors;
• and
• a computer-readable storage medium comprising instructions for controlling the one or more computer processors to be operable to:
• receive a packet comprising a plurality of data elements to be stored in a target node of a buffer tree;
• store the received packet as an uncompacted packet in a first portion of a buffer associated with the target node;
• and
• perform a packet compaction operation on the target node when a compaction trigger condition exists on the target node, including the computer device:
• sorting data elements contained in uncompacted packets in the first portion of the buffer associated with the target node;
• storing the sorted data elements into one or more compacted packets in a second portion of the buffer associated with the target node, including creating the one or more compacted packets on the data storage device and writing the sorted data elements to the data storage device;
• and
• performing a data element compaction operation on one or more sets of data elements by replacing each set of data elements with a corresponding smaller set of replacement data elements, thereby reducing the number of data elements in the target node,
• wherein the compaction trigger condition on the target node is based on an amount of space used by the buffer associated with the target node and based on an amount of free space on the data storage device.