SQL性能优化系列——何为悲观锁和乐观锁[十一]

1.锁的划分方式有哪些?
2.为什么共享锁会发生死锁?
3.乐观锁和悲观锁的思想是什么?乐观锁的两种实现方式?
4.多个事务并发,发生死锁该如何解决?如何降低死锁发生的概率?

索引和锁是数据库中的两个核心知识点,之前从不同维度对索引进行了了解,比如 B+ 树、Hash 索引、页结构、缓冲池和索引原则等,了解它们的工作原理可以加深对索引的理解。同时事务的隔离级别的实现都是通过锁来完成的,为什么要给数据加锁?

实际上加锁是为了保证数据的一致性,这个思想在程序开发领域中同样很重要。在程序开发中也会存在多线程同步的问题。当多个线程并发访问某个数据的时候,尤其是针对一些敏感的数据(比如订单、金额等),就需要保证这个数据在任何时刻最多只有一个线程在进行访问,保证数据的完整性和一致性。

按照锁粒度划分

从锁定对象的粒度大小进行划分,分为行锁页锁表锁

行锁就是按照行的粒度对数据进行锁定。锁定力度小,发生锁冲突概率低,可以实现的并发度高,但是对于锁的开销比较大,加锁会比较慢,容易出现死锁情况。

页锁就是在页的粒度上进行锁定,锁定的数据资源比行锁要多,因为一个页中可以有多个行记录。当使用页锁的时候,会出现数据浪费的现象,但这样的浪费最多也就是一个页上的数据行。页锁的开销介于表锁和行锁之间,会出现死锁。锁定粒度介于表锁和行锁之间,并发度一般。

表锁就是对数据表进行锁定,锁定粒度很大,同时发生锁冲突的概率也会较高,数据访问的并发度低。不过好处在于对锁的使用开销小,加锁会很快。

行锁、页锁和表锁是相对常见的三种锁,除此以外还可以在区和数据库的粒度上锁定数据,对应区锁和数据库锁。不同的数据库和存储引擎支持的锁粒度不同,InnoDB 和 Oracle 支持行锁和表锁。而 MyISAM 只支持表锁,MySQL 中的 BDB 存储引擎支持页锁和表锁。SQL Server 可以同时支持行锁、页锁和表锁,如下表所示:

需要说明的是,每个层级的锁数量是有限制的,因为锁会占用内存空间,锁空间的大小是有限的。当某个层级的锁数量超过了这个层级的阈值时,就会进行锁升级。锁升级就是用更大粒度的锁替代多个更小粒度的锁,比如 InnoDB 中行锁升级为表锁,这样做的好处是占用的锁空间降低了,但同时数据的并发度也下降了。

从数据库管理角度对锁划分

从数据库管理的角度对锁可以分为共享锁排他锁

共享锁

共享锁也叫读锁或 S 锁,共享锁锁定的资源可以被其他用户读取,但不能修改。在进行SELECT的时候,会将对象进行共享锁锁定,当数据读取完毕之后,就会释放共享锁,这样就可以保证数据在读取时不被修改。

比如我们想给 product_comment 在表上加共享锁,可以使用下面这行命令:

LOCK TABLE product_comment READ;

当对数据表加上共享锁的时候,该数据表就变成了只读模式,此时想要更新 product_comment 表中的数据,比如下面这样:

UPDATE product_comment SET product_id = 10002 WHERE user_id = 912178;

系统会做如下提示:

ERROR 1099 (HY000): Table 'product_comment' was locked with a READ lock and can't be updated

也就是当共享锁没有释放时,不能对锁住的数据进行修改。

如果我们想要对表上的共享锁进行解锁,可以使用下面这行命令:

UNLOCK TABLE;

如果想要给某一行加上共享锁呢,比如想对 user_id=912178 的数据行加上共享锁,可以像下面这样:

SELECT comment_id, product_id, comment_text, user_id FROM product_comment WHERE user_id = 912178 LOCK IN SHARE MODE

排他锁

排它锁也叫独占锁、写锁或 X 锁。排它锁锁定的数据只允许进行锁定操作的事务使用,其他事务无法对已锁定的数据进行查询或修改。

如果想给 product_comment 数据表添加排它锁,可以使用下面这行命令:

LOCK TABLE product_comment WRITE;

这时只有获得排它锁的事务可以对 product_comment 进行查询或修改,其他事务如果想要在 product_comment 表上查询数据,则需要等待。可以自己开两个 MySQL 客户端来模拟下。

释放排他锁命令:

UNLOCK TABLE;

同样的,如果想要在某个数据行上添加排它锁,比如针对 user_id=912178 的数据行,则写成如下这样:

SELECT comment_id, product_id, comment_text, user_id FROM product_comment WHERE user_id = 912178 FOR UPDATE;

另外当我们对数据进行更新的时候,也就是INSERT、DELETE、UPDATE时,数据库也会自动使用排它锁,防止其他事务对该数据行进行操作。

当想要获取某个数据表的排它锁的时候,需要先看下这张数据表有没有上了排它锁。如果这个数据表中的某个数据行被上了行锁,就无法获取排它锁。这时需要对数据表中的行逐一排查,检查是否有行锁,如果没有,才可以获取这张数据表的排它锁。这个过程是不是有些麻烦?这里就需要用到意向锁。

意向锁

意向锁(Intent Lock),简单来说就是给更大一级别的空间示意里面是否已经上过锁。举个例子,你可以给整个房子设置一个标识,告诉它里面有人,即使你只是获取了房子中某一个房间的锁。这样其他人如果想要获取整个房子的控制权,只需要看这个房子的标识即可,不需要再对房子中的每个房间进行查找。这样是不是很方便?

返回数据表的场景,如果给某一行数据加上了排它锁,数据库会自动给更大一级的空间,比如数据页或数据表加上意向锁,告诉其他人这个数据页或数据表已经有人上过排它锁了,这样当其他人想要获取数据表排它锁的时候,只需要了解是否有人已经获取了这个数据表的意向排他锁即可。

如果事务想要获得数据表中某些记录的共享锁,就需要在数据表上添加意向共享锁。同理,事务想要获得数据表中某些记录的排他锁,就需要在数据表上添加意向排他锁。这时,意向锁会告诉其他事务已经有人锁定了表中的某些记录,不能对整个表进行全表扫描。

为什么共享锁会发生死锁情况

当使用共享锁的时候会出现死锁的风险,下面用两个 MySQL 客户端来模拟一下事务查询。

首先客户端 1 开启事务,然后采用读锁的方式对user_id=912178的数据行进行查询,这时事务没有提交的时候,这两行数据行上了读锁。

然后我们用客户端 2 开启事务,同样对user_id=912178获取读锁,理论上获取读锁后还可以对数据进行修改,比如执行下面这条语句:

UPDATE product_comment SET product_i = 10002 WHERE user_id = 912178;

当执行的时候客户端 2 会一直等待,因为客户端 1 也获取了该数据的读锁,不需要客户端 2 对该数据进行修改。这时客户端 2 会提示等待超时,重新执行事务。

当有多个事务对同一数据获得读锁的时候,可能会出现死锁的情况

从程序员的角度划分

从程序猿的角度可以分为乐观锁和悲观锁。

乐观锁

乐观锁(Optimistic Locking)认为对同一数据的并发操作不会总发生,属于小概率事件,不用每次都对数据上锁,也就是不采用数据库自身的锁机制,而是通过程序来实现。在程序上,我们可以采用版本号机制或者时间戳机制实现。

乐观锁的版本号机制

在表中设计一个版本字段 version,第一次读的时候,会获取 version 字段的取值。然后对数据进行更新或删除操作时,会执行UPDATE … SET version=version+1 WHERE version=version。此时如果已经有事务对这条数据进行了更改,修改就不会成功。

这种方式类似 SVN、CVS 版本管理系统,当修改了代码进行提交时,首先会检查当前版本号与服务器上的版本号是否一致,如果一致就可以直接提交,如果不一致就需要更新服务器上的最新代码,然后再进行提交。

乐观锁的时间戳机制

时间戳和版本号机制一样,也是在更新提交的时候,将当前数据的时间戳和更新之前取得的时间戳进行比较,如果两者一致则更新成功,否则就是版本冲突。

你能看到乐观锁就是程序员自己控制数据并发操作的权限,基本是通过给数据行增加一个戳(版本号或者时间戳),从而证明当前拿到的数据是否最新。

悲观锁

悲观锁(Pessimistic Locking)也是一种思想,对数据被其他事务的修改持保守态度,会通过数据库自身的锁机制来实现,从而保证数据操作的排它性。

从这两种锁的设计思想中,能看出乐观锁和悲观锁的适用场景:

1.乐观锁适合读操作多的场景,相对来说写的操作比较少。它的优点在于程序实现,不存在死锁问题,不过适用场景也会相对乐观,因为它阻止不了除了程序以外的数据库操作。

2.悲观锁适合写操作多的场景,因为写的操作具有排它性。采用悲观锁的方式,可以在数据库层面阻止其他事务对该数据的操作权限,防止读 – 写和写 – 写的冲突。

总结

从不同维度都可以对锁进行划分,需要注意的是,乐观锁和悲观锁并不是锁,而是锁的设计思想

