Tree.edit performance improvements

[JOOHOJANG]

What would you like to be added: Creating a data structure to compute segment sums of left siblings.

Why is this needed: While I'm working on add benchmark test(https://github.com/yorkie-team/yorkie/issues/623), I found out there's a critical performance issue. The main reason is converting CRDTTreeNode to corresponding index/path takes very long time, because it's linearly adding left siblings.

Therefore, I think new data structure/algorithm is needed to address the shortcomings of the current Tree.

1. Prefix Sum

   • o(1) for query
   • o(n) for update
   • o(n) for insert/delete

2. AVL Tree(RB, LLRB, OST)

   • o(logn) for query
   • o(logn) for update
   • o(logn) for insert/delete

3. BIT(Fenwick Tree)

   • o(logn) for query
   • o(logn) for update
   • o(n) for insert/delete

When considering the characteristics, update will rarely takes place while insert/delete happens a lot. While the AVL Tree appears to be the most suitable, it has the disadvantage of consuming more memory than Prefix Sum and Fenwick/Segment Tree, because it has to maintaining link. Also, Fenwick tree is optimized for calculating segment sums. Thus, even at the same O(logn), they outperform AVL trees in range queries.

So, I'm going to test both the AVL Tree and the Fenwick Tree to determine which one is more suitable for our use case.

FYI) 밀리초 is equals to ms

100 TreeNodes

200 TreeNodes

300 TreeNodes

400 TreeNodes

800 TreeNodes

1000 TreeNodes

[JOOHOJANG]

Significant performance improvements were achieved through tuning, not by applying algorithms.(Thanks to @hackerwins ) However, I will keep this issue open because it needs to be improved.

[hackerwins]

I'll close this issue for now. Let's open a new one when we make further improvements.