We’ve hit a bit of a wall with Dragginz and need some help with a suitable data structure.
We have built a database system that utilise multiple B-Trees to partition data on a per-entity basis. You define your entity like this :
We have automatic fixture data creation, lexicographic sort keys
the B-Tree key is Vec<(String, Vec)> so you can nest entities (as denoted by the sk sort key line in the above schema.) This is great if you want to query a Character, their Pets, their Pets inventories etc.
We’re at the stage where we need to start storing data spatially, and then query the backend to get a list of all the 3d boxes that bound a certain point. I’ve looked at Spatial hashing (seems to be fairly complex to get right with a big world), and R-Trees but there’s no ic-stable-structures implementation for an R-Tree (not exactly low hanging fruit.)
The issue is that I can’t do range queries on compound keys because B-Trees do not work that way. Hadn’t given it much thought and found out the hard way that our design for the 3d chunk data would not scale.
Note I added indexing but that’s not working yet. That was an attempt at a possible solution, but right now I’m not sure whether we need secondary indexes.
Wondered if anybody was working on anything similar, or had advice. Thanks!
I could just store the boxes in a B-Tree and read them into a R-Tree as a lazy static method?
That would be fine on init, but on upgrade I guess the structure would be empty… so we’d have to have a flag like is_populated and if that’s false we read in the data.
There aren’t any upgrade hooks right? You have to do that manually?
Yeah Im not sure. The issue is that everything’s generated by macros so I can’t really have more than one B-Tree for data. I’m going to hack at the rstar crate and see what happens.
