Prev: Data Representation in COBOL
Next: xml acucobol
From: Michael Wojcik on 17 Jan 2006 12:57

In article <11sl2u4ans1jo34(a)corp.supernews.com>, "Rick Smith" <ricksmith(a)mfi.net> writes:
>
> "Michael Wojcik" <mwojcik(a)newsguy.com> wrote in message
> news:dqdtg901874(a)news1.newsguy.com...
> [snip]
> > (And I certainly wouldn't try to teach B-trees, or B+trees, in COBOL;
> > they're not a natural fit and they're outdated.)
>
> If those trees are *out*, what's *in*?

Actually, on reflection, I'll qualify that: B+trees are outdated for
in-memory indices. They're still popular for external indices, as
far as I can tell, though there are competitors such as extendible
hashing.

For in-memory indices, the current favorite is red-black trees, I'd
say - at least they have been favored more recently than B+trees. In
the late 1980s, B+trees were considered pretty much state of the art
for balanced trees, as far as I can tell. AVL trees and red-black
trees (RB-trees) were also known (they predate the B-tree family),
but the former require too many rotations in the worst case to be
practical for many applications, and the latter were not as general
as B-trees and had slightly greater storage requirements, as they're
strictly binary (only one key and two links per node, whereas B-trees
have M keys and M+1 links).

With changes in available resources, the tradeoffs of RB-trees are
now generally more favorable than those for B-trees. They're also
widely available thanks to two major sources: libavl and the C++
standard library (which all but mandates them).

Red-black trees are basically an alternate representation of the
structure of a 2-3-4 tree, which is a kind of B-tree, and I suppose
some people might consider RB-trees just B-trees in a special
representation; but since the implementations are very different,
they're better treated as a different data structure (particularly
for educational purposes, which is what this thread is ostensibly
about).

--
Michael Wojcik michael.wojcik(a)microfocus.com

Web 2.0 is ... like talking to people - without the pesky annoyance of
other people. -- Martin Wood
First  |  Prev  | 
Pages: 1 2 3 4 5 6 7 8 9 10
Prev: Data Representation in COBOL
Next: xml acucobol