Path: csiph.com!weretis.net!feeder6.news.weretis.net!nntp.club.cc.cmu.edu!micro-heart-of-gold.mit.edu!bloom-beacon.mit.edu!bloom-beacon.mit.edu!panix!not-for-mail From: cross@spitfire.i.gajendra.net (Dan Cross) Newsgroups: comp.programming Subject: Re: btree vs binary tree Date: Fri, 16 Mar 2018 15:06:47 +0000 (UTC) Organization: PANIX Public Access Internet and UNIX, NYC Lines: 35 Message-ID: References: NNTP-Posting-Host: spitfire.i.gajendra.net X-Trace: reader2.panix.com 1521212807 19522 166.84.136.80 (16 Mar 2018 15:06:47 GMT) X-Complaints-To: abuse@panix.com NNTP-Posting-Date: Fri, 16 Mar 2018 15:06:47 +0000 (UTC) X-Newsreader: trn 4.0-test77 (Sep 1, 2010) Originator: cross@spitfire.i.gajendra.net (Dan Cross) Xref: csiph.com comp.programming:8477 In article , Melzzzzz 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.