And in fact, some data structures that scale poorly will perform better on small sets of data.

For example, a simple list of pairs with linear lookup time can be faster than a hash table for small amounts of data, because it doesn't have to compute the hash.