[Sumtree]: High level sumtree spec

[AlpinYukseloglu]

Background

For our purposes, a sumtree will be a BST where each internal node stores the sum of its nodes and the leaves store the actual data (which in our case will be cancelled orders for a given tick).

Suggested Design

• It would likely be most appropriate to implement this as an augmented B+ tree with an additional prefix sum query and custom insertion and deletion logic that allows this query to be maintained as correct (e.g. updates necessary internal nodes along the way to insertions/deletions)

Acceptance Criteria

• Implementation-level sumtree spec is converged on

[AlpinYukseloglu]

I think analogizing with B+ trees/other binary tree constructions was not helpful given how unique our sumtree structure is with the whole internal range tracking. We essentially manually worked out insertion/deletion logic in #56 and #59 but it will probably make most sense to write this spec from first principles #60.

Will close this issue for now since the high level spec is already ready (see here), understanding that we still need a full implementation level spec that granularly covers all flows