Earlier quoted context omitted.
Chasing pointers (on the same medium) is usually slower than the access patterns that databases usually use. First, a database can have hash indexes instead of btree indexes, so lookups can be O(1) too, but it turns out that btrees are often better because they can return range results efficiently, and finding the range in a btree is only logarithmic for the first lookup. If your index is clustered - if it covers the…
Depends a lot on the actual access patterns of your data. Many recent web & mobile apps have a lot of screens where you just want to grab one blob of heterogenous data and format it with the UI toolkit of choice. Or if they do display multiple results, it's O(10) rather than O(1000) or O(1M). Chasing pointers is fine for use-cases like this, because you do it once and you have all the information you're looking for.…
The application I work on in my day job does not match the key/value lookup idiom at all. User-defined sorts and filters over user-defined schema, and mass automated operations over data matching certain criteria. If you squint a bit, the app even looks a bit like a database in terms of user actions.
And even relational databases (at least row-oriented with primarily disk storage) have their limit here. With increasing volumes of data, it can't keep up. We can't index all the columns, and indexes can't span multiple tables. We increasingly need more denormalization solutions that convert hotter bits of data into e.g. in-memory caches that are faster for ad-hoc sorts and filters. Database first is a decent place to start, though having a first-class event feed for updates would certainly be nice...