The Internet of Medical Things (IoMT) is an important application of the Internet of Things in health care. In IoMT, efficiency and user privacy are crucial for cloud storage and retrieval of healthcare data documents. Existing schemes, however, often suffer from inefficient retrieval and increased risk of privacy disclosure when dealing with massive data. We propose here a new Efficient Encrypted Parallel Ranking (EEPR) search system, block-based and privacy-preserved, for encrypted cloud healthcare data. We design a parallel binary search tree structure in block and propose a parallel retrieval algorithm adaptable to such a structure. A quantitative analysis through the information retention index shows that our scheme demonstrates better search performance. In addition, feature vectors generated from our scheme are difficult to be reversely analyzed due to unexplainability, enhancing privacy protection for patients and researchers. A formal security analysis shows that our EEPR scheme is resistable to known background attack, and yields a lower time complexity and significantly improves search efficiency as well as accuracy over existing schemes.