Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #8477

Re: btree vs binary tree

Show all headers | View raw

In article <p8cu67$bm2$1@news.albasani.net>,
Melzzzzz  <Melzzzzz@zzzzz.com> wrote:
>I am playing with different implementation of binary trees, and compare
>to btree that is provided in Rust. btree blows out of water any binary
>tree regarding cache performance. eg just iterating through btree is
>order of magnitude faster then binary tree.
>So question is : Why implementations use still red black tree for maps
>instead of btree (eg C++)?
>I can think in direction to make binary trees more cache friendly but
>this is difficult. Just using btree is much more efficient on current
>hardware ;(

Most of them still use RB trees, but they do so for a reason.

Btrees are indeed more cache efficient. However, they require
movement of data to split and rebalance nodes; this can invalidate
iterators, which violates the C++ standard for e.g. std::map and
std::set.

Rust has more precise semantics with respect to ownership, lifetimes
and borrowing, so can statically guarantee that an iterator to some
node in a btree (which would presumably require borrowing an immutable
reference to the tree) doesn't exist at the same time that a node
is being inserted into that tree (which would require a mutable
reference). At least, this is true with the usual caveats about
unsafe code, etc, etc.

C++ can't make that sort of guarantee, so C++ uses a different data
structure: if I have an interator that points to a node in an RB
tree, then even if I rebalance the tree to maintain the RB invariants,
I'm I can still safely indirect the iterator to manipulate that
node.

        - Dan C.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

btree vs binary tree Melzzzzz <Melzzzzz@zzzzz.com> - 2018-03-15 04:52 +0000
  btree vs binary tree Chad <cdalten@gmail.com> - 2018-03-15 14:27 -0700
    Re: btree vs binary tree cross@spitfire.i.gajendra.net (Dan Cross) - 2018-03-16 15:13 +0000
  Re: btree vs binary tree "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2018-03-16 21:51 +0800
  Re: btree vs binary tree cross@spitfire.i.gajendra.net (Dan Cross) - 2018-03-16 15:06 +0000
    Re: btree vs binary tree Melzzzzz <Melzzzzz@zzzzz.com> - 2018-03-16 15:30 +0000
      Re: btree vs binary tree cross@spitfire.i.gajendra.net (Dan Cross) - 2018-03-16 18:20 +0000

csiph-web