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 elementwise insertion to generate more compact trees #8

Open
lorentey opened this issue Mar 7, 2016 · 0 comments
Open

Improve elementwise insertion to generate more compact trees #8

lorentey opened this issue Mar 7, 2016 · 0 comments

Comments

@lorentey
Copy link
Collaborator

lorentey commented Mar 7, 2016

Inserting or appending a sequence of consecutive elements one by one into a tree produces half-filled nodes. This is in contrast with BTreeBuilder that builds trees with fully loaded nodes.

Improve elementwise insertion to detect when an overfull node is preceded by a relatively under-filled one. When this is the case, shift elements into the smaller node rather than splitting the full node into two half-filled ones.

An implementation of this should come with benchmarks proving that the performance advantage of a more compact tree is enough to offset the costs of a more complex insertion algorithm.

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