Simple succinct dynamic predecessor with $O(\sqrt{n})$ redundancy in contiguous space

Question

A dynamic predecessor data structure supporting findPredecessor, insert, and delete over unique ordered keys in an unbounded universe in $O(\lg n)$ worst-case time can be stored contiguously using only $O(1)$ extra words of storage in addition to the storage for the keys themselves:

"Optimal Worst-Case Operations for Implicit Cache-Oblivious Search Trees", Franceschini and Grossi

The structure is complex (IMHO).

Storing $n$ keys in an array that can grow dynamically requires at space for at least $\Theta(\sqrt{n})$ additional keys:

"Resizable Arrays in Optimal Time and Space", Brodnik et al.

Given the latter constraint, is there a simpler dynamic predecessor data structure that uses contiguous space for $n + O(\sqrt{n})$ keys?

There were many implicit ($O(1)$ extra words) dynamic predecessor data structures that predate the result of Franceschini and Grossi:

"Implicit Data Structures for the Dictionary Problem", Frederickson

"Searchability in merging and implicit data structures", Munro and Poblete (does not support delete)

"Developing Implicit Data Structures", Munro

I'm wondering if it is possible to simplify even these structures by using $\Theta(\sqrt{n})$ extra space. I am hoping to find a structure supporting all three operations in $o(n^\varepsilon)$ time.

Answer 1

Pat Morin demonstrates a structure with $O(\sqrt{n})$ extra words of space and $O(\log^2 n)$ insert, delete, and predecessor search in his notes for his advanced data structures class.