I thought the transactions within a block are stored in a Merkle tree, but the blocks themselves are stored as a linked list. So if you wanted to find a particular transaction you'd still have to traverse all the blocks (O(length)) and then inspect each block (O(log(depth))). I have no idea what dominates in verifying a Bitcoin transaction, so maybe in practice the cost of finding a particular block is amortized because you're spending most of your time within a block.
But from the original bitcoin paper[1] I got the impression that to verify any particular transaction you need to traverse the whole list of blocks.
