It's confusing nomenclature, but Postgres' “heap” is not a heap (B-tree) data structure. It is just a bunch of blocks all on the same level, similar to how the “heap” in an operating system (as opposed to the stack) is.

Notably, you can have a Postgres table without a primary key at all, not even an implicit one.

> Based on the limited description of OrioleDB I understand it works like SQLite WITHOUT ROWID, actually storing the row tuple in the primary key b-tree, but I didn’t go read the code

This is my understanding of OrioleDB as well.