Re-considering data structures

[ahmedh409]

The current blockchain uses a singly-linked list, meaning each node only points to the next. The next natural step from a singly-linked list is a doubly-linked list, which would allow traversal in both directions, but both still bottleneck with a query complexity of O(n).
We should consider new data structures for the blockchain as part of a "hardcore refactoring" for the codebase. I had an idea to implement the chain using skip lists which are commonly used in distributed systems and large-scale structures; these have a query complexity of O(log n) instead of linear since they have double links as well as "skip links" which can skip multiple nodes in order to efficiently traverse a list. Here's a paper to introduce the idea.
Another idea is implementing trees (Red-Black?) which tend to have a logarithmic query time, as well. Each "block" could be replaced by a tree which contains media with similar perceptual hashes; in this case, the user would traverse until a "similar" video is found, then it would run down the tree and find the specific video. This seems a little less elegant than skip lists, but could be really interesting - got the idea from the Linux CFS.