The purpose behind the software (from the authors point of view) can be found here: http://www.gnu.org/software/recutils/manual/Purpose.html#Pur...

It's practical for many use cases where that doesn't matter. Keeping track of your personal book collection is good, your bank's online transaction processing system probably not.

I can think of two scenarios (they overlap):

1. Reference data (countries, car makes and models, zip codes, tax rates, etc)

2. “Human scale” databases - ie stuff that a small group of people are manually curating

O(n) would probably be fine for either of those.