btree vs binary tree

From	Melzzzzz <Melzzzzz@zzzzz.com>
Newsgroups	comp.programming
Subject	btree vs binary tree
Date	2018-03-15 04:52 +0000
Organization	albasani.net
Message-ID	<p8cu67$bm2$1@news.albasani.net> (permalink)

Show all headers | View raw

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 ;(

-- 
press any key to continue or any other to quit...

Back to comp.programming | Previous | Next — 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