What are the most known database disk storage layout algorithms? I can list for example algorithms used in databases:


append only b-trees (MVCC like used in CouchDB)
merged logs (like used in Big Table, Hbase, Cassandra)
paged storages grouped in extents (like in InnoDB engine of MySQL)
fractal trees (like used in TokuDB engine of MySQL)


Are there any others? similar or totaly different?
The Fractal Trees I have seen overviewed in Tokutek talks are Cache-Oblivious Lookahead Arrays (COLAs), which are at the intersection of two motivating storage layout ideas. If you're looking for similar layouts, you might be interested in them:


Decreasing insertion time at the cost of increased search time. See Buffered Repository Trees and $B^{\epsilon}$ trees.
Cache-oblivious data structures.


The COLAs paper discusses another data structure at this intersection, as does a more recent improvement.

Implementation-wise, I only know of one other DBMS that uses cache-oblivious data structures: EaseDB, which is in-memory and appears to no longer be under active development.