Maritime trajectory modeling is crucial for ensuring the safety and efficiency of maritime transportation. However, the unique challenges of the open ocean-such as the lack of a pre-determined road network and infrequent vessel interactions-render traditional land-based route prediction systems inadequate. To overcome these obstacles, we present ST-Shape, a spatio-temporal trajectory indexing method designed to swiftly retrieve pertinent historical maritime trajectories, thereby facilitating long-term trajectory prediction. ST-Shape approximates trajectories using two-dimensional polygons and constructs the index with shape indices, thus preserving the spatio-temporal properties of each trajectory. Concurrently, we introduce a straightforward yet robust model that harnesses this indexed data to predict vessel movements. To underpin our research, we have curated a comprehensive maritime trajectory dataset from the Atlantic and Pacific Oceans, classified according to diverse navigational scenarios. Our endeavor serves as a foundational step towards expedited spatio-temporal trajectory retrieval for maritime trajectory prediction, marking a significant stride in enhancing maritime safety and navigational efficiency.