Jamzy Wang

life is a struggle,be willing to do,be happy to bear~~~

MySQL中的索引详解

2015-04-27 23:24

原创声明:本作品采用知识共享署名-非商业性使用 3.0 版本许可协议进行许可,欢迎转载,演绎,但是必须保留本文的署名(包含链接),且不得用于商业目的。

数据库性能优化中最常推荐的方法是什么?

最容易优化SQL查询速度的方法是什么(在不改变表结构的前提下)?

最容易被忽视的数据库开发和维护技巧是什么?

索引

数据库的磁盘读写

在讲解索引之前,先来看一下数据是如何存储在数据库中的。数据库中的数据是存放在磁盘中的,磁盘的读取相对于内存的读取效率是非常非常低的,Latency numbers every programmer should know一文给出了各种常见读写操作的时间对比:

L1 cache reference …………………………………0.5 ns

Branch mispredict ………………………………….5 ns

L2 cache reference …………………………………7 ns

Mutex lock/unlock …………………………………25 ns

Main memory reference ………………………..100 ns

Compress 1K bytes with Zippy ………………3,000 ns = 3 µs

Send 2K bytes over 1 Gbps network ………20,000 ns = 20 µs

SSD random read ………………………………………150,000 ns = 150 µs

Read 1 MB sequentially from memory ..250,000 ns = 250 µs

Round trip within same datacenter …………..500,000 ns = 0.5 ms

Read 1 MB sequentially from SSD* …………..1,000,000 ns = 1 ms

Disk seek ………………………………………………………..10,000,000 ns = 10 ms

Read 1 MB sequentially from disk ………….20,000,000 ns = 20 ms

Send packet CA->Netherlands->CA …………..150,000,000 ns = 150 ms

从上面的数据中我们可以看到在内存中顺序读取1M的数据需要250us,而在磁盘中顺序读取1MB的数据需要20ms,对比一下二者的读取速度,可以发现内存读写要比磁盘读写快近千倍。总之需要记住一点:

1
磁盘IO性能非常低,这会严重影响数据库系统的性能。

磁盘的这个特性不单单对数据库会产生影响,在其他程序中,当代码需要读取一个很大的文件,比如10G大小的文件,也会因为磁盘IO的低效耗费很长时间。

磁盘空间被划分为许多大小相同的块(Block)或者页(Page),Block和Block之间是以链表的形式串联在一起的,一个Block连着另一个Block。而数据库中的数据是以行(Row)为单位一行一行的存放在磁盘块中,一个磁盘块中存放几行或者几十行的数据(具体一个块能存放的数据的行数取决于表中每行数据的大小),如图所示:

磁盘读写的另一个特点是:

1
在访问数据时,一次从磁盘中读出或者写入至少一个完整的Block

也就是说不能从磁盘中单独读取一行数据,只能一下子读取几行或者几十行数据。

数据库的基本操作有INSERT、UPDATE、DELETE、SELECT4种,那么这4种操作是如何实现的呢?

  • SELECT

    1) 定位数据

    2) 读出数据所在的块,对数据加工

    3) 返回数据给用户

  • UPDATE、DELETE

    1) 定位数据

    2) 读出数据所在的块,修改数据

    3) 写回磁盘

  • INSERT

    1) 定位数据要插入的页(如果数据需要排序)

    2) 读出要插入的数据页,插入数据.

    3) 写回磁盘

那么数据库是如何定位数据的呢? 通过表扫描(Table Scan),所谓表扫描指的是:

1
从磁盘中依次读出所有的数据块,一行一行的进行数据匹配,直到找到所需要的行。

这种扫描方法也叫作全表扫描(full table scan),可以看出这种表扫描定位数据的时间复杂度是O(n)(类似在链表中查找特定的值),如果一张表的所有数据占用了10000个块,那么即使只查询一行数据,在最坏情况下需要读取10000个块,平均每次定位数据需要读取5000个块。

