INDEXING CONSIDERATIONS - A Developer's Guide to Data Modeling for SQL Server - page 225

One of the queries we can imagine being fairly popular for this table
would involve finding a customer record based on a customer's last name.
If we don't define any index on this table, the records will be inserted first-
come, because this table will be a heap. The B-tree structure for this table
will be very flat, because we're storing data in no particular order. Fig-
ure 10.3 shows the basic structure of this table.

F IGURE 10.3

B-tree for a heap

The index allocation map (IAM) page is simply the “management”
page for the heap. Each of the child nodes represents pages on disk.
There's a simple header that identifies the page (what extent, and object, it
belongs to). Then each page stores data as it has been inserted. So if we're
looking for a customer with the last name Johnson, we'll start with the first
row on the first page in the first extent that was ever allocated to the table.
We'll check the last name value for that row. If it is not a match, we'll look
at the next one. If it is a match, we'll return that row and then move on to
the next row. This process is known as a table scan. We'll do this for the
entire contents of the table. If there are 100 customers, the scan will go
fairly quickly. If there are 100,000 customers, then, as you can imagine, it'll
be fairly slow.
Now let's assume we don't want this query to take forever, and we
know that the vast majority of queries will involve searching for the last
name field. It might be useful to store the data, on disk, in an order that fa-
cilitates these lookups. Enter the clustered index.
If we define a clustered index on this table, we might define it so that
LastName is the only key value. However, we know that the last names
may not be unique; there are lots of Joneses and Johnsons and Smiths out