既然有锁的存在,就有可能发生死锁的情况。死锁就是多个事务(如果是在程序层面就是多个进程)在执行过程中,因为竞争某个相同的资源而造成阻塞的现象。发生死锁,往往是因为在事务中,锁的获取是逐步进行的。

上面的例子,在客户端 1 获取某数据行共享锁的同时,另一个客户端 2 也获取了该数据行的共享锁,这时任何一个客户端都没法对这个数据进行更新,因为共享锁会阻止其他事务对数据的更新,当某个客户端想要对锁定的数据进行更新的时候,就出现了死锁的情况。当死锁发生的时候,就需要一个事务进行回滚,另一个事务获取锁完成事务,然后将锁释放掉,很像交通堵塞时候的解决方案。

如何避免死锁发生

1.如果事务涉及多个表,操作比较复杂,那么可以尽量一次锁定所有的资源,而不是逐步来获取,这样可以减少死锁发生的概率;

2.如果事务需要更新数据表中的大部分数据,数据表又比较大,这时可以采用锁升级的方式,比如将行级锁升级为表级锁,从而减少死锁产生的概率;

3.不同事务并发读写多张数据表,可以约定访问表的顺序,采用相同的顺序降低死锁发生的概率。

当然在数据库中,也有一些情况是不会发生死锁的,比如采用乐观锁的方式。另外在 MySQL MyISAM 存储引擎中也不会出现死锁,这是因为 MyISAM 总是一次性获得全部的锁,这样的话要么全部满足可以执行,要么就需要全部等待。

思考题

使用 MySQL InnoDB 存储引擎时,为什么对某行数据添加排它锁之前,会在数据表上添加意向排他锁呢?

(本文完)

SQL性能优化系列——为何没有理想的索引[十]

1. 什么是索引片?如何计算过滤因子?
2.设计索引可遵循的原则有哪些?
3.为什么理想的索引在实际工作中很难应用起来?

索引片和过滤因子

索引片就是 SQL 查询语句在执行中需要扫描的一个索引片段,我们会根据索引片中包含的匹配列的数量不同,将索引分成窄索引(比如包含索引列数为 1 或 2)和宽索引(包含的索引列数大于 2)。

如果索引片越宽,那么需要顺序扫描的索引页就越多;如果索引片越窄,就会减少索引访问的开销。比如在 product_comment 数据表中,我们将 comment_id 设置为主键,然后执行下面的 SQL 查询语句:

SELECT comment_id, product_id, comment_text, user_id FROM product_comment WHERE user_id between 100001 and 100100

针对这条 SQL 查询语句,我们可以设置窄索引(user_id)。需要说明的是,每个非聚集索引保存的数据都会存储主键值,然后通过主键值,来回表查找相应的数据,因此每个索引都相当于包括了主键,也就是(comment_id, user_id)。

同样我们可以设置宽索引(user_id, product_id, comment_text),相当于包括了主键,也就是(comment_id, user_id, product_id, comment_text)。

如何通过宽索引避免回表

上面说了宽索引需要顺序扫描的索引页很多,不过它也可以避免通过索引找到主键,再通过主键回表进行数据查找的情况。回表指的就是数据库根据索引找到了数据行之后,还需要通过主键再次到数据表中读取数据的情况。

可以用不同索引片来运行下刚才的 SQL 语句,比如采用窄索引(user_id)的方式,来执行下面这条语句:

SELECT comment_id, product_id, comment_text, user_id FROM product_comment WHERE user_id between 100001 and 100100

运行结果(110 条记录,运行时间 0.062s)

同样,如果我们设置宽索引(user_id, product_id, comment_text),然后执行相同的 SQL 语句,运行结果相同,运行时间为 0.043s,你能看到查询效率有了一些提升。这就是因为我们可以通过宽索引将 SELECT 中需要用到的列(主键列可以除外)都设置在宽索引中,这样就避免了回表扫描的情况,从而提升 SQL 查询效率。

什么是过滤因子

在索引片的设计中,我们还需要考虑一个因素,那就是过滤因子,它描述了谓词的选择性。在 WHERE 条件语句中,每个条件都称为一个谓词,谓词的选择性也等于满足这个条件列的记录数除以总记录数的比例。

过滤因子就是过滤条件,联合过滤因子有更高的过滤能力,这里还需要注意一个条件,那就是条件列的关联性应该尽量相互独立,否则如果列与列之间具有相关性,联合过滤因子的能力就会下降很多。比如城市名称和电话区号就有强相关性,这两个列组合到一起不会加强过滤效果。

你能看到过滤因子决定了索引片的大小(注意这里不是窄索引和宽索引),过滤因子的条件过滤能力越强,满足条件的记录数就越少,SQL 查询需要扫描的索引片也就越小。同理,如果我们没有选择好索引片中的过滤因子,就会造成索引片中的记录数过多的情况。

针对SQL查询的理想索引设计:三星索引

刚才介绍了宽索引和窄索引,有些时候宽索引可以提升 SQL 的查询效率,那么,如果针对 SQL 查询来说,有没有一个标准能让 SQL 查询效率最大化呢?

实际上存在一个三星索引的标准,好比是数据表设计时提到的三范式一样:

1.在 WHERE 条件语句中,找到所有等值谓词中的条件列,将它们作为索引片中的开始列;

2.将 GROUP BY 和 ORDER BY 中的列加入到索引中;

3.将 SELECT 字段中剩余的列加入到索引片中。

这样操作下来,索引片基本上会变成一个宽索引,把能添加的相关列都加入其中。对于一条 SQL 查询来说,这样做的效率是最高的吗?(怎么理解上面3条呢?)

首先,如果要通过索引查找符合条件的记录,就需要将 WHERE 子句中的等值谓词列加入到索引片中,这样索引的过滤能力越强,最终扫描的数据行就越少。

另外,如果要对数据记录分组或者排序,都需要重新扫描数据记录。为了避免进行 file sort 排序,可以把 GROUP BY 和 ORDER BY 中涉及到的列加入到索引中,因为创建了索引就会按照索引的顺序来存储数据,这样再对这些数据按照某个字段进行分组或者排序的时候,就会提升效率。

三星索引的逻辑就是:最小化碎片、避免排序、避免回表查询。

最后,取数据的时候,可能会存在回表情况,这是因为 SELECT 所需的字段并不都保存在索引中,因此可以将 SELECT 中的字段都保存在索引中避免回表的情况,从而提升查询效率。

为什么很难存在理想的索引设计

从三星索引的创建过程中,你能看到三星索引实际上分析了在 SQL 查询过程中所有可能影响效率的环节,通过在索引片中添加索引的方式来提升效率。通过上面的原则,我们可以很快创建一个 SQL 查询语句的三星索引(有时候可能只有两星,比如同时拥有范围谓词和 ORDER BY 的时候)。

但就同三范式一样,很多时候并没有遵循三范式的设计原则,而是采用了反范式设计。同样,有时候并不能需要完全遵循三星索引的原则,原因主要有以下两点:

1.采用三星索引会让索引片变宽,这样每个页能够存储的索引数据就会变少,从而增加了页加载的数量。从另一个角度来看,如果数据量很大,比如有 1000 万行数据,过多索引所需要的磁盘空间可能会成为一个问题,对缓冲池所需空间的压力也会增加。

2.增加了索引维护的成本。如果为所有的查询语句都设计理想的三星索引,就会让数据表中的索引个数过多,这样索引维护的成本也会增加。举个例子,当添加一条记录的时候,就需要在每一个索引上都添加相应的行(存储对应的主键值),假设添加一行记录的时间成本是 10ms(磁盘随机读取一个页的时间),那么如果创建了 10 个索引,添加一条记录的时间就可能变成 0.1s,如果是添加 10 条记录呢?就会花费近 1s 的时间。从索引维护的成本来看消耗还是很高的。当然对于数据库来说,数据的更新不一定马上回写到磁盘上,但即使不及时将脏页进行回写,也会造成缓冲池中的空间占用过多,脏页过多的情况。

总结

针对一条 SQL 查询来说,三星索引是个理想的方式,但实际运行起来要考虑更多维护的成本,在索引效率和索引维护之间进行权衡。

三星索引会让索引变宽,好处就是不需要进行回表查询,减少了磁盘 I/O 的次数,弊端就是会造成频繁的页分裂和页合并,对于数据的插入和更新来说,效率会降低不少。

那如何设计索引?

首先,一张表的索引个数不宜过多,否则一条记录的增加和修改,会因为过多的索引造成额外的负担。针对这个情况,当你需要新建索引的时候,首先考虑在原有的索引片上增加索引,也就是采用复合索引的方式,而不是新建一个新的索引。另外可以定期检查索引的使用情况,对于很少使用到的索引可以及时删除,从而减少索引数量。

同时,在索引片中也需要控制索引列的数量,通常情况下我们将 WHERE 里的条件列添加到索引中,而 SELECT 中的非条件列则不需要添加。除非 SELECT 中的非条件列数少,并且该字段会经常使用到。

