<p>Memory usage. Adding a vector to each of the (now over 600000) CBlockIndex entries would be a significant memory usage increase (at least 48 bytes per entry, to be precise, on stdc++ 64-bit platforms).</p>

<p>For most operations it's also unnecessary. Instead, CChain stores a pointer to all CBlockIndex entries <em>in the main chain</em>, allowing O(1) access to any of those. Also, using the skiplist mechanism (see <code>pskip</code>) in CBlockIndex it's possible to efficiently find the height N ancestor of any given block (in O(log n) or O((log n)^2), IIRC).</p>

CC BY-SA 4.0
2020-04-29T18:28:23.940Z
Why is it 48 bytes per entry? Shouldn't it be 8 byte per entry? (sizeof(void*))
warchantua
CC BY-SA 4.0
2020-04-29T18:30:29.453Z
A vector has an overhead of 3 pointers (begin of memory block, end of memory block, end of used portion of memory block). The memory block itself is dynamically allocated, which has malloc() overhead (16 to 31 bytes on x86_64 Linux, depending on rounding).
Pieter Wuille
CC BY-SA 4.0
2020-04-29T18:23:23.650Z
2020-04-29T18:23:23.650Z
Pieter Wuille
<p>CBlockIndex stores <a href="https://github.com/bitcoin/bitcoin/blob/master/src/chain.h#L144" rel="nofollow noreferrer">a pointer to previous block.</a>. </p>

<p>Is there any specific reason why it does not store a vector of "next" blocks for forward iteration?</p>

<p>If you think, a typical tree (as data structure) has "parent" (<code>pprev</code>) and a list of "children".</p>

<bitcoin-core><bitcoin-core-development>
Why CBlockIndex does not store a vector of next blocks for forward iteration?
warchantua
# Why CBlockIndex does not store a vector of next blocks for forward iteration?

(Asked by: username_0 on 2020-04-29)

CBlockIndex stores [a pointer to previous block.](https://github.com/bitcoin/bitcoin/blob/master/src/chain.h#L144).

Is there any specific reason why it does not store a vector of "next" blocks for forward iteration?

If you think, a typical tree (as data structure) has "parent" (`pprev`) and a list of "children".

**Tags:** bitcoin-core, bitcoin-core-development


---

## 1 answers

### Answer by username_1 on 2020-04-29. Score: 1 | Accepted answer

Memory usage. Adding a vector to each of the (now over 600000) CBlockIndex entries would be a significant memory usage increase (at least 48 bytes per entry, to be precise, on stdc++ 64-bit platforms).

For most operations it's also unnecessary. Instead, CChain stores a pointer to all CBlockIndex entries *in the main chain*, allowing O(1) access to any of those. Also, using the skiplist mechanism (see `pskip`) in CBlockIndex it's possible to efficiently find the height N ancestor of any given block (in O(log n) or O((log n)^2), IIRC).

> **Comments:**
> **username_0**: Why is it 48 bytes per entry? Shouldn't it be 8 byte per entry? (sizeof(void*))  
> **username_1**: A vector has an overhead of 3 pointers (begin of memory block, end of memory block, end of used portion of memory block). The memory block itself is dynamically allocated, which has malloc() overhead (16 to 31 bytes on x86_64 Linux, depending on rounding).  

---

