There are data structures that are optimized for "build-once read-many". So there is definitely some value in separating out static objects from movable ones. You wouldn't use the same data structure for both, though. There are a lot of data structures out there that are optimized for different situations, so choose the right one for each case if you need optimization.

That said... if you keep your code well designed, it should be easy to swap out implementations later after you have everything built so you can test real world situations and find the data structure that works best for you.

I used to have an octree which tried to keep cells "hot" on the cache by putting in a short delay before removing a cell. The idea was that if someone shoots a machine gun with lots of little, fast moving bullets, it would be a waste of memory to delete and recreate the cells. It worked, but the implementation was messy and probably caused more overhead costs than savings. Back then, I didn't even take careful measurements of my timings, so it was impossible to know if I made an improvement or a regression.

If you really want to make a distinction between static objects and movable objects, you could just create two quad trees. One is for static objects and almost never changes, and the other is for moveable objects, which have to check against other moveable objects and against static objects.

There are data structures that are optimized for "build-once read-many". So there is definitely some value in separating out static objects from movable ones. You wouldn't use the same data structure for both, though. There are a lot of data structures out there that are optimized for different situations, so choose the right one for each case if you need optimization.

That said... if you keep your code well designed, it should be easy to swap out implementations later after you have everything built so you can test real world situations and find the data structure that works best for you.

Would you have some suggestions about data structures that could be more suitable than quadtrees for static objects?

You can use a static AABB tree if you need fast ray or AABB queries. It is possible to store the nodes in an array to improve cache performance when traversing it. I use this for generating mesh contacts in my physics engine, but I'm pretty sure it is suitable for graphics (e.g. culling) as well.

I have done some search about AABB tree and it looks promising for both static and moving objects. Are they faster than Quad Tree?

It depends on several implementation details that involves memory management, data structures, and heuristics.

You can achieve O(1) insertion with a Quadtree if you implement the optimizations described by L. Spiro in this post (originally described in GPG 4 IIRC):

http://lspiroengine.com/?p=530

but I can't talk more about this because I never needed to implement such data structure.

As for AABB trees, one detail is the way the nodes are stored in the memory. For both static and dynamic tree is possible to store their nodes in an array in an attempt to decrease memory access time when traversing the tree. For an array-based static tree the insertion is simple. But for an array-based dynamic tree the operations are not so trivial. A free list of nodes needs to be maintained in the tree for quick node allocation when inserting a new leaf. It is also recommended to inflate the node's AABB by some units such that becomes possible not re-inserting the node into the tree in a future time, when updating the AABB. For example, that could be done by checking if the new AABB is still contained in the old AABB. Another optimization is to predictively extend the new AABB by some units in the direction of motion of the object associated with the node.

Here is an example implementation if you need help implementing the dynamic tree with the optmizations/heuristics I've mentioned above:

https://github.com/erincatto/Box2D/blob/master/Box2D/Box2D/Collision/b2DynamicTree.cpp

Here are some nice slides by Erwin

https://bullet.googlecode.com/files/GDC10_Coumans_Erwin_Contact.pdf

For moving objects collision detection is always my key.

As other posters have said. It's down to what your world is.

For me in my game I'm using voxelised space to register and deregister my moving objects. It's actually just a reference count at the moment. But what it does is allow for quick eliminiation 99% of the time. From there even if i do a horrible list search for collisions then it's only on objects that have collided with something or close to.

I think your quad tree is a good idea. That's if your world is operating in 2d space. You could align your quad tree to sectors of voxel space and you could then quickly test for more detailed collisions. Be aware though. In voxelspace i test the neighbor for possible collisions. And on edge cases you might need to visit another node in the quadtree.

Youre doing the right thing anyway by minimising your potential collision sets. Have a look around at combining different ones if they can rapidly shrink your sets.

While you're looking at other data structures you should take a look at loose quad/octree's. I've forgotten much of what I had read about them but you might find them useful.

edit - This is what I had originally read in regards to loose octrees/quadtrees. http://www.tulrich.com/geekstuff/partitioning.html

I am currently finishing to implement a small prototype, and fix some bugs.

After that, I plan to run a first benchmark between a simple quadtree with all game objects and a quadtree with two layers, one for static objects and another for moving objects.

I will publish my results here of course.

Then, I will try to implement some other structures to compare their performance with quadtrees.