Removing a single item from M-BPTREE

[BrianSipos]

I have a need to keep a dynamic multi-map, where individual keys and values can come and go as an index into other data. I don't see a current mechanism to remove a single item from a multi-map, only the name_erase() which takes only a key not an iterator. Does this mechanism currently exist? Or is the current multi-map not a good structure for me.

I can switch to using a single-map to dict instead, just wondering about this API.

[P-p-H-d]

Indeed, the multi-map API lacks a _remove function to remove only the pointed object.
EDIT: It is harder to do that what I was expecting because the iterator (in order for it to remain small) doesn't provide enough information to perform the job (the parent nodes and their child index) and we need to recompute the information from this structure:

• Average case can be very fast as we already know the node and the index in the node O(1).
• Worst case if when we remove one item, and the B+tree becomes unbalanced: we need to search once again the element in the tree, and the worst case is for a multimap when there is only the same key, in which case it is in O(n).

[P-p-H-d]

I have implemented the IT_REMOVE API for B+Tree.

I couldn't implement the O(1) removal (it is O(lg N now)) due the case where the B+Tree is built with N=2 or N=3 (in which case, when you remove an item, the remaining may be totally empty). I think I can work around this but it needs even more work.

Basic testing show no issue. However, more corner cases are needed to be tested due to the complexity of the implementation (mainly due to multimap)