这类问题可能经常面试会被问到，其实我觉得也是很关键的，如何合理使用索引，可以加快你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
它的主要特点是叶子节点存储真实数据，非叶子节点只是相当于一个引路的（关键字），每一次访问索引最后一定要访问到叶子节点，因为这里才存放着数据行
还有叶子节点直接有指针相连接，方便顺序访问（每次看到这个总容易想到跳表....）
那么相比B树，B+ 树有什么优势呢？
（1）支持顺序访问：这就不用说了吧，叶子节点都是有序，而且有指针相连
（2）磁盘读写代价小：B+树非叶子节点没有指向数据行的指针，所以相同的磁盘容量存储的节点数更多，相应的IO读写次数肯定减少了。
（3）查询效率稳定：不会出现极端情况，因为每次都要访问叶子节点才能取到数据。
（4）支持范围查询：遍历轻松
4、索引优化
既然说了那么多索引，那么我们平常时候索引的时候应该怎么使用更高呢？
1、自增主键非常关键
首先Int需要的空间也不紧凑，这样利用率大，编程的时候也不用担心主键的问题；还有就是每次插入都是放在最后面，不会担心页分裂的情况，不需要维护这个（每次创建表的时候都会默认产生一个唯一聚簇索引，是以主键为key的，以后索引都是参照这个，我们创建自增key就是为了方便维护这个聚簇索引）
2、不要随便建很多索引
因为维护需要很大的成本，如果改观不是很大就不要建索引，
3、索引失效的情况
很多索引失效的情况，我在另一篇中写了，写sql时候要注意
4、最左匹配原则
联合索引的时候都会默认从最左边开始，所以索引列的顺序很重要，建立索引的时候就应该把最常用的放在左边，使用select的时候也是这样，从最左边的开始，依次匹配右边的
5、选择有区分度的作为索引
区分度的公式是count(distinct <col>) / count(*)，表示字段不重复的比例，比例越大区分度越好。
网友评论