Access to pages in the data cache must be fast.
Even with real memory, it would be
ridiculously inefficient to scan the whole data cache for a page when you
have gigabytes of data.
Pages in the data cache are therefore hashed for fast
access. Hashing is a technique that uniformly maps a key via a
hash function across a set of hash buckets. A hash table is a
structure in memory that contains an array of pointers (implemented as a linked
list) to the buffer pages. If all the pointers to buffer pages do not fit on a
single hash page, a linked list chains to additional hash pages.
Given a dbid-fi leno-pageno identifier (a combination of the database ID, fi le number, and
page number), the hash function converts that key to the hash bucket that
should be checked; in essence, the hash bucket serves as an index to the
specific page needed. By using hashing, even when large amounts of memory are
present, SQL Server can fi nd a specific data page in cache with only a few
memory reads. Similarly, it takes only a few memory reads for SQL Server to
determine that a desired page is not in cache and that it must be read in from
disk.
