I use UUIDs for pretty much any "primary key"-like scenario:
* They're natively supported in most databases and languages
* They're strongly typed, meaning there's no risk of accidentally doing things that make no semantic sense with them (e.g. adding or multiplying)
* They ensure that any API user will use the correct datatype, rather than some clients breaking when your ids go above 2^31
* They avoid exposing information about how many entries they are, e.g. you can't tell how many users I have by signing up and checking your user ID
* The client can generate them without roundtripping to the database; this can save on roundtrips when you're saving several related pieces of data, and makes it easier to have circular datastructures if you need them
* As others have said, they're usable in an AP datastore
None of this is impossible to do with integers, but UUIDs make it very easy.
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.
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.
You forgot to mention that UUID's hurts JOIN performance. You want to join on 64 bits integers and not on 128 bit UUID's. You can still save the UUID in another column as a unique-id for the purposes you mentioned.
* They're natively supported in most databases and languages
* They're strongly typed, meaning there's no risk of accidentally doing things that make no semantic sense with them (e.g. adding or multiplying)
* They ensure that any API user will use the correct datatype, rather than some clients breaking when your ids go above 2^31
* They avoid exposing information about how many entries they are, e.g. you can't tell how many users I have by signing up and checking your user ID
* The client can generate them without roundtripping to the database; this can save on roundtrips when you're saving several related pieces of data, and makes it easier to have circular datastructures if you need them
* As others have said, they're usable in an AP datastore
None of this is impossible to do with integers, but UUIDs make it very easy.