I am not offering this as a solution to your challenge, but I suggest looking at the thread Compressing a set of integers. I think that I had a similar problem, but I had a few more opportunities for optimization than you have presented.

With help from the others in the thread, I was able to use pack to make a really cool data structure that is similar to a sparse bit vector. My problem had the potential optimization that some bits were more likely than others, and I could reorder.

For the problem I was trying to solve, Table::ParentChild ended up getting written along the way.

For the deployed application, I ended up using a relational database, which performs well enough today in production.

I also suggest, for practical solutions, that you consider algorithms which are O(log(n)), especially those with small constant factors.