>Interval trees reduce to Binary Search Trees when the nodes can't overlap. Interval trees are degenerate R-Trees which can be implemented using GiST which is

>Interval trees reduce to Binary Search Trees when the nodes can't overlap. Interval trees are degenerate R-Trees which can be implemented using GiST which is itself a btree. >Also, Red-Black trees specifically are used in many database clients to implement an in-memory write-back cache of a database table, as the combination of performance requirements for flushing batches of writes to the DB, and reading back arbitrary keys that were written to the cache, make these BSTs nearly optimal for this use-case. Got a source? I'd like to read up on this use case. >But yes, DBMSes themselves don't tend to use BSTs for much. Maybe as a query-plan-AST term-rewriting-phase ADT. Postgres' source does indeed have a red black tree in it: https://doxygen.postgresql.org/structRBTree.html https://doxygen.postgresql.org/structRBTree.html