Learned index has received much attention due to its often dramatic performance and space-efficiency improvements over traditional index designs. Its strength is rooted in its ability of using computation with models or functions, rather than key search, to obtain the position of a search key in a sorted key array. However, the models or functions cannot compute the correct position without errors. Instead, they can only help determine a key scope where last-mile local search is required to find the search key. Both model computation and the last-mile search can be expensive and limit the index’s performance potential. To unlock the full potential of learned index, we propose LiBox, which groups keys in a sorted array into boxes so that (1) the box that covers a search key can be identified without any error by a linear regression function; (2) the last-mile search in the box can be conducted using only one AVX-512 instruction. A learned index based on such a box structure can be highly efficient in which each key search takes a well-predictable number of instructions and memory accesses. In this paper, we present the design of a hierarchical box-based structure. Using moderately extra space in a box to accommodate irregular key distribution, LiBox can serve both read and write queries at the speed of array reference. Libox can also flexibly align its reorganization operation with read/write intensity distribution to support high-performance read by hiding the structural modification cost. We have implemented LiBox and extensively evaluated it. The experiment results show that it outperforms state-of-the-art learned indexes, such as ALEX and LIPP, and non-learned indexes such as ART by up to 1.4 – 4.5 times with similar or higher space efficiency.