System and method for content-addressable search of holographically stored data primarily optimized with respect to search performance. A search is performed, by a holographic correlator system, on a structured representation of original data, stored in a holographic data storage medium. In a first aspect, orthogonal phase encoding of both data storage and search pages provides improvement of correlator system signal to noise ratio and dynamic range. In a second aspect, correlator incorporates heterodyne detection of a plurality of correlation signals, obtained by modulation and amplification thereof by a plurality of frequency-shifted reference beams. In a third aspect, the invention provides a method whereby multiple searches can simultaneously interrogate a single data storage location.