Say we have transaction T(1) from many years ago, at block height 125001; then a new transaction T(2), consuming all the outputs from T(1), comes up around block height 568720 (that's Today). There's a lot of blocks in between; many GB of data, and the nodes need to efficiently check that the outputs of T(1) were never used in all these years since block height 125001 before processing T(2). This looks like a scalability problem. How do the nodes usually do that? Do they perform a linear search? Do they have a B-tree index of all active transactions? A hash-index? Is there a more efficient way to find out? Is the blockchain structured in a way that this search is inherently trivial? What about the nodes that do not store the whole block chain history?
Thanks a lot.