1、索引的本质

索引是帮助MySQL高效获取数据的排好序的数据结构

2、索引底层数据结构对比

2.1 二叉树

缺点：

  • 数据多的时候二叉树的高度很高，同时查询数据时查询次数也会增多
  • 如果索引是递增的，则二叉树相当于链表，查找相当于遍历链表

2.2 红黑树

缺点：

  • 红黑树属于平衡二叉树，在数据多的情况下，数的高度很高，查询次数也比较多

2.3 Hash 表

特点：

  • 对索引的key进行一次hash计算就可以定位出数据存储的位置
  • 很多时候Hash索引要比B+ 树索引更高效

缺点：

  • 仅能满足 “=”，“IN”，不支持范围查询
  • hash冲突问题

2.4 B 树

特点：

  • 每个节点都存储的有数据 找到索引就找到数据了
  • 每个节点都存储者索引数据按顺序排好序

缺点：

  • 由于节点都存有数据，每个节点相当于页的数据默认是16K,数据存在节点上导致存储在每个节点索引就比较少了，树的高度就变高了。
  • 叶子节点的没有指向相邻叶子节点的指针，导致在范围查询的时候要返回根节点在向下查询。查找很慢。

2.5 B+树

特点：

  • 每个节点存储存储排好序的
  • 每个节点都有很多排好序的索引，并且会平衡数的高度
  • 只有根节点会存储数据，这样使得其他节点能够存储更多的索引
  • 叶子结点有双向指针方便范围查找时不用返回根节点在向下查找
  • 叶子节点包含所有索引字段

3、索引存储结构

3.1 非聚簇索引

定义：索引和数据没有存在一块，查询索引后根据索引存储的地址回表查询数据

3.2 聚簇索引

定义：数据和索引存储在一起（主键索引）

3.3 覆盖索引

回表是有代价的，为了避免回表的代价。我们需要指定我们想要查询的列，就有机会达到覆盖索引。

select id,c1 from T where c1=5;

像这样一条查询语句，我们想要的主键id和二级索引c1在二级索引中都覆盖到了，就不需要去回表了，就称为覆盖索引，有效的解决了回表的问题。

3.4 最左匹配原则


主键索引：id
联合索引：(c1,c2)
普通字段commmon
#插入语句
insert into t(id,c1,c2,common) values (1,1,1,'小红');
insert into t(id,c1,c2,common) values (2,1,2,'小名');
insert into t(id,c1,c2,common) values (3,2,1,'小黑');
insert into t(id,c1,c2,common) values (4,2,2,'小花');
#执行语句
select * from t where c1=1 and c2=1;

由于组合索引中同时有c1也有c2，就可以在二级索引中完全过滤出想要的数据了，避免了内存的过滤。使用联合索引要注意一个最左匹配原则

3.5 索引下推

索引下推（ICP index condition pushdown）是索引下推是 MySQL 5.6 及以上版本上推出的，用于对查询进行优化。
索引下推是把本应该在 server 层进行筛选的条件，下推到存储引擎层来进行筛选判断，这样能有效减少回表。