索引

为什么要使用索引？
为了提高查询速率，避免全表扫描
数据存储的最小单位是块或者页，由多行记录构成，把这些加载进内存，然后对每个块或者页进行轮询查找，非常慢，类似于一本字典从第一页开始翻，翻到你需要查的字位置。全表扫描只适用于少量数据。
对于索引，就是引入目录。我们通过部首，拼音，等方式，按照逻辑快速定位，缩小了查找范围，增加了查找速率。

什么样的信息可以成为索引
表设计层面,我们一般建议使用自增ID做PRIMARY KEY,业务主键做UNIQUE KEY,原因如下:
1.如果业务主键做PRIMARY KEY,业务主键的插入顺序比较随机,这样会导致插入时间偏长,而且聚簇索引叶节点分裂严重,导致碎片严重,浪费空间;而自增ID做PRIMARY KEY的情况下,顺序插入,插入快,而且聚簇索引比较紧凑,空间浪费小。
2.一般表设计上除了PRIMARY KEY外,还会有几个索引用来优化读写.而这些非PK索引叶节点中都要存储PRIMARY KEY,以指向数据行,从而关联非索引中的字段内容.这样自增ID（定义为bigint才占用8个字节）和业务主键(通常字符串,多字段,空间占用大)相比,做PRIMARY KEY在索引空间层面的优势也是很明显的(同时也会转换为时间成本层面的优势),表定义中的索引越多,这种优势越明显。

综上所述,我们一般建议使用自增ID做PRIMARY KEY,业务主键做UNIQUE KEY。

使用AVL查找树作为索引
时间复杂度：O(nlogn)
（1）平衡二叉树要求很高，对于每次的插入和删除，通过旋转等操作树的结构调整代价过大；
（2）平衡二叉树，因为是二叉，所以数据量大的时候，树不可避免地会非常深，每一次检索到下一层都会进行一次io，而数据库查询速率与io密切相关，就会导致搜索变慢。

使用B-tree作为索引
B-tree（每个结点都包含关键字和指向孩子结点的指针）：
（1）根结点至少两个孩子
（2）其他节点最多包含m个孩子（m>=2）
（3）除根结点和叶子结点外。其他每个节点至少有ceil（m/2）个孩子（ceil表示取上限3/2=2）
（4）所有叶子结点都位于同一层
（5）关键字按升序排序
（6）关键字个数满足ceil（m/2）-1<=n<=m-1
（7）非叶子结点的指针，指向的结点的关键字值的大小依旧是满足普通树的波浪形（详见我的红黑树解说）。

B-tree

B-tree做索引可以降低树的高度，减少io次数。

B+-tree作为索引
与B-tree的不同定义：
（1）非叶子结点的子树指针与关键字个数相同；
（2）非叶子结点的子树指针P[i]，指向关键字值为[K[i],K[i+1])的子树；
（3）非叶子结点仅用来做索引，数据都保存在叶子结点中；

B+-tree

B+树的磁盘读写代价更低，如果关键字全部都在同一个盘块中，降低io次数；
*B+树的非叶子结点存储的都是关键字和指针，而并非直接的数据，因为指针所占大小远小于数据大小，所以，存放指针可以让该结点的页内存存放更多的关键字+指针，从而降低树的高度，使之扁平化。
B+树所有的查询都要走到叶子结点，所以查询数据速率稳定；
B+树的范围查询，性能高。
B+树3层就可以达到千万级别的数据存储了，但是只需要io三次。

Hash索引
hash索引查询效率高，O(1)。
但是hash索引仅仅适用于“=”或者“in”，不能做范围查询
如果hash分布不好，那么还是会遍历长长的链表，效率低下

hash索引

密集索引和稀疏索引的区别

定义 密集索引和稀疏索引 数据库引擎的索引方式

数据库引擎

使用InnoDB做数据库引擎（主键为密集）

person_info_large

使用MyISAM做数据库引擎（都为稀疏）

