How are regular and composite indexes implemented in RDBs?

Question

In databases like MySQL or Oracle, how are indexes implemented? I think regular indexes are stored as B-trees, but couldn't find anything about composite indexes that index on multiple columns. I'm looking for the names of the data structures used so I can research them.

More generally, where can I find more such information about database implementation details? I'm going to be taking a course on that much later in university, but I'm curious right now.

Answer 1

Composite indexes also use B-Trees, they just concatenate the indexed columns to determine the key. As a side node, Oracle also knows other index types, i.e. bitmap indexes. But that doesn't depend on the number of columns indexed.

Answer 2

B-trees. Every index is stored as a B-tree -- even composite ones.

If you're looking to do more research on how indexes are organized, look into B+ trees and B* trees. For SQL Server, Kalen Delaney's Inside SQL Server: The Storage Engine is an excellent book about the nuts and bolts of SQL Server, including its index organization. So you should definitely check that out.

A commenter points out that Oracle can use bitmap indexes, which are structured very differently than B-trees, but those are rarely used for traditional relational databases -- they're used more often for OLAP type applications and in cases where you need fast access on a nonselective group of data.

EDIT: SQL Server, for example, now uses Columnstore Indexes. If you do any work with large BI type workloads, it's definitely worth looking at these, as they store your data in an entirely different way than a B-Tree.

SQL Server also uses a different mechanism now for memory optimized tables as well, and is something that's very useful for OLTP type queries.