4 ms·

Bitcoin doesn't even use linked lists (it's merkle trees). Similar with other coins.

• hoosieree 4y ago
  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. [1]: https://bitcoin.org/bitcoin.pdf https://bitcoin.org/bitcoin.pdf
  • pshc 4y ago
    In practice you can look up a tx by its hash from the transaction index (implemented with a Merkle tree)