IS the utxo set stored independently from the block set?
Yes. It's called
chainstate, few call it UTXO set.
so for each block that comes in you store;
block (Key: BlockHash)
then extract each tx and store;
tx (Key: TxHash)
AFAIK it's true,
chainstate uses key/value pair method which contain TX hash and block hash.
how does bitcoin search the db for a given utxo to verify a transaction is legitimate if it just stores the blocks?
By access
chainstate, not access blocks