Methods that can parallel search a partitioned data set extended (PSDE) indexes are provided. One method includes managing a set of quick indexes in a memory device in which the set of quick indexes include references to storage locations for a subset of members of a PDSE stored in a set of long-term storage devices. The method further includes receiving a request to determine a storage location of a member of the PDSE and, in response to the request, searching the set of quick indexes to determine the storage location. Systems and computer program products for performing the above method are also provided.