复合索引的具体实现原理（数据结构）

一棵树
假如是单列，就按这列数据进行排序
假如是多列，就按多列数据排序，例如有（1,1） （2,2） （2,1） （1,2）
那在索引中的叶子节点的数据顺序就是（1,1）（1,2）（2,1）（2,2）
这也是为什么查询复合索引的前缀是可以用到索引的原因

假如要了解具体的存储方式，建议先了解一下数据存储格式，假设是innodb
执行如下语句
create table secondindextest(a int, b int);
create index ix_a_b on secondindextest(a,b);
insert into secondindextest select 1,1;
insert into secondindextest select 1,2;
insert into secondindextest select 2,1;
insert into secondindextest select 2,2;
在来看看具体的数据是怎么样存储的 , 打开secondindextest.ibd文件，找到索引页，如下数据
80 00 00 01 80 00 00 01 00 00  01 57 8B 08 00 00
00 18 00 14 80 00 00 01 80 00  00 02 00 00 01 57
8B 09 00 00 00 20 00 14 80 00  00 02 80 00 00 01
00 00 01 57 8B 0A 00 00 00 28  FF B6 80 00 00 02
80 00 00 02 00 00 01 57 8B 0B  00 00 00 00 00 00
00 00
看其中的80 00 00 01 80 00 00 01 就是索引的第一行 1,1 ，这个80代表的是带符号的
后面带的00 00  01 57 8B 08 00 00  00 18 00 14 包括了主键的位置以及下一行的偏移量等信息
往后看，可以看到80 00 00 01 80 00 00 02
80 00 00 02  80 00 00 01
80 00 00 02  80 00 00 02
分别代表了(1,2) , (2,1) , (2,2)
你所问的存放问题实际上就是跟着第一列继续放

1   第二列也做了排序，首先根据第一列排序，在第一列一样的情况下，第二列再排序
2   一个查询只能使用一个索引，不存在你说的分别查找两棵树的情况

引用:

例如mysql 单列索引是将该列数据当做关键字构建一颗b+tree，但是组合索引是怎么样实现的呢?例如两个字段的组合索引，SELECT * FROM TABLE1 WHERE A=22 AND b=33 ; 是要建两棵树吗？假如只建立一颗树，那b列是怎么样存放的？

A=22 AND b=33
你假设一下 C=A*10000+B ,然后根据C做BTREE。后面的所以搜索一切就容易了。其实就是相同的原理。以A先放，A相同的情况下按B的顺序放。

一个索引，创建一个树，也只能创建一个树，不管是单列，还是多列联合。
假如是联合索引，第二列也会放在第一列后面。
假定有一张表

create table t (c1 int , c2 int , c3 int , c4 int)

场景1

create index t_ix1 on t(c1) ;
create index t_ix2 on t(c2) ;

此时，你执行

select * from t where c1 = 100  -- 会用到 t_ix1 
select * from t where c2 = 100  -- 会用到 t_ix2 
select * from t where c1 = 100 and c2 = 100 -- 只能用到 t_ix1 和 t_ix2 中的一个。

场景2

create index t_ix1 on t(c1 ,c2)
create index t_ix2 on t(c2)

你再执行

select * from t where c1 = 100  -- 会用到 t_ix1 
select * from t where c2 = 100  -- 会用到 t_ix2 ,假如没有 t_ix2 ,就会全表扫描
select * from t where c1 = 100 and c2 = 100 -- 会用到 t_ix1

另，条件中的各个语句 在顺序上，不会影响执行计划

select * from t where c1 = 100 and c2 = 100 
select * from t where c2 = 100 and c1 = 100