shop_info_small
表结构：frm
innodb的数据和索引都存储在.ibd中

myisam的数据存在.MYD中，索引存在.MYI中

数据库两种引擎存储方式的持久化表现

如何优化慢sql
（1）分析慢日志，定位慢sql
查询慢sql信息

show variables like ‘%query%’

查找本次会话的慢查询数目

show status like ‘%slow_queries%’

（2）explain分析慢sql

关键字type
关键字extra

业务SQL经常会有order by,一般来说这需要真实的物理排序才能达到这个效果, 这就是我们所说的Using filesort,一般来说它需要检索出所有的符合where条件的数据记录,而后在内存/文件层面进行物理排序,所以一般是一个很耗时的操作,是我们极力想要避免的.
但其实对于MySQL来说,却不一定非得物理排序才能达到order by的效果,也可以通过索引达到order by的效果,却不需要物理排序.
因为索引通过叶节点上的双向链表实现了逻辑有序性,比如说对于where a=? order by b limit 1; 可以直接使用index(a,b)来达到效果,不需要物理排序,从索引的根节点,走到叶节点,找到a=?的位置,因为这时b是有序的,只要顺着链表向右走,扫描1个位置,就可以找到想要的1条记录,这样既达到了业务SQL的要求,也避免了物理的排序操作。这种情况下,执行计划的Extra部分就不会出现Using filesort,因为它只扫描了极少量的索引叶节点就返回了结果,所以一般而言,执行很快,资源消耗很少,是我们想要的效果.

（3）调整慢sql的查询逻辑
（4）尽量走索引

实际慢sql场景

磁盘持久化数据单位
在计算机中磁盘存储数据最小单元是扇区，一个扇区的大小是512字节，而文件系统（例如XFS/EXT4）他的最小单元是块，一个块的大小是4k，而对于我们的InnoDB存储引擎也有自己的最小储存单元——页（Page），一个页的大小是16K。

如果数据库只按这样的方式存储，那么如何查找数据就成为一个问题，因为我们不知道要查找的数据存在哪个页中，也不可能把所有的页遍历一遍，那样太慢了。所以人们想了一个办法，用B+树的方式组织这些数据。如图所示：

B+树在页中

我们先将数据记录按主键进行排序，分别存放在不同的页中（为了便于理解我们这里一个页中只存放3条记录，实际情况可以存放很多），除了存放数据的页以外，还有存放键值+指针的页，如图中page number=3的页，该页存放键值和指向数据页的指针，这样的页由N个键值+指针组成。当然它也是排好序的。这样的数据组织形式，我们称为索引组织表。现在来看下，要查找一条数据，怎么查？

如select * from user where id=5;

这里id是主键,我们通过这棵B+树来查找，首先找到根页，你怎么知道user表的根页在哪呢？其实每张表的根页位置在表空间文件中是固定的，即page number=3的页（这点我们下文还会进一步证明），找到根页后通过二分查找法，定位到id=5的数据应该在指针P5指向的页中，那么进一步去page number=5的页中查找，同样通过二分查询法即可找到id=5的记录：

<colgroup><col><col><col></colgroup>
| 5 | zhao2 | 27 |

现在我们清楚了InnoDB中主键索引B+树是如何组织数据、查询数据的，我们总结一下：

1、InnoDB存储引擎的最小存储单元是页，页可以用于存放数据也可以用于存放键值+指针，在B+树中叶子节点存放数据，非叶子节点存放键值+指针。

2、索引组织表通过非叶子节点的二分查找法以及指针确定数据在哪个页中，进而在去数据页中查找到需要的数据；

那么回到我们开始的问题，通常一棵B+树可以存放多少行数据？

这里我们先假设B+树高为2，即存在一个根节点和若干个叶子节点，那么这棵B+树的存放总记录数为：根节点指针数*单个叶子节点记录行数。

上文我们已经说明单个叶子节点（页）中的记录数=16K/1K=16。（这里假设一行记录的数据大小为1k，实际上现在很多互联网业务数据记录大小通常就是1K左右）。

