这类问题可能经常面试会被问到，其实我觉得也是很关键的，如何合理使用索引，可以加快你sql的执行速度，这是非常关键的。

1、概述

  索引实际上就是一个目录，跟着索引可以快速找到你的数据行，避免了盲目的一个磁盘一个磁盘的找，那有的人就比较较劲了，那我就想一个一个查，因为维护索引也需要很大的成本
  的确是这样的，如果你的表数据经常就是insert、update之类的，还是不要在对应列建立索引了，但很多业务情况都是select居多，因为磁盘IO的读写比内存慢超级超级多，所以在select居多的场景建索引提升非常明显。
  从上面我们也可以看出，建立索引的目标就是为了减少磁盘IO，那么衡量一个索引的好坏也就是IO次数了，什么时候会执行IO读写呢？因为数据都是存在磁盘上的嘛，索引也不例外，你要把索引分批加载到内存来（索引的基础是建立在磁盘局部性原理上的），才能比较嘛，假设有n个磁盘，我们可以计算一下各个数据结构的效率，线性就不说了

  磁盘局部性原理：考虑到磁盘IO是非常高昂的操作，计算机操作系统做了一些优化，当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)。具体一页有多大数据跟操作系统有关，一般为4k或8k，也就是我们读取一页内的数据时候，实际上才发生了一次IO，这个理论对于索引的数据结构设计非常有帮助。

• 二叉搜索树：好的情况O（log 2(n)）,坏的情况O（n）(极端不平衡，退化成线性了)

• 自平衡二叉搜索树、红黑树：都是O（log 2(n)），因为加了自平衡算法和约束。

• B树（m阶多路搜索树）：O(logm(n))

• B + 树：控制在有限的次数内，与N无关
    经过了比较，你肯定知道了哪个好哪个坏了吧，接下来我就重点介绍一下B树和B+ 树，因为这是数据库引擎比较常选择的。

3、B树

  实际上B树就是一个多路平衡搜索树，就像下图这样

B树.png

  和二叉搜索树是一样的，我举个例子好了，例如说磁盘块1，有两个数据17和35，三个指针P1、P2、P3，小于17的跟随P1指向磁盘块2，17—35之间的跟随P2 指向磁盘块3，大于35的跟随P3指向磁盘块4，如果你是正好17或是35 ，那就命中啦，直接返回；同理
  每次增删改的时候就会调整这个树，这样就会保证平衡，具体我也忘了怎么调整的，因为平常也不怎么关注它是怎么调整的.....都是别人写好了的，有兴趣的可以去搜一搜，反正我每次看了一下又忘了........吐槽自己...

这样其实是比较完美的，但还存在几个问题：

（1）无法定位数据行：只能找到key,然后根据key再找到数据
  我们其实可以这样解决，在节点中增加一个字段，用来指向对应数据行，这样带来了一点开销
（2）无法进行范围查询
  只能先查找左边界，然后查找后边界，然后遍历，没什么办法了
  这样B+树就诞生了，它比B树的IO读写次数更少

3、B+ 树

  和B树很类似又不同，如下图

image.png

4、索引优化

既然说了那么多索引，那么我们平常时候索引的时候应该怎么使用更高呢？

1、自增主键非常关键

首先Int需要的空间也不紧凑，这样利用率大，编程的时候也不用担心主键的问题；还有就是每次插入都是放在最后面，不会担心页分裂的情况，不需要维护这个（每次创建表的时候都会默认产生一个唯一聚簇索引，是以主键为key的，以后索引都是参照这个，我们创建自增key就是为了方便维护这个聚簇索引）

2、不要随便建很多索引

因为维护需要很大的成本，如果改观不是很大就不要建索引，

3、索引失效的情况

很多索引失效的情况，我在另一篇中写了，写sql时候要注意

4、最左匹配原则

联合索引的时候都会默认从最左边开始，所以索引列的顺序很重要，建立索引的时候就应该把最常用的放在左边，使用select的时候也是这样，从最左边的开始，依次匹配右边的

5、选择有区分度的作为索引

区分度的公式是count(distinct <col>) / count(*)，表示字段不重复的比例，比例越大区分度越好。