what is the structure of a Mysql multi-column index?
Note: At the time this answer was written, the question was:


  In a B-Tree index, are all columns of a single row stored together, or
  are the columns stored in separate structures?




Most RDBMSs (including MySQL) implement indexes as B+Tree not B-Tree.
There are two types of B+Tree indexes: Clustered and Non-Clustered.

Both have in common that each intermediate level (including the root) of the index contains all columns that make up the key. The leaf level contains all key columns plus additional information.

In a clustered index, that additional information are all other columns of that table. For non-Clustered indexes, that additional information contains at least a reference to the actual table row. Some RDBMSs allow to also add additional columns here, so called "included" columns.

Either way, a B+Tree always contains the complete tuple relevant to the current index level within a single B-Tree node (which is usually equivalent to a data page. This storage organization is also called the "N-ary Storage Model" or NSM.

Some RDBMSs allow for column oriented storage, like SQL Server with the Column Store Index. That model is called the "Decomposition Storage Model" or DMS. However, a structure using the DSM is not organized as a B+Tree (or even a B-Tree).

There is a third form of storage that combines the two ideas. It is called PAX (partition attributes across). However it is rarely implemented.

References:

http://en.wikipedia.org/wiki/B%2BTree

http://www.pdl.cmu.edu/ftp/Database/pax.pdf

http://en.wikipedia.org/wiki/Column-oriented_DBMS