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.
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.
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.