It is interesting to note how practical data structures have evolved over the last 20 years, since this paper was written. Balanced trees were pervasive back then and the primary workhorse in all database systems I designed or worked with. Today they are rarely used in new system designs, since the practical tradeoffs started making less and less sense over a decade ago. Balanced trees have a very high space overhead that becomes prohibitively costly as data sizes grow.
Succinct implicit tree structures are unbalanced, so in theory have higher latency variance, but they also can have a space overhead 2-3 orders of magnitude smaller. As a practical consequence, the cost of traversing a level in the tree is dramatically lower than for balanced trees. The number of levels traversed tends to be used in literature as a shorthand metric for "optimality" but it smuggles in the assumption that traversal costs are similar across algorithms in practice. Searching a nicely balanced O(logn) gigabyte metadata structure has a hard time competing with an equivalent unbalanced tree that fits the metadata entirely in L2 cache, even when the tree is very unbalanced (and the average case is much better).
I am not entirely sure when I stopped using balanced trees. I went from always using balanced trees to never using balanced trees, gradually over many years.