attaswift/BTree

Improve elementwise insertion to generate more compact trees

lorentey opened this issue · 0 comments

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.