Improve elementwise insertion to generate more compact trees
lorentey opened this issue · 0 comments
lorentey commented
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.