Any Dimensional Linked Graph

This idea comes before the tree idea.

Yes, I really want to store tuples efficiently.

This is a linked list. You know this.

This is a linked graph, where each field of the tuples is ordered differently.

To search a field faster, upgrade that field’s linked list into a skip list. You can do the upgrade only for the fields that you need to search through. Scanning doesn’t need skip list.

Spacetime Complexity

$n$: number of tuples; size of the dataset
$m$: number of fields; tuple size

space: $O(m \cdot n)$
search: $O(n)$ (linked list) or $O(log(n))$ (skip list)
sequential scan: $O(1)$ per element

Yes, this is clearly better than the tree idea.