Yep, in that case you could use an indirection vector containing, for each key k, the offset to the first byte of k. This is what is typically done in B-trees, where the indirection vector is stored in the header of a disk page. It's described for example in Section 3.3 "Variable-length records" of Goetz Graefe's "Modern B-Tree Techniques".