A re-recordable data storage medium is disclosed. One embodiment of the medium includes a dielectric material and a filler material. The dielectric material is organized in columnar channels over which memory cells are logically distributed. The filler material is within the columnar channels to realize the memory cells. The filler material of each memory cell has at least a first configuration and a second configuration. The first configuration corresponds to a first storable logical value, and the second configuration corresponds to a second storable logical value.