[nixme]

Simple explanation: Most database indexes are forms of B-trees. Insertion into a binary tree isn't constant time O(1), it's usually O(log n).

[jbert]

Thanks, I was thinking in terms of hashes (which doesn't really make sense for searching/ordering).