linear storage literally implements operational semantics, but has O(N) lookup and uses space very ineffectively, as it is implemented as a list of assignments.

sparse storage is slightly more efficient storage, in comparison with linear. It uses balanced tree data structure, and provides logarithmic lookup and update method.