Suggestion: BTreeMap/BTreeSet O(log(n)) n-th element access reads like "we can't do O(log(n)) so that's that".
Maybe we can't improve the order of complexity but we can improve the constant factor.
At a minimum we know the size so we could iterate from the nearest end halving the time.
Could we also skip up to 2B of leaf nodes at a time rather than iterating through each one individually?
I'm curious what's the best we can do without converting BTree into an Order statistic tree - Wikipedia?