I'd expect most database lookups to scale like O(log(n)) for a lookup. For scalability I'd also mainly be interested in the case where you had enough data that it doesn't all get stored in RAM, which would require a far larger dataset than you have.