> The problem with a "pointer" like this is that you then can't move stuff around as easily

You can, it just requires one further level of pointer indirection. Rather than pointing to the physical location of the data, you store a pointer to an offset in an array of pointers.

Alternatively you can point directly if you're prepared to update those pointers when you move things around. Luckily a graph database is ideally suited for this kind of operation because it makes discovering those pointers exceptionally simple and efficient.