Re:Apple Developer Documentation Is Missing
by fnord123 on Monday October 28, 2019 @07:29PM
(#21382900)
>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:
Interval trees reduce to Binary Search Trees when the nodes can't overlap. Most markup DOMs (in browsers, WYSIWYG editors, etc.) are held as an Interval-tree ADT which is actually implemented by a BST.
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.
But yes, DBMSes themselves don't tend to use BSTs for much. Maybe as a query-plan-AST term-rewriting-phase ADT.