另外,单列索引和复合索引的长度也需要控制,在 MySQL InnoDB 中,系统默认单个索引长度最大为 767 bytes,如果单列索引长度超过了这个限制,就会取前缀索引,也就是取前 255 字符。这实际上也是告诉我们,字符列会占用较大的空间,在数据表设计的时候,尽量采用数值类型替代字符类型,尽量避免用字符类型做主键,同时针对字符字段最好只建前缀索引

思考题

针对下面的 SQL 语句,如果创建三星索引该如何创建?使用三星索引和不使用三星索引在查询效率上又有什么区别?

SELECT comment_id, comment_text, user_id FROM product_comment where user_id BETWEEN 100000 AND 200000

(本文完)

SQL性能优化系列——从磁盘I/O角度理解SQL查询成本[九]

1.数据库的缓冲池在数据库中起到了怎样的作用?如果对缓冲池内的数据进行更新,数据会直接更新到磁盘上么?
2.对数据页加载都有哪些方式?
3.如何查看一条SQL语句在缓冲池中进行加载的页的数量?

数据库存储的基本单元是页,即使是查询一行数据,但是对于磁盘I/O来说要加载该行数据所在的一页的信息,因为页是最小的存储单位。如果查询数据是多行,查询时间是否会成本增加呢?其实数据库会采用缓冲池的方式提升页的查询效率。

数据库缓冲池

磁盘I/O需要消耗很多时间,而在内存中操作则效率会提升很多,为了能让数据表或索引中的数据随时被我们所用,DBMS会申请占用内存来作为数据缓冲池,这样可以让磁盘活动最小化,从而减少与磁盘直接进行I/O的时间,这样访问成本会低很多。

缓冲池如何读取数据呢?

缓冲池管理器会尽量将经常使用的数据保存起来,当数据库进行页面读操作的时候首先会判断该页是否在缓冲池中,如果存在就直接读取,如果不在就通过内存或磁盘将页面保存到缓冲池中再进行读取。

如果执行SQL语句更新了缓冲池中的数据,这些数据会立即更新到磁盘上么?

事实上,当对数据库中的记录进行修改时,首先修改的是缓冲池中页里面的记录信息,然后数据库才会以一定的频率刷新到磁盘上。并不是每一次更新都会立即进行磁盘回写。缓冲池会采用一种叫做checkpoint的机制将数据回写到磁盘上,这样能提升数据库的整体性能。比如,当缓冲池不够用时,需要释放掉一些不常用的页,就采用checkpoint的方式将不常用的脏页回写到磁盘上,然后从缓冲池中释放掉这些页。脏页(dirty page)是指缓冲池中被修改过的页,与磁盘上的页不一致。

查看缓冲池大小

如果使用的是MySQL的 MyISAM 存储引擎,它只缓存索引,不缓存数据,对应的键缓存参数为 key_buffer_size 可以进行查看。

如果使用的是InnoDB 存储引擎,可以通过查看 innodb_buffer_size 变量查看缓冲池大小,如:

mysql > show variables like 'innodb_buffer_pool_size'

也可以通过命令修改缓冲池大小(如修改为128M):

mysql > set global innodb_buffer_pool_size = 134217728;

另外,在InnoDB存储引擎中可以开启多个缓冲池,通过命令可以查看缓冲池的数量:

mysql > show variables like 'innodb_buffer_pool_instances'

实际上innodb_buffer_pool_instances默认情况下是8,为什么这里只显示为1?这是因为需要先将innodb_buffer_pool_size设置为大于1GB,缓冲池个数才会大于1。

数据页加载的三种方式

缓冲池中没有数据时,有三种读取数据方式,每种方式效率不同。

1.内存读取

如果数据存储在内存中,都取到缓冲池中约1ms,效率还是很高的。

2.随机读取

如果数据没有在内存中,就需要在磁盘上对该页进行查找,整体时间预估在 10ms 左右,这 10ms 中有 6ms 是磁盘的实际繁忙时间(包括了寻道和半圈旋转时间),有 3ms 是对可能发生的排队时间的估计值,另外还有 1ms 的传输时间,将页从磁盘服务器缓冲区传输到数据库缓冲区中。这 10ms 看起来很快,但实际上对于数据库来说消耗的时间已经非常长了,因为这还只是一个页的读取时间。

3.顺序读取

顺序读取其实是一种批量读取的方式,因为我们请求的数据在磁盘上往往都是相邻存储的,顺序读取可以帮我们批量读取页面,这样的话,一次性加载到缓冲池中就不需要再对其他页面单独进行磁盘 I/O 操作了。如果一个磁盘的吞吐量是 40MB/S,那么对于一个 16KB 大小的页来说,一次可以顺序读取 2560(40MB/16KB)个页,相当于一个页的读取时间为 0.4ms。采用批量读取的方式,即使是从磁盘上进行读取,效率也比从内存中只单独读取一个页的效率要高。

统计SQL语句的查询成本

前面说过,一条 SQL 查询语句在执行前需要确定查询计划,如果存在多种查询计划的话,MySQL 会计算每个查询计划所需要的成本,从中选择成本最小的一个作为最终执行的查询计划。

如果我们想要查看某条 SQL 语句的查询成本,可以在执行完这条 SQL 语句之后,通过查看当前会话中的 last_query_cost 变量值来得到当前查询的成本。这个查询成本对应的是 SQL 语句所需要读取的页的数量。

以 product_comment 表为例,如果我们想要查询 comment_id=900001 的记录,然后看下查询成本,我们可以直接在聚集索引上进行查找:

mysql> SELECT comment_id, product_id, comment_text, user_id FROM product_comment WHERE comment_id = 900001;

然后再看下查询优化器的成本,实际上我们只需要检索一个页即可:

mysql> SHOW STATUS LIKE 'last_query_cost';

如果我们想要查询 comment_id 在 900001 到 9000100 之间的评论记录呢?

mysql> SELECT comment_id, product_id, comment_text, user_id FROM product_comment WHERE comment_id BETWEEN 900001 AND 900100;

然后再看下查询优化器的成本,这时我们大概需要进行 20 个页的查询。

mysql> SHOW STATUS LIKE 'last_query_cost';

你能看到页的数量是刚才的 20 倍,但是查询的效率并没有明显的变化,实际上这两个 SQL 查询的时间基本上一样,就是因为采用了顺序读取的方式将页面一次性加载到缓冲池中,然后再进行查找。虽然页数量(last_query_cost)增加了不少,但是通过缓冲池的机制,并没有增加多少查询时间。

总结

SQL查询是一个动态过程,从页加载的角度看,可以得到以下两点结论:

1.位置决定效率。如果页就在数据库缓冲池中,那么效率是最高的,否则还需要从内存或者磁盘中进行读取,当然针对单个页的读取来说,如果页存在于内存中,会比在磁盘中读取效率高很多。

2.批量决定效率。如果我们从磁盘中对单一页进行随机读,那么效率是很低的(差不多 10ms),而采用顺序读取的方式,批量对页进行读取,平均一页的读取效率就会提升很多,甚至要快于单个页面在内存中的随机读取。

所以说,遇到 I/O 并不用担心,方法找对了,效率还是很高的。我们首先要考虑数据存放的位置,如果是经常使用的数据就要尽量放到缓冲池中,其次我们可以充分利用磁盘的吞吐能力,一次性批量读取数据,这样单个页的读取效率也就得到了提升。

(本文完)

SQL性能优化系列——从数据页角度理解B+树查询[八]

1.数据库中的存储结构是怎样的?
2.为什么页是数据库存储空间的基本单位?
3.从数据页角度看,B+树是怎样进行查询的?

B+树和 Hash 索引的原理前面已经说过了,这些索引结构给我们提供了高效的检索方式,不过这些索引信息及数据记录都是存储在文件上的,确切地说是存储在页结构中。对数据库存储结构以及页结构的底层了解可以加深对索引运行机制的认识,从而对索引的存储、查询原理、以及对SQL查询效率有更深的理解。

数据库中的存储结构

记录是按照行存储的,但是数据库读取并不以行为单位,否则一次读取(也就是一次I/O操作)只能处理一行数据,效率会非常低。因此在数据库中,不论读一行,还是读多行,都是将这些行所在的页进行加载。也即是说,数据库管理存储空间的基本单位是页(Page)

一个页中可以存储多个行记录(Row),同时数据库中还存在区(Extent)、段(Segment)和表空间(Tablespace)。行、页、区、段、表空间的关系如图所示:

从图可以看到一个表空间包括一个或多个段、一个段包括一个或多个区、一个区包括多个页、一个页又包含多行记录。

区(Extent)是比页大一级的存储结构,在 InnoDB 存储引擎中,一个区会分配 64 个连续的页。因为 InnoDB 中的页大小默认是 16KB,所以一个区的大小是 64*16KB=1MB。

段(Segment)由一个或多个区组成,区在文件系统是一个连续分配的空间(在 InnoDB 中是连续的 64 个页),不过在段中不要求区与区之间是相邻的。段是数据库中的分配单位,不同类型的数据库对象以不同的段形式存在。当我们创建数据表、索引的时候,就会相应创建对应的段,比如创建一张表时会创建一个表段,创建一个索引时会创建一个索引段。

表空间(Tablespace)是一个逻辑容器,表空间存储的对象是段,在一个表空间中可以有一个或多个段,但是一个段只能属于一个表空间。数据库由一个或多个表空间组成,表空间从管理上可以划分为系统表空间、用户表空间、撤销表空间、临时表空间等。

