Electronic Health Record (EHR) data is being required to be shaped into a standardized and interoperable format for easy and secure accessing from anywhere, towards the vision of a borderless Health Information Exchange (HIE). Towards this vision, EHR data is being securely stored in different cloud repositories, making it however difficult and time-consuming to access it in emergency cases from healthcare practitioners, or even from the owners. In order to access the EHR data, it is needed specific credentials and real-time approved consent, which cannot be feasible in cases where this data must be urgently accessed and furtherly processed. In this paper, a health record indexing methodology is being proposed (i.e. HR index) that facilitates the real-time accessing of non-privileged users, to the cloud stored EHR data of citizens who are facing emergency situations. In this context, the research that has been conducted prior to specifying and designing the proposed HR index is being provided, including a detailed study of data and health data indexing techniques and methodologies. The overall vision, scope and usage of the HR index is provided in the context of an Emergency scenario, concluding to the design and evaluation of the HR index, under specific circumstances and requirements.