Box2D is a well optimized engine designed by an experienced physics/game programmer. Originally Box2D used a hash grid that required a fixed height and width.
When Erin upgraded to a better broadphase algorithm he went with Nathanael Presson's btDbvt. This is the broadphase used by Bullet Physics. Erin modified and optimized the algorithm for 2d.
You can read a super high level overiew in the Box2D manual ( §4.11, or search for Dynamic Tree).
Here's an except from the in code documentation (which is very good considering it's not part of the public API).
A dynamic AABB tree broad-phase, inspired by Nathanael Presson's
btDbvt. A dynamic tree arranges data in a binary tree to accelerate
queries such as volume queries and ray casts. Leafs are proxies with
an AABB. In the tree we expand the proxy AABB by b2_fatAABBFactor so
that the proxy AABB is bigger than the client object. This allows the
client object to move by small amounts without triggering a tree
Nodes are pooled and relocatable, so we use node indices rather than
My understanding of the Dynamic Tree's algorithm is this. The Dynamic tree is the cross between a classic avl binary tree and a quadtree. The end effect is a quadtree that that only splits each node in half, and the split line isn't fixed (the two halves aren't equal sized like a quad tree). AVL comes in because quadree with dynamic splits can degenerate to essentially a list (O(n) lookup speed). The AVL is used to rebalance subtrees so to ensure O lg(N) lookup speed.
Best of all the code is MIT so feel free to copy / derived / shamelessly-steal / etc.