Commvault interview questions

In the first round questions were related to linked list, bst, string and so on. In the second round we were given two blocks of memory, one for data and one for index. The question was basically, to implement a very basic datebase system(they didn't tell this). The user will input a key and string pair, where key is unique. Both memory blocks are paged and the input string had a maximum size same as the page size. The index block consists of the KEY and a reference to the corresponding data in the data block(like page no and offset). User can create, and read records by key. Accessing a key from index block should not be linear(O(n)), it should faster. We were allowed to store only the page tables for each block in memory, nothing else should be stored in memory other than in the index and data block. If we were to write the two blocks to disk and then reread the key access still should be faster. My friend told me that he used b tree to solve this, I couldn't solve this.