# How does EVM search in the storage?

It says that each smart contract has an (independent?) storage and "This storage can be thought of as a very large array, initially full of zeros. Each value in the array is 32-bytes wide, and there are 2^256 such values". Since 2^256 is an enormously high number and each (I suppose only "full") node has to store the same data for each deployed contract I assume only nonzero values are stored. Then how does EVM search for a needed value in the storage? Are the non-zero values ordered increasingly and EVM uses binary search? I probably need a deeper understanding of how computer memory works in low level. If that is the case, is there any accessible article on this topic?

• The article you linked describes how this works :) Read down to the "Locating Fixed-Sized Values" section May 22, 2020 at 6:05
• I have read the whole thing. The problem arises when we locate dynamical sized values though, because we use hash to find the place to store the value. The hash can be very big, so the memory band would be (even astronomically) big. May 22, 2020 at 7:05
• and there would be a lot of zeros (empty spaces) in between the stored values May 22, 2020 at 7:27
• You (or article) is mixing up ethereum.stackexchange.com/questions/1232/… Storage is like a hashtable and is not a contiguous array.
– eth
May 23, 2020 at 8:33
• thanks for the answer, but isn't hashtable still an array where the index is hash of the key? May 24, 2020 at 10:17

Just to be clear, this is about the actual, real implementation of the EVM rather than its more abstract definition. A program running on the EVM just uses the `SLOAD`/`SSTORE` instructions as if really had 2^256 words of memory for storage.
In EVMC, you can find a very simple example implementation for the "host", which handles storage, that uses `std::map` from the C++ STL (usually implemented as a balanced binary tree). This lives on memory - in reality you probably want something like a database that stores things on disk if you're running a node.