What's about the 1:1 relation of components and quadtrees? I mean to create a separate quad tree for each sortable component? This solution has the highest memory cost but probably the fastest search. But the extra memory consuption is not a big deal IMHO, it's just a couple extra MB at most.
A QuadTree is a storage structure with attention to a partial neighborhood relation. By itself it is totally independent on what kind of objects are stored. Any higher level of abstraction can use (its own instance of) QuadTree to manage its belonging objects. For example, a sub-system that manages the Listener (meaning a simulated hearing) component can check for spatial vicinity by utilizing a QuadTree; the Collision sub-system can manage a set of colliders by utilizing a QuadTree (where a collider itself refers to Collision component); the lighting sub-system manages lights in a QuadTree; and so on. However, in an implementation where separation of concerns are respected, a QuadTree is just an utility used behind the scenes, and there is an instance of QuadTree for each concern. A sub-system provides services on its interface, and whether it used a QuadTree or whatsoever is irrelevant from a clients point of view. Doing this allows to change internal implementations when necessary without impact on the clients.