上文中我们已经强调过,磁盘的读写性能是非常低的,全表扫描需要大量的磁盘IO操作(这些IO操作中极大部分是无效的,因为不是我们需要找的数据),这极大的影响了数据定位的性能。而数据定位又是所有数据操作必须的,因此数据定位操作的效率会直接影响所有的数据操作的效率。自然地,我们需要寻找一种方法来减少磁盘IO。减少磁盘IO的方法有:

  • 1)减少数据占用的磁盘空间 压缩算法、优化数据存储结构

  • 2)减少访问数据的总量 读出或写入的数据中,有一部分是数据操作所必须的,这部分称作有效数据。剩余的部分则不是数据操作必须的数据,称为无效数据。例如,查询id是‘000183’的记录。那么这条记录是有效记录,其他记录则是无效记录。我们要努力减少无效数据的访问。

索引

在数据库中,索引的含义与日常意义上的“索引”一词并无多大区别(想想查字典的过程),它用于提高数据库表数据访问速度,它有如下特点:

  • 索引是对数据库表中一列或多列的值进行排序的一种结构。
  • 索引是表数据的目录结构。
  • 索引提供指向存储在表的指定列中的数据值的指针,然后根据指定的排序顺序对这些指针排序。
  • 索引可以避免全表扫描。多数查询可以仅扫描少量索引页及数据页,而不是遍历所有数据页。

下面将具体阐述索引的作用。

我们发现在多数情况下,定位操作并不需要匹配整行数据, 而是只需要匹配某一列或某几列的值,这些用来确定一条数据的列,统称为键(Key),如:

1
2
3
4
5
匹配1列:
select user_name, user_email, user_age, user_gender from user_info where user_id = "01103300";

匹配2列:
select user_email, user_gender from user_info where user_name = "myname" AND user_age = 15;

那么根据减少无效数据访问的原则,我们可以将键的值存放到独立的块中,并且为每一个键值添加一个指针, 指向原来的数据块,这种键值组织方式叫作“Dense Index”,如下图所示:

这种Dense Index就是最初的索引实现方式。当有了这种索引之后,数据的定位操作不再需要进行全表扫描而只需要进行索引扫描(Index Scan),依次读出所有的索引块,进行键值的匹配。当找到匹配的键值后,根据该行的指针直接读取对应的数据块,进行操作。

假设一个块中能存储100行数据,10,000,000行的数据需要100,000个块的存储空间。假设键值列(+指针)占用一行数据1/10的空间。那么大约需要10,000个块来存储Dense索引。因此我们用大约1/10的额外存储空间换来了大约全表扫描10倍的定位效率。

在实际的应用中,这样的定位效率仍然不能满足需求,于是,许多索引优化方法被提出。

我们来确定一下索引优化需要实现什么功能:

1
对于给定的某个表中的某列值,如何组织这些值使得对于特定值的查找能够最大限度的减少磁盘访问。

比如,我们要对一个表中的id(整型)建立索引,我们需要解决的问题就是“给你一个整数序列,如何组织这个整数序列使得查找某个整数的性能达到最优”。对于这种数据的查找问题,往往通过排序二分查找算法来提高性能。假设有如下数据:

1
2
3
4
5
6
7
表结构:
id    name        age       email         gender
1   Brighton   10  abc@gmail.com    male
2   Downtown   15  def@gmail.com    female
3   Mianus     29  dfd@gmail.com    female
4   Redwood    54  odk@gmail.com    male
...

每一行数据对应的磁盘块号如下:

1
2
3
4
5
6
(id, block id)
1, 894454
2, 453654
3, 342344
4, 435435
...

上述(id,block id)代表的就是索引数据。现在需要查找id = 100000的数据所在的行该怎么做呢? 一种做法自然是遍历这个索引数据,如果id有序,我们可以用二分查找来加快这个查找过程。如果id无序或者我们用name这个字段做索引呢?可以先对索引排序再用二分查找算法查找。

上面的表述中我们默认索引数据按照数组的方式组织,那么是否还有其他更好的数据组织方式呢?当然有,比如b-tree,比如hash表。后文中我们将具体介绍b-tree, hash表实现的索引的区别。