在 InnoDB 中存在两种表空间的类型:共享表空间和独立表空间。如果是共享表空间就意味着多张表共用一个表空间。如果是独立表空间,就意味着每张表有一个独立的表空间,也就是数据和索引信息都会保存在自己的表空间中。独立的表空间可以在不同的数据库之间进行迁移。

通过命令可以查看InnoDB表空间类型:

mysql > show variables like 'innodb_file_per_table';

你能看到 innodb_file_per_table=ON,这就意味着每张表都会单独保存为一个.ibd 文件。

数据页内的结构

页如果按类型分,常见的有数据页(保存B+树节点)、系统页、Undo页和事务数据页。其中数据页是最常用的页。

表页的大小限定了表行的最大长度,不同DBMS的表页大小不同,MySQL的InnoDB存储引擎中,默认页的大小是16KB,可以通过命令查看:

mysql> show variables like '%innodb_page_size%';

另,SQLServer的页大小为8KB,而在Oracle中用术语块(Block)代表页,支持的块大小为2、4、8、16、32和64KB。

数据库 I/O 操作的最小单位是页,与数据库相关的内容都会存储在页结构里。数据页包括七个部分,分别是文件头(File Header)、页头(Page Header)、最大最小记录(Infimum+supremum)、用户记录(User Records)、空闲空间(Free Space)、页目录(Page Directory)和文件尾(File Tailer)。

页结构的示意图如下所示:

各部分如下:

这7部分又可以分为3部分。

首先是文件通用部分,也就是文件头和文件尾。它们类似集装箱,将页的内容进行封装,通过文件头和文件尾校验的方式来确保页的传输是完整的。

在文件头中有两个字段,分别是 FIL_PAGE_PREV 和 FIL_PAGE_NEXT,它们的作用相当于指针,分别指向上一个数据页和下一个数据页。连接起来的页相当于一个双向的链表,如下图所示:

需要说明的是采用链表的结构让数据页之间不需要是物理上的连续,而是逻辑上的连续。

这里文件尾的校验方式就是采用 Hash 算法进行校验。举个例子,当进行页传输的时候,如果突然断电了,造成了该页传输的不完整,这时通过文件尾的校验和(checksum 值)与文件头的校验和做比对,如果两个值不相等则证明页的传输有问题,需要重新进行传输,否则认为页的传输已经完成。

第二个部分是记录部分,页的主要作用是存储记录,所以“最小和最大记录”和“用户记录”部分占了页结构的主要空间。另外空闲空间是个灵活的部分,当有新的记录插入时,会从空闲空间中进行分配用于存储新记录,如下图所示:

第三部分是索引部分,这部分重点指的是页目录,它起到了记录的索引作用,因为在页中,记录是以单向链表的形式进行存储的。单向链表的特点就是插入、删除非常方便,但是检索效率不高,最差的情况下需要遍历链表上的所有节点才能完成检索,因此在页目录中提供了二分查找的方式,用来提高记录的检索效率。这个过程就好比是给记录创建了一个目录:

1.将所有的记录分成几个组,这些记录包括最小记录和最大记录,但不包括标记为“已删除”的记录。

2.第 1 组,也就是最小记录所在的分组只有 1 个记录;最后一组,就是最大记录所在的分组,会有 1-8 条记录;其余的组记录数量在 4-8 条之间。这样做的好处是,除了第 1 组(最小记录所在组)以外,其余组的记录数会尽量平分。

3.在每个组中最后一条记录的头信息中会存储该组一共有多少条记录,作为 n_owned 字段。

4.页目录用来存储每组最后一条记录的地址偏移量,这些地址偏移量会按照先后顺序存储起来,每组的地址偏移量也被称之为槽(slot),每个槽相当于指针指向了不同组的最后一个记录。如下图所示:

页目录存储的是槽,槽相当于分组记录的索引。我们通过槽查找记录,实际上就是在做二分查找。这里我以上面的图示进行举例,5 个槽的编号分别为 0,1,2,3,4,我想查找主键为 9 的用户记录,我们初始化查找的槽的下限编号,设置为 low=0,然后设置查找的槽的上限编号 high=4,然后采用二分查找法进行查找。

首先找到槽的中间位置 p=(low+high)/2=(0+4)/2=2,这时我们取编号为 2 的槽对应的分组记录中最大的记录,取出关键字为 8。因为 9 大于 8,所以应该会在槽编号为 (p,high] 的范围进行查找

接着重新计算中间位置 p’=(p+high)/2=(2+4)/2=3,我们查找编号为 3 的槽对应的分组记录中最大的记录,取出关键字为 12。因为 9 小于 12,所以应该在槽 3 中进行查找。

遍历槽 3 中的所有记录,找到关键字为 9 的记录,取出该条记录的信息即为我们想要查找的内容。

从数据页的角度看 B+ 树是如何查询的

MySQL 的 InnoDB 存储引擎采用 B+ 树作为索引,而索引又可以分成聚集索引和非聚集索引(二级索引),这些索引都相当于一棵 B+ 树,如图所示。一棵 B+ 树按照节点类型可以分成两部分:

1.叶子节点,B+ 树最底层的节点,节点的高度为 0,存储行记录。

2.非叶子节点,节点的高度大于 0,存储索引键和页面指针,并不存储行记录本身。

可以用业结构对比,看下B+树的结构:

在一棵 B+ 树中,每个节点都是一个页,每次新建节点的时候,就会申请一个页空间。同一层上的节点之间,通过页的结构构成一个双向的链表(页文件头中的两个指针字段)。非叶子节点,包括了多个索引行,每个索引行里存储索引键和指向下一层页面的页面指针。最后是叶子节点,它存储了关键字和行记录,在节点内部(也就是页结构的内部)记录之间是一个单向的链表,但是对记录进行查找,则可以通过页目录采用二分查找的方式来进行。

当我们从页结构来理解 B+ 树的结构的时候,可以帮我们理解一些通过索引进行检索的原理:

1.B+树如何进行记录检索的?

如果通过B+树的索引查询行数据,首先是从B+树根节点开始,逐层检索,直到找到叶子节点,也就是找到对应的数据页为止,将数据页加载到内存中,页目录中的槽(slot)采用二分查找法的方式先找到一个粗略的记录分组,然后再在分组中通过链表遍历的方式查找记录。

2.普通索引和唯一索引在查询效率上有什么不同?

在查询效率上基本没有差别:唯一索引就是在普通索引上增加了约束性,也就是关键字唯一,找到了关键字就停止检索。而普通索引,可能会存在用户记录中的关键字相同的情况,根据页结构的原理,当我们读取一条记录的时候,不是单独将这条记录从磁盘中读出去,而是将这个记录所在的页加载到内存中进行读取。InnoDB 存储引擎的页大小为 16KB,在一个页中可能存储着上千个记录,因此在普通索引的字段上进行查找也就是在内存中多几次“判断下一条记录”的操作,对于 CPU 来说,这些操作所消耗的时间是可以忽略不计的。所以对一个索引字段进行检索,采用普通索引还是唯一索引在检索效率上基本上没有差别。

总结

数据库中的基本存储单位,也就是页(Page),磁盘 I/O 都是基于页来进行读取的,在页之上还有区、段和表空间,它们都是更大的存储单位。我们在分配空间的时候会按照页为单位来进行分配,同一棵树上同一层的页与页之间采用双向链表,而在页里面,记录之间采用的单向链表的方式。

链表这种数据结构的特点是增加、删除比较方便,所以在对记录进行删除的时候,有时候并不是真的删除了记录,而只是逻辑上的删除,也就是在标记为上标记为“已删除”。但链表还有个问题就是查找效率低,因此在页结构中还专门设计了页目录这个模块,专门给记录做一个目录,通过二分查找法的方式进行检索提升效率。

(本文完)

SQL性能优化系列——索引的使用原则[七]

1.什么情况使用索引?
2.什么情况不需要创建索引?
3.如何避免索引失效?

前面说到了索引的使用和底层原理,那么如何通过索引实现查询效率的最大化?

哪些情况可以创建索引

1.字段的数值有唯一性限制,比如用户名;

2.频繁作为 WHERE 查询条件的字段,尤其在数据表大的情况下;

3.需要经常 ORDER BY 和 GROUP BY 的列;

4.UPDATE、DELETE的 WHERE 条件列,一般也需要创建索引;

5.DISTINCT 字段需要创建索引;

6.做多表 JOIN 连接操作时,创建索引需要注意以下原则:

首先,连接表的数量尽量不要超过3张,因为每增加一张表就相当于增加了一次嵌套的循环,数量级增长非常快,严重影响查询效率。

其次,对 WHERE 条件创建索引,因为 WHERE 才是对数据条件的过滤。

最后,对用于连接的字段创建索引,并且该字段在多张表中的数据类型必须一致。

哪些情况不需要创建索引

1.WHERE 条件(包括 GROUP BY、ORDER BY)里用不到的字段不需要创建索引,索引的价值在于快速定位,如果起不到定位的字段不需要创建索引。

2.如果表记录太少,比如少于1000条,不需要创建索引,原因前面说到过。

