<p>First, a blockchain is it's own data structure.  It's best to think of it as one.  It represents a way to organize data in which desirable properties are gained.  However, that still does not explain how to hold one in memory/storage.</p>

<p>In Bitcoin, the blockchain is stored on disk (not memory) using leveldb.  This is a key/value database where the keys are the block hashes and the values are the blocks.</p>

<p>For an in-memory equivalent, a hash map is what you are looking for.  This is a data structure where the key is a hash of the contents (such as a block header).  From there, the header's Merkel root would point to another hash map of transactions arranged in a Merkle tree (as per the protocol).</p>

<p>However, an in-memory solution (which seems to be what you are after) is a terrible solution for a blockchain.  The data simply grows too quickly.  You will want to store the data to disk and have a fast way to query it.  This is why Bitcoin uses an existing database such as leveldb.</p>

CC BY-SA 3.0
2018-01-27T10:46:51.637Z
This is a great suggestion. I think I'll go with the leveldb implementation. A couple of questions :-

1.) How would I model a fork, the fact that two blocks can exist at the same height at a given point in time. This is especially important while choosing the parent block to mine against.

2.) If all blocks are stored in disk, isn't validating a new block a very time consuming operation since we need to validate each transaction in the block against all transactions ever done (by querying the DB) to prevent a double spend ?
Aarsh Shah
CC BY-SA 3.0
2018-01-27T10:47:04.397Z
3.) What do you think of an implementation where I store the block headers (80 bytes each ) in memory and store the transaction data which occupies the bulk of the space in level-db ? This will make it faster  to validate the blockchain by verifying the correctness of the prevHash field of each block.
Aarsh Shah
CC BY-SA 3.0
2018-01-27T10:34:34.957Z
2018-01-27T18:02:32.830Z
2018-01-27T18:02:32.830Z
Jestin
<p>Actually, it occurs to me, I wonder could you use <a href="https://git-scm.com/" rel="nofollow noreferrer">Git</a>?</p>

<p>You could just use a stacked file naming convention that is the hash of the file contents header (including a Merkle Root or a hash for the contents) and refer in the header section of the file to the previous file. This allows for forks.</p>

CC BY-SA 3.0
2018-01-27T09:06:22.620Z
Thanks for the reply.

1.) Please can you elaborate a bit on how Git stores it's files ? Even some links would do ?
2) How would you leverage this to store the Blockchain in-memory ?
Aarsh Shah
CC BY-SA 3.0
2018-01-27T12:15:20.920Z
I was thinking that you were looking for a simple file structure for storing blockchain, I probably could have started the second paragraph with or. Git would allow for some interesting operations. You could probably read [Git from the bottom up](https://github.com/Willtech/GitRefDocs/blob/master/git.from.bottom.up.pdf) and [Pro git](https://github.com/Willtech/GitRefDocs/blob/master/progit.pdf) - too big for the inline viewer; you have to download it. Bitcoin blockchain is a little to big to store in memory generally speaking at ~150GB.
Willtech
CC BY-SA 3.0
2018-01-27T07:22:00.380Z
2018-01-27T11:46:28.290Z
2018-01-27T11:46:28.290Z
Willtech
<p>I'm working on a functional mini-Blockchain implementation in Scala. I've given this a lot of thought but still can't comprehend the most suitable data structure to model a Blockchain. Specifically :-</p>

<p>1.) It can't be a simple Linked list/Stack, because there are forks , which means that two different blocks can refer to the same Block.Should it be a List of top blocks , i.e. a list of topmost(heightwise) blocks ? I can then traverse the blockchain by starting my traversal from either of the topmost blocks.</p>

<p>2.) How do I make a block point to the previous block ? I know that every block has the hash of the previous block. But how is that enough for me to go from a block to the block it refers to in my blockchain data structure ?</p>

<p>Would really appreciate any help I can get.</p>

<blockchain>
What data structure should I use to model a Blockchain
Aarsh Shah
# What data structure should I use to model a Blockchain

(Asked by: username_0 on 2018-01-27)

I'm working on a functional mini-Blockchain implementation in Scala. I've given this a lot of thought but still can't comprehend the most suitable data structure to model a Blockchain. Specifically :-

1.) It can't be a simple Linked list/Stack, because there are forks , which means that two different blocks can refer to the same Block.Should it be a List of top blocks , i.e. a list of topmost(heightwise) blocks ? I can then traverse the blockchain by starting my traversal from either of the topmost blocks.

2.) How do I make a block point to the previous block ? I know that every block has the hash of the previous block. But how is that enough for me to go from a block to the block it refers to in my blockchain data structure ?

Would really appreciate any help I can get.

**Tags:** blockchain


---

## 2 answers

### Answer by username_1 on 2018-01-27. Score: 1

First, a blockchain is it's own data structure. It's best to think of it as one. It represents a way to organize data in which desirable properties are gained. However, that still does not explain how to hold one in memory/storage.

In Bitcoin, the blockchain is stored on disk (not memory) using leveldb. This is a key/value database where the keys are the block hashes and the values are the blocks.

For an in-memory equivalent, a hash map is what you are looking for. This is a data structure where the key is a hash of the contents (such as a block header). From there, the header's Merkel root would point to another hash map of transactions arranged in a Merkle tree (as per the protocol).

However, an in-memory solution (which seems to be what you are after) is a terrible solution for a blockchain. The data simply grows too quickly. You will want to store the data to disk and have a fast way to query it. This is why Bitcoin uses an existing database such as leveldb.

> **Comments:**
> **username_0**: This is a great suggestion. I think I'll go with the leveldb implementation. A couple of questions :-  1.) How would I model a fork, the fact that two blocks can exist at the same height at a given point in time. This is especially important while choosing the parent block to mine against.  2.) If all blocks are stored in disk, isn't validating a new block a very time consuming operation since we need to validate each transaction in the block against all transactions ever done (by querying the DB) to prevent a double spend ?  
> **username_0**: 3.) What do you think of an implementation where I store the block headers (80 bytes each ) in memory and store the transaction data which occupies the bulk of the space in level-db ? This will make it faster  to validate the blockchain by verifying the correctness of the prevHash field of each block.  

---

### Answer by username_2 on 2018-01-27. Score: 0

Actually, it occurs to me, I wonder could you use [Git](https://git-scm.com/)?

You could just use a stacked file naming convention that is the hash of the file contents header (including a Merkle Root or a hash for the contents) and refer in the header section of the file to the previous file. This allows for forks.

> **Comments:**
> **username_0**: Thanks for the reply.  1.) Please can you elaborate a bit on how Git stores it's files ? Even some links would do ? 2) How would you leverage this to store the Blockchain in-memory ?  
> **username_2**: I was thinking that you were looking for a simple file structure for storing blockchain, I probably could have started the second paragraph with or. Git would allow for some interesting operations. You could probably read [Git from the bottom up](https://github.com/username_2/GitRefDocs/blob/master/git.from.bottom.up.pdf) and [Pro git](https://github.com/username_2/GitRefDocs/blob/master/progit.pdf) - too big for the inline viewer; you have to download it. Bitcoin blockchain is a little to big to store in memory generally speaking at ~150GB.  

---

