Any Dimensional Quad-Tree

storing fixed size tuples shouldn’t be too hard. the “best” graph databases on the market fails anyway. For 3-tuple they need to store $P(3,3) = 3 \cdot 2 = 6$ copies of data. For 4-tuple, $P(4,4) = 24$ copies - wait, they don’t even support 4-tuple. *whimpers*

combinatory explosion. not very efficient. also, we need to get that 8-tuple in here.

2D quadtrees are used in games a lot for efficient spatial lookups - “efficient” as in “more efficient than storing everything in an array”. most implementations can’t be balanced on the fly, so that’s a problem we should solve before we put this into a production database.

attempting to balance this tree

i used a 2D quadtree to test this idea before we generalize this to higher dimensions.

the initial idea was to move where the quadtree is split. This might work, until it doesn’t.

it doesn’t.

ok. new plan. we treat this as a BSP tree and balance it that way.

it works. now it’s not a quadtree. we can assign AVL weights (-1, 0, +1) to every node, but like, there is no simple “rotate” here. I guess that isn’t so much of a problem? Well, this is either not too much of a problem or the reason why people don’t put BSP trees in databases.

what if we cut the space diagonally

So I have the strange idea of making the tree cut diagonally. Strings can be treated as rational numbers (0x0.data here) anyway.

The idea comes from the observation that in a graph database, we will see data like this:

(a x 0)
(a y 1)
(a z 2)

If we cut along the first axis, it just makes the tree deeper for no benefit at all!

It makes scanning along an axis more complex though.