[c0deb0t]

For binary trees, indexing can be done by saving the subtree size of each node and doing a sort of binary search. Not sure if this is fast for B-trees that have more than 2 children nodes, though.

[Lichtso]

Do you mean OSTs?

https://en.wikipedia.org/wiki/Order_statistic_tree