Introduction to Indexes

You are used to working with indexes in daily life. Many books have a table of contents. This table of contents shows the book's outline, and in this outline, you can see on which page every topic starts. You can read just the table of contents and search for a subject that interests you. After you find an interesting topic, you can quickly go straight to the correct page number.

In this example, the book is organized according to the table of contents. The table of contents is not ordered alphabetically but it is ordered by its outline. If you want to search for a specific topic, you have to search the table of contents sequentially from the beginning to the end.

Every entry in the table of contents can be considered a key to the index, whereas the page number is no more than a pointer to the physical page where the topic starts.

Most books have an indexat the end.The index is just a collection of keywords that are organized alphabetically. These keywords represent different topics: For every keyword the index shows the page or pages where this topic is covered. Because these keywords are alphabetically ordered, it is easy to search for a specific topic without having to read the index sequentially.

An index key in SQL Server is like a keyword in the index of a book, and the page number of the index in the book is the pointer to the physical page where the topic is covered.

Perhaps it is difficult to visualize a book as a table in a database, but a book is information that is stored in a sequence of physical pages, which is not very different from the way SQL Server 2000 stores data, as you will see later in this chapter.

Let's consider another familiar example. Every telephone company maintains a database of customers. This database has, at least, the family name, first name, address, and telephone number of every customer.

Applications for new telephone lines are stored in order, but the telephone directory shows entries in alphabetical order. If you know the customer's family name, you can easily search for their telephone number by browsing the telephone directory. To help us carry out this search, every page in the telephone directory is labeled with either the first or the last entry on the page, so you can read the labels and search for the entry you want to find.

To search for a specific entry in the directory, you follow a process that could be called a binary search. SQL Server uses binary search when it scans an index searching for specific information.

Having the data ordered by more than one attribute—that is, surname, first name, and address as in this case—is what you do when you use a compos ite index. In this case, the combination of surname, first name, and address is the index key. Telephone directory data is physically written in this order, and this is what you call a clustered index in SQL Server. You will look at clustered indexes later in this chapter.

Because you often need to search for businesses offering a specific kind of service, some companies offer special yellow pages books to help people search for specific businesses. The yellow pages order telephone entries by activity. Entries are ordered alphabetically for every activity.

The yellow pages show a typical example of a nonclustered index in SQL Server.

Searching for customers living in a specific street or area will mean having to sequentially read the standard telephone book and extract, one by one, every entry that matches the searching criteria. Just as in the preceding case, when SQL Server doesn't have a suitable index to execute a query, the only choice available is to read the entire table first and then filter out every entry that matches the searching criteria.