Removing nodes when they are underoccupied about btree4j HOT 5 OPEN

@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.

from btree4j.

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.

from btree4j.

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

from btree4j.

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

from btree4j.

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

from btree4j.