Removing nodes when they are underoccupied

[mr-bat]

Why don't you remove unnecessary nodes when they become under-occupied? How are you going to deal with a large number of useless branch nodes in tree?

[myui]

@mr-bat I just noticed your comment. Sorry to be late.

It's because prefix b+tree requires a special case for deletion. Unlike general b+-tree, prefix b+-tree stores shortest possible separator as see in https://github.com/myui/btree4j/blob/master/src/main/java/btree4j/BTree.java#L802

Then, even if a key is deleted, it's hard to determine while the intermediate seperator(s) in branch nodes can be deleted or not.

[myui]

But as described in the paper, delete can be implemented with a careful implementation.
No merge feature (merging small leaves and branch shrinking) since my original motivation was append-only usecase.

Better to implement it for delete-heavy workloads.

[plummip]

Could you explain a bit how we approach this situation?
I tryed implementing it without any luck.
-merge neighbour nodes that share the same parent
-set left/right
-remove parent separator
[if > 0 keys] -recalculate parent separator
[else] -point parent-parent to node & remove parent node

[myui]

see https://gist.github.com/myui/e2424bcd2b11741f68581a6c80b5e438

[mr-bat]

You can also look at this project https://github.com/mr-bat/BPlusTree.
I ended up implementing a B+ tree of my own.