IMHO, prolly trees optimize for the wrong thing.
What they're good at is targeting specific internal node size distributions, so that e.g. most nodes end up with, say, around 128 items, almost none with a single item and none with over 256.
What this helps with is read speed: if you have a prolly tree, you're way more likely to cut down on possibilities when going through one internal node.
But you sacrifice write speed: with MSTs, you only modify the nodes between the leaf and the root.
Additionally, because you end up modifying more nodes for each write on average, it's less likely that two similar trees share internal nodes, compared to MSTs (structural sharing is worse).
So I'd say that prolly trees will have slightly slower writes, but faster reads and worse structural sharing.
I don't know if those reasons were the deciding factor for Bluesky, but what I'm trying to say is that prolly trees aren't "the better MSTs" that I've seen them portrayed before :)
Comments
What they're good at is targeting specific internal node size distributions, so that e.g. most nodes end up with, say, around 128 items, almost none with a single item and none with over 256.
This makes the trees much less degenerate.
But you sacrifice write speed: with MSTs, you only modify the nodes between the leaf and the root.
I don't know if those reasons were the deciding factor for Bluesky, but what I'm trying to say is that prolly trees aren't "the better MSTs" that I've seen them portrayed before :)