How is the balanced binary tree of accounting key prefixes constructed?

CockroachDB design doc talks about a balanced binary tree when describing accounting aggregate:

If upon receiving the message, the parent range also does not include the key prefix, it in turn forwards it to its parent or left child in the balanced binary tree which is maintained to describe the range hierarchy.

How is the balanced binary tree constructed? What invariants does the balanced binary tree maintain? I browsed the code base and but failed to find the relevant code.

Hey @yaojingguo, the design doc was written very early on in the project’s existence, and that part never ended up getting implemented as described. I’ll remove it from the doc. Thanks for asking about it!

Hey @yaojingguo, I did actually build that balanced tree (it was a red-black tree), but it was removed as we didn’t need it once we started work on distributed sql execution of queries. It really should be removed form the design doc.