下面再用一个具体的例子来对比一下不用索引和使用索引的数据的读取效率对比。假设有如下的数据库表结构:

1
2
3
4
5
Field name       Data type      Size on disk
id (Primary key) Unsigned INT   4 bytes
firstName        Char(50)       50 bytes
lastName         Char(50)       50 bytes
emailAddress     Char(100)      100 bytes

假设现在表中有 r = 5,000,000 条记录,每条记录的长度是 R = 204 bytes, 这些记录存储在MyISAM存储引擎中(默认会为Primary Key建立索引),磁盘块的默认大小是 size B = 1,024 bytes。那么,一个磁盘块中可以存 bfr = (B/R) = 1024/204 = 5 条记录,存所有记录需要 N = (r/bfr) = 5000000/5 = 1,000,000 块。那么通过全表扫描的方式定位数据平均需要读取 N/2 = 500,000 个磁盘块。

现在有两个查询操作,一个通过id查询,一个通过frirstName查询,我们来对比一下二者的性能差异。

  • 基于id查询:

由于id已排序,所以可以用二分查找来降低查找时间,定位数据平均只需要读取 log2 1000000 = 19.93 = 20 磁盘块。

  • 基于firstName查询:

由于firstName 没有经过排序,所以不能用二分查找定位数据,同时在表中firstName也不是唯一的,因此定位数据需要进行全表扫描,需要读取N = 1,000,000 个块。

从上述对比可以看出索引的巨大优化效果。

索引类型

常见的索引类型根据其实现包括hash index、btree index、full text index等, 索引类型的选择主要取决于应用的不同需求:

1
2
3
4
hash index: 主要用于满足精确匹配
btree index: 主要用于满足范围查询、精确匹配
fulltext index: 主要用于全文关键字查询
spatial (R-Tree) index: 用于空间索引

MySQL中不同的存储引擎支持不同的索引类型:

1
2
3
heap 引擎支持 hash index
myisaminnodb 引擎支持 btree index
myisaminnodb-ft 支持 fulltext index

hash index

hash 索引是一种非常高效的索引类型,一般实现为 hashtable, 属于内存型索引,典型的 key/value 类型, 在 mysql中只有memory storage engine支持 hash indexe。

hash索引的特点:

1
2
3
1. 只支持通过column值精确匹配(=, IN(), and <=>),不支持范围查询(> ,<),不支持部分匹配(like)
2. 不支持 order by
3. 不支持 index statistics( MySQL 查询计划没有帮助)

b-tree

B树是一种适合磁盘等慢速设备的索引结构,能够以较少磁盘读取次数查找数据(至于B树为什么能够减少磁盘访问推荐阅读此文:从B树、B+树、B*树谈到R 树),Oracle、Mysql均使用B树实现索引。

为何不是二叉树存储索引?

1)树的层次太深。由于二叉树出度为2,假如Key的数量N很大的话,会造成树的层次过多。这样造成的直接结果是若要查找的Key在比较靠近叶子节点的深度时,会造成大量磁盘IO。(为了存取设计的简易,通常将每一个节点放进单独的磁盘块中

2)通常就算是用二叉树作为索引的存储结构,也并非用的二叉树,而是二叉平衡树或者红黑树,因为二叉树是可能不平衡的,若要保持平衡,在每一次插入、更新或者删除节点的时候就要对树做相应的旋转操作,以保持起平衡。这本身也是很耗费计算资源的操作

能用 B+ 树查询的操作(前提是查询条件所在列建了索引)

1
2
3
4
1) 精确查找匹配某个值的记录(Match the full value),如查找last nameJack的记录
2)查找以某个值为前缀的记录(Match a column prefix),如查找以 J开头的last name
3)查找某个范围内的记录(Match a range of values),比如查找 last name Allen  barrymore
4)上述1)、2)、3)的任意组合,只能是建了索引的相同列。

