4 ms·
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: r
by artemisart 4y ago
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.