Hm, after thinking a bit and taking your explanation i came across this:
When transaction is spread to miner, he:
1. checks where prev_out hashes are located in block chain (starting from newest block in chain and going backward) - i.e. chain is on block 150000 and prev_out hash for our new TxIn is in 130000 so app starts at block 150000 and goes backwards till he hit 130000 block and proper hash in it. After that he checks TxOuts in that transaction adiacent for our new TxIn
2. checks whether there are any double spends by checking any TxIns (starting from TxOuts locations and going forwards till newest block in chain) that spent already coins in TxOuts - i.e. TxOut is in block 130000 and transaction is already spent in block 140000 so it goes from block 130000 until it finds proper TxIn in block 140000.

I am right in these assumptions? Or prev_out is a hash of block (+ additional necessary stuff) where transaction is located to find it really fast?