Re: all foreign key should have index?

From: David Cressey <dcressey_at_verizon.net>
Date: Fri, 03 Feb 2006 08:11:53 GMT
Message-ID: <dfEEf.6228$J81.2322_at_trndny01>


"Christopher Browne" <cbbrowne_at_acm.org> wrote in message

> Some people assume that "index" is synonymous with "B-tree"; there are
> other data structures that they may not believe should be called an
> "index." Pointedly, hashing is a sometimes-efficient mechanism for
> searching for data. (It tends to seem less attractive when applied to
> disk-based structures than it is for in-memory data, but that's noth
> particularly relevant here...)

Oracle/rdb (originally DEC Rdb) has a structure called a "hashed index".

It's an index. Given a key, it yields a pointer or a list of pointers. The pointers locate table rows.

It's also hashing. A hash algorithm on the key value yields a hash bucket number, which in turn allows retrieval of the bucket in one disk i/o.

By co-locating the index, the table rows, and perhaps table rows of a child table, and index hash buckets of a child table, you can get a fair amount of work done with just one disk i/o. This has been around for about 15 years. Received on Fri Feb 03 2006 - 09:11:53 CET

Original text of this message