0

CBlockIndex stores a pointer to previous block..

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".

1

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).

| improve this answer | |
  • Why is it 48 bytes per entry? Shouldn't it be 8 byte per entry? (sizeof(void*)) – warchantua Apr 29 at 18:28
  • 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). – Pieter Wuille Apr 29 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.