A seek is an efficient access method that can be fulfilled using an index structure.
Seeking touches fewer pages than scanning,
and can only occur on an index of some type.
Think of a seek as what you would do with a phone book
if I told you to find the phone number of someone
with last name and the first name.
* Scan
A scan is basically an access method whereby all data, or some range of data,
in an index or heap must be touched or retrieved in order to fulfill a request.
Think of a scan as what you would do with a phone book
if I told you to find the phone numbers for everyone in the book,
or the phone number for all people with the first name,
or for someone with a phone number of (555) 555-5555...
* Singleton Lookup
A singleton lookup is a seek operation
whereby a single record/page of data is retrieved.
This can occur for example when you perform a query that needs to access only a single record,
or a few records from a single page.
The navigation through a B-tree in a singleton lookup would be similar to the following diagram:
* Full Scan - key ordered
A key-ordered full scan is a scan operation
whereby all the leaf pages of a given B-tree structure
are retrieved by following the page linkage
(i.e. starting with the first page in the leaf level
and following to the next page via the doubly-linked list, and so on and so on).
Note that this type of scan can only be performed on a B-tree structure and NOT against a heap.
This occurs for example
when you perform a query that must return all the rows and columns in a clustered table,
or only a few rows but the filter predicate has no index to seek with,
or against a non-clustered index
if you want all rows for a table but only values from columns
that are covered by the non-clustered index. (Navigational diagram follows under Range Scan)
* Range Scan
A range-scan is a scan operation
whereby a range of pages are retrieved
- think of this as a full-scan with boundaries.
The navigation through a B-tree in a range scan would be similar to the following diagram
(a full scan operation would be exactly the same,
only the entire leaf would be scanned instead of just a portion of it):
* Full Scan - Allocation Ordered
An allocation ordered full scan is the same as a key ordered full scan,
only instead of scanning the data via page linkage,
the pages from the leaf of the index (or from a heap)
are scanned via page ID values taken from system pages
that track which pages are allocated to the given index/heap
(pages that track this are called 'IAM' pages).
Basically all the physical page ID values
are gathered for pages allocated to the given index/heap,
and then those pages are retrieved directly - even in a B-tree structure,
the root/intermediate pages for the index would not be touched at all
(no reason to do so,
since the physical page ID values take you directly to the leaf pages needed).
This is the ONLY type of operation that is directly supported against a heap
(though seeks and range-scans can occur indirectly
via non-clustered indexes that are built against the heap table).
The navigation through a B-tree in this type of scan
would be similar to the following
(notice that the root/intermediate levels aren't touched)
...navigation through a heap would be similar as well,
only a heap wouldn't include root/intermediate pages at all in the structure:
* Read-Ahead
Read-ahead is an access method mechanism
that attempts to intelligently pre-fetch data
that resides on-disk into the data cache prior to it being needed for use by the CPU
- this is done to try and optimize the IO throughput of a system
in order to keep the CPU as busy as possible without waiting on the slower IO system
to get needed data.
This type of operation is typically reserved for scans of data
that fetch medium/large amounts of pages/data,
and can issue 1,8,32, or 64 page IOs in a single IO operation
- the size of operation that can be performed is very heavily impacted
by the contiguity of the data
(the more contiguous the data, the bigger the IOs that can performed,
the better performance you see).
There are 2 kinds of read-ahead operations,
1 that works with allocation ordered scans, and 1 that works with key-ordered scans.
With allocation ordered scan,
the IAM pages in the database list the extents used by a heap or index
- the engine will read the IAM and build a sorted list of the physical disk addresses
that must be read, allowing the engine to optimize it's IOs
as large sequential read performed in sequence based on their location on disk,
vs. multiple small, random reads.
With key-ordered scans,
the engine uses the information stored in the intermediate index pages 1 level
above the leaf level to schedule serial read-aheads for pages
that contain the keys found.
If a request is made for example for all keys from 1 to 100,
- the engine will first read the index page above the leaf page for key 1
(on it's way to traversing to the leaf page);
- however, instead of simply reading each leaf page in sequence from page 1 to page 100,
the engine scans the intermediate level page
and builds a list of the leaf pages that must be read to get pages 1 thru 100,
- then schedules all reads in key order - in addition,
the engine will recognize if pages are contiguous
and perform a single read to retrieve the adjacent pages in a single operation
as opposed to multiple, smaller operations.
A similar type of operation is used to pre-fetch data
from a base cluster or heap when scanning through a non-clustered index -
since the leaf rows of a non-clustered index
contain pointers to the data rows in the cluster/heap structure,
as the storage engine reads through the leaf of the non-clustered index,
it also starts scheduling asynchronous reads for the corresponding data rows
whose pointers have already been retrieved.
This allows the engine to fetch data efficiently from the underlying cluster/heap
before it has completed the scan of the non-clustered index.
The navigation for a read-ahead in a key-ordered scan would look something like the following:
Source:
http://www.mssqltips.com/sqlservertip/2261/sql-server-fragmentation-storage-basics-and-access-methods-part-1-of-9/