What is the structure that SQL Server uses to build and maintain indexes called?
They are generally B+ Trees for your standard clustered and non-clustered indexes:
Columnstore indexes have a different structure:
In SQL server 2014 you have some new types too for the in-memory tables such as the Bw-Tree index:
And the hash index:
Not forgetting the full text indexes too:
As pointed out there are also spatial indexes:
And XML Indexes: