Re: Ben Pfaff's Paper Comparing AVL, Red-Black, And Other Trees.
- From: cri@xxxxxxxx (Richard Harter)
- Date: Sat, 23 Aug 2008 16:01:46 GMT
On Thu, 21 Aug 2008 14:39:42 -0700, Ben Pfaff
<blp@xxxxxxxxxxxxxxx> wrote:
cri@xxxxxxxx (Richard Harter) writes:
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.
Is that different from a B-tree?
It might be. :-)
B-trees are an obvious path to improved locality and I should
have thought of them when I posed the question. But I was
thinking more like this:
Suppose we are building some kind of tree structure. A tree
basically is a collection of nodes, where a node typically has
key and data information, children links, and perhaps some other
links. When we insert or delete items in a tree we call little
routines that have names like getnode and freenode that do the
obvious.
When I write a tree manager of some kind I usually have a little
node manager that has a getnode and free node as an interface.
The usage looks like:
node = getnode();
freenode(node);
The routines are written for efficiency and use the usual tricks.
It is only recently that it occurred to me that there is a
problem with this approach. (I'm rather slow sometimes.)
It's fine in an environment where all memory accesses have about
the same cost and not so fine in environments where you have
tiers of caching because you want children near their parents for
fast tree traversal. To do this we need to tell getnode where
the parent is, e.g.,
child = getnode(parent);
In addition we need a getnode that can deliver a node "near" the
parent most of the time. Of course it still has to be very fast.
So my question really is: Is there stuff out there on building
this kind of node service, and is it 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.
.
- References:
- Re: Ben Pfaff's Paper Comparing AVL, Red-Black, And Other Trees.
- From: Richard Harter
- Re: Ben Pfaff's Paper Comparing AVL, Red-Black, And Other Trees.
- Prev by Date: Re: Ben Pfaff's Paper Comparing AVL, Red-Black, And Other Trees.
- Next by Date: Re: question on relativization of an algorithm
- Previous by thread: Re: Ben Pfaff's Paper Comparing AVL, Red-Black, And Other Trees.
- Next by thread: extra income
- Index(es):
Relevant Pages
|
