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

Consider using fixed gaps instead of a halfway mark when appending #13

Open
dmarkow opened this issue Jan 15, 2020 · 0 comments
Open

Consider using fixed gaps instead of a halfway mark when appending #13

dmarkow opened this issue Jan 15, 2020 · 0 comments

Comments

@dmarkow
Copy link
Owner

dmarkow commented Jan 15, 2020

Even with an upper limit of 2.1 billion, 32 items added to a list sequentially hits the max possible rank. This means that after just 32 items, the entire list has to be rebalanced. Right now, every insertion after this shifts the entire list. Even after #12 is fixed, it will still have to rebalance every ~25 inserts.

If we made a fixed gap of 2,000 for example, this would allow 1 million appended items before hitting the max rank, while still leaving enough of a gap to allow for around a dozen inserts between existing items until rebalancing would be needed.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant