How does indexes work ?

Hi,
I've always wondered something about indexes and I wanted to know if any of you knew the answer.

I know that putting indexes on some fields in a database can be crucial to speed up the time of response in a query. But I don't clearly understand how this work.

I understand that in a database in which you have let's say 3000 rows, when you search a specific record based on a field that has no index on it you usually have to scan about 1500 rows (a mean : 3000 / 2) until you find the record you're searching. If you have an index on it, there's no scan, you go immediately to the row you're searching.

Now... how that works ?

Example. I have a database like this
employees[id, first_name, last_name, adress, security_number];

id is the primary key, then.. it has an index automatically. Let's say I don't put any index anywhere else.

Let's say that I do this
SELECT first_name
FROM employees
WHERE security_number = '123A52DBD'; // The DBMS is going to scan al the records.. I understand this

Now let's say I do this
SELECT first_name
FROM emplyees
WHERE id = 10231;

What is the DBMS going to do ?
Does it have an internal table where it keeps the correspondence between index values and their memory adress ?
But even then... how is this internal table organized ? How come when having a specific index value (e.g. 10231) the DBMS finds it immediately in the internal table and does not have to scan for it ? For me having an internal table would only push the problem further : you still have a table with index values and need to find a specific value in it... so it's just like starting all over again, no ?

Anyone can explain this to me ? Received on Wed Aug 15 2001 - 13:57:47 CDT