Bitcoin Stack Exchange is a question and answer site for Bitcoin crypto-currency enthusiasts. It only takes a minute to sign up.
Sign up to join this community
The blockchain looks like a double linked list, and all the transactions are stored into each block. What kind of algorithm does bitcoin use to find a specific transaction efficiently, since the blockchain is growing bigger and bigger?
The bitcoin network use its compute power to keep data consistency, if we simplify this model(write once read many, no update, no cheat) and use its consistency policy into the geographically distributed file system, does that work?
The blockchain is either a tree structure (with each block just referencing its parent), or a single path through this tree (a singly linked list).
Internally in software (at least in the reference implementation), indexes exist of course to find blocks (by height, and by hash).
Technically however, there is no indexing of transactions at all. They're not necessary for validation. Instead, a database is maintained with just the outputs of transactions that have not been spent yet (which is indexed by transaction hash and nothing more). Every block that is validated updates this database: its new outputs are added, the outputs consumed by it are removed. This database is tiny, compared to the blockchain (400MB vs 16GB as of march 2014).
In fact, earlier blocks themselves are not used during validation at all. We only need them for serving them to other nodes that are starting up - otherwise they would have no way to know the current state in a zero-trust manner.
This last point is important for Bitcoin's security model: full nodes never trust data they have not validated themselves. This is why we can't just copy the database of unspent outputs from someone and forgetting about the blocks before that point.
Regarding separation of data across nodes: such mechanisms typically have very bad DoS properties, where knocking out a few network nodes can mean that some data becomes inaccessible.
For just blocks, it is certainly possible to not have every node store and serve every block ever (and this will likely be implemented somewhere in the future). Again, all they are needed for is bootstrapping a new node.
The database of unspent outputs can also be sharded, namely by only retaining outputs of transactions within a certain range of hashes. However, this still requires each node to validate each block, and the result is technucally not a full node. You would need a set of nodes, that together validate the full range of hashes, to be sure blocks are fully valid.
