Add indexes

[GGAlanSmithee]

Indexes

Equivalent of a SQL column index. A new feature which enables the user to add an index to a component, which would - in theory - speed up querying entities with the index.

I am thinking of something in the lines of:

entityManager.createIndex('comp1')
entityManager.createIndex('comp2')

entityManager.getEntititesByComponents('comp1', 'comp2') // sped up, because of indexes

Thoughts on a possible implementation

1. create per-component indexes (a list of entity ids)

const indexes = {
    'comp1': [ 1, 3, 6, 14, ],
    'comp2': [ 3, 6, 7, 14,  18, ],
    'comp3': [ 6, 14, 25, ],
    'comp4': null,
}

2. When fetching entities, look for indexes and use them to invalidate entitites (todo: find a fitting algorithm with a low time complexity)

Caveat

It's not unlikely that the additional overhead of indexes would negate any possible wins, in which case a cache-based system would be preferable, (see #79)

[GGAlanSmithee]

Another kind of index (for getting entities by components)

Using binarhy-search, we can add an index for a component, like:

entityManager.addIndex(myComp, (a, b) => {
	if (a[posKey].x < b[posKey].x) return -1
    if (a[posKey].x > b[posKey].x) return 1
    if (a[posKey].y < b[posKey].y) return -1
    if (a[posKey].y > b[posKey].y) return 1
    return 0
})

Which could then be used for fethcing an entity by a component. This have some limitations though, since the index would have to be very specific, and it's not obvious to me where it would be used (internally).

To be effective, sorting the index would have to be done eagerly, ahead-of-time, which would force us to housekeep these indexes, so this have the same problem as the above solutions, even if this solves a different use-case.