Microsoft SQL Server 2012 Internals

SQL Server B-tree indexes

In SQL Server, most indexes are organized using a B-tree structure (see Figure 7-1). In fact, in this chapter, any reference to any kind of index without qualifying it indicates a B-tree index. The term B-tree stands for “balanced tree,” and SQL Server uses a special kind called B+ trees (pronounced “b-plus trees”). The difference between B-trees and B+ trees isn’t really relevant for this discussion of the way SQL Server indexes are managed, so the difference will be ignored. Index structures are referred to as simply B-trees. Unlike a normal tree, B-trees are always inverted, with their root (a single page) at the top and their leaf level at the bottom. The existence of intermediate levels depends on multiple factors. ...