A compressed memory is divided into a plurality of segments, each segment is divided into a plurality of sub-segments, and each sub-segment in an uncompressed data space is compressed into block (s) in a compressed data space. Upon a read request to a sub-segment in a segment in compressed memory is received, the corresponding entry is firstly determined based on a first level address mapping between the sub-segment and the entry, and then the corresponding block (s) is determined based on a second level address mapping between the entry and the block (s). By use of two-level address mappings, the size of entry can be reduced, thereby achieving low metadata overhead. Moreover, the proposed data layout for compressed memory.