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

To understand the performance implications of an index, it is useful to
understand how indexes are logically structured. In SQL Server 2008,
there are a number of types of indexes based on the types of data each can
hold; however, we are concerned primarily with the indexes on the most
commonly used types of data, such as strings, numeric data, and so on.
These indexes use a basic structure known as a B-tree. A B-tree is a
data structure that uses a tree analogy for storing data in parent and child
nodes. Figure 10.1 shows a basic B-tree.

F IGURE 10.1

A basic B-tree structure

Simple, yes? This basic structure can be applied to the very familiar
concept of a book index. As you walk through this, it may be useful to ac-
tually grab a book with an index (you may in fact be holding a book with an
index right now). Flip to any page in the index. Look for a top-level word;
often these are in boldface and are left-aligned with the column on the
page. These are the root, or parent node, of the index. The entries be-
neath the word are indented. For each lower-level entry, the index either
gives you a pointer, which is the page number, or more entries even lower
in the index. The page number points you to the information you are look-
ing for—the data.
For each word, there can be any number of entries and subentries. For
human readability, we rarely see more than three or four levels in a book
index. However, in the context of an index on a table, SQL Server can han-
dle reading quite a few levels of an index and can split and manage the
index nodes based on the volume of data and the information you've given
to it (how you have defined the index). But basically, the index serves the
same purpose to the SQL Server query engine that a book index serves for