IAVL Gas pricing

[ValarDragon]

Currently our IAVL gas pricing is a bit naive. Its pricing model currently is a flat "get" fee, plus some cost per byte read. However the work is really constant overhead + O(depth) + db read per byte + rebalance cost at a given depth.

• We should definitely have a cost per depth, since these are extra reads that are required.

• For rebalancing, there are a couple options, either amortize the rebalance cost over the minimal number of operations until next rebalance, have a full rebalance charge at once, or make some metric to determine how much closer to a rebalance its being pushed. There are downsides to both:

  • If we amortize to the minimum number of operations until the next rebalance, then in most scenarios the total amount charged for this will be more than the cost of rebalancing. If the tree is perfectly balanced and of size n, I can typically make it rebalance with n/2 deletes, but on average it will take more operations to force it to rebalance. This also complicated, since you have to do this calculation for every depth.
  • Having a full rebalance charge during a rebalance is do-able. It also avoids the above complications and can be an extremely precise charge, but it kinda sucks that one person is getting the charge for the rebalance.
  • Making some metric for determining how close we are being pushed to a rebalance at every given depth is do-able. We just have to do it at every depth.