3.如果字段中有大量重复数据也不需要创建索引,比如性别字段,原因前面也说到过。

4.频繁更新的字段不一定要创建索引。因为数据更新时,也需要更新索引,如果索引太多,在更新索引时也会造成负担,影响效率。

哪些情况下索引会失效

1.如果索引进行了表达式计算,则会失效

可以使用 EXPLAIN 关键字查看MySQL中一条SQL语句的执行计划,比如:

EXPLAIN SELECT comment_id, user_id, comment_text FROM product_comment WHERE comment_id+1 = 900001

运行结果:

+----+-------------+-----------------+------------+------+---------------+------+---------+------+--------+----------+-------------+
| id | select_type | table           | partitions | type | possible_keys | key  | key_len | ref  | rows   | filtered | Extra       |
+----+-------------+-----------------+------------+------+---------------+------+---------+------+--------+----------+-------------+
|  1 | SIMPLE      | product_comment | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 996663 |   100.00 | Using where |
+----+-------------+-----------------+------------+------+---------------+------+---------+------+--------+----------+-------------+

可以看出如果对索引进行了表达式计算,索引就失效了。这是因为需要把索引字段的值都取出来,然后依次进行表达式计算进行条件判断,因此采用的是全表扫描的方式,运行会慢很多,最终运行时间为2.538秒。

为了避免索引失效,可以改造SQL:

SELECT comment_id, user_id, comment_text FROM product_comment WHERE comment_id = 900000

运行时间为0.039秒。

2.如果对索引使用函数,也会造成失效

比如要对 commont_text 的前三位为 abc 的内容进行条件筛选,执行计划:

EXPLAIN SELECT comment_id, user_id, comment_text FROM product_comment WHERE SUBSTRING(comment_text, 1,3)='abc'

运行结果:

+----+-------------+-----------------+------------+------+---------------+------+---------+------+--------+----------+-------------+
| id | select_type | table           | partitions | type | possible_keys | key  | key_len | ref  | rows   | filtered | Extra       |
+----+-------------+-----------------+------------+------+---------------+------+---------+------+--------+----------+-------------+
|  1 | SIMPLE      | product_comment | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 996663 |   100.00 | Using where |
+----+-------------+-----------------+------------+------+---------------+------+---------+------+--------+----------+-------------+

可以看到索引失效,重写SQL:

SELECT comment_id, user_id, comment_text FROM product_comment WHERE comment_text LIKE 'abc%'

分析结果:

+----+-------------+-----------------+------------+-------+---------------+--------------+---------+------+------+----------+-----------------------+
| id | select_type | table           | partitions | type  | possible_keys | key          | key_len | ref  | rows | filtered | Extra                 |
+----+-------------+-----------------+------------+-------+---------------+--------------+---------+------+------+----------+-----------------------+
|  1 | SIMPLE      | product_comment | NULL       | range | comment_text  | comment_text | 767     | NULL |  213 |   100.00 | Using index condition |
+----+-------------+-----------------+------------+-------+---------------+--------------+---------+------+------+----------+-----------------------+

可以看到,经过查询重写后,可以使用索引进行范围检索,从而提高查询效率。

3.在 WHERE 子句中,如果在 OR 前的条件列进行了索引,而在 OR 后的条件列没有进行索引,那么索引会失效

4.当使用 LIKE 进行模糊查询的时候,后面不能是%

这个很好理解,如果一本字典按照字母顺序进行排序,我们会从首位进行匹配,而不会对中间位置进行匹配,否则索引就失效了。

5.索引列与 NULL 或 NOT NULL 进行判断的时候也会失效

这是因为索引并不存储空值,所以最好是在设计数据表的时候就将字段设置为 NOT NULL 约束,比如可以将 INT 类型的字段默认值设置为0,将字符类型的字段默认值设置为空字符串(”)。

6.在使用联合索引的时候要注意最左原则

最左原则就是需要从左到右的使用索引中的字段,一条SQL语句可以只使用联合索引的一部分,但是要从最左侧开始,否则就会失效。(联合索引有这段)

思考题

针对 product_comment 数据表,其中 comment_time 已经创建了普通索引。假设想查询在某段时间期间的记录:

SELECT comment_id, comment_text, comment_time FROM product_comment WHERE DATE(comment_time) >= '2018-10-01 10:00:00' AND comment_time <= '2018-10-02 10:00:00'

此时索引会失效吗?为什么?如果失效如何重写SQL?

(本文完)

SQL性能优化系列——Hash索引的原理[六]

上一篇说了B+树的原理,这篇说一下Hash的原理和使用。Hash本身是一个函数,又被称为散列函数,它可以帮助提升检索数据的效率。打个比方,Hash就好像一个智能前台,你只要告诉它想要查找的人的姓名,它就会告诉你这个人的位置,只需要一次交互就可以完成查询,效率非常高。MD5就是Hash函数的一种。

Hash算法是通过某种确定性的算法(如MD5、SHA1、SHA2、SHA3)将输入变为输出。相同的输入永远得到相同的输出。如果想验证两个文件是否相同,只需要对两个文件进行Hash函数运算比较结果是否相同即可。

代码统计Hash检索效率

Python的数据结构中有数组和字典两种,其中数组检索类似于全表扫描,需要对整个数组进行检索。字典是Hash表实现的,存储的是key-value值,数据检索效率很高。

没有对比就没有伤害,例如:

实验1:在数组中添加10000个元素,然后分别对这10000个元素进行检索,最后统计检索时间。

import time
# 插入数据
result = []
for i in range(10000):
       result.append(i)
# 检索数据
time_start=time.time()
for i in range(10000):
       temp = result.index(i)
time_end=time.time()
print('检索时间', time_end-time_start)

运行结果:

检索时间为 1.2436728477478027 秒。

实验2:采用Hash表的形式存储数据,即在Python中采用字典方式添加10000个元素,然后检索这10000个数据,最后统计时间。

import time
# 插入数据
result = {}
for i in range(1000000):
       result[i] = i
# 检索数据
time_start=time.time()
for i in range(10000):
       temp = result[i]
time_end=time.time()
print('检索时间:',time_end-time_start)

运行结果:

检索时间为 0.0019941329956054688 秒。

通过对比,检索效率差别很大。因为Hash算法复杂度为O(1),数组检索数据的算法复杂度为O(n)。

MySQL中的Hash索引

采用Hash进行检索效率非常高,基本上一次检索就可以找到数据,而B+树需要自顶向下依次查找,多次访问节点才能找到数据,中间需要多次I/O操作,从效率上来说Hash比B+树更高。

Hash索引示意图如下:

键值key通过Hash映射找到bucket。在这里bucket指的是一个能存储一条或多条记录的存储单位。一个桶的结构包含了一个内存指针数组,其中的每一行数据都会指向下一条,形成链表结构,当遇到Hash冲突时,会在桶中进行键值的查找。

什么是Hash冲突?

如果桶的空间小于输入的空间,不同的输入可能会映射到同一个桶中,这时就会产生Hash冲突,如果冲突的量很大,就会影响读取的性能。

Hash索引与B+树索引的区别

1.Hash索引不能进行范围查询,而B+树可以。因为Hash索引指向的数据是无序的,B+树的叶子节点是个有序链表。

2.Hash索引不支持联合索引的最左侧原则(即联合索引的部分索引无法使用),而B+树可以。因为Hash索引在计算Hash值时,是将索引键合并后再一起计算Hash值,所以不会对每个索引单独计算Hash值,因此如果用到联合索引的一个或几个索引时,联合索引无法被利用。

3.Hash索引不支持 ORDER BY 排序,因为 Hash 索引指向的数据是无序的,因此无法起到排序优化的作用,而B+树可以。同理,也无法使用Hash索引进行模糊查询,而B+树使用 LIKE 进行模糊查询的时候,LIKE 后面前模糊查询(%开头)的话可以起到优化作用。

对于等值查询来说,通常Hash索引的效率更高,不过当索引列的重复值很多效率就会很低。因为遇到 Hash 冲突时,需要对桶中的行指针进行比较,找到查询的关键字,非常耗时。所以,Hash 索引通常不会用到重复值多的列上,比如列为性别、年龄的情况等。

总结

Hash 索引存在很多限制,相比之下数据库中B+树索引的使用面更广。不过键值型数据库 Redis 存储的核心就是 Hash 表。

(本文完)

SQL性能优化系列——索引的原理[五]

1.为什么索引要存放到硬盘上?如何评价索引的数据结构设计的好坏?
2.使用平衡二叉树作为索引的数据结构有哪些不足?
3.B树和B+树的数据结构是怎样的?为什么常用B+树作为索引的数据结构?

既然前面说索引其实是一种数据结构,那么索引的数据结构究竟是怎样的?

如何评价索引的数据结构好坏

数据库服务器有两种存储介质:硬盘和内存。内存为临时存储,容量有限,且发生断电或故障重启时会造成数据丢失;硬盘属于永久性存储,所以需要把数据存储在硬盘上。

