複合インデクスとは、テーブルの複数のカラムを組み合わせて１つのインデクスとするものです。
たとえば、以下のようなカラムを持つ「従業員マスタ」というテーブルに「姓」と「名」で１つのインデクスを作成することを指します。
従業員マスタ

従業員番号	姓	名	性別	住所	生年月日	入社年月日	会社	所属部門	職位	レコード作成日時
1998025	ランダル	スンヤラ	M	東京都千代田区１丁目１番地	1972/07/12	1998/04/01	関東支社	開発部	理事	2001/02/01 10:00:01
1999003	徳川	家康	M	東京都千代田区２丁目２番地	1980/12/10	1999/04/01	本社	営業部	主事	2001/02/01 10:00:01
：	：	：	：	：	：	：	：	：	：	：

プライマリーキー：従業員番号 インデックス０:(姓,名)
この「インデックス０」が複合インデクスです。従業員数が多く、「姓」だけでは同じデータが重なってしまう場合に「姓」と「名」の両方を１つのインデクスにしてしまうことにより、効率よく検索できることを狙っています。

何が効率がよいのか、もう少し具体的に説明してみます。
一般にインデクスは下のようにキーと、そのキーを持つデータがテーブルのどの行に存在するかを特定する行IDから成り立っています。

インデクス		テーブルデータ
キー 行ID 佐藤 0105 0212 0387 ランダル 0056 : :	⇒ ⇒ ⇒	行ID 姓 名 ... 0105 佐藤 太郎 ... 0212 佐藤 次郎 ... 0387 佐藤 三郎 ... 0056 ランダル スンヤラ ... : : : ...

上記のように「姓」だけでインデクスを作成すると、姓＝佐藤 かつ 名＝太郎という条件で検索を実行した場合に、インデクスで３件のレコードがヒットしますので、ヒットした３レコードのテーブルデータを１つずつ調べて、「名」が一致するかどうかを検査する必要があります。
これを検索速度から見ますと、テーブルデータを調べる処理時間がインデクスを検索する処理時間に加算されることになりますので、インデクスの検索だけで行を決定できる場合よりも時間がかかります。

そこで今度は「姓」「名」を複合インデクスとすると、インデクスは下のようになります。

インデクス		テーブルデータ
キー 行ID 佐藤 太郎 0105 次郎 0212 三郎 0387 ランダル スンヤラ 0056 : :	⇒	行ID 姓 名 ... 0105 佐藤 太郎 ... 0212 佐藤 次郎 ... 0387 佐藤 三郎 ... 0056 ランダル スンヤラ ... : : : ...

このように複合インデクスを作成すると、姓＝佐藤 かつ 名＝太郎の条件で検索を実行した場合は、インデクスを検索するだけで、行ID:0105が目的のデータであることが決定できます。

