I've recently learned about a new Bitcoin node implementation in Rust called Bitcrust. They state that they have found a novel way of storing the Bitcoin blockchain as a "Spend tree" instead of tracking the UTXO set and claim to have significantly improved the performance of database interactions that way.
Can someone explain how the Bitcrust-db achieves that?
My understanding after a quick look at the code is that they use this sequential scan of stacked records of spends only for the recent 3 blocks (https://github.com/tomasvdw/bitcrust/blob/556375ccfaa81ca241b25f7b5b7f00fb97d5bd6b/src/store/spend_tree/record.rs#L296)
If the sequential scan did not find a match (if the input is from older blocks), they use this huge 2^58-bit bitmap, that is sparsely mapped to sparse files (if the filesystem does not support sparse files, they will use 16GB of storage for each 'range' that contains at least one bit set)
the code that uses 58-bit index: https://github.com/tomasvdw/bitcrust/blob/556375ccfaa81ca241b25f7b5b7f00fb97d5bd6b/src/store/spend_index.rs#L67 (more exactly, a 52-bit index to a map of U64 values)
the 'hash' variable there does not contain a true hash, it is just a mapping of the internal storage indexes to 58-bit value: https://github.com/tomasvdw/bitcrust/blob/556375ccfaa81ca241b25f7b5b7f00fb97d5bd6b/src/store/spend_tree/record.rs#L168