虽然内存读取速度很快,但还是需要将索引存到硬盘上,当在硬盘上进行查询时,也就产生了磁盘的I/O操作。相比内存的存取来说,磁盘I/O存取消耗的时间要高很多。通过索引查找某行数据时,需要计算磁盘I/O次数,次数越多,消耗时间越长。如果索引的数据结构尽可能减少磁盘的I/O操作,则消耗的时间也越少。

二叉树的局限性

二分查找法是一种高效的数据检索方式,时间复杂度为O(log2n),是不是二叉树就适合做索引呢?

先看最基础的二叉搜索树,搜索某个节点和插入节点的规则一样,假设搜索插入的数值为key:

1.如果key大于根节点,则在右子树中查找;

2.如果key小于根节点,则在左子树中查找;

3.如果key等于根节点,则直接返回根节点即可。

例如,对数列(34,22,89,5,23,77,91)创造出来的二叉树,如下图所示:

但是存在特殊情况,就是二叉树的深度非常大。比如给出的数据顺序为(5,22,23,34,77,89,91),创造出来的二叉树如下图所示:

能看出,第一个树深度是3,也就是说最多需要3次比较就可以找到节点,第二个树深度是7,最多需要7次比较才能找到节点。

第二棵树也是二分查找树,但是性能上已经退化成了一条链表,查找数据的时间复杂度变成了O(n)。为解决这个问题,人们提出了平衡二叉搜索树(AVL树),它在二分搜索树的基础上增加了约束,每个节点的左子树和右子树的高度差不得超过1,也即是说节点的左子树和右子树仍然为平衡二叉树。

注:常见平衡二叉树包括:平衡二叉搜索树、红黑树、数堆、伸展树。平衡二叉搜索树是最早提出来自平衡的二叉搜索树,当提到平衡二叉树时一般就是指平衡二叉搜索树。

上面说过数据查询的时间主要依赖于磁盘I/O的次数,如果采用二叉树的形式,即使通过平衡二叉树进行改进,树的深度也是O(log2n),当n比较大时,深度依然很高。比如:

每访问一个节点就需要进行一次磁盘I/O操作,对于上面的树来说,需要进行5次I/O操作。虽然平衡二叉树比较的效率高,但是树的深度也同样高,意味着磁盘I/O操作次数多,会影响整体查询效率。

如果针对同样的数据将二叉树改造成M叉树(M>2)呢?当M=3时,同样的31个节点可以由下面的三叉树存储:

能看到,当数据量大的时候,以及树的分叉M大的时候,M叉树的高度会远小于二叉树的高度。B树也就由此产生了。

什么是B树

B树英文名叫Balance Tree,平衡的多路搜索树,它的高度远小于平衡二叉树的高度,在文件系统和数据库系统中常用B树作为索引的数据结构。

B树数据结构如下:

B树作为平衡的多路搜索树,它的每一个节点最多包含M个子节点,M称为B树的阶。同时能看到,每个磁盘块中包括了关键字和子节点的指针。如果一个磁盘块中包括了x个关键字,那么指针数就是x+1个。对于一个100阶的B树来说,如果有3层的话最多可以存储约100万的索引数据,对于大量的索引数据来说,采用B数的结构是非常适合的,因为高度远小于二叉树。

一个M阶的B树有如下特性:

1.根节点的儿子数的范围是[2,M];

2.每个中间节点的包含k-1个关键字和k个孩子,孩子的数量=关键字的数量+1,k的取值范围为[ceil(M/2),M];(ceil函数为向上取整)

3.叶子节点包括k-1个关键字(叶子节点没有孩子),k的取值范围为[ceil(M/2),M];

4.假设中间节点节点的关键字为:key[1],key[2],。。。,key[k-1],且关键字按照升序排序,即key[i]<key[i+1]。此时k-1个关键字相当于划分了k个范围,也即是对应k个指针,分别为:p[1],p[2],…p[k],其中p[1]指向关键字小于key[1]的子树,p[i]指向关键字属于(key[i-1],key[i])的子树,p[k]指向关键字大于key[k-1]的子树;

5.所有叶子节点位于同一层。

上面的图所示的B树刚好符合上面5点特征。

那么如何用B树来进行查找呢?假设想要查找关键字9,步骤如下:

1.与根节点的关键字(17,35)进行比较,9小于17,得到指针p1;

2.按指针p1找到磁盘块2,关键字为(8,12),9在8和12之间,得到指针p2;

3.按指针p2找到磁盘块6,关键字为(9,10),然后就找到了关键字9.

什么是B+树

B+树基于B树做了改进,主流的DBMS都支持B+树的索引方式,比如MySQL。B+树和B树的差异如下:

1.有k个孩子的节点就有k个关键字。即孩子数量=关键字数量。

2.非叶子节点的关键字也会同时存在在子节点中,并且是在子节点中所有关键字的最大(或最小)。

3.非叶子节点仅用于索引,不保存数据记录,跟记录有关的信息都存在叶子节点中。而B树中,非叶子节点既保存索引,也保存数据记录。

4.所有关键字都在叶子节点中出现,叶子节点构成一个有序链表,而且叶子节点本身按照关键字的大小从小到大顺序链接。

下图就是B+树,阶数为3,根节点中的关键字1、18、35分别是子节点(1,8,14)、(18,24,31)和(35,41,53)中的最小值。每一层父节点的关键字都会出现在下一层的子节点的关键字中,因此在叶子节点中包括了所有关键字的信息,并且每一个叶子节点都有一个指向下一个叶子节点的指针,这样就形成了一个链表。

比如,要查找关键字16,B+树会自顶向下逐层查找:

1.与根节点(1,18,35)比较,16在1和18之间,得到指针p1(指向磁盘块2);

2.找到磁盘块2,关键字为(1,8,14),16大于14,得到指针p3(指向磁盘块7);

3.找到磁盘块7,关键字为(14,16,17),然后找到关键字16,所以关键字16对应的数据。

整个过程总共进行了3次I/O操作,看起来B+数和B树的查询过程差不多,但是B+树和B树的根本差异在于B+树的中间节点并不直接存储数据。这样好处有什么呢?

首先,B+树查询效率更稳定。“稳定”怎么理解呢?因为B+树每次只有访问到叶子节点才能找到对应的数据,而在B树中,非叶子节点也会存储数据,这样就会造成查询效率不稳定的情况:有时候访问到了非叶子节点就可以找到关键字,而有时需要访问到叶子节点才能找到关键字。

其次,B+树查询效率更高。因为B+树比B树更矮胖(阶数更大,深度更低),查询所需磁盘I/O也会更少。同样的磁盘页大小,B+树可以存储更多的节点关键字。

不仅是对单个关键字的查询上,在查询范围上,B+树的效率也比B树高。因为所有关键字都出现在叶子节点中,并通过有序链表进行了链接。而在B树中则需要通过中序遍历才能完成查询范围的查找,效率要低很多。(何谓中序遍历?中序遍历(LDR)是二叉树遍历的一种,也叫做中根遍历、中序周游。在二叉树中,中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。)

总结

磁盘的I/O操作次数对索引的使用效率至关重要。B树和B+树都可以作为索引的数据结构,在MySQL中采用的是B+树。通过以上对比,B+树在查询性能上更稳定,在磁盘页大小相同的情况下,树的结构更矮胖,所需进行的磁盘I/O次数更少,更适合进行关键字的范围查询。

(本文完)

SQL性能优化系列——索引概览[四]

1.索引种类?
2.什么情况需要创建索引?

索引的本质是帮我们快速定位想要查找的数据。

索引是万能的?

索引(Index),好比一本书的目录,可以快速定位与查找特定值,从而加快数据查询效率。

索引就是帮助数据库管理系统高效获取数据的数据结构。

如果不使用索引,就必须从第一条记录开始扫描,直到把所有数据表都扫描完才能找到目标数据。但是创建更多的索引就行了吗?

索引不是万能的,某些情况使用索引反而会降低效率。

索引的价值是帮我们从海量数据中查找目标数据,如果数据量少,使用索引与否效率区别不大。(1000行的数据量就很少,不需要创建索引。)另外,数据重复度大,比如高于10%时,也不需要对该字段使用索引,比如前面举的性别这个例子,就不需要创建索引,因为想要在100万行数据中查找其中的50万行(比如性别为男的数据),一旦创建了索引,就需要先访问50万次索引,然后再访问50万次数据表,这样加起来的开销比不使用索引可能还大。没有数据支撑的空谈都是耍流氓,下面做两个实验:

实验1:数据行数少的情况下,索引效率咋样?

heros_without_index表,数据共69条就不列进来了,下面只是数据结构:

SET NAMES utf8mb4;
SET FOREIGN_KEY_CHECKS = 0;

-- ----------------------------
-- Table structure for heros_without_index
-- ----------------------------
DROP TABLE IF EXISTS `heros_without_index`;
CREATE TABLE `heros_without_index`  (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL,
  `hp_max` float NULL DEFAULT NULL,
  `hp_growth` float NULL DEFAULT NULL,
  `hp_start` float NULL DEFAULT NULL,
  `mp_max` float NULL DEFAULT NULL,
  `mp_growth` float NULL DEFAULT NULL,
  `mp_start` float NULL DEFAULT NULL,
  `attack_max` float NULL DEFAULT NULL,
  `attack_growth` float NULL DEFAULT NULL,
  `attack_start` float NULL DEFAULT NULL,
  `defense_max` float NULL DEFAULT NULL,
  `defense_growth` float NULL DEFAULT NULL,
  `defense_start` float NULL DEFAULT NULL,
  `hp_5s_max` float NULL DEFAULT NULL,
  `hp_5s_growth` float NULL DEFAULT NULL,
  `hp_5s_start` float NULL DEFAULT NULL,
  `mp_5s_max` float NULL DEFAULT NULL,
  `mp_5s_growth` float NULL DEFAULT NULL,
  `mp_5s_start` float NULL DEFAULT NULL,
  `attack_speed_max` float NULL DEFAULT NULL,
  `attack_range` varchar(255) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL,
  `role_main` varchar(255) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL,
  `role_assist` varchar(255) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL,
  `birthdate` date NULL DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE
) ENGINE = InnoDB AUTO_INCREMENT = 10069 CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Dynamic;

对name进行条件查询:

SELECT id, name, hp_max, mp_max FROM heros_without_index WHERE name = '刘禅'

对name字段建立索引后,heros_with_index表,数据完全相同,69条,数据结构如下:

SET NAMES utf8mb4;
SET FOREIGN_KEY_CHECKS = 0;

-- ----------------------------
-- Table structure for heros_with_index
-- ----------------------------
DROP TABLE IF EXISTS `heros_with_index`;
CREATE TABLE `heros_with_index`  (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL,
  `hp_max` float NULL DEFAULT NULL,
  `hp_growth` float NULL DEFAULT NULL,
  `hp_start` float NULL DEFAULT NULL,
  `mp_max` float NULL DEFAULT NULL,
  `mp_growth` float NULL DEFAULT NULL,
  `mp_start` float NULL DEFAULT NULL,
  `attack_max` float NULL DEFAULT NULL,
  `attack_growth` float NULL DEFAULT NULL,
  `attack_start` float NULL DEFAULT NULL,
  `defense_max` float NULL DEFAULT NULL,
  `defense_growth` float NULL DEFAULT NULL,
  `defense_start` float NULL DEFAULT NULL,
  `hp_5s_max` float NULL DEFAULT NULL,
  `hp_5s_growth` float NULL DEFAULT NULL,
  `hp_5s_start` float NULL DEFAULT NULL,
  `mp_5s_max` float NULL DEFAULT NULL,
  `mp_5s_growth` float NULL DEFAULT NULL,
  `mp_5s_start` float NULL DEFAULT NULL,
  `attack_speed_max` float NULL DEFAULT NULL,
  `attack_range` varchar(255) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL,
  `role_main` varchar(255) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL,
  `role_assist` varchar(255) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL,
  `birthdate` date NULL DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE,
  UNIQUE INDEX `name`(`name`) USING BTREE
) ENGINE = InnoDB AUTO_INCREMENT = 10069 CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Dynamic;

对name再查询:

SELECT id, name, hp_max, mp_max FROM heros_with_index WHERE name = '刘禅'

对比两种查询时间:

mysql> use buerguo;
Database changed
mysql> SELECT id, name, hp_max, mp_max FROM heros_without_index WHERE name = ‘刘禅’
-> ;
+——-+——+——–+——–+
| id | name | hp_max | mp_max |
+——-+——+——–+——–+
| 10015 | 刘禅 | 8581 | 1694 |
+——-+——+——–+——–+
1 row in set (0.00 sec)

mysql> SELECT id, name, hp_max, mp_max FROM heros_with_index WHERE name = ‘刘禅’
-> ;
+——-+——+——–+——–+
| id | name | hp_max | mp_max |
+——-+——+——–+——–+
| 10015 | 刘禅 | 8581 | 1694 |
+——-+——+——–+——–+
1 row in set (0.00 sec)

mysql>

通过观察,两种查询时间相差无几,装逼失败。。

其实想说的是:理论上数据量少时,创建name字段索引的查询时间要比没有创建索引的查询时间长,也就是说数据量不大的情况下,索引发挥不出作用。

实验2:性别(男或女)字段真的不应该创建索引吗?

如果一个字段的取值少,比如性别这个字段,通常不需要创建索引,但是特殊情况还是需要考虑的,比方说唐僧到女儿国了,100万女施主,男性只有5个(小白龙也算上),男性只是女性20万分之一了。

女儿国数据表user_gender:

SET NAMES utf8mb4;
SET FOREIGN_KEY_CHECKS = 0;

-- ----------------------------
-- Table structure for user_gender
-- ----------------------------
DROP TABLE IF EXISTS `user_gender`;
CREATE TABLE `user_gender`  (
  `user_id` int(11) NOT NULL,
  `user_name` varchar(255) CHARACTER SET utf8mb4 COLLATE utf8mb4_0900_ai_ci NOT NULL,
  `user_gender` tinyint(1) NOT NULL,
  PRIMARY KEY (`user_id`) USING BTREE
) ENGINE = InnoDB CHARACTER SET = utf8mb4 COLLATE = utf8mb4_0900_ai_ci ROW_FORMAT = Dynamic;

要筛选男性可以使用语句,查询语句如下:(*也就三个字段:user_id,user_name,user_gender)

SELECT * FROM user_gender WHERE user_gender = 1

为了防止装逼失败,直接说结论吧。在未创建索引的情况下,运行效率不高,如果对user_gender字段创建索引呢?

SELECT * FROM user_gender WHERE user_gender = 1

同样的数据,运行结果相同,时间却只是未创建索引时的10分之1,查询效率提升了不止一个档次。

通过上面两个实验想要说明什么呢,其实索引价值就是快速定位,如果想要定位的数据有很多,那么索引就失去了他的使用价值,比如通常情况下性别字段男女比例平衡。不过有时考虑到这个字段中数值分布的情况,在实验2中,性别字段的数值分布非常特殊,男性比例非常少,使用索引查询效率就提升了。因此,不仅要看字段中的数值个数,还要根据数值的分布情况来考虑是否需要创建索引。

索引种类

从功能逻辑上说,索引共有4种:普通索引、唯一索引、主键索引、全文索引。

普通索引是基础的索引,没有任何约束,主要用于提高查询效率。

唯一索引是在普通索引的基础上添加了数据唯一性的约束,在一张表中可以有多个唯一索引。

主键索引是在唯一索引的基础上增加了不为空的约束,也就是NOT NULL+UNIQUE,一张表中最多只有一个主键索引(这是由主键索引的物理实现方式决定的,因为数据存储在文件中只能按一种顺序进行存储,但可以有多个普通索引或唯一索引)。

全文索引用的不多,MySQL中全文索引只支持英文。通常可以采用专门的全文搜索引擎如ES和Solr。

前三种索引是同一类索引,只是对数据的约束性逐渐提升。

按物理实现方式,索引分为两种:聚集索引和非聚集索引。非聚集索引又称为二级索引或辅助索引。

聚集索引可以按主键来排序存储数据,查找行更有效。举例:在一本字典中查找“数”这个字,直接在字典中找拼音“shu”的位置即可。这样找到了索引的位置,在它后面就是想要的数据行。

非聚集索引:数据库系统会有单独的存储空间存放非聚集索引,这些索引项是按照顺序存储的,但索引项指向的内容是随机存储的。即是说系统会进行两次查找,第一次先找到索引,第二次找到索引对应的位置的数据行取出。非聚集索引不会把索引指向的内容直接放到索引后面,而是维护单独的索引表(只维护索引,不维护索引指向的数据),为数据检索提供方便。举例:如果想要找“数”字,按照部首查找方式,先找到偏旁部首,然后这个目录告诉我们“数”字在第多少页,然后我们才去指定的页码找这个字。

(都快忘了字典咋用的了。。)

聚集索引与非聚集索引使用区别:

1.聚集索引叶子节点存储的就是数据记录,非聚集索引的叶子节点存储的是数据位置。非聚集索引不会影响数据表的物理存储顺序。

2.一个表只能有一个聚集索引,因为只能有一种排序存储的方式,但是可以有多个非聚集索引,也就是多个索引目录提供数据检索。

3.使用聚集索引的时候,数据的查询效率高,但如果对数据进行插入,删除,更新等操作,效率会比非聚集索引低。

实验3:使用聚集索引和非聚集索引的查询效率

还以刚才的user_gender表举例,对比一下聚集索引和非聚集索引查询效率。通过建表语句看到,该表设置了user_id为主键也就是聚集索引的字段是user_id。此处查询一下user_id=90001的用户信息:

(把该表中唐僧5人踢出去然后空降了10位精壮的成年男子。。)

对user_id和user_name两种情况的查询结果如下:

mysql> SELECT user_id, user_name, user_gender FROM user_gender WHERE user_id = 900001
-> ;
+———+—————-+————-+
| user_id | user_name | user_gender |
+———+—————-+————-+
| 900001 | student_890001 | 0 |
+———+—————-+————-+
1 row in set (0.00 sec)

mysql> SELECT user_id, user_name, user_gender FROM user_gender WHERE user_name = ‘student_890001’
-> ;
+———+—————-+————-+
| user_id | user_name | user_gender |
+———+—————-+————-+
| 900001 | student_890001 | 0 |
+———+—————-+————-+
1 row in set (0.54 sec)

