HashMapDB does not differenciate between leaf and branch nodes

[Trantorian1]

Bug Report

Bonsai-trie version: 83b2cab

Current behavior:

HashMapDB does not differentiate between leaf and branch nodes during insertion. This is in contrast to RocksDB which stores leaf and branch nodes in different columns (this is handled here using the get_cf method of DatabaseKey). This results in surprising behavior when retrieving keys from HashMapDB for example, since these will also include branch keys.

Expected behavior:

It would be more logical from the user perspective for a difference to be made between leaf and branch nodes in HashMapDB to allow to retrieve only the keys the user themselves inserted into the db.

Steps to reproduce:

1. Create a new BonsaiStorage with a HashMapDb and initialize a dummy tree.
2. Insert multiple nodes & commit.
3. Call get_keys, ignoring the first size byte. You will notice the resulting keys do not only contain those manually inserted.

Related code:

This is what a potential solution to this issue would look like.

fn insert(                                                     
    &mut self,                                                 
    key: &crate::bonsai_database::DatabaseKey,                 
    value: &[u8],                                              
    _batch: Option<&mut Self::Batch>,                          
) -> Result<Option<Vec<u8>>, Self::DatabaseError> {            
    Ok(self.db.insert(key.get_cf().to_vec().extend_from_slice(key.as_slice()), value.to_vec()))
}                                                              

Note that this would mean that any retrieval code would also have to be update accordingly

[cchudant]

Fixed by #34