Does a universal index exist?
One can show a lower bound for the data structure you are asking for under the Strong Exponential Time hypothesis. In particular, if all the entries have one bit, then one can use the data structure to do subset queries: i.e the data structure stores a family ${\cal F}$ of $N$ sets, each of size at most $k$. Then, the user may make "subset" queries - give a set $S$ and ask whether there is an $X \in {\cal F}$ such that $S \subseteq X$.

Such a query can be supported if we have a "universal index" - if we look for the lexicographically first entry coming after $S$, where we sort first by the columns where $S$ is $1$ and then along the ones where $S$ is $0$ then any element appearing after $S$ according to this order must be a superset of $S$.

Now, subset queries are equivalent to "dot product = 0" queries from this awesome answer by Ryan Williams - go read it. I will just summarize the effects of this answer on the universal index problem; assuming the Strong Exponential Time Hypothesis one can't support queries with running time $O(poly(k)N^{0.99})$, even if the family ${\cal F}$ is given in advance and we only have queries of type $3$ (i.e the data structure is static), and we have $poly(N,k)$ pre-processing time.