可以通过看执行时间进行对比。

然后通过对user_name字段创建普通索引,再查询,运行时间也降低到0.05.s了。

结论:

1.对where子句的字段建立索引,可以大幅提升查询效率。

2.采用聚集索引进行数据查询,比使用非聚集索引的查询效率高。如果查询次数比较多,尽量使用主键索引进行数据查询。

 

除了业务逻辑和物理实现方式,索引还可以按照字段个数进行划分,分成单一索引和联合索引。索引列为一列时为单一索引,多个列组合在一起创建的索引称之为联合索引。

注意:创建联合索引需要注意创建时的顺序,因为联合索引(x,y,z)和(z,y,x)在使用的时候效率可能会存在差别。

需要说明的是联合索引存在最左匹配原则。也就是按照最左有限的方式进行索引的匹配。比如(x,y,z),如果查询条件是where x=1 and y=2 and z=3,就可以匹配上联合索引;如果查询条件是where y=2,就无法匹配上联合索引。

实验4:联合索引的最左原则

还是以user_gender表为例,把user_id和user_name设置为联合主键,对比查询效率。

SELECT user_id, user_name, user_gender FROM user_gender WHERE user_id = 900001 AND user_name = 'student_890001'

查询用时:0.046s

SELECT user_id, user_name, user_gender FROM user_gender WHERE user_id = 900001

查询用时:0.046s

然后看普通查询:

SELECT user_id, user_name, user_gender FROM user_gender WHERE user_name = 'student_890001'

查询用时:0.943s

可以看到使用联合索引(user_id,user_name)时,在where子句中队联合索引中的字段user_id和user_name进行条件查询,或者只对user_id进行查询,效率基本上是一样的;当对user_name进行条件查询时,效率会低很多,这是因为根据联合索引的最左原则,user_id在user_name的左侧,如果没有使用user_id直接使用user_name进行条件查询,联合索引就会失效。

总结

使用索引可以从海量数据中快速定位数据,不过索引也存在不足:占用存储空间、降低数据库写操作的性能等。如果有多个索引还会增加索引选择的时间。当使用索引时,需要权衡索引的利(提升查询效率)弊(维护索引所需的代价)。

思考

关于联合索引的最左原则指的是什么?使用联合索引时需要注意哪些地方?

(本文完)

SQL性能优化系列——反范式设计[三]

1.有了范式设计,为什么有时还需要反范式设计?
2.反范式设计的适用场景?存在哪些问题?

反范式设计

尽管数据表的设计有很多范式,但实际上在设计表的时候不一定要参照这些标准。因为在设计的过程中,有时为了性能和读取效率会违反范式化的原则,即通过增加少量冗余、通过空间换取时间的优化思路,对查询效率进行优化。

比如,查询某商品前1000评论,涉及两张表。

商品评论表:product_comment

字段 comment_id product_id comment_text comment_time user_id
含义 商品评论id 商品id 评论内容 评论时间 用户id
DROP TABLE IF EXISTS `product_comment`;
CREATE TABLE `product_comment`  (
  `comment_id` int(11) NOT NULL AUTO_INCREMENT,
  `product_id` int(11) NOT NULL,
  `comment_text` varchar(255) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL,
  `comment_time` datetime(0) NOT NULL,
  `user_id` int(11) NOT NULL,
  PRIMARY KEY (`comment_id`) USING BTREE
) ENGINE = InnoDB AUTO_INCREMENT = 10000 CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Dynamic;

用户表:user

字段 user_id user_name create_time
含义 用户id 用户昵称 注册时间
DROP TABLE IF EXISTS `user`;
CREATE TABLE `user`  (
  `user_id` int(11) NOT NULL,
  `user_name` varchar(255) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL,
  `create_time` datetime(0) NOT NULL,
  PRIMARY KEY (`user_id`) USING BTREE
) ENGINE = InnoDB CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Dynamic;

下面用这两种表进行模拟反范式优化。

模拟数据:两张百万量级数据表(通过存储过程实现)

用户表:随机生成100万用户

CREATE DEFINER=`root`@`localhost` PROCEDURE `insert_many_user`(IN start INT(10), IN max_num INT(10))
BEGIN
DECLARE i INT DEFAULT 0;
DECLARE date_start DATETIME DEFAULT ('2017-01-01 00:00:00');
DECLARE date_temp DATETIME;
SET date_temp = date_start;
SET autocommit=0;
REPEAT
SET i=i+1;
SET date_temp = date_add(date_temp, interval RAND()*60 second);
INSERT INTO user(user_id, user_name, create_time)
VALUES((start+i), CONCAT('user_',i), date_temp);
UNTIL i = max_num
END REPEAT;
COMMIT;
END

date_start用来定义注册的初始时间;

date_temp变量计算每个用户的注册时间,新注册的和上一个注册的间隔60s;

REPEAT。。UNTIL 。。END REPEAT循环,对max_num个用户的数据进行计算;

autocommit设置为0,这样等计算完成再统一插入,效率更高。

然后运行call insert_many_user(10000,1000000);调用存储过程,通过start和max_num两个参数对初始的user_id和要创建的用户数量进行设置。

 

商品评论表:随机生成100万条商品评论

CREATE DEFINER=`root`@`localhost` PROCEDURE `insert_many_product_comments`(IN START INT(10), IN max_num INT(10))
BEGIN
DECLARE i INT DEFAULT 0;
DECLARE date_start DATETIME DEFAULT ('2018-01-01 00:00:00');
DECLARE date_temp DATETIME;
DECLARE comment_text VARCHAR(25);
DECLARE user_id INT;
SET date_temp = date_start;
SET autocommit=0;
REPEAT
SET i=i+1;
SET date_temp = date_add(date_temp, INTERVAL RAND()*60 SECOND);
SET comment_text = substr(MD5(RAND()),1, 20);
SET user_id = FLOOR(RAND()*1000000);
INSERT INTO product_comment(comment_id, product_id, comment_text, comment_time, user_id)
VALUES((START+i), 10001, comment_text, date_temp, user_id);
UNTIL i = max_num
END REPEAT;
COMMIT;
END

执行call insert_many_products_commonts(10000,1000000);调用存储过程。

 

反范式优化实验对比

如果查询10001这个商品的前1000条评论,sql:

SELECT p.comment_text, p.comment_time, u.user_name FROM product_comment AS p 
LEFT JOIN user AS u 
ON p.user_id = u.user_id 
WHERE p.product_id = 10001 
ORDER BY p.comment_id DESC LIMIT 1000

运行时长0.395秒,查询效率并不高。

关联查询product_comment和user,数据量超过百万量级,查询效率会降低。因为查询在两表上进行聚集索引扫描,然后嵌套循环,这样查询耗费的时间会有几百毫秒甚至更久。

如果想提升查询效率,可以考虑在商品评论表中添加用户昵称字段:user_name

这样形成了product_comment2:

DROP TABLE IF EXISTS `product_comment2`;
CREATE TABLE `product_comment2`  (
  `comment_id` int(11) NOT NULL AUTO_INCREMENT,
  `product_id` int(11) NOT NULL,
  `comment_text` varchar(255) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL,
  `comment_time` datetime(0) NOT NULL,
  `user_id` int(11) NOT NULL,
  `user_name` varchar(255) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL,
  PRIMARY KEY (`comment_id`) USING BTREE
) ENGINE = InnoDB AUTO_INCREMENT = 10000 CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Dynamic;

这样查询只需要:

SELECT comment_text, comment_time, user_name FROM product_comment2 WHERE product_id = 10001 ORDER BY comment_id DESC LIMIT 1000

优化后只需要扫描一次聚集索引,运行时间是之前的十分之一,查询效率明显提升。(难怪个别网站不允许修改昵称)

反范式存在的问题与适用场景

当冗余信息有价值或能显著提升查询效率的时候,就可以采取反范式优化。

此外,反范式优化常用在数据仓库的设计中,因为数据仓库通常存储历史数据,实时性要求不高,对历史数据分析需求强。此时适当允许数据冗余度,更方便数据分析。

数据仓库和数据库的使用区别:

1.数据库设计目的在于捕获数据,数据仓库设计目的在于分析数据;

2.数据库对数据增删改实时性要求高,需要存储在线用户数据,数据仓库存储的一般是历史数据;

3.数据库设计尽量避免冗余,但为了提升查询效率允许少量冗余,数据仓库设计更偏向反范式设计。

了解

最近正在基于Hadoop建设某国企的数据集市项目(地域性非全网),恰如老师所言,我们就是在遵循反范式的设计。

简要来说,我们把数据加工链路分为四层,从下到上依次为:ODS贴源层、DWD明细层、DWS汇总层和ADS应用层。

多源异构的业务数据被源源不断ETL到ODS贴源层之后,经过清洗、规范、转换、拼接等,生成各类宽表存储在DWD明细层;再根据业务模型设计,以这些宽表为基础,生成各类标准的指标数据存储在DWS汇总层;ADS层则基于DWS层的汇总指标再度组合,计算得出应用层数据,直接面向业务需求。

在这样的系统设计中,反范式不仅体现在“宽表”的设计中,更体现在数据加工链路的完整生命周期中——上层都是对下层的冗余。