对于各种树的介绍和异同可以看这篇文章B树、B+树、红黑树、AVL树

索引底层数据结构是B+树，B+树最大的优点在于它将索引存放在磁盘，让检索技术摆脱了内存限制。

单例索引：一个索引只能包含一个列，一个表可以有多个单例索引

组合索引：一个组合索引包含两个或以上的列，原理简单，在a，b，c字段上创建索引，索引记录会首先安装A排序，A一样照B排序，B一样照C排序。

聚簇索引：数据存储和索引放一块，b+树叶子节点存放的是数据表的行记录，可以理解成将数据存储和索引放到了一块,这是主键索引，因为InnoDB数据文件本身要按主键聚集，所以InnoDB要求必须有主键，如果没有就自动生成一个隐含的字段作为主键

为什么mysql表要有一个自增的id主键，因为mysql索引用b+数，得是一个递增的，因为如果不递增增加数据的话得裂表影响效率，而且不建议使用太长的字段作为主键。

非聚簇索引：数据和索引是分开的，B+树叶子节点存放的不是数据表的行记录。

聚簇索引优点：

• 数据访问更快，因为聚簇索引将数据放在同一个B+树中，所以比非聚簇索引快
• 聚簇索引对于主键的排序查找和范围查找速度非常快

缺点：

• 插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将出现页分裂，严重影响性能，我们一般会定义一个自增的ID作为主键
• 更新主键的代价很高
• 二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据。

1、一级索引

索引和数据存储在一起，都存储在同一个B+tree中的叶子节点。一般主键索引都是一级索引。

2、二级索引

二级索引树的叶子节点存储的是主键而不是数据。也就是说，在找到索引后，得到对应的主键，再回到一级索引中找主键对应的数据记录。

3、一级索引和二级索引的关系：回表

一级索引可以单独存在，二级索引不能单独存在，必须依附于一级索引，这叫做“回表”。

select 所需获得列中有大量的非索引列，索引就需要到表中找到相应的列的信息，这就叫回表

4、索引建立原则

（1）最左前缀匹配原则，非常重要的原则，mysql会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配，比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引，d是用不到索引的。
如果建立(a,b,d,c)的索引则都可以用到，a,b,d的顺序可以任意调整。

（2）=和in可以乱序，比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意顺序，
mysql的查询优化器会帮你优化成索引可以识别的形式

（3）尽量选择区分度高的列作为索引,区分度的公式是count(distinct col)/count(*)，表示字段不重复的比例，
比例越大我们扫描的记录数越少，唯一键的区分度是1，而一些状态、性别字段可能在大数据面前区分度就是0，
那可能有人会问，这个比例有什么经验值吗？使用场景不同，这个值也很难确定，
一般需要join的字段我们都要求是0.1以上，即平均1条扫描10条记录

（4）索引列不能参与计算，保持列“干净”，比如from_unixtime(create_time) = ’2014-05-29’就不能使用到索引，
原因很简单，b+树中存的都是数据表中的字段值，但进行检索时，需要把所有元素都应用函数才能比较，
显然成本太大。所以语句应该写成create_time = unix_timestamp(’2014-05-29’);

（5）尽量的扩展索引，不要新建索引。比如表中已经有a的索引，现在要加(a,b)的索引，那么只需要修改原来的索引即可

5、可能索引失效的原因

和索引建立原则类似

• 范围查询，>,<,!=,or会导致索引失效,like ‘%liu’ 百分号在前也会导致索引失效

  • 最左前缀匹配原则，非常重要的原则，mysql会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配，比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引，d是用不到索引的，把c>3放到最后。

• 使用select * 类似的语句可能会导致不用索引，优化器可能会选择TABLE ACCESS FULL

• 单键值的b树索引列上存在null值，导致COUNT(*)不能走索引

• 索引列上有函数运算，导致不走索引

• 建立组合索引，但查询谓词并未使用组合索引的第一列，此处有一个INDEX SKIP SCAN概念

6、唯一索引和主键索引的区别

1、概念：主键是一种约束、是一种逻辑键实际上不存在；唯一索引是一个索引、是物理键，实际上存在。

2、主键索引不能有空值，唯一索引可以有空值（可以有多个空值）

3、主键可以建立外键， 唯一索引不能

4、一个表中只能有一个主键，但是可以有多个外键

5、主键更适合那些不容易更改的唯一标识，如自动递增列、身份证号等

7、为什么唯一索引比普通索引快（查询会快一点点点点）

查询效率：唯一索引查询时有很小概率会比普通索引快，有概率普通索引有一条数据在一个页表末尾，一条数据在页表前面，需要两次io，这时唯一索引会比普通索引快一点。

更新效率：唯一索引更新的时候需要把索引页读到内存中，不然不能判断数据是否唯一，会比普通索引慢

总结：少用唯一索引。

8、为什么数据库联合索引不符合最左前缀就会失效

这就得看看联合索引在底层是怎么放的

单一索引是一个节点存一个键，联合索引是一个节点存多个键，每个键都是有顺序的，两个节点比较是第一个节点如果相同，就比较第二个节点，查找的时候也是这样，如果第一个节点找到了，就开始比较第二个节点是否相同。

9、为什么b+树大层数总是2-4层

​ 我们来计算一下3层b+树能放多少数据，mysql默认页是16KB，假设一条数据1KB，一页就能放16条记录，假设有三层数据，假如我们的主键id为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节。这样算下来就是 16384 / 14 = 1170，就是说一个页上可以存放1170个指针，两层是1170*16，三层是1170 * 16 * 1170，千万行足够大部分场景，再大也要分库分表了。