I'm not going to have 100's of millions of objects, so I can't speak to that.
But for my one hobby project, I'm using RDF and a triple store. Even with a "small" dataset, you can get an explosion of properties.
I want to be able to add arbitrary properties to arbitrary things and relate them all together. Build the graph organically.
So far, its working really well. But underneath, its (likely) just a couple of b+trees do all of the heavy lifting.