Place the new data key where it should be. Now create another index block that will be used as a root in a kind of tree structure. Now update the header record with the relative record number of this new root block. The recommendation is that it be sized to match the data block for the same reasons that the data block size was selected. Whenever direct access is needed, one or two seeks will produce the record.
Maintenance is predictable.
Key sequence access is possible without excessive overhead. No sorting is required. First, a header record with a pointer to the root of the index must be maintained. Secondly, the program must manage the data blocks and keep them in key sequence. Thirdly, the program must manage the index blocks and keep the maximum keys in order within the block.