# 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:

1. Decreasing insertion time at the cost of increased search time. See Buffered Repository Trees and $B^{\epsilon}$ trees.
2. 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.

Columnar stores. There are some great papers on the topic from the c-store project: http://db.lcs.mit.edu/projects/cstore/

The most interesting thing about columnar stores is that many operations can be performed directly on compressed data.

Append only again but with concurrency friendly caching by RethinkDB. http://www.rethinkdb.com/papers/rrcache.pdf

--Sai

There is a distinction between LSM-Tree and Log-Structured Storage: