Assume there was a database system that had a data type called VARINT or some variant that allowed instead of fixed-length INTs regardless of value, a 1 would only take 1 BIT (1), 2 would take 2 BITs (10), etc.In this perfect world, a VARINT could be used to autoincrement a PRIMARY column.  However, there's still the issue of the field growing in size, so the older parts of this TABLE would be very fast, but the younger parts would get slower and slower.What counting system could be used to hold the space consumed constant and small or at least grow at a much slower rate?
VAR autoincrement with constant space consumption for super large tables
integers;database theory;performance
If you want an ID (i.e. unique label, whether number or not) which is stored as a binary (or $k$-ary) string you will have at least logarithmic growth, because with $o(\log n)$ bits you can't identify more than $k^{o(\log n)}=o(n)$ objects. So you can't do much better.You could however map the old IDs to new IDs every time the size of the table doubles. If the entry #$2^m$ is inserted, the old IDs become $\mathrm{id}'=2^{m+1}+\mathrm{id}$ and the younger elements get shorter IDs. This only works if you don't use the IDs elsewhere (major drawback for a PRIMARY) and you have a reason to believe that newer entries get requested more often than older ones.Finally one may ask whether you really need big integers for some kind of ID. According to this there are $\approx 10^{80}\leq 2^{267}$ atoms in the observable universe, so a kilobit sized ID will do for most purposes.