Measure Trees

Measure trees map a totally-ordered measure space with an associative operation to value space which the measure is derived from. They are similar to finger trees, but their topology may be arbitrary.

The leaves of the tree hold the values, and each branch of the tree holds a list of edges to either branches or leaves, along with the measures of the linked nodes.

Encoding

The root branch is a version and other branches are blobs. Each branch holds a list of (measure, link) or (measure, value) tuples. The leaves may be the values directly, or the values may reference other blobs. Values should not reference braids unless the measure is independent of the content of the braid.

Examples

Random access into arbitrarily large byte sequences may be efficiently achieved with measure trees. The leaves are blobs holding raw byte sequences, measured by their size. A particular position of the byte sequence may be found by accumulating the sizes of each item in the root node until the accumulated measure at an item exceeds the start of the range. If a branch, descend into that item and repeat, if a leaf, descend into the leaf and seek to the appropriate offset.