The proliferation of multi-dimensional trajectory data, fueled by large-scale IoT and the emerging low-altitude economy, particularly UAV operations, drives repositories to jointly support (x,y), (x,y,t), (x,y,z), and (x,y,z,t) queries within a single storage framework. Yet existing HBase-based systems fall short in three respects: severe row-key interval fragmentation when altitude is jointly encoded with horizontal coordinates, locality-unfriendly spatial encodings with workload-blind shape-code ordering, and coarse-grained temporal indexes that leave intra-slot boundary ambiguity unresolved. We present AeroMesa, an efficient data management system for multi-dimensional spatio-temporal trajectories built on Apache HBase and Redis, that natively supports (x,y), (x,y,t), (x,y,z), and (x,y,z,t) queries within a unified storage framework. AeroMesa addresses the above limitations through three designs: a decoupled horizontal-altitude architecture with a multi-granularity Height Spatio-Temporal Index (HTSI) that eliminates joint encoding fragmentation; Hilbert-BFS with Workload-Aware Jaccard (WAJ) reordering that improves spatial locality; and TI+, a dual-offset temporal index that resolves intra-slot false positives. Evaluations on T-Drive and an 87,537-trajectory high-fidelity UAV simulation demonstrate that AeroMesa reduces 3D/4D query latency by up to 30x over XZ3/TXZ3, lowers 2D latency by up to 17.9% over TMan, and cuts temporal candidates by up to 51.3% over MCTM, with sub-linear scalability confirmed under 200x data expansion, confirming AeroMesa's efficiency for multi-dimensional spatio-temporal trajectory management.