xna - Quad Tree with a lot of Moving Objects

I have a Quad Tree implementation that is very useful for what I am trying to do. My problem is that when my viewport has a lot of objects, the Update for the Quad Tree takes a very long time.

It is a known fact that Quad Trees are slow for non-static objects. I tried a few methods to try to speed things up, but the fact is, I need to update a large number of objects very often.

Is there a better algorithm I should be looking at instead? Are there some derived Quad Tree implementations you know about that might be useful to me?

Answer

How are you moving Quad Tree objects? The simplest (and slowest) method is to remove the object and re-insert it. The open-source XNA Quad Tree me and a friend made does a little bit of logic when an object moves:

If the object is still inside the same quad
    if the object fits into a child quad

        Add to child
Else
    move the object to the parent(s) until it fits, and optionally going back down into children

If you're already doing something like that, it could be worth looking into other spatial index methods like Spatial Hashing.