>> Heck, even RAM isn't 1.0. I'm also involved with the Redis project,
>> which is an in-memory database. Even for a pure-RAM database, it turns
>> out that just using linked lists and 100% random access is slower than
>> accessing page images.
>
> That's a slightly different problem, though. Sequential vs. random
> access is about whether fetching pages n, n+1, n+2, ... is faster than
> skipping around, not whether accessing fewer pages is faster than
> more.
It's not though. Redis stores stuff as lists and sets, so it actually
does a lot of sequential access of data. Like if people are accessing
an ordered set, they're usually pulling the whole thing. It turns out
that *even in RAM* storing stuff in an ordered fashion on data "pages"
is more efficient than just using pointers.
-- -- Josh Berkus PostgreSQL Experts Inc.
http://www.pgexperts.com