I have a question to enhance a B-Tree and add a function called find(k) which gets a key – k and returns the index of it in the sorted keys of the tree, using $ O(N)$ space complexity, and it needs to be in $ O(t \cdot \log_t{n})$ time complexity. I also need to show that the function does not make the regular functions (insert, delete, split child) any different then what they used to be before ( time complexity- wise)

for example, for this tree (Only example! max degree = 3, t=2 because $ MaxDeg = 2 \cdot t – 1$ ):

find(50) would return: 6 (because its in the sixth element of the sorted keys: 10 10 20 20 20 50 60 70 80)

I thought about storing how many keys are before each key, and thus we can actually do it in $ O(1)$ but it seems unrealistic, if the question asks for $ O(t \cdot log_t{n})$

Thank you!