Re:Ask HN: What are some cool but obscure data structures yo...
by artemisart on Friday July 22, 2022 @06:14PM
(#32197750)
Cache oblivious data structures are absolutely used in every serious database.
From what I remember/can find online (don't take this as a reference):
B-tree: relational DB, SQLite, Postgres, MySQL, MongoDB.
B+-tree: LMDB, filesystems, maybe some relational DBs.
LSM trees (Log-structured merge tree, very cool) for high write performance: LevelDB, Bigtable, RocksDB, Cassandra, ScyllaDB, TiKV/TiDB.
B-epsilon tree: TokuDB, not sure if it exists anymore.
COLA (Cache-oblivious lookahead array): I don't know where it's used.
Maybe modern dict implementations can qualify too, e.g. Python.
From what I remember/can find online (don't take this as a reference): B-tree: relational DB, SQLite, Postgres, MySQL, MongoDB. B+-tree: LMDB, filesystems, maybe some relational DBs. LSM trees (Log-structured merge tree, very cool) for high write performance: LevelDB, Bigtable, RocksDB, Cassandra, ScyllaDB, TiKV/TiDB. B-epsilon tree: TokuDB, not sure if it exists anymore. COLA (Cache-oblivious lookahead array): I don't know where it's used.
Maybe modern dict implementations can qualify too, e.g. Python.