It's not like an auto increment key is meaningful, so the read performance will be the same either way. As for writes, a new key could go anywhere in the index, but OTOH you can insert multiple values concurrently (unlike with auto increment keys with MVCC where you'll have collisions and one insert will have to be rolled back and redone). As always, benchmark your use case and see what gives acceptable performance.

> As for writes, a new key could go anywhere in the index

This forces index tree rebalancing to occur on many (even most) writes, which is hugely detrimental to performance.

Which tree structure is this for? Many tree structures (e.g. the classic red-black tree) perform much better (doing less rebalancing) for randomized inserts than for ordered ones.