那么现在我们需要计算出非叶子节点能存放多少指针，其实这也很好算，我们假设主键ID为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节，这样一共14字节，我们一个页中能存放多少这样的单元，其实就代表有多少指针，即16384/14=1170。那么可以算出一棵高度为2的B+树，能存放1170*16=18720条这样的数据记录。

根据同样的原理我们可以算出一个高度为3的B+树可以存放：1170* 1170 *16=21902400条这样的记录。所以在InnoDB中B+树高度一般为1-3层，它就能满足千万级的数据存储。在查找数据时一次页的查找代表一次IO，所以通过主键索引查询通常只需要1-3次IO操作即可查找到数据。

---

使用了索引但还是很慢要怎么处理？
（1）B+树有最左匹配原则：那如果好几个查询字段都有索引，我们要注意顺序，最好可以第一次查找就能定位到比较精确的内容；比如名字和性别都建立了索引，那性别检索完一次之后因为他不够细化，所以需要再次检索的数据量依旧很大，就会影响效率了，并且性别这种字段，就不应该建立索引(字段的选择性
select count(1)/count(distinct col) )；
（2）索引字段尽可能的小，因为上面分析了，如果非叶子结点的关键字的大小太大，那么会使得该页中可存放的关键字+指针的数量变少，从而，存储相同量数据时，建立索引所需要的高度更深，增加io次数；
（3）对于type为all的需要优化，对于extra为using filesort和using temporary的需要优化；
（4）is null走索引，is not null不走索引；
（5）like只有前匹配走索引，如“a%”，其他的范围查找都不走索引；
（6）函数不走索引；
（7）使用不等于操作符如：<>、!= 等不走索引；
（8）对于count(*)当索引字段有not null约束时走索引，否则不走索引；
（9）隐式类型转换不走索引。
索引越多越好吗？
当然不是，物极必反。
（1）数据量小的表不需要建立索引，因为建立索引会增加额外的开销；
（2）数据变更需要维护索引，因此更多的索引意味着更多的维护成本；
（3）更多的索引意味着更多的存储空间。

当然索引也并不是越多越好，我曾经遇到这样一个问题：某台MySQL服务器iostat显示磁盘使用率一直处于100%，经过分析后发现是由于开发人员添加了太多的索引，在删除一些不必要的索引之后，磁盘使用率马上下降为20%。可见索引的添加也是非常有技术含量的。

什么情况下，明明创建了索引却没有使用索引
查询优化器
根据查询优化器选择最快成本最低的解。
(1)找到所有索引，计算不同索引执行的代价；
(2)全表扫描的代价；
(3)拿到最低成本最快的解。

并不是在所有的查询条件中出现的列都需要添加索引。对于什么时候添加B+树索引，一般的经验是，在访问表中很少一部分时使用B+树索引才有意义。对于性别字段、地区字段、类型字段，它们可取值的范围很小，称为低选择性。Cardinality/size越接近1越好。

Cardinality为NULL，在某些情况下可能会发生索引建立了却没有用到的情况。或者对两条基本一样的语句执行EXPLAIN，但是最终出来的结果不一样：一个使用索引，另外一个使用全表扫描。这时最好的解决办法就是做一次ANALYZE TABLE的操作。因此我建议在一个非高峰时间，对应用程序下的几张核心表做ANALYZE TABLE操作，这能使优化器和索引更好地为你工作。

主键索引只查一次，非主键索引必须回表查询吗？
不是，覆盖索引的话，可以不用回表。
指的是从索引中就可以获取结果了，不需要回表。
最左前缀匹配
如果联合索引(key1,key2,key3)
其实是三个索引
(key1)，(key1,key2)，(key1,key2,key3)
所以我们需要用最有辨别度的列做第一个索引。

参考资料：
慕课网
一棵b+树可以存放多少数据呢
null值会走索引吗？