Leveling algorithm

[zenhack]

Beyond just finding splits in the input itself, some systems will organize the splits into a tree, see e.g: https://godoc.org/github.com/bobg/hashsplit#Tree

We should include this in the spec as well.

[cole-miller]

I'd be happy to try writing this up if you don't already have something in progress.

[zenhack]

Go for it! Quoting Cole Miller (2020-08-29 16:54:52)

…

I'd be happy to try writing this up if you don't already have something in progress.

[zenhack]

Coming back to this (it's been almost two years, I expect others have wandered off at this point, but I have renewed interest...), I feel like there's an approach to turning this into a tree that is much simpler, and also deals with issues like balance that leveling doesn't cover by itself: Treat the tree as a B+ tree mapping indicies (or byte offsets) to chunks. Then, constructing the tree consists of just inserting each chunk into the tree in sequence. I think this gives us all the properties we actually want, and I suspect is much less awkward to formalize; there's some work to do to to define everything precisely, but that seems doable. It will be easier to specify than describing all the usual operations on the data structure, since we only actually need insert (and only at the end).