The inverse is also true, often you have linear or even quadratic lookup times when something like an index can give you the result "immediately".

I wish languages other than SQL had a concept of adding an index. Imagine a variant of Python's list or C++'s vector where you can add indicies on arbitrary fields of the contents, like a more flexible dict. Something like (pseudocode)

    books = List<Book, indices=[Book.title, Book.author]>

and then you could up by title or author without traversing the whole list. Sure you can just use a separate dict, but then you have to keep both in sync, it is harder to bind it to UI controls, and so on.