> Our investigation revealed that in case of frequent insertions and deletions Tarantool initiated a complex process of tree rebalancing (all our indexes were of TREE type).
It's all about 1.5. New version (1.6) uses brand new bps-tree, not sg/avl-tree. It behaves better on all workloads.
AVLTree was "temporary" hack. Our implementation works better, for their needs. BTW - AVL is not bad, but it's hard to implement a good one (believe me :) ).
You may read code of it here: https://github.com/tarantool/tarantool/blob/1.6/src/lib/sala... . It's very thoroughly commented.