少し本題から外れますが、「従業員マスタ」の場合は上のインデクスで十分かもしれませんが、これが「顧客マスタ」で何百万レコードもあるような場合は、同姓同名が相当な数存在することになります。
そこで、「生年月日」を複合インデクスに追加したくなるかもしれません。
それでも重複が多いなら、「都道府県」を追加・・・等と、きりがありません。まるで年金記録の照合問題みたいですね。(^^;
このように考えてクエリ（データベースを検索して結果を取出す処理）で使われる検索条件をなんでもかんでもインデクスにしてしまうといろいろ弊害が生ずるのですが、今回のテーマではないので、別の機会に解説することにします。
また、「レコード作成日時」のようなカラムをインデクスにするのも考えものです。これについても別途解説する予定です。

さて、ようやくここからが本題です。
このシステムでは、検索につかわれる条件に必ず「会社」を指定するようになっていたとします。
例：会社＝本社 かつ 姓＝佐藤 かつ 名＝太郎
そこで、データベース設計者は「会社」も複合インデクスに含めるべきではないか？と考えインデクス０は(会社,姓,名)としました。

インデクス		テーブルデータ
キー 行ID 本社 佐藤 太郎 0105 次郎 0212 三郎 0387 : : 関東支社 ランダル スンヤラ 0056 : :	⇒ ⇒ ⇒ ：	行ID 姓 名 会社 ... 0105 佐藤 太郎 本社 ... 0212 佐藤 次郎 本社 ... 0387 佐藤 三郎 本社 ... : : : 本社 ... 0056 ランダル スンヤラ 関東支社 ... : : : 関東支社 ...

ここで問題になるのは複合インデクスの特徴の１つである、「キーとして構成されているカラムの全てが検索条件に指定されていなくても、キーの先頭から途中までのカラムが指定されていれば、インデクスが使われる」という点です。
これにより、上記インデクスにおいて例えば、会社＝本社 かつ 生年月日＜1960/01/01のような検索条件を実行すると、「インデクス０」を参照して、「本社」のテーブルデータの「生年月日」を１つずつ検査する動きになります。
もしこのインデクス０がなければ、インデスクの参照はおこなわれず、テーブルデータを全件読み込んで「生年月日」を検査するという動作になります。
テーブルデータを全件読み込むよりも、インデスクを使用した方が速いのではないかと誤解する方も多いのですが、テーブルの全件検査はブロック読み込みという方式で何件もまとまった単位で連続して読み込みますので、検査だけであればそれほど時間はかかりません。※1
それに比べて、インデクスを参照してから次にテーブルデータを読み込むという処理は１レコード単位のランダムアクセス処理の積み重ねとなりますので、１件ごとの時間は短くても件数が多くなるとトータルとして膨大な時間となります。
例えば、データの９０％が本社で、支社は１０％しかないという場合では、本社データの検索にインデスクを使用すると、使わない場合に比べて数百倍遅くなる可能性があります。
上記に似た実例で、１０分以上かかっていた検索がインデクスを使用しない設定にしたら１０秒以内で終わるようになったという経験があります。※2

ではこのような場合、具体的にどのようにしたら良いのでしょうか？
例えば、データの散らばりが小さいカラムを複合インデスクの後ろに持ってきたらどうでしょうか？
インデクス０を(姓,名,会社)としてみましょう。

インデクス		テーブルデータ
キー 行ID 佐藤 太郎 本社 0105 次郎 本社 0212 三郎 本社 0387 : 本社 : ランダル スンヤラ 関東支社 0056 : 関東支社 :	⇒	行ID 姓 名 会社 ... 0105 佐藤 太郎 本社 ... 0212 佐藤 次郎 本社 ... 0387 佐藤 三郎 本社 ... : : : 本社 ... 0056 ランダル スンヤラ 関東支社 ... : : : 関東支社 ...

なるほどこのようにすることで
会社＝本社 かつ 姓＝佐藤 かつ 名＝太郎
というクエリにはインデクスが使われ、
会社＝本社 かつ 生年月日＜1960/01/01
の場合はインデクスが使われず無駄な処理は発生しません。
しかし、上図でも分かるとおり会社データが重複して追加されることになりますので、インデクスが大きくなってしまい、リソースの圧迫やデータの更新性能に悪影響が発生するでしょう。
結論としては、複合インデクスといえども「会社」のようなデータの散らばりの少ないカラムはインデクスに含めず、テーブルデータを検査することで判定するようにした方がよいということです。
同じ理由で、「性別」や「所属部門」、「職位」など（コードで定義できるような数が少ないもの）も複合インデクスに含めるべきではありません。

※1)１レコードのデータ長が極端に大きいテーブルの場合は、テーブルスキャンに時間がかかることもあります。

※2)データベース製品によっては、統計情報からクエリの最適化を行い、データの散らばりが小さい場合はインデクスを使用しない検索ストラテジをとるものもあります。
しかし、統計情報のメンテナンス状況により最適化が不十分になったり、サポートしていない製品やデータベースエンジン(MySQLは使用するエンジンによって動作が異なります)もありますので、やはり設計段階で留意しておくべきと考えます。