The problem of both locality and length also only exist in modern databases. Good old Ingres QUEL offered the choice of hash and btree indexes, and the the ability to compress indexes. Index compression is of course much easier with sequential indexes, but it would at least optimize the static host part of the uuid away.