3 ms·

>You need to know the principle of a BST. Unless you're building a database working in a unique scenario, actually traversing it going to be done by some librar

>You need to know the principle of a BST. Unless you're building a database working in a unique scenario, actually traversing it going to be done by some library. Looks like you got stung by the confusion between binary tree and B-Tree (and B+Trees). 1. The b in btree isn't binary. 2. Databases use B+Trees. 3. binary trees are almost worthless.

derefr 7y ago
> 3. binary trees are almost worthless. 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.
- fnord123 7y ago
  >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

derefr 7y ago

> 3. binary trees are almost worthless. 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.

fnord123 7y ago
>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