Ethereum Storage (or Storage) is a key/value store where keys and values are both 32 bytes. It is sparse (like a hash table), and there are no inherent gas savings from having two 32 byte values next to each other. Storing one of the values at key 1 and the other at key 1000, costs the same amount of gas as storing them at key 1 and key 2. (Gas savings from packing storage are still possible, such as fitting 2 uint128
values within a single key, instead of using 2 keys.)
Storage gas costs are primarily: 20,000 gas when a value is set to non-zero from zero; 5,000 gas when writing to existing storage or setting a value to zero; and a 15,000 gas refund when a non-zero value is set to zero.
See: Ethereum Memory
Source: https://ethereum.stackexchange.com/questions/1232/difference-between-memory-and-storage/1235