Binary Trees are optimal except when they’re not
While it's true that an optimal search tree will have depth , we can't just increase indefinitely, because we also increase the number of comparisons we must do in each node. If we use a naïve comparison scheme, each keys ask for two comparisons. We can therefore store the result of the expensive comparison, then do inexpensive comparisons for the result. A classical spinning rust disk reading a block will cause a few millisecond delay, that may be really, really expensive relative to the comparison of two keys in memory. With the comparison cost, and , the cost of accessing the node. *. To conclude, binary trees are optimal when we ignore the cost of accessing a node, but they aren't when it becomes costly to access a node. Disks operates on small blocks of 512 bytes, but file systems operate in somewhat larger, but fixed-sized blocks, something like 4 or 8k. A good strategy is therefore to fit as many keys as possible in that block, since even if the number of comparisons is large, it will still be faster than bringing that block into main memory.