Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve performance of Splay Tree in crdt.Text data structure to prevent skewness #906

Open
m4ushold opened this issue Oct 2, 2024 · 0 comments
Assignees

Comments

@m4ushold
Copy link
Contributor

m4ushold commented Oct 2, 2024

Description:
In the crdt.Text data structure, Splay trees are used, and while they are efficient when performing operations sequentially within a contiguous range, they suffer from the issue of becoming skewed when elements are sequentially inserted. This leads to a linear arrangement in the tree. In a tree with N vertices, performing M operations guarantees O((N+M) log N) time. However, if the tree becomes skewed, each operation may initially take O(N) time before returning to more efficient performance. This issue can cause performance degradation in the crdt.Text data structure, making it crucial to explore methods to prevent skewness and maintain efficiency.

Why:
To maintain and enhance the performance and efficiency of the crdt.Text data structure in the face of potential skewness issues in the Splay trees. And If a single operation takes O(n) time, the responsiveness of the editing environment will degrade.

@m4ushold m4ushold self-assigned this Oct 2, 2024
@m4ushold m4ushold mentioned this issue Oct 2, 2024
2 tasks
@devleejb devleejb moved this from Backlog to In progress in Yorkie Project - 2024 Oct 15, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
Status: In progress
Development

No branches or pull requests

1 participant