Re: How do indexes work on non-unique values ?

"rhian" <williams.rhian_at_freenet.de> wrote in message <news:a0310e5c.0301231242.1a8c1512_at_posting.google.com>...

> i have been told that creating an index on a field which can only
> contain 2 possible values (i.e male/female) is a bad idea be because
> order(n/2) is still order(n) and you get no benefit from doing a
> binary search on the index file.
>
> I think i understand how an index works and is beneficial when created
> on a unique value, such as primary key. e.g
>
> primary key values page number
> 1 1
> 101 2
> 201 3
> 301 4
>
> so if i were searching for 250 i would find the relevant page in
> minimal number of goes, then the page would be load into memory and
> scanned sequentially until the relevant record was found
>
> I don't understand how this works for indexes on foreign keys, which i
> understand to be beneficial or how it would work for my initial
> example

Some DBMS products support "bitmap" indexes which would be suitable for your male/female example. The space required for the index would be one bit per table row per unique field value:

male 011110101010101110001
female 100001010101010001100

null    000000000000000000010

Most DBMS indexes are based on n-way trees, with the nodes jiggered to just fit within a disk block. However, there are a number of ways to represent duplicate keys within the nodes.

--
Joe Foster <mailto:jlfoster%40znet.com>  Wanna buy a Bridge? <http://xenu.net/>
WARNING: I cannot be held responsible for the above        They're   coming  to
because  my cats have  apparently  learned to type.        take me away, ha ha!