什么是索引,索引的作用
当我们要在新华字典里查某个字(如「先」)具体含义的时候,通常都会拿起一本新华字典来查,你可以先从头到尾查询每一页是否有「先」这个字,这样做(对应数据库中的全表扫描)确实能找到,但效率无疑是非常低下的,更高效的方相信大家也都知道,就是在首页的索引里先查找「先」对应的页数,然后直接跳到相应的页面查找,这样查询时候大大减少了,可以为是 O(1)。
数据库中的索引也是类似的,通过索引定位到要读取的页,大大减少了需要扫描的行数,能极大的提升效率,简而言之,索引主要有以下几个作用:
- 即上述所说,索引能极大地减少扫描行数
- 索引可以帮助服务器避免排序和临时表
- 索引可以将随机 IO 变成顺序 IO
MySQL中索引的存储类型有两种:BTREE和HASH
,具体和表的存储引擎相关;
MyISAM和InnoDB存储引擎只支持BTREE索引,MEMORY/HEAP存储引擎可以支持HASH和BTREE索引。
第一点上文已经解释了,我们来看下第二点和第三点
先来看第二点,假设我们不用索引,试想运行如下语句
|
|
则 MySQL 的流程是这样的,扫描所有行,把所有行加载到内存后,再按 age 排序生成一张临时表,再把这表排序后将相应行返回给客户端,更糟的,如果这张临时表的大小大于 tmp_table_size 的值(默认为 16 M),内存临时表会转为磁盘临时表,性能会更差,如果加了索引,索引本身是有序的 ,所以从磁盘读的行数本身就是按 age 排序好的,也就不会生成临时表,就不用再额外排序 ,无疑提升了性能。
再来看随机 IO 和顺序 IO。先来解释下这两个概念。
相信不少人应该吃过旋转火锅,服务员把一盘盘的菜放在旋转传输带上,然后等到这些菜转到我们面前,我们就可以拿到菜了,假设装一圈需要 4 分钟,则最短等待时间是 0(即菜就在你跟前),最长等待时间是 4 分钟(菜刚好在你跟前错过),那么平均等待时间即为 2 分钟,假设我们现在要拿四盘菜,这四盘菜随机分配在传输带上,则可知拿到这四盘菜的平均等待时间是 8 分钟(随机 IO),如果这四盘菜刚好紧邻着排在一起,则等待时间只需 2 分钟(顺序 IO)。
上述中传输带就类比磁道,磁道上的菜就类比扇区(sector)中的信息,磁盘块(block)是由多个相邻的扇区组成的,是操作系统读取的最小单元,这样如果信息能以 block 的形式聚集在一起,就能极大减少磁盘 IO 时间,这就是顺序 IO 带来的性能提升,下文中我们将会看到 B+ 树索引就起到这样的作用。
如图示:多个扇区组成了一个 block,如果要读的信息都在这个 block 中,则只需一次 IO 读
而如果信息在一个磁道中, 分散地分布在各个扇区中,或者分布在不同磁道的扇区上(寻道时间是随机IO主要瓶颈所在),将会造成随机 IO,影响性能。
我们来看一下一个随机 IO 的时间分布:
- seek Time: 寻道时间,磁头移动到扇区所在的磁道
- Rotational Latency:完成步骤 1 后,磁头移动到同一磁道扇区对应的位置所需求时间
- Transfer Time 从磁盘读取信息传入内存时间
这其中寻道时间占据了绝大多数的时间(大概占据随机 IO 时间的占 40%)。
随机 IO 和顺序 IO 大概相差百倍 (随机 IO:10 ms/ page, 顺序 IO 0.1ms / page),可见顺序 IO 性能之高,索引带来的性能提升显而易见!
索引的种类
索引主要分为以下几类
- B+树索引
- 哈希索引
B+树索引
B+ 树索引之前在此文中详细阐述过,强烈建议大家看一遍,对理解 B+ 树有很大的帮助,简单回顾一下吧
B+ 树是以 N 叉树的形式存在的,这样有效降低了树的高度,查找数据也不需要全表扫描了,顺着根节点层层往下查找能很快地找到我们的目标数据。 每个节点的大小即一个页的大小,一次 IO 会将一个页(每页包含多个磁盘块)的数据都读入(即磁盘预读,程序局部性原理:读到了某个值,很大可能这个值周围的数据也会被用到,干脆一起读入内存),叶子节点通过指针的相互指向连接,能有效减少顺序遍历时的随机 IO,而且我们也可以看到,叶子节点都是按索引的顺序排序好的,这也意味着根据索引查找或排序都是排序好了的,不会再在内存中形成临时表。
详解:Mysql设计利用了磁盘预读原理,将一个B+Tree节点大小设为一个页大小,在新建节点时直接申请一个页的空间,这样就能保证一个节点物理上存储在一个页里,加之计算机存储分配都是按页对齐的,这样就实现了每个Node节点只需要一次I/O操作。
一般来说B+Tree比BTree更适合实现外存的索引结构,因为存储引擎的设计专家巧妙的利用了外存(磁盘)的存储结构,即磁盘的最小存储单位是扇区(sector),而操作系统的块(block)通常是整数倍的sector,操作系统以页(page)为单位管理内存,一页(page)通常默认为4K,数据库的页通常设置为操作系统页的整数倍16K,因此索引结构的节点被设计为一个页的大小,然后利用外存的“预读取”原则,每次读取的时候,把整个节点的数据读取到内存中,然后在内存中查找,已知内存的读取速度是外存读取I/O速度的几百倍,那么提升查找速度的关键就在于尽可能少的磁盘I/O,那么可以知道,每个节点中的key个数越多,那么树的高度越小,需要I/O的次数越少,因此一般来说B+Tree比BTree更快,因为B+Tree的非叶节点中不存储data,就可以存储更多的key。
B树和B+树的区别,数据库为什么使用B+树而不是B树?
- 在B树中,键和值即存放在内部节点又存放在叶子节点;在B+树中,内部节点只存键,叶子节点则同时存放键和值。
- B+树的叶子节点有一条链相连,而B树的叶子节点各自独立的。
- B+树索引的所有数据均存储在叶子节点,而且数据是按照顺序排列的,链表连着的。那么B+树使得范围查找,排序查找,分组查找以及去重查找变得异常简单。
- B+树非叶子节点上是不存储数据的,仅存储键值,而B树节点中不仅存储键值,也会存储数据。innodb中页的默认大小是16KB,如果不存储数据,那么就会存储更多的键值,相应的树的阶数(节点的子节点树)就会更大,树就会更矮更胖,如此一来我们查找数据进行磁盘的IO次数有会再次减少,数据查询的效率也会更快.
- 因为B树不管叶子节点还是非叶子节点,都会保存数据,这样导致在非叶子节点中能保存的指针数量变少(有些资料也称为扇出),指针少的情况下要保存大量数据,只能增加树的高度,导致IO操作变多,查询性能变低;B 树进行范围查询,会产生大量随机IO
- 在B+树中叶子节点存放数据,非叶子节点存放键值+指针。
哈希索引
哈希索引基本散列表实现,散列表(也称哈希表)是根据关键码值(Key value)而直接进行访问的数据结构,它让码值经过哈希函数的转换映射到散列表对应的位置上,查找效率非常高。假设我们对名字建立了哈希索引,则查找过程如下图所示:
对于每一行数据,存储引擎都会对所有的索引列(上图中的 name 列)计算一个哈希码(上图散列表的位置),散列表里的每个元素指向数据行的指针,由于索引自身只存储对应的哈希值,所以索引的结构十分紧凑,这让哈希索引查找速度非常快!
当然了哈希表的劣势也是比较明显的,不支持区间查找,不支持排序,所以更多的时候哈希表是与 B Tree等一起使用的,在 InnoDB 引擎中就有一种名为「自适应哈希索引」的特殊索引,当 innoDB 注意到某些索引值使用非常频繁时,就会内存中基于 B-Tree 索引之上再创建哈希索引,这样也就让 B+ 树索引也有了哈希索引的快速查找等优点,这是完全自动,内部的行为,用户无法控制或配置,不过如果有必要,可以关闭该功能。
innoDB 引擎本身是不支持显式创建哈希索引的,我们可以在 B+ 树的基础上创建一个伪哈希索引,它与真正的哈希索引不是一回事,它是以哈希值而非键本身来进行索引查找的,这种伪哈希索引的使用场景是怎样的呢,假设我们在 db 某张表中有个 url 字段,我们知道每个 url 的长度都很长,如果以 url 这个字段创建索引,无疑要占用很大的存储空间,如果能通过哈希(比如CRC32)把此 url 映射成 4 个字节,再以此哈希值作索引 ,索引占用无疑大大缩短!不过在查询的时候要记得同时带上 url 和 url_crc,主要是为了避免哈希冲突,导致 url_crc 的值可能一样
|
|
这样做把基于 url 的字符串索引改成了基于 url_crc 的整型索引,效率更高,同时索引占用的空间也大大减少,一举两得,当然人可能会说需要手动维护索引太麻烦了,那可以改进触发器实现。
除了上文说的两个索引 ,还有空间索引(R-Tree),全文索引等,由生产中不是很常用,这里不作过多阐述
高性能索引策略
不同的索引设计选择能对性能产生很大的影响,有人可能会发现生产中明明加了索引却不生效,有时候加了虽然生效但对搜索性能并没有提升多少,对于多列联合索引,哪列在前,哪列在后也是有讲究的,我们一起来看看
加了索引,为何却不生效
加了索引却不生效可能会有以下几种原因
1、索引列是表示式的一部分,或是函数的一部分
|
|
或者
|
|
上述两个 SQL 虽然在列 book_id 和 gmt_create 设置了索引 ,但由于它们是表达式或函数的一部分,导致索引无法生效,最终导致全表扫描。
2、隐式类型转换
以上两种情况相信不少人都知道索引不能生效,但下面这种隐式类型转换估计会让不少人栽跟头,来看下下面这个例子:
假设有以下表:
|
|
执行 SQL 语句
|
|
交易编号 tradeid 上有索引,但用 EXPLAIN 执行却发现使用了全表扫描,为啥呢,tradeId 的类型是 varchar(32), 而此 SQL 用 tradeid 一个数字类型进行比较,发生了隐形转换,会隐式地将字符串转成整型,如下:
|
|
这样也就触发了上文中第一条的规则 ,即:索引列不能是函数的一部分。
3、隐式编码转换
这种情况非常隐蔽,来看下这个例子
|
|
trade_detail 是交易详情, tradelog 是操作此交易详情的记录,现在要查询 id=2 的交易的所有操作步骤信息,则我们会采用如下方式
|
|
由于 tradelog 与 trade_detail 这两个表的字符集不同,且 tradelog 的字符集是 utf8mb4,而 trade_detail 字符集是 utf8, utf8mb4 是 utf8 的超集,所以会自动将 utf8 转成 utf8mb4。即上述语句会发生如下转换:
|
|
自然也就触发了 「索引列不能是函数的一部分」这条规则。怎么解决呢,第一种方案当然是把两个表的字符集改成一样,如果业务量比较大,生产上不方便改的话,还有一种方案是把 utf8mb4 转成 utf8,如下
|
|
这样索引列就生效了。
4、使用 order by 造成的全表扫描
|
|
上述语句在 age 上加了索引,但依然造成了全表扫描,这是因为我们使用了 SELECT *,导致回表查询,MySQL 认为回表的代价比全表扫描更大,所以不选择使用索引,如果想使用到 age 的索引,我们可以用覆盖索引来代替:
|
|
或者加上 limit 的条件(数据比较小)
|
|
这样就能利用到索引。
无法避免对索引列使用函数,怎么使用索引
时候我们无法避免对索引列使用函数,但这样做会导致全表索引,是否有更好的方式呢。
比如我现在就是想记录 2016 ~ 2018 所有年份 7月份的交易记录总数
|
|
由于索引列是函数的参数,所以显然无法用到索引,我们可以将它改造成基本字段区间的查找如下
|
|
前缀索引与索引选择性
之前我们说过,如于长字符串的字段(如 url),我们可以用伪哈希索引的形式来创建索引,以避免索引变得既大又慢,除此之外其实还可以用前缀索引(字符串的部分字符)的形式来达到我们的目的,那么这个前缀索引应该如何选取呢,这叫涉及到一个叫索引选择性的概念
索引选择性:不重复的索引值(也称为基数,cardinality)和数据表的记录总数的比值,比值越高,代表索引的选择性越好,唯一索引的选择性是最好的,比值是 1。
画外音:我们可以通过 SHOW INDEXES FROM table 来查看每个索引 cardinality 的值以评估索引设计的合理性
怎么选择这个比例呢,我们可以分别取前 3,4,5,6,7 的前缀索引,然后再比较下选择这几个前缀索引的选择性,执行以下语句
|
|
得结果如下
sel3 | sel4 | sel5 | sel6 | sel7 |
---|---|---|---|---|
0.0239 | 0.0293 | 0.0305 | 0.0309 | 0.0310 |
可以看到当前缀长度为 7 时,索引选择性提升的比例已经很小了,也就是说应该选择 city 的前六个字符作为前缀索引,如下
|
|
我们当前是以平均选择性为指标的,有时候这样是不够的,还得考虑最坏情况下的选择性,以这个 demo 为例,可能一些人看到选择 4,5 的前缀索引与选择 6,7 的选择性相差不大,那就得看下选择 4,5 的前缀索引分布是否均匀了
|
|
可能会出现以下结果
cnt | pref |
---|---|
305 | Sant |
200 | Toul |
90 | Chic |
20 | Chan |
可以看到分布极不均匀,以 Sant,Toul 为前缀索引的数量极多,这两者的选择性都不是很理想,所以要选择前缀索引时也要考虑最差的选择性的情况。
前缀索引虽然能实现索引占用空间小且快的效果,但它也有明显的弱点,MySQL 无法使用前缀索引做 ORDER BY 和 GROUP BY ,而且也无法使用前缀索引做覆盖扫描,前缀索引也有可能增加扫描行数。
假设有以下表数据及要执行的 SQL
d | |
---|---|
1 | zhangssxyz@163.com |
2 | zhangs1@163.com |
3 | zhangs1@163.com |
4 | zhangs1@163.com |
|
|
如果我们针对 email 设置的是整个字段的索引,则上表中根据 「zhangssxyz@163.com」查询到相关记记录后,再查询此记录的下一条记录,发现没有,停止扫描。此时可知只扫描一行记录,如果我们以前六个字符(即 email(6))作为前缀索引,则显然要扫描四行记录,并且获得行记录后不得不回到主键索引再判断 email 字段的值,所以使用前缀索引要评估它带来的这些开销。
另外有一种情况我们可能需要考虑一下,如果前缀基本都是相同的该怎么办,比如现在我们为某市的市民建立一个人口信息表,则这个市人口的身份证虽然不同,但身份证前面的几位数都是相同的,这种情况该怎么建立前缀索引呢。
一种方式就是我们上文说的,针对身份证建立哈希索引,另一种方式比较巧妙,将身份证倒序存储,查的时候可以按如下方式查询:
|
|
这样就可以用身份证的后六位作前缀索引了,是不是很巧妙 ^_^
实际上上文所述的索引选择性同样适用于联合索引的设计,如果没有特殊情况,我们一般建议在建立联合索引时,把选择性最高的列放在最前面,比如,对于以下语句:
|
|
单就这个语句而言, (staff_id,customer_id) 和 (customer_id, staff_id) 这两个联合索引我们应该建哪一个呢,可以统计下这两者的选择性。
|
|
结果为:
|
|
从中可以看出 customer_id 的选择性更高,所以应该选择 customer_id 作为第一列。
索引设计准则:三星索引
上文我们得出了一个索引列顺序的经验 法则:将选择性最高的列放在索引的最前列,这种建立在某些场景可能有用,但通常不如避免随机 IO 和 排序那么重要,这里引入索引设计中非常著名的一个准则:三星索引。
如果一个查询满足三星索引中三颗星的所有索引条件,理论上可以认为我们设计的索引是最好的索引。什么是三星索引
- 第一颗星:WHERE 后面参与查询的列可以组成了单列索引或联合索引
- 第二颗星:避免排序,即如果 SQL 语句中出现 order by colulmn,那么取出的结果集就已经是按照 column 排序好的,不需要再生成临时表
- 第三颗星:SELECT 对应的列应该尽量是索引列,即尽量避免回表查询。
所以对于如下语句:
|
|
设计的索引应该是 (age, name,city) 或者 (name, age,city)
当然 了三星索引是一个比较理想化的标准,实际操作往往只能满足期望中的一颗或两颗星,考虑如下语句:
|
|
假设我们分别为这三列建了联合索引,则显然它符合第三颗星(使用了覆盖索引),如果索引是(city, age, name),则虽然满足了第一颗星,但排序无法用到索引,不满足第二颗星,如果索引是 (city, name, age),则第二颗星满足了,但此时 age 在 WHERE 中的搜索条件又无法满足第一星,
另外第三颗星(尽量使用覆盖索引)也无法完全满足,试想我要 SELECT 多列,要把这多列都设置为联合索引吗,这对索引的维护是个问题,因为每一次表的 CURD 都伴随着索引的更新,很可能频繁伴随着页分裂与页合并。
综上所述,三星索引只是给我们构建索引提供了一个参考,索引设计应该尽量靠近三星索引的标准,但实际场景我们一般无法同时满足三星索引,一般我们会优先选择满足第三颗星(因为回表代价较大)至于第一,二颗星就要依赖于实际的成本及实际的业务场景考虑。
为什么要一定要设置主键?
from: https://zhuanlan.zhihu.com/p/116866170
其实这个不是一定的,有些场景下,小系统或者没什么用的表,不设置主键也没关系,mysql最好是用自增主键,主要是以下两个原因:果定义了主键,那么InnoDB会选择主键作为聚集索引、如果没有显式定义主键,则innodb 会选择第一个不包含有NULL值的唯一索引作为主键索引、如果也没有这样的唯一索引,则innodb 会选择内置6字节长的ROWID作为隐含的聚集索引。所以,反正都要生成一个主键,那你还不如自己指定一个主键,提高查询效率!
前面我写了几篇关于 mysql 索引的文章,索引是 mysql 非常重要的一部分。你也可能经常会看到一些关于 mysql 军规、mysql 查询优化的文章,其实这些操作的背后都是基于一定的原理的,你要想明白这些原理,首先就得知道 mysql 底层的一些东西。
我在这里举几个例子吧。
我们都知道表的主键一般都要使用自增 id,不建议使用业务 id ,是因为使用自增 id 可以避免页分裂。这个其实可以相当于一个结论,你都可以直接记住这个结论就可以了。
但是如果你要弄明白什么是页分裂,或者什么情况下会页分裂,这个时候你就需要对 mysql 的底层数据结构要有一定的理解了。
我这里也稍微解释一下页分裂,mysql (注意本文讲的 mysql 默认为InnoDB 引擎)底层数据结构是 B+ 树,所谓的索引其实就是一颗 B+ 树,一个表有多少个索引就会有多少颗 B+ 树,mysql 中的数据都是按顺序保存在 B+ 树上的(所以说索引本身是有序的)。
然后 mysql 在底层又是以数据页为单位来存储数据的,一个数据页大小默认为 16k,当然你也可以自定义大小,也就是说如果一个数据页存满了,mysql 就会去申请一个新的数据页来存储数据。
如果主键为自增 id 的话,mysql 在写满一个数据页的时候,直接申请另一个新数据页接着写就可以了。
如果主键是非自增 id,为了确保索引有序,mysql 就需要将每次插入的数据都放到合适的位置上。
当往一个快满或已满的数据页中插入数据时,新插入的数据会将数据页写满,mysql 就需要申请新的数据页,并且把上个数据页中的部分数据挪到新的数据页上。
这就造成了页分裂,这个大量移动数据的过程是会严重影响插入效率的。
其实对主键 id 还有一个小小的要求,在满足业务需求的情况下,尽量使用占空间更小的主键 id,因为普通索引的叶子节点上保存的是主键 id 的值,如果主键 id 占空间较大的话,那将会成倍增加 mysql 空间占用大小。
主键是用自增还是UUID
最好是用自增主键,主要是以下两个原因:
1. 如果表使用自增主键,那么每次插入新的记录,记录就会顺序添加到当前索引节点的后续位置,当一页写满,就会自动开辟一个新的页。 2. 如果使用非自增主键(如uuid),由于每次插入主键的值近似于随机,因此每次新纪录都要被插到索引页的随机某个位置,此时MySQL为了将新记录插到合适位置而移动数据,甚至目标页面可能已经被回写到磁盘上而从缓存中清掉,此时又要从磁盘上读回来,这增加了很多开销,同时频繁的移动、分页操作造成索引碎片,得到了不够紧凑的索引结构,后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。
不过,也不是所有的场景下都得使用自增主键,可能场景下,主键必须自己生成,不在乎那些性能的开销。那也没有问题。
自增主键用完了怎么办?
在mysql中,Int整型的范围(-2147483648~2147483648),约20亿!因此不用考虑自增ID达到最大值这个问题。而且数据达到千万级的时候就应该考虑分库分表了。
主键为什么不推荐有业务含义?
最好是主键是无意义的自增ID,然后另外创建一个业务主键ID,
因为任何有业务含义的列都有改变的可能性,主键一旦带上了业务含义,那么主键就有可能发生变更。主键一旦发生变更,该数据在磁盘上的存储位置就会发生变更,有可能会引发页分裂,产生空间碎片。
还有就是,带有业务含义的主键,不一定是顺序自增的。那么就会导致数据的插入顺序,并不能保证后面插入数据的主键一定比前面的数据大。如果出现了,后面插入数据的主键比前面的小,就有可能引发页分裂,产生空间碎片。
货币字段用什么类型
货币字段一般都用 Decimal类型, float和double是以二进制存储的,数据大的时候,可能存在误差。
以下是FLOAT和DOUBLE的区别:
浮点数以8位精度存储在FLOAT中,并且有四个字节。
浮点数存储在DOUBLE中,精度为18位,有八个字节。
表中有大字段X(例如:text类型),且字段X不会经常更新,以读为主,那么是拆成子表好?还是放一起好?
其实各有利弊,拆开带来的问题:连接消耗;不拆可能带来的问题:查询性能,所以要看你的实际情况,如果表数据量比较大,最好还是拆开为好。这样查询速度更快。
字段为什么要定义为NOT NULL?
一般情况,都会设置一个默认值,不会出现字段里面有null,又有空的情况。主要有以下几个原因:
索引性能不好,Mysql难以优化引用可空列查询,它会使索引、索引统计和值更加复杂。可空列需要更多的存储空间,还需要mysql内部进行特殊处理。可空列被索引后,每条记录都需要一个额外的字节,还能导致MYisam 中固定大小的索引变成可变大小的索引。
如果某列存在null的情况,可能导致count() 等函数执行不对的情况。
sql 语句写着也麻烦,既要判断是否为空,又要判断是否为null等。
总结
本文简述了索引的基本原理,索引的几种类型,以及分析了一下设计索引尽量应该遵循的一些准则,相信我们对索引的理解又更深了一步。另外强烈建议大家去学习一下附录中的几本书。文中的挺多例子都是在文末的参考资料中总结出来的,读经典书籍,相信大家会受益匪浅!