Design an API system to store/modify/rebalance a persistent Binary Search Tree with Billions of nodes

Provided a naive solution, whcih I feel is embarassing to reproduce here.
Any inputs/solutions welcome.