1. 索引分类
我们可以按照四个角度来分类索引。
- 按「数据结构」分类:B+tree索引、Hash索引、Full-text索引。
- 按「物理存储」分类:聚簇索引(主键索引)、二级索引(辅助索引)。
- 按「字段特性」分类:主键索引、唯一索引、普通索引、前缀索引。
- 按「字段个数」分类:单列索引、联合索引。
2. B树和B+树
2.1 B 树( B- 树)
- 关键字分布在整棵树的所有节点。
- 任何一个关键字 出现且只出现在一个节点中。
- 搜索有可能在 非叶子节点 结束。
- 其搜索性能等价于在关键字全集内做一次二分查找。如下图所示:
2.2 B+ 树
- 非叶子节点的子树指针与关键字个数相同。
- 非叶子节点的子树指针 P[i],指向关键字属于 [k[i],K[i+1]) 的子树(注意:区间是前闭后开)。
- 为所有叶子节点增加一个链指针。
- 所有关键字都在叶子节点出现。
2.3 B+树 查询
- InnoDB 的数据是按「数据页」为单位来读写的,也就是说,当需要读一条记录的时候,并不是将这个记录本身从磁盘读出来,而是以页为单位,将其整体读入内存。
- 如果某个查询语句使用了二级索引,但是查询的数据不是主键值,这时在二级索引找到主键值后,需要去聚簇索引中获得数据行,这个过程就叫作「回表」,也就是说要查两个 B+ 树才能查到数据。
- 不过,当查询的数据是主键值时,因为只在二级索引就能查询到,不用再去聚簇索引查,这个过程就叫作「索引覆盖」,也就是只需要查一个 B+ 树就能找到数据。
2.4 为什么选用B+树
1、B+Tree vs B Tree
B+树的高度比较稳定,因为它的非叶子节点不会保存数据,只保存键值和指针的情况下,一个页能承载大量的数据。
- B+ 树的磁盘读写代价更低。B+ 树的内部没有指向关键字具体信息的指针,所以其内部节点相对 B 树更小,如果把所有关键字存放在同一块盘中,那么盘中所能容纳的关键字数量也越多,一次性读入内存的需要查找的关键字也就越多,相应的,IO 读写次数就降低了。
- 树的查询效率更加稳定。B+ 树所有数据都存在于叶子节点,所有关键字查询的路径长度相同,每次数据的查询效率相当。而 B 树可能在非叶子节点就停止查找了,所以查询效率不够稳定。
- B+ 树只需要去遍历叶子节点就可以实现整棵树的遍历。
2. B+Tree vs 二叉树
对于有 N 个叶子节点的 B+Tree,其搜索复杂度为O(logdN)
,其中 d 表示节点允许的最大子节点个数为 d 个。
在实际的应用当中, d 值是大于100的,这样就保证了,即使数据达到千万级别时,B+Tree 的高度依然维持在 3到4 层左右,也就是说一次数据查询操作只需要做 3到4 次的磁盘 I/O 操作就能查询到目标数据。
而二叉树的每个父节点的儿子节点个数只能是 2 个,意味着其搜索复杂度为 O(logN)
,这已经比 B+Tree 高出不少,因此二叉树检索到目标数据所经历的磁盘 I/O 次数要更多。
2.3 B+Tree vs Hash
Hash 在做等值查询的时候效率贼快,搜索复杂度为 O(1)。
但是 Hash 表不适合做范围查询,它更适合做等值的查询,这也是 B+Tree 索引要比 Hash 表索引有着更广泛的适用场景的原因。
2.5 B+ 树存储多少数据
InnoDB存储引擎它也是有最小存储单位的,叫做页(Page),默认大小是16kb。页可以放一行一行的数据(叶子节点),也可以放主键+指针(非叶子节点)。
假如我们的主键id为bigint类型,长度为8字节,而指针大小在InnoDB源码中设置为6字节。这样算下来就是 16*1024 / 14 = 1170,就是说一个页上可以存放1170个指针。
一个指针指向一个存放记录的页,一个页里可以放16条数据,那么一颗高度为2的B+树就可以存放 1170 * 16=18720 条数据。同理,高度为3的B+树,就可以存放 1170 * 1170 * 16 = 21902400 条1k数据的记录。
B+树的高度一般为2-4层,就可以满足千万级数据的存储。
查找数据的时候,一次页的查找代表一次IO,那我们通过主键索引查询的时候,其实最多只需要2-4次IO就可以了。
3. 聚集索引和非聚集索引
3.1 InnoDB 和 MyISAM 区别
InnoDB 是由一个聚集索引和非聚集索引构成。MyISAM 全是非聚集索引。
但是无论是什么,底层的数据结构都是用 B+树实现的。
1. MyISAM 非聚集索引
MyISAM的索引方式也叫做“非聚集”的,之所以这么称呼是为了与InnoDB的聚集索引区分。
非聚簇索引的主键索引和辅助索引两棵B+树看上去没什么不同,节点的结构完全一致只是存储的内容不同而已。
主键索引B+树的节点存储了主键,辅助键索引B+树存储了辅助键。表数据存储在独立的地方,这两颗B+树的叶子节点都使用一个地址指向真正的表数据,对于表数据来说,这两个键没有任何差别。
由于索引树是独立的,通过辅助键检索无需访问主键的索引树。
索引文件(.MYI)和数据文件(.MYD)文件是分离的, 索引文件仅保存数据记录的地址(指针去查找)。
2. InnoDB 聚集索引
- 聚集索引(clustered index)就是按照每张表的主键构造一棵B+树,同时叶子节点中存放的即为整张表的行记录数据,也将聚集索引的叶子节点称为数据页。
- 聚集索引的这个特性决定了索引组织表中数据也是索引的一部分。同 B+ 树数据结构一样,每个数据页都通过一个双向链表来进行链接。
- 由于实际的数据页只能按照一棵 B+ 树进行排序,因此每张表只能拥有一个聚集索引。在多数情况下,查询优化器倾向于采用聚集索引。因为聚集索引能够在 B+ 树索引的叶子节点上直接找到数据。此外,由于定义了数据的逻辑顺序,聚集索引能够特别快地访问针对范围值的查询。查询优化器能够快速发现某一段范围的数据页需要扫描。
- 聚集索引的存储并不是物理上连续的,而是逻辑上连续的。
- 如果一个主键被定义了,那么这个主键就是作为聚集索引。如果没有主键被定义,那么该表的第一个唯一非空索引被作为聚集索引。如果没有主键也没有合适的唯一索引,那么innodb内部会生成一个隐藏的主键作为聚集索引,这个隐藏的主键是一个6个字节的列,改列的值会随着数据的插入自增。
- 聚集索引的另一个好处是,它对于主键的排序查找和范围查找速度非常快。叶子节点的数据就是用户所要查询的数据。
3.2 InnoDB的聚集索引和非聚集索引
在数据库中,B+ 树的高度一般都在 2~4 层,这也就是说查找某一键值的行记录时最多只需要 2 到 4 次 IO,这倒不错。因为当前一般的机械磁盘每秒至少可以做 100 次 IO,2~4 次的 IO 意味着查询时间只需 0.02~0.04 秒。
1. InnoDB 是由一个聚集索引和非聚集索引构成
数据库中的B+树索引可以分为聚集索引(clustered inex)和辅助索引(secondary index)。辅助索引有时也称非聚集索引(non-clustered index)。
但是不管是聚集还是辅助的索引,其内部都是B+树的,即高度平衡的,叶子节点存放着所有的数据。聚集索引与辅助索引不同的是,叶子节点存放的是否是一整行的信息。
2. InnoDB 非聚集索引
叶子节点并不包含行记录的全部数据(只有索引字段本身的数据,废话)。叶子节点除了包含键值以外,每个叶子节点中的索引行中还包含了一个书签(bookmark)。该书签用来告诉InnoDB存储引擎哪里可以找到与索引相对应的行数据。
如果在一棵高度为3的辅助索引树中查找数据,那需要对这棵辅助索引树遍历3次找到指定主键,如果聚集索引树的高度同样为3,那么还需要对聚集索引树进行3次查找,最终找到一个完整的行数据所在的页,因此一共需要6次逻辑IO访问以得到最终的一个数据页。
3.3 总结
例如知道了InnoDB的索引实现后,就很容易明白为什么不建议使用过长的字段作为主键,因为所有辅助索引都引用主索引,过长的主索引会令辅助索引变得过大。
再例如,用非单调的字段作为主键在InnoDB中不是个好主意,因为InnoDB数据文件本身是一颗B+Tree,非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整,十分低效,而使用自增字段int作为主键则是一个很好的选择。
4. 索引机制
4.1 查看索引
1 | SHOW INDEX FROM table_name; |
Cardinality:非常关键的值,表示索引中唯一值的数目的估计值。Cardinality表的行数应尽可能接近1,如果非常小,那么用户需要考虑是否可以删除此索引。
Null:是否索引的列含有NULL值。可以看到idx_b这里为Yes,因为定义的列b允许NULL值。
4.2 Cardinality
Cardinality值非常关键,优化器会根据这个值来判断是否使用这个索引。
但是这个值并不是实时更新的,如果需要更新索引Cardinality的信息,可以使用ANALYZE TABLE命令。
对两条基本一样的语句执行EXPLAIN,但是最终出来的结果不一样:一个使用索引,另外一个使用全表扫描。这时最好的解决办法就是做一次ANALYZE TABLE的操作。因此我建议在一个非高峰时间,对应用程序下的几张核心表做ANALYZE TABLE操作,这能使优化器和索引更好地为你工作。
在InnoDB存储引擎中,Cardinality统计信息的更新发生在两个操作中:INSERT和UPDATE。但是表中1/16的数据已发生过变化,或者stat_modified_counter>2 000 000 000
4.3 覆盖索引
InnoDB存储引擎支持覆盖索引(covering index,或称索引覆盖),即从辅助索引中就可以得到查询的记录,而不需要查询聚集索引中的记录。
对于InnoDB存储引擎的辅助索引而言,由于其包含了主键信息,因此其叶子节点存放的数据为(primary key1,primary key2,…,key1,key2,…)。例如,下列语句都可仅使用一次辅助联合索引来完成查询:
1 | SELECT key2 FROM table WHERE key1=xxx; |
覆盖索引的另一个好处是对某些统计问题而言的。
1 | SELECT COUNT(*)FROM buy_log; |
InnoDB存储引擎并不会选择通过查询聚集索引来进行统计。由于buy_log表上还有辅助索引,而辅助索引远小于聚集索引,选择辅助索引可以减少IO操作。
1 | SELECT COUNT(*)FROM buy_log |
表buy_log有(userid,buy_date)的联合索引,这里只根据列b进行条件查询,一般情况下是不能进行该联合索引的,但是这句SQL查询是统计操作,并且可以利用到覆盖索引的信息,因此优化器会选择该联合索引。
4.4 强制使用某个索引
如果用户确定指定某个索引来完成查询,那么最可靠的是使用FORCE INDEX,而不是USE INDEX。
6. 索引方案
6.1 建立索引机制
最左前缀匹配原则(重要,重要,重要)
复合索引(col1, col2, col3),能使用的是(col1), (col1, col2), (col1, col2, col3)。 (col1, col3)会启用(col1)的索引查询
ESR原则
精确(equal)匹配的字段放在最前面,排序(sort)条件放中间,范围(range)匹配的字段放在最后面
尽量选择区分度高的列作为索引
区分度的公式是 count(distinct col)/count(*),表示字段不重复的比例,比例越大我们扫描的记录数越少,唯一键的区分度是1。
使用短索引
例如,有一个CHAR(200)列,如果在前10个或20个字符内,多数值是唯一的,那么就不要对整个列进行索引。对前10个或者20个字符进行索引能够节省大量索引空间,也可能会使查询更快。
尽量的扩展索引,不要新建索引
比如表中已经有a的索引,现在要加(a,b)的索引,那么只需要修改原来的索引即可。索引的列不要为 null
也能建立索引, 但是会造成不符合预期的行为。
6.2 索引失效的场景
联合索引非最左匹配
数据类型隐式转换
1
2
3phone varchar(20)
select phone where phone = '1000000' # 用到索引
select phone where phone = 1000000 # 用不到索引索引列参与计算 , WHERE
age
+10=30索引列使用了函数, from_unixtime(create_time) = ’2014-05-29’,应该写成create_time = unix_timestamp(’2014-05-29’)。
模糊查询 like 以%开头
查询结果集是原表中的大部分数据,mysql估计使用全表扫描要比使用索引快,则不使用索引。
or前后没有同时使用索引,虽然name字段上加了索引,但是age字段没有索引,使用or的时候会全表扫描。
7. 头脑风暴
- B+树走索引是从上往下,全表扫描是从左往右。
- InnoDB只能有一个聚集索引,索引和数据在一起。
- InnoDB其他的索引就做辅助索引,走索引后,找到的数据时在用聚集索引,再次回表查询。
- 建立索引:最左匹配,区分度高,不要为 null,扩展索引,数量控制。
- 查询索引:复合索引,不参与函数,不强转类型。