6
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

--Sai

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy