MySQL/InnoDB - Clustering Index with UUID
Face it, wherever you have the UUID as a KEY, it will be in a fragmented BTree.  But, the BTree is kept reasonably clean.  That is, when a BTree block is too full to accept another row, it splits into two blocks, each about half full.  As time goes on, any new inserts into either of those blocks will simply add to the blocks without immediately splitting.  The end result of 'random' inserts is blocks that average about 69% full.  This is only slightly worse than 100% full.

InnoDB uses only BTrees.  The data is 'clustered' with the PRIMARY KEY.  There is always a PRIMARY KEY:


an explicit PK, or
the first UNIQUE key with non-null column(s), or
a fabricated, hidden, 6-byte PK.


If your UUID is the PK, then you are doing splits/fragmentation on the data.  If your UUID is a secondary key, then that BTree suffers from splits/fragmentation.  There is (almost) no escaping it.

I say 'almost' because if you are using Type-1 UUIDs, you can shuffle the bits to make them approximately time oriented.  This makes them much like AUTO_INCREMENT ids.  I discuss that in my blog.

Yes, you could rebuild whatever index contains the UUID. This is via the OPTIMIZE TABLE, which rebuilds the table, blocking access during the process.  And, as I say, you won't gain much from it.  Ordinary blocks splits are not costly; OPTIMIZE is.  I often tell people to 'never' use OPTIMIZE.

Is your entire table small enough to be cached in the buffer_pool?  If so, UUIDs are not too much of a performance problem.  On the other hand, once the table (or the UUID index) gets much bigger than the buffer pool, processing becomes I/O-bound.  This is because of the random nature of UUIDs.  As the table grows, each INSERT and each SELECT (using UUID) becomes more and more likely to require a disk hit.

If you cannot avoid UUIDs (which would be my first recommendation), you can at least shrink them from taking 110 bytes via a casual implementation (VARCHAR(36) w/utf8) or 36 bytes (CHAR(36) w/ascii) and shrink it down to 16 bytes (BINARY(16)).  See my blog for the pair of Stored Functions.  Smaller --> More cacheable --> Less I/O --> Faster.

If you would like to discuss further what you are doing, I would be happy to elaborate further.