I cannot recall where I read about this approach so apologies to the originator for not granting credit where it is due.
A long piece of rock (or other material) can be used to encode a huge amount of data with just one mark.
You need a long flat rock and the means of measuring length very accurately. **
First, encode data as a string of bits.
Then take that enormous binary string and treat it as a really big number X and put the mark to divide the length of the rock into the ratio 1:X
The accuracy limits will be governed by the size of the rock, thermal and other causes for expansion/contraction and deformation and (depending on how accurately you make the cut / how much compression you want to achieve) quantum effects on the fine grained positioning.
Multiple marks on the same rock provide extra "layers" of recording.
Just imagine - the whole of Slashdot's debates reduced to a single scratch ;-)
** Actually you need a means of defining what you mean by length first - take into account surface irregularities... [cf lengths of coastlines - thanks Mandelbrot!!]