B树的索引分为两种,非聚集索引和聚集索引(cluster index),非聚集索引与聚集索引相比:

1
2
3
4
1. 叶子结点并非数据结点
2. 叶子结点为每一真正的数据行存储一个“键-指针”对
3. 叶子结点中还存储了一个指针偏移量,根据页指针及指针偏移量可以定位到具体的数据行。
4. 类似的,在除叶结点外的其它索引结点,存储的也是类似的内容,只不过它是指向下一级的索引页的。

非聚集索引

非聚集索引是MySQL的MyISAM索引实现方式。MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。

  • 非聚集索引的查询操作

此处输入图片的描述

  • 非聚集索引与插入操作

如果一张表包含一个非聚集索引但没有聚集索引,则新的数据将被插入到最末一个数据页中,然后非聚集索引将被更新。如果也包含聚集索引,该聚集索引将被用于查找新行将要处于什么位置,随后,聚集索引、以及非聚集索引将被更新。

  • 非聚集索引与删除操作

如果在删除命令的Where子句中包含的列上,建有非聚集索引,那么该非聚集索引将被用于查找数据行的位置,数据删除之后,位于索引叶子上的对应记录也将被删除。如果该表上有其它非聚集索引,则它们叶子结点上的相应数据也要删除。 如果删除的数据是该数所页中的唯一一条,则该页也被回收,同时需要更新各个索引树上的指针。

注意:由于没有自动的合并功能,如果应用程序中有频繁的随机删除操作,最后可能导致表包含多个数据页,但每个页中只有少量数据。

聚集索引

聚集索引是MySQL的InnoDB索引实现方式。和MyISAM索引实现相比,InnoDB的数据文件本身就是索引文件。在InnoDB中,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引。每个叶子节点包括 primary key(或者 row_id), transactionID, rollback pointer 和行数据, 非叶子节点只包括被索引列的索引信息。

innodb 中的 btree 实际上是 b+ tree。为何是b+tree而不是b-tree?

1
2
3
1.b+tree出度相比b-tree更大,因为其非叶节点不需要存储Key相对应的物理地址指针
2.叶节点包含了所有的Key,查询比较均衡
3.每个叶节点都保存了指向下一个叶节点的指针,对于范围查询存取更方便

聚集索引主要优点:

1
2
相关的数据临近存放, 利于磁盘存取
row 的读取更快,因为 row  index 一起存放

聚集索引主要缺点:

1
2
3
4
如果访问模式与存储顺序无关,则 cluster index 无用
按主键顺序插入和读取最快, 但是如果按主键随机插入(特别是字符串) 则读写效率降低
更新 cluster index 列的代价较大, 会将整个 row 重新写到新的位置上,并且所有 secondary index 也要更新
如果 cluster index 建立在内容较长的字符串字段上, 会导致所有的 secondary index 都较大
  • 聚集索引的查询操作

此处输入图片的描述

  • 索引更新

最简单的情况下,插入操作根据索引找到对应的数据页,然后通过挪动已有的记录为新数据腾出空间,最后插入数据。如果数据页已满,则需要拆分数据页(页拆分是一种耗费资源的操作,一般数据库系统中会有相应的机制要尽量减少页拆分的次数,通常是通过为每页预留空间来实现): 1. 在该使用的数据段(extent)上分配新的数据页,如果数据段已满,则需要分配新段。 2. 调整索引指针,这需要将相应的索引页读入内存并加锁。 3. 大约有一半的数据行被归入新的数据页中。 4. 如果表还有非聚集索引,则需要更新这些索引指向新的数据页。

联合索引

在 MySQL 中有一个限制,一个表在一次查询中最多使用一个索引。但是我们对一张表的很多字段可能都需要使用索引,这个时候怎么办呢? 正是联合索引来解决这个问题。

联合索引可以用于的查询(下面的所有例子都基于联合索引 ABC(按照 A、B、C 顺序建立的联合索引)):

  • 1)联合索引 ABC 依然符合最左前缀的原则

