Indexes: look up entities by the value of their components

[alice-i-cecile]

What problem does this solve or what need does it fill?

An "index" is a way to quickly find entries based on their value.
In the context of an ECS, indexes would let us e.g. "find all entities with components of this enum value", identify all entities inside a spatial region using a quadtree on Transform, quickly look up entities by their Name, or filter entities to find all components whose value lies within a range.

What solution would you like?

Provide a native, efficient, fool-proof indexing solution.
Ideally, this should be user-extensible to account for other forms of acceleration data-structure.
This will be naturally coupled with change detection to ensure efficient updating.

The design of this is rather challenging, and requires a full RFC.

What alternative(s) have you considered?

Linear time search will always work... slowly. Parallel query tools will help though.

Users can hand-roll this themselves right now, using a resource and Query::get. This is not particularly ergonomic, requires writing a lot of boilerplate, forces users to duplicate the API work for each project, and forces them to reckon with the perils of synchronization alone.

Additional context

May be useful for #3742. Would be useful for #1470. #1205 discusses some of the challenges and possible designs for data synchronization.

[laundmo]

I just released a crate which would benefit a lot from some better way of integrating with bevy: https://crates.io/crates/bevy_spatial

[alice-i-cecile]

Immutable components (#16208) + an easy way to mutate these values while triggering hooks / observers (mutate_via_reinsertion?) completely solves the data-validity problem here. With those in place, all we need to do is build a nice API.