OSEC

Neohapsis is currently accepting applications for employment. For more information, please visit our website www.neohapsis.com or email hr@neohapsis.com
 
Subject: Re: B-Tree vs Hash
From: Bennett Todd (betrahul.net)
Date: Wed Apr 12 2000 - 14:43:57 CDT

2000-04-12-15:11:25 Chris Horry:
> It's never really occured to me that there is a difference between
> the two, all I know is that B-Tree is a newer system. The boss
> just asked me why one and not the other.

Hash tables are one popular structure for efficiently storing and
retrieving values by arbitrary keys. They have some difficulties ---
care is required to produce graceful behavior as the table size
grows by orders of magnitude. Hash tables are intrinsically
unordered. Well implemented, a hash table can _look_ like constant
time ("O(1)", in computer science lingo) for lookups as well as
stores, but when you take into account the table reorganizations
required to support gracefully growing the table over a wide range
of sizes, they end up degrading to O(logN) at best.

Balanced Trees (b-trees) are another popular data structure for
key->value mapping. They're traditionally more popular with the
database crowd than the systems programmers, although I'm not really
sure why. They are clearly and plainly O(logN) for pretty much
everything, with an obscure footnote that sufficiently pathological
input can make 'em degrade to be much worse (true of hashes as well,
and given good implementations this isn't a practical problem with
either data structure).

The biggest operational difference comes when you want to dump the
whole table out. A natural iterator over a hash will dump the values
in an apparently random, scrambled order, while the dump of the
b-tree will produce the keys in sorted order.

-Bennett

  • application/pgp-signature attachment: stored