即只有 ABC、AB、A 三种情况可以使用到索 引, 也不能跳 index,即 AC 同时查询只能使用到联合索引的 A 部分。

  • 2) 第一个列的精确匹配、第二列的范围查询

例如: select d from table where A = “x” and B >= “y” and C = “z”

只有 A = “x”和 B >= “y”能使用到索引, C = “z”不能使用索引, 因为如果联合索引 ABC 中的某一个字段使用了范围查询,则后面的字段不能再使用索引。

联合索引,经常要使用范围查询的, 将该范围查询索引字段尽量放在后面,因为联合索引中某个索引使用范围查询后, 其后的索引将不再有效。

Spatial (R-Tree) index

MyISAM支持R-Tree索引,不需要最左前缀匹配。主要用户地理位置相关查询。有个GEOMETRY数据类型采用R-tree索引。

全文索引

全文检索是一种基于关键字的查询,支持全文内的检索,而 btree、hash 只能支持精确匹配和 leftmost 查询, 另外, 全文检索不像 btree、hash 那样要求准确的结果。

MyISAM 是少有的支持全文检索的引擎, 其特点如下:

  • 全文检索语法支持有限
  • 百万量级

相比于MyISAM, Sphinx 是一款非常优秀的全文检索系统,其特点如下:

  • 功能和性能都很强大的全文检索系统
  • 十亿级别数据规模
  • 非实时检索,需要主动拉数据
  • 相关性不易扩展

索引的负面影响

虽然索引可以提高查询速度,但是它们也会导致数据库系统更新数据的性能下降,因为大部分数据更新需要同时更新索引,一般会减小1/3 ~1/2。因此只有在频繁查询,并且更新操作较少的数据上建立索引。可以通过profile,日志和实验分析获取。

MySQL中如何建索引

MySQL会自动给申明为PRIMARY KEYKEYUNIQUEINDEX的列建立索引。建立索引语法如下:

1
2
3
CREATE [UNIQUE|FULLTEXT|SPATIAL] INDEX index_name
USING [BTREE | HASH | RTREE]
ON table_name (column_name [(length)] [ASC | DESC],...)

删除索引语法如下:

1
DROP INDEX index_name ON table_name

我们尝试在products表上对name列建立索引:

此处输入图片的描述

然后我们用 show index from products; 命令查看products表上已经建立的索引,如:

此处输入图片的描述

从上图中我们可以看到,products表中建了2个索引,一个是针对productID的索引,这事MySQL自动创建的,另一个就是我们刚才对name建立的索引。

这里需要注意几点:

1
2
3
unique索引指的是索引上的值都是唯一的。
fulltext索引只能在MyISAM引擎上创建的表中才能建立,且要求列的属性是`CHAR`、`VARCHAR`、`TEXT`。
spatial索引只能在MyISAM引擎上创建的表中才能建立。

同时using 字段中的值的选择取决于表所使用的引擎类型:

此处输入图片的描述

MySQL中如何正确使用索引

索引设计优化索引设计规范:

1
2
3
4
5
6
7
8
索引不是越多越好。虽然能改善查询,但是也能减慢插入和更新的速度
索引的创建需要以SQL为基础,一般需要提供所有对表的相关SQL来均衡索引的创建
长字符类的字段适当情况添加前缀索引,减小索引文件大小,提高检索效率。比如idx_name(name(10))
对于InnoDB引擎的表,最好使用自增ID或者数值类字段做主键
索引中的字段数建议不超过5
合理创建联合索引(避免冗余),使用前缀索引,(a,b,c) 相当于 (a) (a,b) (a,b,c)
模糊匹配like %xxx”,不会使用索引
不在索引列进行计算,否则不会使用索引

Ref

How does database indexing work?

How to Design Indexes, Really

由浅入深理解索引的实现

MySQL Query Optimization

SQL Indexing For Dummies

How MySQL Uses Indexes

How b-tree database indexes work and how to tell if they are efficient (100’ level)

MySQL索引背后的数据结构及算法原理

Comments