Additionally, it's provable that in the context of a physical computer, no data structure actually has O(1) read / write / anything performance over an arbitrary amount of data.

Consider that the universe enforces both a maximum information density per cubic meter, and a maximum speed at accessing a given physical location.