为什么使用索引

一、hashmap底层使用红黑树
二、索引时在存储引擎中实现的，因此不同存储引擎的索引可能不同
索引的优点：

1. 类似大学图书馆建书目索引，可以减少磁盘I/O的次数，加快查询速率
2. 通过创建唯一索引，可以保证数据库表中每一行数据的唯一性，如果这个数据建了索引，那么会自动给他加上唯一约束 。
3. 在实现数据的参考完整性方面，可以加速表和表之间的连接 。换句话说，对于有依赖关系的子表和父表联合查询时，可以提高查询速度
4. 在使用分组和排序子句进行数据查询时，可以显著减少查询中分组和排序的时间 ，降低CPU的消耗。因为索引是排好序的能快速查找的数据结构，既然排好序，那进行分组和排序时会更高效

缺点：

1. 创建索引和维护索引要耗费时间，随着数据量的增加，所耗费的时间也会增加。
2. 索引存储在磁盘上，需要占磁盘空间
3. 虽然索引大大提高了查询速度，但是当对表中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速度。因为索引是排好序的能快速查找的数据结构，假如索引现在是1，1，2，2，3，4，4，假如要增加一个索引3，那么4，4，需要移动，删除和修改同理。如何解决这个问题：在维护表时，先删除表中的索引，然后插入数据，插入完成后再建索引

InnoDB中索引的推演

假如要查找一些数据：

索引前的查找

一、在一个页中查找

数据通过单链表的形式存储，不然你每次删除条数据，后面的数据还要往前移
二、在很多页中查找：确定数据在哪一页，从所在页中查找相应的数据（此时的查找套路同【在一个页中查找】），但是在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，由于我们并不能快速的定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找，在每一个页中根据我们上面的查找方式去查找指定的记录。因为要遍历所有的数据页，所以这种方式显然是超级耗时的。如果一个表有一亿条记录呢？此时索引应运而生。

设计索引

简单的索引设计方案

创建一个表，表中的字段如下，

record_type：表示记录的类型，0表示普通记录、2表示最小记录（即这条数据是本页的最小数据）、3表示最大记录（即这条数据是本页的最大数据）、1暂时还没用过
next_record：表示下一条数据所在地址相对于本条记录的地址偏移量，本文用箭头来表明下一条记录是谁。
c1、c2、c3列：记录字段值

那么一页中的数据就是这样：

假如数据有很多，一页放不下，并且要求按照c1列大小递增排列：

假如我们现在想查找某条数据，我们只能从头开始遍历，效率太慢。如果想快速定位到需要查找的数据在哪页中该咋办？我们可以为快速定位记录所在的数据页而建立一个目录 ，建这个目录必须完成下边这些事：

1. 下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。
2. 给所有的页建立一个目录项。

所以我们为上边几个页做好的目录就像这样子：

以页28为例，它对应目录项2，这个目录项中包含着该页的页号28以及该页中用户记录的最小主键值（c1）5 （注意：要求按照c1列大小递增排列）。我们只需要把目录项在物理存储器上连续存储（比如：数组），就可以实现根据主键值快速查找某条记录的功能了。比如：查找主键值为20的记录：

1. 先从目录项中根据二分法快速确定出主键值为20的记录在目录项3中（因为12<20<209 ），它对应的页是页9 。
2. 再根据前边说的在页中查找记录的方式去页9中定位具体的记录。

这个目录有一个别名，称为索引 。

InnoDB中的索引方案

如前所述，如果目录项在物理存储器上连续存储（比如：数组），假如我删了一页数据，那么该页在目录项的数据也要删除，那么后面的数据得向前移，这是个弊端，那我们可以让目录项也像数据那样使用单向链表进行连接

如果目录项记录太多，一页放不下，也可以增加一些记录目录项的页

如果记录目录项的页太多了，当我们查找某条数据在哪页时，又需要从第一条目录项开始查找，效率太低，那我们可以给目录项记录页创建目录页

这个数据结构，它的名称是 B+树 。
假设所有存放用户记录的叶子节点代表的数据页可以存放100条用户记录，所有存放目录项记录的内节点代表的数据页可以存放1000条目录项记录，那么：
如果B+树只有1层，也就是只有1个用于存放用户记录的节点，最多能存放100条记录。
如果B+树有2层，最多能存放 1000×100=10,0000 条记录。
如果B+树有3层，最多能存放 1000×1000×100=1,0000,0000 条记录。
如果B+树有4层，最多能存放 1000×1000×1000×100=1000,0000,0000 条记录。相当多的记录！！！你的表里能存放 100000000000 条记录吗？所以一般情况下，我们用到的B+树都不会超过4层，这是因为树的层次越低，IO次数越少