Re: Ben Pfaff's Paper Comparing AVL, Red-Black, And Other Trees.

On Thu, 21 Aug 2008 11:38:51 -0700, Ben Pfaff
<blp@xxxxxxxxxxxxxxx> wrote:

Le Chaud Lapin <jaibuduvin@xxxxxxxxx> writes:

I'm having trouble (re) finding his paper if anyone would be so kind
to provide a link.

http://benpfaff.org/papers/libavl.pdf

As a matter of curiousity is there any work on arranging trees in
blocks, with a view to improving locality. That is, the space
for nodes is allocated in blocks large enought to hold, say, the
children, grandchildren, and great-granchildren of a node. When
we traverse the tree we make one fetch of 14 nodes in one place
rather three fetches of 1 node each from different places. There
are obvious variations on the theme. My question is whether
people do this sort of thing and whether it is worth doing.



Richard Harter, cri@xxxxxxxx
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
.