Continuously generated volumes of health data make healthcare a data-intensive domain. This data needs to be collected, stored, and shared among different healthcare actors for various purposes, such as reporting, analysis, collaborative research, and personalized healthcare services. However, the existing data storage and exchange solutions in the healthcare domain exhibit several challenges related to e.g., data security, patient privacy, and interoperability. Recently, the industry and research community turned its focus to the possible use of blockchain technology to solve some of these challenges in the healthcare domain. The blockchain technology along with the support from smart contracts is considered a salient facilitator for secure and efficient health data sharing. This is due to its unique features, such as decentralization, trustlessness, immutability, traceability, and transparency. In this paper, we provide a comprehensive survey of the state-of-the-art efforts that envision the use of blockchain-based solutions in the healthcare domain. To this end, we introduce a systematic framework for classifying and analyzing such systems. The framework consists of classification in several dimensions: interactions between healthcare entities, functional components of healthcare storage systems, challenges in the healthcare domain that can be overcome by using the blockchain technology, and benefits for healthcare storage systems derived from the fundamental features of the technology. When analyzing over 40 systems and solutions proposed in the state-of-the-art, we perform their rigorous placement by identifying the exact scope of each solution and mapping it to the above taxonomies of interactions, functional components, challenges, and benefits. We additionally provide an extensive discussion of compliance with privacy-related regulations of General Data Protection Regulation (GDPR) in EU, and Health Insurance Portability and Accountability Act (HIPAA). Following the results of the analysis, we have outlined a number of important research gaps and future directions yet to be addressed.