Balanced append tree data structure

摘要

Techniques are described for employing a substantially self-balanced append tree data structure to store and access information. The append tree data structure is a hierarchical data structure in which a leaf node or a parent node may be added to expand the append tree data structure. The determination to add a leaf node or a parent node may be based on a counter for leaf nodes present in the append tree data structure. Nodes in the append tree data structure may be blocks in memory, with each block corresponding to a plurality of positions that may be employed to tracking message identifiers in a messaging service.

主权项

1. A system, comprising:
at least one computing device configured to implement one or more services, wherein the one or more services are configured to:
access a data structure comprising a plurality of nodes that are hierarchically related, the data structure being an append tree data structure that includes:
a plurality of leaf nodes at a first hierarchical level of the data structure, the plurality of leaf nodes being unrelated as a parent of other nodes; andone or more parent nodes at one or more second hierarchical levels of the data structure, at least one of the one or more parent nodes being related as a parent of at least two of the plurality of leaf nodes;examine a binary counter incremented for each leaf node added to the plurality of leaf nodes of the data structure, the binary counter indicating a value associated with an order in which the plurality of leaf nodes were added to the data structure; anddetermine a value of a binary count of 1-valued bits in a portion of the binary counter inclusively ranging from a least significant bit of the binary counter to a least significant 0-valued bit of the binary counter, the value of the binary count indicating a number of additional parent nodes to be added to the data structure prior to adding an additional leaf node to the data structure.