I think binary heap -> B-heap is analogous to balanced binary tree -> B-tree. It applies a similar idea, but provides O(1) lookup for the minimum element, O(1) average insert, and O(n) search [1], instead of O(log n) min-lookup, O(log n) insert, and O(log n search) [2]. So a B-tree would not perform well in applications where a heap is desirable.
I mean in the context of block-oriented access, like VM as discussed in the article. That a block-aware data structure performs much better than a block-unaware one isn’t that surprising or interesting, at least to me.
The question is: In the context of a block-oriented store, like a VM system, when is b-heap better or worse than b-tree and variants?
Note, I said “and variants” deliberately because of course plain b-tree is pretty simple. Just comparing O between b-heap and b-tree isn’t enough because B-tree variants can have the same O characteristics, I think.
[1] https://en.wikipedia.org/wiki/Binary_heap [2] https://en.wikipedia.org/wiki/B-tree