[Flow]

I've read your first link and I don't get why you talk about "A relational database needs to store rows in order". AFAIK you have to add an "order by" clause to ensure ordering of any kind.

Relational algebra is probably not dependent of ordering for the common operations. Of course, the actual implementation of a relational database might need ordering of keys to be reasonably efficient. Is that what you meant?

[Millennium]

The question is "what in order" means. The DB needs to store rows in some order that makes sense to it, but that might or might not match whatever order a user might want.

That's where ORDER BY comes in: presenting the data in some order that makes sense to the user. That might be completely different from what's stored in the DB. But the DB needs its own order, in order to be able to access things in a reasonably efficient manner.

[Millennium]

To put it another way, the SQL standard doesn't guarantee any particular ordering. This does not mean that table storage must be unordered: it means that a database can store them in any order it wants, which might not be any order at all, or it might have some particular kind of order which the DB depends on to do its work.

But as a database user, you cannot count on that order matching what you, personally, would have implemented if you'd had a chance. ORDER BY clauses allow you to tell the database to sort the results of a query according to something appropriate for your particular needs, but this has no effect on how they are stored.

[gtrubetskoy]

It needs to store rows in order to support indexes, so that a row could be found without having to scan the whole table, and that's exactly what B-Trees let you do, and also add or remove rows without having to rewrite the whole table, but only affected blocks.

[Flow]

What you say, isn't that more or less exactly what I wrote?