Lets say you have a large grid. You have objects that operate on sets of points. Presumably the reasonable way to implement this to have reasonable performance at runtime (namely say reasonably sized grids for games), presuming memory is available is that:
You have pointers to every object that operates on a particular point for every point.
Let us presume that however that the precision of the grid is prohibitive and you don't want to store pointers for every point, presumably you would implement something like:
Split the grid hierarchically
The next question is, what is the best way to find subsets of a space containing a point in a set of said subsets?
Perhaps:
One can either do a naive selection search (N) through the entire set or one can index origin/inverse pos axes and then do an intersection of matched ranges.
With regards to indexing of properties of objects stored in memory datastructures, one can presumably optimally implement:
Maintain B-Tree index on object properties Search indexes and do intersect/union for queries
So essentially this is a question as to whether:
- Did I miss something about requesting this sort of information from a grid?
- How one generally goes about implementing in-memory indexes (though of course they are probably only useful with a large set with small ranges, considering the intersection would be huge cost?)
Sorted String Table (SSTable) or B+ Tree for a Database Index?
There is that thread. I don't understand how they are storing an index in what appears to be something like an array. How do they get around the N cost of insertion/shifting into the middle of an (dynamic/on disk) array?
