<p>Reachability query, which determines whether a path exists between any two nodes in a graph, has been the cornerstone of graph operation research for decades. Traditional algorithms, such as depth-first search and transitive closure, are often limited by either slow query or substantial storage. Extensive efforts have increasingly focused on designing reachability indexes to balance the tradeoff between index space and query time. However, existing solutions are limited to specific tradeoff points and lack theory for adjustable, quantifiable tradeoffs. In this work, we introduce Reachability-state Encoding (RE), which adjusts the number of encoded node pairs per chunk to affect compression ratio and decoding time, thus allowing for a smooth transition between the minimal storage and the fastest query. We establish theoretical upper bounds for the minimum encoding length of RE in relation to the size and entropy of reachability-states, which quantifies the limits of compression within the encoding process and ensures superior performance in dense graphs compared to traditional methods. We have implemented a prototype algorithm, RE-toy, to validate the effectiveness of RE. Through experiments conducted on both synthetic and real-world graphs, RE-toy consistently achieves numerous optimal tradeoff points in space-time, demonstrating robust performance across graphs of varying densities. RE thus provides a practical and adaptable approach for managing the balance between storage demands and computational efficiency in reachability queries.</p>