五分钟理解一致性哈希算法(consistent hashing)

    一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简 单哈希算法带来的问题,使得分布式哈希(DHT)可以在P2P环境中真正得到应用。
    一致性hash算法提出了在动态变化的Cache环境中,判定哈希算法好坏的四个定义:
1、平衡性(Balance):平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。
2、单调性(Monotonicity):单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。
3、分散性(Spread):在分布式环境中,终端有可能看不到所有的缓冲,而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时,由于不同终端所见的缓冲范围有可能不同,从而导致哈希的结果不一致,最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的,因为它导致相同内容被存储到不同缓冲中去,降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生,也就是尽量降低分散性。
4、负载(Load):负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中,那么对于一个特定的缓冲区而言,也可能被不同的用户映射为不同 的内容。与分散性一样,这种情况也是应当避免的,因此好的哈希算法应能够尽量降低缓冲的负荷。
    在分布式集群中,对机器的添加删除,或者机器故障后自动脱离集群这些操作是分布式集群管理最基本的功能。如果采用常用的hash(object)%N算法,那么在有机器添加或者删除后,很多原有的数据就无法找到了,这样严重的违反了单调性原则。接下来主要讲解一下一致性哈希算法是如何设计的:
环形Hash空间
按照常用的hash算法来将对应的key哈希到一个具有2^32次方个桶的空间中,即0~(2^32)-1的数字空间中。现在我们可以将这些数字头尾相连,想象成一个闭合的环形。如下图
                                                                         
把数据通过一定的hash算法处理后映射到环上
现在我们将object1、object2、object3、object4四个对象通过特定的Hash函数计算出对应的key值,然后散列到Hash环上。如下图:
    Hash(object1) = key1;
    Hash(object2) = key2;
    Hash(object3) = key3;
    Hash(object4) = key4;
                                                           
将机器通过hash算法映射到环上
在采用一致性哈希算法的分布式集群中将新的机器加入,其原理是通过使用与对象存储一样的Hash算法将机器也映射到环中(一般情况下对机器的hash计算是采用机器的IP或者机器唯一的别名作为输入值),然后以顺时针的方向计算,将所有对象存储到离自己最近的机器中。
假设现在有NODE1,NODE2,NODE3三台机器,通过Hash算法得到对应的KEY值,映射到环中,其示意图如下:
Hash(NODE1) = KEY1;
Hash(NODE2) = KEY2;
Hash(NODE3) = KEY3;
                                                             
通过上图可以看出对象与机器处于同一哈希空间中,这样按顺时针转动object1存储到了NODE1中,object3存储到了NODE2中,object2、object4存储到了NODE3中。在这样的部署环境中,hash环是不会变更的,因此,通过算出对象的hash值就能快速的定位到对应的机器中,这样就能找到对象真正的存储位置了。
机器的删除与添加
普通hash求余算法最为不妥的地方就是在有机器的添加或者删除之后会照成大量的对象存储位置失效,这样就大大的不满足单调性了。下面来分析一下一致性哈希算法是如何处理的。
1. 节点(机器)的删除
    以上面的分布为例,如果NODE2出现故障被删除了,那么按照顺时针迁移的方法,object3将会被迁移到NODE3中,这样仅仅是object3的映射位置发生了变化,其它的对象没有任何的改动。如下图:
                                                              
2. 节点(机器)的添加
    如果往集群中添加一个新的节点NODE4,通过对应的哈希算法得到KEY4,并映射到环中,如下图:
                                                              
    通过按顺时针迁移的规则,那么object2被迁移到了NODE4中,其它对象还保持这原有的存储位置。通过对节点的添加和删除的分析,一致性哈希算法在保持了单调性的同时,还是数据的迁移达到了最小,这样的算法对分布式集群来说是非常合适的,避免了大量数据迁移,减小了服务器的的压力。
平衡性
根据上面的图解分析,一致性哈希算法满足了单调性和负载均衡的特性以及一般hash算法的分散性,但这还并不能当做其被广泛应用的原由,因为还缺少了平衡性。下面将分析一致性哈希算法是如何满足平衡性的。hash算法是不保证平衡的,如上面只部署了NODE1和NODE3的情况(NODE2被删除的图),object1存储到了NODE1中,而object2、object3、object4都存储到了NODE3中,这样就照成了非常不平衡的状态。在一致性哈希算法中,为了尽可能的满足平衡性,其引入了虚拟节点。
    ——“虚拟节点”( virtual node )是实际节点(机器)在 hash 空间的复制品( replica ),一实际个节点(机器)对应了若干个“虚拟节点”,这个对应个数也成为“复制个数”,“虚拟节点”在 hash 空间中以hash值排列。
以上面只部署了NODE1和NODE3的情况(NODE2被删除的图)为例,之前的对象在机器上的分布很不均衡,现在我们以2个副本(复制个数)为例,这样整个hash环中就存在了4个虚拟节点,最后对象映射的关系图如下:
                                                                 
根据上图可知对象的映射关系:object1->NODE1-1,object2->NODE1-2,object3->NODE3-2,object4->NODE3-1。通过虚拟节点的引入,对象的分布就比较均衡了。那么在实际操作中,正真的对象查询是如何工作的呢?对象从hash到虚拟节点到实际节点的转换如下图:
                                         
“虚拟节点”的hash计算可以采用对应节点的IP地址加数字后缀的方式。例如假设NODE1的IP地址为192.168.1.100。引入“虚拟节点”前,计算 cache A 的 hash 值:
Hash(“192.168.1.100”);
引入“虚拟节点”后,计算“虚拟节”点NODE1-1和NODE1-2的hash值:
Hash(“192.168.1.100#1”); // NODE1-1
Hash(“192.168.1.100#2”); // NODE1-2

btree索引和hash索引的区别

来源:https://www.cnblogs.com/ziqiumeng/p/7680204.html

Hash 索引结构的特殊性,其检索效率非常高,索引的检索可以一次定位,不像B-Tree 索引需要从根节点到枝节点,最后才能访问到页节点这样多次的IO访问,所以 Hash 索引的查询效率要远高于 B-Tree 索引。可能很多人又有疑问了,既然 Hash 索引的效率要比 B-Tree 高很多,为什么大家不都用 Hash 索引而还要使用 B-Tree 索引呢?任何事物都是有两面性的,Hash 索引也一样,虽然 Hash 索引效率高,但是 Hash 索引本身由于其特殊性也带来了很多限制和弊端,主要有以下这些。

(1)Hash 索引仅仅能满足”=”,”IN”和”<=>”查询,不能使用范围查询。

由于 Hash 索引比较的是进行 Hash 运算之后的 Hash 值,所以它只能用于等值的过滤,不能用于基于范围的过滤,因为经过相应的 Hash 算法处理之后的 Hash 值的大小关系,并不能保证和Hash运算前完全一样。

(2)Hash 索引无法被用来避免数据的排序操作。

由于 Hash 索引中存放的是经过 Hash 计算之后的 Hash 值,而且Hash值的大小关系并不一定和 Hash 运算前的键值完全一样,所以数据库无法利用索引的数据来避免任何排序运算;

(3)Hash 索引不能利用部分索引键查询。

对于组合索引,Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值,而不是单独计算 Hash 值,所以通过组合索引的前面一个或几个索引键进行查询的时候,Hash 索引也无法被利用。

(4)Hash 索引在任何时候都不能避免表扫描。

前面已经知道,Hash 索引是将索引键通过 Hash 运算之后,将 Hash运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中,由于不同索引键存在相同 Hash 值,所以即使取满足某个 Hash 键值的数据的记录条数,也无法从 Hash 索引中直接完成查询,还是要通过访问表中的实际数据进行相应的比较,并得到相应的结果。

(5)Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。

对于选择性比较低的索引键,如果创建 Hash 索引,那么将会存在大量记录指针信息存于同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦,会浪费多次表数据的访问,而造成整体性能低下

2. B-Tree索引
B-Tree 索引是 MySQL 数据库中使用最为频繁的索引类型,除了 Archive 存储引擎之外的其他所有的存储引擎都支持 B-Tree 索引。不仅仅在 MySQL 中是如此,实际上在其他的很多数据库管理系统中B-Tree 索引也同样是作为最主要的索引类型,这主要是因为 B-Tree 索引的存储结构在数据库的数据检 索中有非常优异的表现。        一般来说, MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的结构来存储的,也就是所有实际需要的数据都存放于 Tree 的 Leaf Node ,而且到任何一个 Leaf Node 的最短路径的长度都是完全相同的,所以我们大家都称之为 B-Tree 索引当然,可能各种数据库(或 MySQL 的各种存储引擎)在存放自己的 B-Tree 索引的时候会对存储结构稍作改造。如 Innodb 存储引擎的 B-Tree 索引实际使用的存储结构实际上是 B+Tree ,也就是在 B-Tree 数据结构的基础上做了很小的改造,在每一个  Leaf Node 上面出了存放索引键的相关信息之外,还存储了指向与该 Leaf Node 相邻的后一个 LeafNode 的指针信息,这主要是为了加快检索多个相邻 Leaf Node 的效率考虑。        在 Innodb 存储引擎中,存在两种不同形式的索引,一种是 Cluster 形式的主键索引( Primary Key ),另外一种则是和其他存储引擎(如 MyISAM 存储引擎)存放形式基本相同的普通 B-Tree 索引,这种索引在 Innodb 存储引擎中被称为 Secondary Index 。下面我们通过图示来针对这两种索引的存放  形式做一个比较。
MySQL的btree索引和hash索引的区别
图示中左边为 Clustered 形式存放的 Primary Key ,右侧则为普通的 B-Tree 索引。两种 Root Node 和 Branch Nodes 方面都还是完全一样的。而 Leaf Nodes 就出现差异了。在 Prim中, Leaf Nodes 存放的是表的实际数据,不仅仅包括主键字段的数据,还包括其他字段的数据据以主键值有序的排列。而 Secondary Index 则和其他普通的 B-Tree 索引没有太大的差异,Leaf Nodes 出了存放索引键 的相关信息外,还存放了 Innodb 的主键值。
所以,在 Innodb 中如果通过主键来访问数据效率是非常高的,而如果是通过 Secondary Index 来访问数据的话, Innodb 首先通过 Secondary Index 的相关信息,通过相应的索引键检索到 Leaf Node之后,需要再通过 Leaf Node 中存放的主键值再通过主键索引来获取相应的数据行。MyISAM 存储引擎的主键索引和非主键索引差别很小,只不过是主键索引的索引键是一个唯一且非空 的键而已。而且 MyISAM 存储引擎的索引和 Innodb 的 Secondary Index 的存储结构也基本相同,主要的区别只是 MyISAM 存储引擎在 Leaf Nodes 上面出了存放索引键信息之外,再存放能直接定位到 MyISAM 数据文件中相应的数据行的信息(如 Row Number ),但并不会存放主键的键值信息

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

来源:http://blog.codinglabs.org/articles/theory-of-mysql-index.html
作者 张洋 | 发布于 2011-10-18
MySQL 索引 B树 优化

摘要

本文以MySQL数据库为研究对象,讨论与数据库索引相关的一些话题。特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引,哈希索引,全文索引等等。为了避免混乱,本文将只关注于BTree索引,因为这是平常使用MySQL时主要打交道的索引,至于哈希索引和全文索引本文暂不讨论。

文章主要内容分为三个部分。

第一部分主要从数据结构及算法理论层面讨论MySQL数据库索引的数理基础。

第二部分结合MySQL数据库中MyISAM和InnoDB数据存储引擎中索引的架构实现讨论聚集索引、非聚集索引及覆盖索引等话题。

第三部分根据上面的理论基础,讨论MySQL中高性能使用索引的策略。

数据结构及算法基础

索引的本质

MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。提取句子主干,就可以得到索引的本质:索引是数据结构。

我们知道,数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快,因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找(linear search),这种复杂度为O(n)的算法在数据量很大时显然是糟糕的,好在计算机科学的发展提供了很多更优秀的查找算法,例如二分查找(binary search)、二叉树查找(binary tree search)等。如果稍微分析一下会发现,每种查找算法都只能应用于特定的数据结构之上,例如二分查找要求被检索数据有序,而二叉树查找只能应用于二叉查找树上,但是数据本身的组织结构不可能完全满足各种数据结构(例如,理论上不可能同时将两列都按顺序进行组织),所以,在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法。这种数据结构,就是索引。

看一个例子:

图1

图1展示了一种可能的索引方式。左边是数据表,一共有两列七条记录,最左边的是数据记录的物理地址(注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的)。为了加快Col2的查找,可以维护一个右边所示的二叉查找树,每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针,这样就可以运用二叉查找在O(log2n)O(log2n)的复杂度内获取到相应数据。

虽然这是一个货真价实的索引,但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树(red-black tree)实现的,原因会在下文介绍。

B-Tree和B+Tree

目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构,在本文的下一节会结合存储器原理及计算机存取原理讨论为什么B-Tree和B+Tree在被如此广泛用于索引,这一节先单纯从数据结构角度描述它们。

B-Tree

为了描述B-Tree,首先定义一条数据记录为一个二元组[key, data],key为记录的键值,对于不同数据记录,key是互不相同的;data为数据记录除key外的数据。那么B-Tree是满足下列条件的数据结构:

d为大于1的一个正整数,称为B-Tree的度。

h为一个正整数,称为B-Tree的高度。

每个非叶子节点由n-1个key和n个指针组成,其中d<=n<=2d。

每个叶子节点最少包含一个key和两个指针,最多包含2d-1个key和2d个指针,叶节点的指针均为null 。

所有叶节点具有相同的深度,等于树高h。

key和指针互相间隔,节点两端是指针。

一个节点中的key从左到右非递减排列。

所有节点组成树结构。

每个指针要么为null,要么指向另外一个节点。

如果某个指针在节点node最左边且不为null,则其指向节点的所有key小于v(key1)v(key1),其中v(key1)v(key1)为node的第一个key的值。

如果某个指针在节点node最右边且不为null,则其指向节点的所有key大于v(keym)v(keym),其中v(keym)v(keym)为node的最后一个key的值。

如果某个指针在节点node的左右相邻key分别是keyikeyikeyi+1keyi+1且不为null,则其指向节点的所有key小于v(keyi+1)v(keyi+1)且大于v(keyi)v(keyi)

图2是一个d=2的B-Tree示意图。

图2

由于B-Tree的特性,在B-Tree中按key检索数据的算法非常直观:首先从根节点进行二分查找,如果找到则返回对应节点的data,否则对相应区间的指针指向的节点递归进行查找,直到找到节点或找到null指针,前者查找成功,后者查找失败。B-Tree上查找算法的伪代码如下:

  1. BTree_Search(node, key) {
  2. if(node == null) return null;
  3. foreach(node.key)
  4. {
  5. if(node.key[i] == key) return node.data[i];
  6. if(node.key[i] > key) return BTree_Search(point[i]->node);
  7. }
  8. return BTree_Search(point[i+1]->node);
  9. }
  10. data = BTree_Search(root, my_key);

关于B-Tree有一系列有趣的性质,例如一个度为d的B-Tree,设其索引N个key,则其树高h的上限为logd((N+1)/2)logd((N+1)/2),检索一个key,其查找节点个数的渐进复杂度为O(logdN)O(logdN)。从这点可以看出,B-Tree是一个非常有效率的索引数据结构。另外,由于插入删除新的数据记录会破坏B-Tree的性质,因此在插入删除时,需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质,本文不打算完整讨论B-Tree这些内容,因为已经有许多资料详细说明了B-Tree的数学性质及插入删除算法,有兴趣的朋友可以在本文末的参考文献一栏找到相应的资料进行阅读。

B+Tree

B-Tree有许多变种,其中最常见的是B+Tree,例如MySQL就普遍使用B+Tree实现其索引结构。

与B-Tree相比,B+Tree有以下不同点:

每个节点的指针上限为2d而不是2d+1。

内节点不存储data,只存储key;叶子节点不存储指针。

图3是一个简单的B+Tree示意。

图3

由于并不是所有节点都具有相同的域,因此B+Tree中叶节点和内节点一般大小不同。这点与B-Tree不同,虽然B-Tree中不同节点存放的key和指针可能数量不一致,但是每个节点的域和上限是一致的,所以在实现中B-Tree往往对每个节点申请同等大小的空间。

一般来说,B+Tree比B-Tree更适合实现外存储索引结构,具体原因与外存储器原理及计算机存取原理有关,将在下面讨论。

带有顺序访问指针的B+Tree

一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化,增加了顺序访问指针。

图4

如图4所示,在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针,就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能,例如图4中如果要查询key为从18到49的所有数据记录,当找到18后,只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点,极大提到了区间查询效率。

这一节对B-Tree和B+Tree进行了一个简单的介绍,下一节结合存储器存取原理介绍为什么目前B+Tree是数据库系统实现索引的首选数据结构。

为什么使用B-Tree(B+Tree)

上文说过,红黑树等数据结构也可以用来实现索引,但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构,这一节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。

一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。下面先介绍内存和磁盘存取原理,然后再结合这些原理分析B-/+Tree作为索引的效率。

主存存取原理

目前计算机使用的主存基本都是随机读写存储器(RAM),现代RAM的结构和存取原理比较复杂,这里本文抛却具体差别,抽象出一个十分简单的存取模型来说明RAM的工作原理。

图5

从抽象角度看,主存是一系列的存储单元组成的矩阵,每个存储单元存储固定大小的数据。每个存储单元有唯一的地址,现代主存的编址规则比较复杂,这里将其简化成一个二维地址:通过一个行地址和一个列地址可以唯一定位到一个存储单元。图5展示了一个4 x 4的主存模型。

主存的存取过程如下:

当系统需要读取主存时,则将地址信号放到地址总线上传给主存,主存读到地址信号后,解析信号并定位到指定存储单元,然后将此存储单元数据放到数据总线上,供其它部件读取。

写主存的过程类似,系统将要写入单元地址和数据分别放在地址总线和数据总线上,主存读取两个总线的内容,做相应的写操作。

这里可以看出,主存存取的时间仅与存取次数呈线性关系,因为不存在机械操作,两次存取的数据的“距离”不会对时间有任何影响,例如,先取A0再取A1和先取A0再取D3的时间消耗是一样的。

磁盘存取原理

上文说过,索引一般以文件形式存储在磁盘上,索引检索需要磁盘I/O操作。与主存不同,磁盘I/O存在机械运动耗费,因此磁盘I/O的时间消耗是巨大的。

图6是磁盘的整体结构示意图。

图6

一个磁盘由大小相同且同轴的圆形盘片组成,磁盘可以转动(各个磁盘必须同步转动)。在磁盘的一侧有磁头支架,磁头支架固定了一组磁头,每个磁头负责存取一个磁盘的内容。磁头不能转动,但是可以沿磁盘半径方向运动(实际是斜切向运动),每个磁头同一时刻也必须是同轴的,即从正上方向下看,所有磁头任何时候都是重叠的(不过目前已经有多磁头独立技术,可不受此限制)。

图7是磁盘结构的示意图。

图7

盘片被划分成一系列同心环,圆心是盘片中心,每个同心环叫做一个磁道,所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段,每个段叫做一个扇区,每个扇区是磁盘的最小存储单元。为了简单起见,我们下面假设磁盘只有一个盘片和一个磁头。

当需要从磁盘读取数据时,系统会将数据逻辑地址传给磁盘,磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址,即确定要读的数据在哪个磁道,哪个扇区。为了读取这个扇区的数据,需要将磁头放到这个扇区上方,为了实现这一点,磁头需要移动对准相应磁道,这个过程叫做寻道,所耗费时间叫做寻道时间,然后磁盘旋转将目标扇区旋转到磁头下,这个过程耗费的时间叫做旋转时间。

局部性原理与磁盘预读

由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,磁盘的存取速度往往是主存的几百分分之一,因此为了提高效率,要尽量减少磁盘I/O。为了达到这个目的,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理:

当一个数据被用到时,其附近的数据也通常会马上被使用。

程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。

预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页得大小通常为4k),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续运行。

B-/+Tree索引的性能分析

到这里终于可以分析B-/+Tree索引的性能了。

上文说过一般使用磁盘I/O次数评价索引结构的优劣。先从B-Tree分析,根据B-Tree的定义,可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理,将一个节点的大小设为等于一个页,这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的,在实际实现B-Tree还需要使用如下技巧:

每次新建节点时,直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里,加之计算机存储分配都是按页对齐的,就实现了一个node只需一次I/O。

B-Tree中一次检索最多需要h-1次I/O(根节点常驻内存),渐进复杂度为O(h)=O(logdN)O(h)=O(logdN)。一般实际应用中,出度d是非常大的数字,通常超过100,因此h非常小(通常不超过3)。

综上所述,用B-Tree作为索引结构效率是非常高的。

而红黑树这种结构,h明显要深的多。由于逻辑上很近的节点(父子)物理上可能很远,无法利用局部性,所以红黑树的I/O渐进复杂度也为O(h),效率明显比B-Tree差很多。

上文还说过,B+Tree更适合外存索引,原因和内节点出度d有关。从上面分析可以看到,d越大索引的性能越好,而出度的上限取决于节点内key和data的大小:

dmax=floor(pagesize/(keysize+datasize+pointsize))dmax=floor(pagesize/(keysize+datasize+pointsize))

floor表示向下取整。由于B+Tree内节点去掉了data域,因此可以拥有更大的出度,拥有更好的性能。

这一章从理论角度讨论了与索引相关的数据结构与算法问题,下一章将讨论B+Tree是如何具体实现为MySQL中索引,同时将结合MyISAM和InnDB存储引擎介绍非聚集索引和聚集索引两种不同的索引实现形式。

MySQL索引实现

在MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。

MyISAM索引实现

MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图:

图8

这里设表一共有三列,假设我们以Col1为主键,则图8是一个MyISAM表的主索引(Primary key)示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中,主索引和辅助索引(Secondary key)在结构上没有任何区别,只是主索引要求key是唯一的,而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引,则此索引的结构如下图所示:

图9

同样也是一颗B+Tree,data域保存数据记录的地址。因此,MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记录。

MyISAM的索引方式也叫做“非聚集”的,之所以这么称呼是为了与InnoDB的聚集索引区分。

InnoDB索引实现

虽然InnoDB也使用B+Tree作为索引结构,但具体实现方式却与MyISAM截然不同。

第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道,MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。而在InnoDB中,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引。

图10

图10是InnoDB主索引(同时也是数据文件)的示意图,可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集,所以InnoDB要求表必须有主键(MyISAM可以没有),如果没有显式指定,则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键,如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含字段作为主键,这个字段长度为6个字节,类型为长整形。

第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说,InnoDB的所有辅助索引都引用主键作为data域。例如,图11为定义在Col3上的一个辅助索引:

图11

这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效,但是辅助索引搜索需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。

了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助,例如知道了InnoDB的索引实现后,就很容易明白为什么不建议使用过长的字段作为主键,因为所有辅助索引都引用主索引,过长的主索引会令辅助索引变得过大。再例如,用非单调的字段作为主键在InnoDB中不是个好主意,因为InnoDB数据文件本身是一颗B+Tree,非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键则是一个很好的选择。

下一章将具体讨论这些与索引有关的优化策略。

索引使用策略及优化

MySQL的优化主要分为结构优化(Scheme optimization)和查询优化(Query optimization)。本章讨论的高性能索引策略主要属于结构优化范畴。本章的内容完全基于上文的理论基础,实际上一旦理解了索引背后的机制,那么选择高性能的策略就变成了纯粹的推理,并且可以理解这些策略背后的逻辑。

示例数据库

为了讨论索引策略,需要一个数据量不算小的数据库作为示例。本文选用MySQL官方文档中提供的示例数据库之一:employees。这个数据库关系复杂度适中,且数据量较大。下图是这个数据库的E-R关系图(引用自MySQL官方手册):

图12

MySQL官方文档中关于此数据库的页面为http://dev.mysql.com/doc/employee/en/employee.html。里面详细介绍了此数据库,并提供了下载地址和导入方法,如果有兴趣导入此数据库到自己的MySQL可以参考文中内容。

最左前缀原理与相关优化

高效使用索引的首要条件是知道什么样的查询会使用到索引,这个问题和B+Tree中的“最左前缀原理”有关,下面通过例子说明最左前缀原理。

这里先说一下联合索引的概念。在上文中,我们都是假设索引只引用了单个的列,实际上,MySQL中的索引可以以一定顺序引用多个列,这种索引叫做联合索引,一般的,一个联合索引是一个有序元组<a1, a2, …, an>,其中各个元素均为数据表的一列,实际上要严格定义索引需要用到关系代数,但是这里我不想讨论太多关系代数的话题,因为那样会显得很枯燥,所以这里就不再做严格定义。另外,单列索引可以看成联合索引元素数为1的特例。

以employees.titles表为例,下面先查看其上都有哪些索引:

  1. SHOW INDEX FROM employees.titles;
  2. +——–+————+———-+————–+————-+———–+————-+——+————+
  3. | Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Null | Index_type |
  4. +——–+————+———-+————–+————-+———–+————-+——+————+
  5. | titles | 0 | PRIMARY | 1 | emp_no | A | NULL | | BTREE |
  6. | titles | 0 | PRIMARY | 2 | title | A | NULL | | BTREE |
  7. | titles | 0 | PRIMARY | 3 | from_date | A | 443308 | | BTREE |
  8. | titles | 1 | emp_no | 1 | emp_no | A | 443308 | | BTREE |
  9. +——–+————+———-+————–+————-+———–+————-+——+————+

从结果中可以到titles表的主索引为<emp_no, title, from_date>,还有一个辅助索引<emp_no>。为了避免多个索引使事情变复杂(MySQL的SQL优化器在多索引时行为比较复杂),这里我们将辅助索引drop掉:

  1. ALTER TABLE employees.titles DROP INDEX emp_no;

这样就可以专心分析索引PRIMARY的行为了。

情况一:全列匹配。

  1. EXPLAIN SELECT * FROM employees.titles WHERE emp_no=‘10001’ AND title=‘Senior Engineer’ AND from_date=‘1986-06-26’;
  2. +—-+————-+——–+——-+—————+———+———+——————-+——+——-+
  3. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  4. +—-+————-+——–+——-+—————+———+———+——————-+——+——-+
  5. | 1 | SIMPLE | titles | const | PRIMARY | PRIMARY | 59 | const,const,const | 1 | |
  6. +—-+————-+——–+——-+—————+———+———+——————-+——+——-+

很明显,当按照索引中所有列进行精确匹配(这里精确匹配指“=”或“IN”匹配)时,索引可以被用到。这里有一点需要注意,理论上索引对顺序是敏感的,但是由于MySQL的查询优化器会自动调整where子句的条件顺序以使用适合的索引,例如我们将where中的条件顺序颠倒:

  1. EXPLAIN SELECT * FROM employees.titles WHERE from_date=‘1986-06-26’ AND emp_no=‘10001’ AND title=‘Senior Engineer’;
  2. +—-+————-+——–+——-+—————+———+———+——————-+——+——-+
  3. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  4. +—-+————-+——–+——-+—————+———+———+——————-+——+——-+
  5. | 1 | SIMPLE | titles | const | PRIMARY | PRIMARY | 59 | const,const,const | 1 | |
  6. +—-+————-+——–+——-+—————+———+———+——————-+——+——-+

效果是一样的。

情况二:最左前缀匹配。

  1. EXPLAIN SELECT * FROM employees.titles WHERE emp_no=‘10001’;
  2. +—-+————-+——–+——+—————+———+———+——-+——+——-+
  3. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  4. +—-+————-+——–+——+—————+———+———+——-+——+——-+
  5. | 1 | SIMPLE | titles | ref | PRIMARY | PRIMARY | 4 | const | 1 | |
  6. +—-+————-+——–+——+—————+———+———+——-+——+——-+

当查询条件精确匹配索引的左边连续一个或几个列时,如<emp_no>或<emp_no, title>,所以可以被用到,但是只能用到一部分,即条件所组成的最左前缀。上面的查询从分析结果看用到了PRIMARY索引,但是key_len为4,说明只用到了索引的第一列前缀。

情况三:查询条件用到了索引中列的精确匹配,但是中间某个条件未提供。

  1. EXPLAIN SELECT * FROM employees.titles WHERE emp_no=‘10001’ AND from_date=‘1986-06-26’;
  2. +—-+————-+——–+——+—————+———+———+——-+——+————-+
  3. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  4. +—-+————-+——–+——+—————+———+———+——-+——+————-+
  5. | 1 | SIMPLE | titles | ref | PRIMARY | PRIMARY | 4 | const | 1 | Using where |
  6. +—-+————-+——–+——+—————+———+———+——-+——+————-+

此时索引使用情况和情况二相同,因为title未提供,所以查询只用到了索引的第一列,而后面的from_date虽然也在索引中,但是由于title不存在而无法和左前缀连接,因此需要对结果进行扫描过滤from_date(这里由于emp_no唯一,所以不存在扫描)。如果想让from_date也使用索引而不是where过滤,可以增加一个辅助索引<emp_no, from_date>,此时上面的查询会使用这个索引。除此之外,还可以使用一种称之为“隔离列”的优化方法,将emp_no与from_date之间的“坑”填上。

首先我们看下title一共有几种不同的值:

  1. SELECT DISTINCT(title) FROM employees.titles;
  2. +——————–+
  3. | title |
  4. +——————–+
  5. | Senior Engineer |
  6. | Staff |
  7. | Engineer |
  8. | Senior Staff |
  9. | Assistant Engineer |
  10. | Technique Leader |
  11. | Manager |
  12. +——————–+

只有7种。在这种成为“坑”的列值比较少的情况下,可以考虑用“IN”来填补这个“坑”从而形成最左前缀:

  1. EXPLAIN SELECT * FROM employees.titles
  2. WHERE emp_no=‘10001’
  3. AND title IN (‘Senior Engineer’, ‘Staff’, ‘Engineer’, ‘Senior Staff’, ‘Assistant Engineer’, ‘Technique Leader’, ‘Manager’)
  4. AND from_date=‘1986-06-26’;
  5. +—-+————-+——–+——-+—————+———+———+——+——+————-+
  6. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  7. +—-+————-+——–+——-+—————+———+———+——+——+————-+
  8. | 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 59 | NULL | 7 | Using where |
  9. +—-+————-+——–+——-+—————+———+———+——+——+————-+

这次key_len为59,说明索引被用全了,但是从type和rows看出IN实际上执行了一个range查询,这里检查了7个key。看下两种查询的性能比较:

  1. SHOW PROFILES;
  2. +———-+————+——————————————————————————-+
  3. | Query_ID | Duration | Query |
  4. +———-+————+——————————————————————————-+
  5. | 10 | 0.00058000 | SELECT * FROM employees.titles WHERE emp_no=‘10001’ AND from_date=‘1986-06-26’|
  6. | 11 | 0.00052500 | SELECT * FROM employees.titles WHERE emp_no=‘10001’ AND title IN |
  7. +———-+————+——————————————————————————-+

“填坑”后性能提升了一点。如果经过emp_no筛选后余下很多数据,则后者性能优势会更加明显。当然,如果title的值很多,用填坑就不合适了,必须建立辅助索引。

情况四:查询条件没有指定索引第一列。

  1. EXPLAIN SELECT * FROM employees.titles WHERE from_date=‘1986-06-26’;
  2. +—-+————-+——–+——+—————+——+———+——+——–+————-+
  3. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  4. +—-+————-+——–+——+—————+——+———+——+——–+————-+
  5. | 1 | SIMPLE | titles | ALL | NULL | NULL | NULL | NULL | 443308 | Using where |
  6. +—-+————-+——–+——+—————+——+———+——+——–+————-+

由于不是最左前缀,索引这样的查询显然用不到索引。

情况五:匹配某列的前缀字符串。

  1. EXPLAIN SELECT * FROM employees.titles WHERE emp_no=‘10001’ AND title LIKE ‘Senior%’;
  2. +—-+————-+——–+——-+—————+———+———+——+——+————-+
  3. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  4. +—-+————-+——–+——-+—————+———+———+——+——+————-+
  5. | 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 56 | NULL | 1 | Using where |
  6. +—-+————-+——–+——-+—————+———+———+——+——+————-+

此时可以用到索引,但是如果通配符不是只出现在末尾,则无法使用索引。(原文表述有误,如果通配符%不出现在开头,则可以用到索引,但根据具体情况不同可能只会用其中一个前缀)

情况六:范围查询。

  1. EXPLAIN SELECT * FROM employees.titles WHERE emp_no < ‘10010’ and title=‘Senior Engineer’;
  2. +—-+————-+——–+——-+—————+———+———+——+——+————-+
  3. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  4. +—-+————-+——–+——-+—————+———+———+——+——+————-+
  5. | 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 4 | NULL | 16 | Using where |
  6. +—-+————-+——–+——-+—————+———+———+——+——+————-+

范围列可以用到索引(必须是最左前缀),但是范围列后面的列无法用到索引。同时,索引最多用于一个范围列,因此如果查询条件中有两个范围列则无法全用到索引。

  1. EXPLAIN SELECT * FROM employees.titles
  2. WHERE emp_no < ‘10010’
  3. AND title=‘Senior Engineer’
  4. AND from_date BETWEEN ‘1986-01-01’ AND ‘1986-12-31’;
  5. +—-+————-+——–+——-+—————+———+———+——+——+————-+
  6. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  7. +—-+————-+——–+——-+—————+———+———+——+——+————-+
  8. | 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 4 | NULL | 16 | Using where |
  9. +—-+————-+——–+——-+—————+———+———+——+——+————-+

可以看到索引对第二个范围索引无能为力。这里特别要说明MySQL一个有意思的地方,那就是仅用explain可能无法区分范围索引和多值匹配,因为在type中这两者都显示为range。同时,用了“between”并不意味着就是范围查询,例如下面的查询:

  1. EXPLAIN SELECT * FROM employees.titles
  2. WHERE emp_no BETWEEN ‘10001’ AND ‘10010’
  3. AND title=‘Senior Engineer’
  4. AND from_date BETWEEN ‘1986-01-01’ AND ‘1986-12-31’;
  5. +—-+————-+——–+——-+—————+———+———+——+——+————-+
  6. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  7. +—-+————-+——–+——-+—————+———+———+——+——+————-+
  8. | 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 59 | NULL | 16 | Using where |
  9. +—-+————-+——–+——-+—————+———+———+——+——+————-+

看起来是用了两个范围查询,但作用于emp_no上的“BETWEEN”实际上相当于“IN”,也就是说emp_no实际是多值精确匹配。可以看到这个查询用到了索引全部三个列。因此在MySQL中要谨慎地区分多值匹配和范围匹配,否则会对MySQL的行为产生困惑。

情况七:查询条件中含有函数或表达式。

很不幸,如果查询条件中含有函数或表达式,则MySQL不会为这列使用索引(虽然某些在数学意义上可以使用)。例如:

  1. EXPLAIN SELECT * FROM employees.titles WHERE emp_no=‘10001’ AND left(title, 6)=‘Senior’;
  2. +—-+————-+——–+——+—————+———+———+——-+——+————-+
  3. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  4. +—-+————-+——–+——+—————+———+———+——-+——+————-+
  5. | 1 | SIMPLE | titles | ref | PRIMARY | PRIMARY | 4 | const | 1 | Using where |
  6. +—-+————-+——–+——+—————+———+———+——-+——+————-+

虽然这个查询和情况五中功能相同,但是由于使用了函数left,则无法为title列应用索引,而情况五中用LIKE则可以。再如:

  1. EXPLAIN SELECT * FROM employees.titles WHERE emp_no 1=‘10000’;
  2. +—-+————-+——–+——+—————+——+———+——+——–+————-+
  3. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  4. +—-+————-+——–+——+—————+——+———+——+——–+————-+
  5. | 1 | SIMPLE | titles | ALL | NULL | NULL | NULL | NULL | 443308 | Using where |
  6. +—-+————-+——–+——+—————+——+———+——+——–+————-+

显然这个查询等价于查询emp_no为10001的函数,但是由于查询条件是一个表达式,MySQL无法为其使用索引。看来MySQL还没有智能到自动优化常量表达式的程度,因此在写查询语句时尽量避免表达式出现在查询中,而是先手工私下代数运算,转换为无表达式的查询语句。

索引选择性与前缀索引

既然索引可以加快查询速度,那么是不是只要是查询语句需要,就建上索引?答案是否定的。因为索引虽然加快了查询速度,但索引也是有代价的:索引文件本身要消耗存储空间,同时索引会加重插入、删除和修改记录时的负担,另外,MySQL在运行时也要消耗资源维护索引,因此索引并不是越多越好。一般两种情况下不建议建索引。

第一种情况是表记录比较少,例如一两千条甚至只有几百条记录的表,没必要建索引,让查询做全表扫描就好了。至于多少条记录才算多,这个个人有个人的看法,我个人的经验是以2000作为分界线,记录数不超过 2000可以考虑不建索引,超过2000条可以酌情考虑索引。

另一种不建议建索引的情况是索引的选择性较低。所谓索引的选择性(Selectivity),是指不重复的索引值(也叫基数,Cardinality)与表记录数(#T)的比值:

Index Selectivity = Cardinality / #T

显然选择性的取值范围为(0, 1],选择性越高的索引价值越大,这是由B+Tree的性质决定的。例如,上文用到的employees.titles表,如果title字段经常被单独查询,是否需要建索引,我们看一下它的选择性:

  1. SELECT count(DISTINCT(title))/count(*) AS Selectivity FROM employees.titles;
  2. +————-+
  3. | Selectivity |
  4. +————-+
  5. | 0.0000 |
  6. +————-+

title的选择性不足0.0001(精确值为0.00001579),所以实在没有什么必要为其单独建索引。

有一种与索引选择性有关的索引优化策略叫做前缀索引,就是用列的前缀代替整个列作为索引key,当前缀长度合适时,可以做到既使得前缀索引的选择性接近全列索引,同时因为索引key变短而减少了索引文件的大小和维护开销。下面以employees.employees表为例介绍前缀索引的选择和使用。

从图12可以看到employees表只有一个索引<emp_no>,那么如果我们想按名字搜索一个人,就只能全表扫描了:

  1. EXPLAIN SELECT * FROM employees.employees WHERE first_name=‘Eric’ AND last_name=‘Anido’;
  2. +—-+————-+———–+——+—————+——+———+——+——–+————-+
  3. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  4. +—-+————-+———–+——+—————+——+———+——+——–+————-+
  5. | 1 | SIMPLE | employees | ALL | NULL | NULL | NULL | NULL | 300024 | Using where |
  6. +—-+————-+———–+——+—————+——+———+——+——–+————-+

如果频繁按名字搜索员工,这样显然效率很低,因此我们可以考虑建索引。有两种选择,建<first_name>或<first_name, last_name>,看下两个索引的选择性:

  1. SELECT count(DISTINCT(first_name))/count(*) AS Selectivity FROM employees.employees;
  2. +————-+
  3. | Selectivity |
  4. +————-+
  5. | 0.0042 |
  6. +————-+
  7. SELECT count(DISTINCT(concat(first_name, last_name)))/count(*) AS Selectivity FROM employees.employees;
  8. +————-+
  9. | Selectivity |
  10. +————-+
  11. | 0.9313 |
  12. +————-+

<first_name>显然选择性太低,<first_name, last_name>选择性很好,但是first_name和last_name加起来长度为30,有没有兼顾长度和选择性的办法?可以考虑用first_name和last_name的前几个字符建立索引,例如<first_name, left(last_name, 3)>,看看其选择性:

  1. SELECT count(DISTINCT(concat(first_name, left(last_name, 3))))/count(*) AS Selectivity FROM employees.employees;
  2. +————-+
  3. | Selectivity |
  4. +————-+
  5. | 0.7879 |
  6. +————-+

选择性还不错,但离0.9313还是有点距离,那么把last_name前缀加到4:

  1. SELECT count(DISTINCT(concat(first_name, left(last_name, 4))))/count(*) AS Selectivity FROM employees.employees;
  2. +————-+
  3. | Selectivity |
  4. +————-+
  5. | 0.9007 |
  6. +————-+

这时选择性已经很理想了,而这个索引的长度只有18,比<first_name, last_name>短了接近一半,我们把这个前缀索引 建上:

  1. ALTER TABLE employees.employees
  2. ADD INDEX `first_name_last_name4` (first_name, last_name(4));

此时再执行一遍按名字查询,比较分析一下与建索引前的结果:

  1. SHOW PROFILES;
  2. +———-+————+———————————————————————————+
  3. | Query_ID | Duration | Query |
  4. +———-+————+———————————————————————————+
  5. | 87 | 0.11941700 | SELECT * FROM employees.employees WHERE first_name=‘Eric’ AND last_name=‘Anido’ |
  6. | 90 | 0.00092400 | SELECT * FROM employees.employees WHERE first_name=‘Eric’ AND last_name=‘Anido’ |
  7. +———-+————+———————————————————————————+

性能的提升是显著的,查询速度提高了120多倍。

前缀索引兼顾索引大小和查询速度,但是其缺点是不能用于ORDER BY和GROUP BY操作,也不能用于Covering index(即当索引本身包含查询所需全部数据时,不再访问数据文件本身)。

InnoDB的主键选择与插入优化

在使用InnoDB存储引擎时,如果没有特别的需要,请永远使用一个与业务无关的自增字段作为主键。

经常看到有帖子或博客讨论主键选择问题,有人建议使用业务无关的自增主键,有人觉得没有必要,完全可以使用如学号或身份证号这种唯一字段作为主键。不论支持哪种论点,大多数论据都是业务层面的。如果从数据库索引优化角度看,使用InnoDB引擎而不使用自增主键绝对是一个糟糕的主意。

上文讨论过InnoDB的索引实现,InnoDB使用聚集索引,数据记录本身被存于主索引(一颗B+Tree)的叶子节点上。这就要求同一个叶子节点内(大小为一个内存页或磁盘页)的各条数据记录按主键顺序存放,因此每当有一条新的记录插入时,MySQL会根据其主键将其插入适当的节点和位置,如果页面达到装载因子(InnoDB默认为15/16),则开辟一个新的页(节点)。

如果表使用自增主键,那么每次插入新的记录,记录就会顺序添加到当前索引节点的后续位置,当一页写满,就会自动开辟一个新的页。如下图所示:

图13

这样就会形成一个紧凑的索引结构,近似顺序填满。由于每次插入时也不需要移动已有数据,因此效率很高,也不会增加很多开销在维护索引上。

如果使用非自增主键(如果身份证号或学号等),由于每次插入主键的值近似于随机,因此每次新纪录都要被插到现有索引页得中间某个位置:

图14

此时MySQL不得不为了将新记录插到合适位置而移动数据,甚至目标页面可能已经被回写到磁盘上而从缓存中清掉,此时又要从磁盘上读回来,这增加了很多开销,同时频繁的移动、分页操作造成了大量的碎片,得到了不够紧凑的索引结构,后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。

因此,只要可以,请尽量在InnoDB上采用自增字段做主键。

后记

这篇文章断断续续写了半个月,主要内容就是上面这些了。不可否认,这篇文章在一定程度上有纸上谈兵之嫌,因为我本人对MySQL的使用属于菜鸟级别,更没有太多数据库调优的经验,在这里大谈数据库索引调优有点大言不惭。就当是我个人的一篇学习笔记了。

其实数据库索引调优是一项技术活,不能仅仅靠理论,因为实际情况千变万化,而且MySQL本身存在很复杂的机制,如查询优化策略和各种引擎的实现差异等都会使情况变得更加复杂。但同时这些理论是索引调优的基础,只有在明白理论的基础上,才能对调优策略进行合理推断并了解其背后的机制,然后结合实践中不断的实验和摸索,从而真正达到高效使用MySQL索引的目的。

另外,MySQL索引及其优化涵盖范围非常广,本文只是涉及到其中一部分。如与排序(ORDER BY)相关的索引优化及覆盖索引(Covering index)的话题本文并未涉及,同时除B-Tree索引外MySQL还根据不同引擎支持的哈希索引、全文索引等等本文也并未涉及。如果有机会,希望再对本文未涉及的部分进行补充吧。

参考文献

[1] Baron Scbwartz等 著,王小东等 译;高性能MySQL(High Performance MySQL);电子工业出版社,2010

[2] Michael Kofler 著,杨晓云等 译;MySQL5权威指南(The Definitive Guide to MySQL5);人民邮电出版社,2006

[3] 姜承尧 著;MySQL技术内幕-InnoDB存储引擎;机械工业出版社,2011

[4] D Comer, Ubiquitous B-tree; ACM Computing Surveys (CSUR), 1979

[5] Codd, E. F. (1970). “A relational model of data for large shared data banks”. Communications of the ACM, , Vol. 13, No. 6, pp. 377-387

[6] MySQL5.1参考手册 – http://dev.mysql.com/doc/refman/5.1/zh/index.html

Mysql的分页查询性能优化

MySQL limit分页查询的性能优化

 

Mysql的分页查询十分简单,但是当数据量大的时候一般的分页就吃不消了。

传统分页查询:SELECT c1,c2,cn… FROM table LIMIT n,m

MySQL的limit工作原理就是先读取前面n条记录,然后抛弃前n条,读后面m条想要的,所以n越大,偏移量越大,性能就越差。

推荐分页查询方法:

1、尽量给出查询的大致范围

  1. SELECT c1,c2,cn… FROM table WHERE id>=20000 LIMIT 10;

2、子查询法

  1. SELECT c1,c2,cn… FROM table WHERE id>=
  2. (
  3. SELECT id FROM table LIMIT 20000,1
  4. )
  5. LIMIT 10;

3、高性能MySQL一书中提到的只读索引方法

优化前SQL:

  1. SELECT c1,c2,cn… FROM member ORDER BY last_active LIMIT 50,5

优化后SQL:

  1. SELECT c1, c2, cn .. .
  2. FROM member
  3. INNER JOIN (SELECT member_id FROM member ORDER BY last_active LIMIT 50, 5)
  4. USING (member_id)

分别在于,优化前的SQL需要更多I/O浪费,因为先读索引,再读数据,然后抛弃无需的行。而优化后的SQL(子查询那条)只读索引(Cover index)就可以了,然后通过member_id读取需要的列。

4、第一步用用程序读取出ID,然后再用IN方法读取所需记录

程序读ID:

  1. SELECT id FROM table LIMIT 20000, 10;
  2. SELECT c1, c2, cn .. . FROM table WHERE id IN (id1, id2, idn.. .)

 

 

==============

 

 

MySQL的limit用法和分页查询的性能分析及优化

一、limit用法

在我们使用查询语句的时候,经常要返回前几条或者中间某几行数据,这个时候怎么办呢?不用担心,mysql已经为我们提供了这样一个功能。

SELECT * FROM table LIMIT [offset,] rows | `rows OFFSET offset ` 
(LIMIT offset, `length`)
SELECT
*
FROM table
where condition1 = 0
and condition2 = 0
and condition3 = -1
and condition4 = -1
order by id asc
LIMIT 2000 OFFSET 50000

LIMIT 子句可以被用于强制 SELECT 语句返回指定的记录数。LIMIT 接受一个或两个数字参数。参数必须是一个整数常量。如果给定两个参数,第一个参数指定第一个返回记录行的偏移量第二个参数指定返回记录行的最大数目初始记录行的偏移量是 0(而不是 1): 为了与 PostgreSQL 兼容,MySQL 也支持句法: LIMIT # OFFSET #。

mysql> SELECT * FROM table LIMIT 5,10; // 检索记录行 6-15 

//为了检索从某一个偏移量到记录集的结束所有的记录行,可以指定第二个参数为 -1:

mysql> SELECT * FROM table LIMIT 95,-1; // 检索记录行 96-last. 

//如果只给定一个参数,它表示返回最大的记录行数目:
mysql> SELECT * FROM table LIMIT 5; //检索前 5 个记录行
//换句话说,LIMIT n 等价于 LIMIT 0,n

二、Mysql的分页查询语句的性能分析

MySql分页sql语句,如果和MSSQL的TOP语法相比,那么MySQL的LIMIT语法要显得优雅了许多。使用它来分页是再自然不过的事情了。

最基本的分页方式:

SELECT ... FROM ... WHERE ... ORDER BY ... LIMIT ... 

在中小数据量的情况下,这样的SQL足够用了,唯一需要注意的问题就是确保使用了索引:
举例来说,如果实际SQL类似下面语句,那么在category_id, id两列上建立复合索引比较好:

SELECT * FROM articles WHERE category_id = 123 ORDER BY id LIMIT 50, 10

子查询的分页方式:

随着数据量的增加,页数会越来越多,查看后几页的SQL就可能类似:
SELECT * FROM articles WHERE category_id = 123 ORDER BY id LIMIT 10000, 10

一言以蔽之,就是越往后分页,LIMIT语句的偏移量就会越大,速度也会明显变慢
此时,我们可以通过子查询的方式来提高分页效率,大致如下:

SELECT * FROM articles WHERE  id >=  
(SELECT id FROM articles  WHERE category_id = 123 ORDER BY id LIMIT 10000, 1) LIMIT 10 

JOIN分页方式

SELECT * FROM `content` AS t1   
JOIN (SELECT id FROM `content` ORDER BY id desc LIMIT ".($page-1)*$pagesize.", 1) AS t2   
WHERE t1.id <= t2.id ORDER BY t1.id desc LIMIT $pagesize; 

经过我的测试,join分页和子查询分页的效率基本在一个等级上,消耗的时间也基本一致。
explain SQL语句:

id select_type table type possible_keys key key_len ref rows Extra
1 PRIMARY <derived2> system NULL NULL NULL NULL 1  
1 PRIMARY t1 range PRIMARY PRIMARY 4 NULL 6264 Using where
2 DERIVED content index NULL PRIMARY 4 NULL 27085 Using index

为什么会这样呢?因为子查询是在索引上完成的,而普通的查询时在数据文件上完成的,通常来说,索引文件要比数据文件小得多,所以操作起来也会更有效率。

实际可以利用类似策略模式的方式去处理分页,比如判断如果是一百页以内,就使用最基本的分页方式,大于一百页,则使用子查询的分页方式。

三、对于有大数据量的mysql表来说,使用LIMIT分页存在很严重的性能问题。

查询从第1000000之后的30条记录:

SQL代码1:平均用时6.6秒 SELECT * FROM `cdb_posts` ORDER BY pid LIMIT 1000000 , 30

SQL代码2:平均用时0.6秒 SELECT * FROM `cdb_posts` WHERE pid >= (SELECT pid FROM  
`cdb_posts` ORDER BY pid LIMIT 1000000 , 1) LIMIT 30

因为要取出所有字段内容,第一种需要跨越大量数据块并取出,而第二种基本通过直接根据索引字段定位后,才取出相应内容,效率自然大大提升。对limit的优化,不是直接使用limit,而是首先获取到offset的id,然后直接使用limit size来获取数据。

可以看出,越往后分页,LIMIT语句的偏移量就会越大,两者速度差距也会越明显。

实际应用中,可以利用类似策略模式的方式去处理分页,比如判断如果是一百页以内,就使用最基本的分页方式,大于一百页,则使用子查询的分页方式。

优化思想:避免数据量大时扫描过多的记录

为了保证index索引列连续,可以为每个表加一个自增字段,并且加上索引

参考:mysql分页offset过大,Sql优化经验

 

 

========

 

 

MySQL单表百万数据记录分页性能优化

背景:

自己的一个网站,由于单表的数据记录高达了一百万条,造成数据访问很慢,Google分析的后台经常报告超时,尤其是页码大的页面更是慢的不行。

测试环境:

先让我们熟悉下基本的sql语句,来查看下我们将要测试表的基本信息

use infomation_schema
SELECT * FROM TABLES WHERE TABLE_SCHEMA = ‘dbname’ AND TABLE_NAME = ‘product’

查询结果:

从上图中我们可以看到表的基本信息:

表行数:866633
平均每行的数据长度:5133字节
单表大小:4448700632字节

关于行和表大小的单位都是字节,我们经过计算可以知道
平均行长度:大约5k
单表总大小:4.1g
表中字段各种类型都有varchar、datetime、text等,id字段为主键

测试实验

1.   直接用limit start, count分页语句, 也是我程序中用的方法:

select * from product limit start, count
当起始页较小时,查询没有性能问题,我们分别看下从10, 100, 1000, 10000开始分页的执行时间(每页取20条), 如下:

select * from product limit 10, 20   0.016秒
select * from product limit 100, 20   0.016秒
select * from product limit 1000, 20   0.047秒
select * from product limit 10000, 20   0.094秒

我们已经看出随着起始记录的增加,时间也随着增大, 这说明分页语句limit跟起始页码是有很大关系的,那么我们把起始记录改为40w看下(也就是记录的一般左右)                                    select * from product limit 400000, 20   3.229秒

再看我们取最后一页记录的时间
select * from product limit 866613, 20   37.44秒

难怪搜索引擎抓取我们页面的时候经常会报超时,像这种分页最大的页码页显然这种时
间是无法忍受的。

从中我们也能总结出两件事情:
1)limit语句的查询时间与起始记录的位置成正比
2)mysql的limit语句是很方便,但是对记录很多的表并不适合直接使用。

2.   对limit分页问题的性能优化方法

利用表的覆盖索引来加速分页查询
我们都知道,利用了索引查询的语句中如果只包含了那个索引列(覆盖索引),那么这种情况会查询很快。

因为利用索引查找有优化算法,且数据就在查询索引上面,不用再去找相关的数据地址了,这样节省了很多时间。另外Mysql中也有相关的索引缓存,在并发高的时候利用缓存就效果更好了。

在我们的例子中,我们知道id字段是主键,自然就包含了默认的主键索引。现在让我们看看利用覆盖索引的查询效果如何:

这次我们之间查询最后一页的数据(利用覆盖索引,只包含id列),如下:
select id from product limit 866613, 20 0.2秒
相对于查询了所有列的37.44秒,提升了大概100多倍的速度

那么如果我们也要查询所有列,有两种方法,一种是id>=的形式,另一种就是利用join,看下实际情况:

SELECT * FROM product WHERE ID > =(select id from product limit 866613, 1) limit 20
查询时间为0.2秒,简直是一个质的飞跃啊,哈哈

另一种写法
SELECT * FROM product a JOIN (select id from product limit 866613, 20) b ON a.ID = b.id
查询时间也很短,赞!

其实两者用的都是一个原理嘛,所以效果也差不多

来源:https://www.cnblogs.com/scotth/p/7995856.html

优化MySQL中的分页

一道面试的问题,当MySQL表中有数据量很大的时候如何做分页。。。。当时只知道在数据量很大的时候可以分表,但不知道不分表时可以怎么做。。。。唉,谁让代理商就那么几条数据,一个简单的limit,offset就完全hold住了(捂脸🙈)。。。

翻译一篇关于优化MySQL中的分页的文章,原文地址:Optimized Pagination using MySQL,谢谢,3Q,康桑阿米达~~~

很多应用往往只展示最新或最热门的几条记录,但为了旧记录仍然可访问,所以就需要个分页的导航栏。然而,如何通过MySQL更好的实现分页,始终是比较令人头疼的问题。虽然没有拿来就能用的解决办法,但了解数据库的底层或多或少有助于优化分页查询。
我们先从一个常用但性能很差的查询来看一看。

1
2
3
4
SELECT *
FROM city
ORDER BY id DESC
LIMIT 0, 15

这个查询耗时0.00sec。So,这个查询有什么问题呢?实际上,这个查询语句和参数都没有问题,因为它用到了下面表的主键,而且只读取15条记录。

1
2
3
4
5
CREATE TABLE city (
  id int(10) unsigned NOT NULL AUTO_INCREMENT,
  city varchar(128) NOT NULL,
  PRIMARY KEY (id)
) ENGINE=InnoDB;

真正的问题在于offset(分页偏移量)很大的时候,像下面这样:

1
2
3
4
SELECT *
FROM city
ORDER BY id DESC
LIMIT 100000, 15;

上面的查询在有2M行记录时需要0.22sec,通过EXPLAIN查看SQL的执行计划可以发现该SQL检索了100015行,但最后只需要15行。大的分页偏移量会增加使用的数据,MySQL会将大量最终不会使用的数据加载到内存中。就算我们假设大部分网站的用户只访问前几页数据,但少量的大的分页偏移量的请求也会对整个系统造成危害。Facebook意识到了这一点,但Facebook并没有为了每秒可以处理更多的请求而去优化数据库,而是将重心放在将请求响应时间的方差变小
对于分页请求,还有一个信息也很重要,就是总共的记录数。我们可以通过下面的查询很容易的获取总的记录数。

1
2
SELECT COUNT(*)
FROM city;

然而,上面的SQL在采用InnoDB为存储引擎时需要耗费9.28sec。一个不正确的优化是采用SQL_CALC_FOUND_ROWS,SQL_CALC_FOUND_ROWS可以在能够在分页查询时事先准备好符合条件的记录数,随后只要执行一句select FOUND_ROWS(); 就能获得总记录数。但是在大多数情况下,查询语句简短并不意味着性能的提高。不幸的是,这种分页查询方式在许多主流框架中都有用到,下面看看这个语句的查询性能。

1
2
3
4
SELECT SQL_CALC_FOUND_ROWS *
FROM city
ORDER BY id DESC
LIMIT 100000, 15;

这个语句耗时20.02sec,是上一个的两倍。事实证明使用SQL_CALC_FOUND_ROWS做分页是很糟糕的想法。
下面来看看到底如何优化。文章分为两部分,第一部分是如何获取记录的总数目,第二部分是获取真正的记录。

高效的计算行数

如果采用的引擎是MyISAM,可以直接执行COUNT(*)去获取行数即可。相似的,在堆表中也会将行数存储到表的元信息中。但如果引擎是InnoDB情况就会复杂一些,因为InnoDB不保存表的具体行数。
我们可以将行数缓存起来,然后可以通过一个守护进程定期更新或者用户的某些操作导致缓存失效时,执行下面的语句:

1
2
3
SELECT COUNT(*)
FROM city
USE INDEX(PRIMARY);

获取记录

下面进入这篇文章最重要的部分,获取分页要展示的记录。上面已经说过了,大的偏移量会影响性能,所以我们要重写查询语句。为了演示,我们创建一个新的表“news”,按照时事性排序(最新发布的在最前面),实现一个高性能的分页。为了简单,我们就假设最新发布的新闻的Id也是最大的。

1
2
3
4
CREATE TABLE news(
   id INT UNSIGNED PRIMARY KEY AUTO_INCREMENT,
   title VARCHAR(128) NOT NULL
) ENGINE=InnoDB;

一个比较高效的方式是基于用户展示的最后一个新闻Id。查询下一页的语句如下,需要传入当前页面展示的最后一个Id。

1
2
3
4
SELECT *
FROM news WHERE id < $last_id
ORDER BY id DESC
LIMIT $perpage

查询上一页的语句类似,只不过需要传入当前页的第一个Id,并且要逆序。

1
2
3
4
SELECT *
FROM news WHERE id > $last_id
ORDER BY id ASC
LIMIT $perpage

上面的查询方式适合实现简易的分页,即不显示具体的页数导航,只显示“上一页”和“下一页”,例如博客中页脚显示“上一页”,“下一页”的按钮。但如果要实现真正的页面导航还是很难的,下面看看另一种方式。

1
2
3
4
5
6
7
8
9
10
SELECT id
FROM (
   SELECT id, ((@cnt:= @cnt + 1) + $perpage - 1) % $perpage cnt
   FROM news 
   JOIN (SELECT @cnt:= 0)T
   WHERE id < $last_id
   ORDER BY id DESC
   LIMIT $perpage * $buttons
)C
WHERE cnt = 0;

通过上面的语句可以为每一个分页的按钮计算出一个offset对应的id。这种方法还有一个好处。假设,网站上正在发布一片新的文章,那么所有文章的位置都会往后移一位,所以如果用户在发布文章时换页,那么他会看见一篇文章两次。如果固定了每个按钮的offset Id,这个问题就迎刃而解了。Mark Callaghan发表过一篇类似的博客,利用了组合索引和两个位置变量,但是基本思想是一致的。
如果表中的记录很少被删除、修改,还可以将记录对应的页码存储到表中,并在该列上创建合适的索引。采用这种方式,当新增一个记录的时候,需要执行下面的查询重新生成对应的页号。

1
2
SET @p:= 0;
UPDATE news SET page=CEIL((@p:= @p + 1) / $perpage) ORDER BY id DESC;

当然,也可以新增一个专用于分页的表,可以用个后台程序来维护。

1
2
3
4
5
6
7
8
UPDATE pagination T
JOIN (
   SELECT id, CEIL((@p:= @p + 1) / $perpage) page
   FROM news
   ORDER BY id
)C
ON C.id = T.id
SET T.page = C.page;

现在想获取任意一页的元素就很简单了:

1
2
3
4
SELECT *
FROM news A
JOIN pagination B ON A.id=B.ID
WHERE page=$offset;

还有另外一种与上种方法比较相似的方法来做分页,这种方式比较试用于数据集相对小,并且没有可用的索引的情况下—比如处理搜索结果时。在一个普通的服务器上执行下面的查询,当有2M条记录时,要耗费2sec左右。这种方式比较简单,创建一个用来存储所有Id的临时表即可(这也是最耗费性能的地方)。

1
2
3
4
5
CREATE TEMPORARY TABLE _tmp (KEY SORT(random))
SELECT id, FLOOR(RAND() * 0x8000000) random
FROM city;

ALTER TABLE _tmp ADD OFFSET INT UNSIGNED PRIMARY KEY AUTO_INCREMENT, DROP INDEX SORT, ORDER BY random;

接下来就可以向下面一样执行分页查询了。

1
2
3
4
5
SELECT *
FROM _tmp
WHERE OFFSET >= $offset
ORDER BY OFFSET
LIMIT $perpage;

——————————————–俺只是个分割线———————————————————-
简单来说,对于分页的优化就是。。。避免数据量大时扫描过多的记录。
博客比较长,所以翻译的有些粗糙。。。,之后会在好好检查一遍的。在自己做测试时,有些查询时间与作者有点不一致,不过作者这篇博客是写于2011年的,so~不要在意具体数据,领会精神吧~~

MySQL索引原理及慢查询优化

原文出处: 美团技术博客

MySQL凭借着出色的性能、低廉的成本、丰富的资源,已经成为绝大多数互联网公司的首选关系型数据库。虽然性能出色,但所谓“好马配好鞍”,如何能够更好的使用它,已经成为开发工程师的必修课,我们经常会从职位描述上看到诸如“精通MySQL”、“SQL语句优化”、“了解数据库原理”等要求。我们知道一般的应用系统,读写比例在10:1左右,而且插入操作和一般的更新操作很少出现性能问题,遇到最多的,也是最容易出问题的,还是一些复杂的查询操作,所以查询语句的优化显然是重中之重。

本人从13年7月份起,一直在美团核心业务系统部做慢查询的优化工作,共计十余个系统,累计解决和积累了上百个慢查询案例。随着业务的复杂性提升,遇到的问题千奇百怪,五花八门,匪夷所思。本文旨在以开发工程师的角度来解释数据库索引的原理和如何优化慢查询。

一个慢查询引发的思考
select count(*) from task where status=2 and operator_id=20839 and operate_time>1371169729 and operate_time<1371174603 and type=2;
系统使用者反应有一个功能越来越慢,于是工程师找到了上面的SQL。
并且兴致冲冲的找到了我,“这个SQL需要优化,给我把每个字段都加上索引”
我很惊讶,问道“为什么需要每个字段都加上索引?”
“把查询的字段都加上索引会更快”工程师信心满满
“这种情况完全可以建一个联合索引,因为是最左前缀匹配,所以operate_time需要放到最后,而且还需要把其他相关的查询都拿来,需要做一个综合评估。”
“联合索引?最左前缀匹配?综合评估?”工程师不禁陷入了沉思。
多数情况下,我们知道索引能够提高查询效率,但应该如何建立索引?索引的顺序如何?许多人却只知道大概。其实理解这些概念并不难,而且索引的原理远没有想象的那么复杂。

MySQL索引原理
索引目的
索引的目的在于提高查询效率,可以类比字典,如果要查“mysql”这个单词,我们肯定需要定位到m字母,然后从下往下找到y字母,再找到剩下的sql。如果没有索引,那么你可能需要把所有单词看一遍才能找到你想要的,如果我想找到m开头的单词呢?或者ze开头的单词呢?是不是觉得如果没有索引,这个事情根本无法完成?

索引原理
除了词典,生活中随处可见索引的例子,如火车站的车次表、图书的目录等。它们的原理都是一样的,通过不断的缩小想要获得数据的范围来筛选出最终想要的结果,同时把随机的事件变成顺序的事件,也就是我们总是通过同一种查找方式来锁定数据。
数据库也是一样,但显然要复杂许多,因为不仅面临着等值查询,还有范围查询(>、<、between、in)、模糊查询(like)、并集查询(or)等等。数据库应该选择怎么样的方式来应对所有的问题呢?我们回想字典的例子,能不能把数据分成段,然后分段查询呢?最简单的如果1000条数据,1到100分成第一段,101到200分成第二段,201到300分成第三段……这样查第250条数据,只要找第三段就可以了,一下子去除了90%的无效数据。但如果是1千万的记录呢,分成几段比较好?稍有算法基础的同学会想到搜索树,其平均复杂度是lgN,具有不错的查询性能。但这里我们忽略了一个关键的问题,复杂度模型是基于每次相同的操作成本来考虑的,数据库实现比较复杂,数据保存在磁盘上,而为了提高性能,每次又可以把部分数据读入内存来计算,因为我们知道访问磁盘的成本大概是访问内存的十万倍左右,所以简单的搜索树难以满足复杂的应用场景。

磁盘IO与预读
前面提到了访问磁盘,那么这里先简单介绍一下磁盘IO和预读,磁盘读取数据靠的是机械运动,每次读取数据花费的时间可以分为寻道时间、旋转延迟、传输时间三个部分,寻道时间指的是磁臂移动到指定磁道所需要的时间,主流磁盘一般在5ms以下;旋转延迟就是我们经常听说的磁盘转速,比如一个磁盘7200转,表示每分钟能转7200次,也就是说1秒钟能转120次,旋转延迟就是1/120/2 = 4.17ms;传输时间指的是从磁盘读出或将数据写入磁盘的时间,一般在零点几毫秒,相对于前两个时间可以忽略不计。那么访问一次磁盘的时间,即一次磁盘IO的时间约等于5+4.17 = 9ms左右,听起来还挺不错的,但要知道一台500 -MIPS的机器每秒可以执行5亿条指令,因为指令依靠的是电的性质,换句话说执行一次IO的时间可以执行40万条指令,数据库动辄十万百万乃至千万级数据,每次9毫秒的时间,显然是个灾难。下图是计算机硬件延迟的对比图,供大家参考:

考虑到磁盘IO是非常高昂的操作,计算机操作系统做了一些优化,当一次IO时,不光把当前磁盘地址的数据,而是把相邻的数据也都读取到内存缓冲区内,因为局部预读性原理告诉我们,当计算机访问一个地址的数据的时候,与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)。具体一页有多大数据跟操作系统有关,一般为4k或8k,也就是我们读取一页内的数据时候,实际上才发生了一次IO,这个理论对于索引的数据结构设计非常有帮助。

索引的数据结构
前面讲了生活中索引的例子,索引的基本原理,数据库的复杂性,又讲了操作系统的相关知识,目的就是让大家了解,任何一种数据结构都不是凭空产生的,一定会有它的背景和使用场景,我们现在总结一下,我们需要这种数据结构能够做些什么,其实很简单,那就是:每次查找数据时把磁盘IO次数控制在一个很小的数量级,最好是常数数量级。那么我们就想到如果一个高度可控的多路搜索树是否能满足需求呢?就这样,b+树应运而生。

详解b+树

如上图,是一颗b+树,关于b+树的定义可以参见B+树,这里只说一些重点,浅蓝色的块我们称之为一个磁盘块,可以看到每个磁盘块包含几个数据项(深蓝色所示)和指针(黄色所示),如磁盘块1包含数据项17和35,包含指针P1、P2、P3,P1表示小于17的磁盘块,P2表示在17和35之间的磁盘块,P3表示大于35的磁盘块。真实的数据存在于叶子节点即3、5、9、10、13、15、28、29、36、60、75、79、90、99。非叶子节点只不存储真实的数据,只存储指引搜索方向的数据项,如17、35并不真实存在于数据表中。

b+树的查找过程
如图所示,如果要查找数据项29,那么首先会把磁盘块1由磁盘加载到内存,此时发生一次IO,在内存中用二分查找确定29在17和35之间,锁定磁盘块1的P2指针,内存时间因为非常短(相比磁盘的IO)可以忽略不计,通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存,发生第二次IO,29在26和30之间,锁定磁盘块3的P2指针,通过指针加载磁盘块8到内存,发生第三次IO,同时内存中做二分查找找到29,结束查询,总计三次IO。真实的情况是,3层的b+树可以表示上百万的数据,如果上百万的数据查找只需要三次IO,性能提高将是巨大的,如果没有索引,每个数据项都要发生一次IO,那么总共需要百万次的IO,显然成本非常非常高。

b+树性质
1.通过上面的分析,我们知道IO次数取决于b+数的高度h,假设当前数据表的数据为N,每个磁盘块的数据项的数量是m,则有h=㏒(m+1)N,当数据量N一定的情况下,m越大,h越小;而m = 磁盘块的大小 / 数据项的大小,磁盘块的大小也就是一个数据页的大小,是固定的,如果数据项占的空间越小,数据项的数量越多,树的高度越低。这就是为什么每个数据项,即索引字段要尽量的小,比如int占4字节,要比bigint8字节少一半。这也是为什么b+树要求把真实的数据放到叶子节点而不是内层节点,一旦放到内层节点,磁盘块的数据项会大幅度下降,导致树增高。当数据项等于1时将会退化成线性表。
2.当b+树的数据项是复合的数据结构,比如(name,age,sex)的时候,b+数是按照从左到右的顺序来建立搜索树的,比如当(张三,20,F)这样的数据来检索的时候,b+树会优先比较name来确定下一步的所搜方向,如果name相同再依次比较age和sex,最后得到检索的数据;但当(20,F)这样的没有name的数据来的时候,b+树就不知道下一步该查哪个节点,因为建立搜索树的时候name就是第一个比较因子,必须要先根据name来搜索才能知道下一步去哪里查询。比如当(张三,F)这样的数据来检索时,b+树可以用name来指定搜索方向,但下一个字段age的缺失,所以只能把名字等于张三的数据都找到,然后再匹配性别是F的数据了, 这个是非常重要的性质,即索引的最左匹配特性。

慢查询优化
关于MySQL索引原理是比较枯燥的东西,大家只需要有一个感性的认识,并不需要理解得非常透彻和深入。我们回头来看看一开始我们说的慢查询,了解完索引原理之后,大家是不是有什么想法呢?先总结一下索引的几大基本原则

建索引的几大原则
1.最左前缀匹配原则,非常重要的原则,mysql会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配,比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引,d是用不到索引的,如果建立(a,b,d,c)的索引则都可以用到,a,b,d的顺序可以任意调整。
2.=和in可以乱序,比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意顺序,mysql的查询优化器会帮你优化成索引可以识别的形式
3.尽量选择区分度高的列作为索引,区分度的公式是count(distinct col)/count(*),表示字段不重复的比例,比例越大我们扫描的记录数越少,唯一键的区分度是1,而一些状态、性别字段可能在大数据面前区分度就是0,那可能有人会问,这个比例有什么经验值吗?使用场景不同,这个值也很难确定,一般需要join的字段我们都要求是0.1以上,即平均1条扫描10条记录
4.索引列不能参与计算,保持列“干净”,比如from_unixtime(create_time) = ’2014-05-29’就不能使用到索引,原因很简单,b+树中存的都是数据表中的字段值,但进行检索时,需要把所有元素都应用函数才能比较,显然成本太大。所以语句应该写成create_time = unix_timestamp(’2014-05-29’);
5.尽量的扩展索引,不要新建索引。比如表中已经有a的索引,现在要加(a,b)的索引,那么只需要修改原来的索引即可

回到开始的慢查询
根据最左匹配原则,最开始的sql语句的索引应该是status、operator_id、type、operate_time的联合索引;其中status、operator_id、type的顺序可以颠倒,所以我才会说,把这个表的所有相关查询都找到,会综合分析;
比如还有如下查询

select * from task where status = 0 and type = 12 limit 10;
select count(*) from task where status = 0 ;
那么索引建立成(status,type,operator_id,operate_time)就是非常正确的,因为可以覆盖到所有情况。这个就是利用了索引的最左匹配的原则

查询优化神器 – explain命令
关于explain命令相信大家并不陌生,具体用法和字段含义可以参考官网explain-output,这里需要强调rows是核心指标,绝大部分rows小的语句执行一定很快(有例外,下面会讲到)。所以优化语句基本上都是在优化rows。

慢查询优化基本步骤
0.先运行看看是否真的很慢,注意设置SQL_NO_CACHE
1.where条件单表查,锁定最小返回记录表。这句话的意思是把查询语句的where都应用到表中返回的记录数最小的表开始查起,单表每个字段分别查询,看哪个字段的区分度最高
2.explain查看执行计划,是否与1预期一致(从锁定记录较少的表开始查询)
3.order by limit 形式的sql语句让排序的表优先查
4.了解业务方使用场景
5.加索引时参照建索引的几大原则
6.观察结果,不符合预期继续从0分析

几个慢查询案例
下面几个例子详细解释了如何分析和优化慢查询

复杂语句写法
很多情况下,我们写SQL只是为了实现功能,这只是第一步,不同的语句书写方式对于效率往往有本质的差别,这要求我们对mysql的执行计划和索引原则有非常清楚的认识,请看下面的语句

select
   distinctcert.emp_id
from
   cm_logcl
inner join
   (
      select
         emp.id as emp_id,
         emp_cert.id ascert_id
      from
         employeeemp
      left join
         emp_certificateemp_cert
            onemp.id=emp_cert.emp_id
      where
         emp.is_deleted=0
   )cert
      on (
         cl.ref_table=‘Employee’
         and cl.ref_oid= cert.emp_id
      )
      or (
         cl.ref_table=‘EmpCertificate’
         and cl.ref_oid= cert.cert_id
      )
where
   cl.last_upd_date >=‘2013-11-07 15:03:00’
   and cl.last_upd_date<=‘2013-11-08 16:00:00’;

0.先运行一下,53条记录 1.87秒,又没有用聚合语句,比较慢

53 rows in set (1.87 sec)
1.explain

+—-+————-+————+——-+———————————+———————–+———+——————-+——-+——————————–+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +—-+————-+————+——-+———————————+———————–+———+——————-+——-+——————————–+ | 1 | PRIMARY | cl | range | cm_log_cls_id,idx_last_upd_date | idx_last_upd_date | 8 | NULL | 379 | Using where; Using temporary | | 1 | PRIMARY | <derived2> | ALL | NULL | NULL | NULL | NULL | 63727 | Using where; Using join buffer | | 2 | DERIVED | emp | ALL | NULL | NULL | NULL | NULL | 13317 | Using where | | 2 | DERIVED | emp_cert | ref | emp_certificate_empid | emp_certificate_empid | 4 | meituanorg.emp.id | 1 | Using index | +—-+————-+————+——-+———————————+———————–+———+——————-+——-+——————————–+
简述一下执行计划,首先mysql根据idx_last_upd_date索引扫描cm_log表获得379条记录;然后查表扫描了63727条记录,分为两部分,derived表示构造表,也就是不存在的表,可以简单理解成是一个语句形成的结果集,后面的数字表示语句的ID。derived2表示的是ID = 2的查询构造了虚拟表,并且返回了63727条记录。我们再来看看ID = 2的语句究竟做了写什么返回了这么大量的数据,首先全表扫描employee表13317条记录,然后根据索引emp_certificate_empid关联emp_certificate表,rows = 1表示,每个关联都只锁定了一条记录,效率比较高。获得后,再和cm_log的379条记录根据规则关联。从执行过程上可以看出返回了太多的数据,返回的数据绝大部分cm_log都用不到,因为cm_log只锁定了379条记录。
如何优化呢?可以看到我们在运行完后还是要和cm_log做join,那么我们能不能之前和cm_log做join呢?仔细分析语句不难发现,其基本思想是如果cm_log的ref_table是EmpCertificate就关联emp_certificate表,如果ref_table是Employee就关联employee表,我们完全可以拆成两部分,并用union连接起来,注意这里用union,而不用union all是因为原语句有“distinct”来得到唯一的记录,而union恰好具备了这种功能。如果原语句中没有distinct不需要去重,我们就可以直接使用union all了,因为使用union需要去重的动作,会影响SQL性能。
优化过的语句如下

select
   emp.id
from
   cm_logcl
inner join
   employeeemp
      on cl.ref_table = ‘Employee’
      and cl.ref_oid = emp.id  
where
   cl.last_upd_date >=‘2013-11-07 15:03:00’
   and cl.last_upd_date<=‘2013-11-08 16:00:00’
   and emp.is_deleted = 0  
union
select
   emp.id
from
   cm_logcl
inner join
   emp_certificateec
      on cl.ref_table = ‘EmpCertificate’
      and cl.ref_oid = ec.id  
inner join
   employeeemp
      on emp.id = ec.emp_id  
where
   cl.last_upd_date >=‘2013-11-07 15:03:00’
   and cl.last_upd_date<=‘2013-11-08 16:00:00’
   and emp.is_deleted = 0

4.不需要了解业务场景,只需要改造的语句和改造之前的语句保持结果一致

5.现有索引可以满足,不需要建索引

6.用改造后的语句实验一下,只需要10ms 降低了近200倍!

+—-+————–+————+——–+———————————+——————-+———+———————–+——+————-+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +—-+————–+————+——–+———————————+——————-+———+———————–+——+————-+ | 1 | PRIMARY | cl | range | cm_log_cls_id,idx_last_upd_date | idx_last_upd_date | 8 | NULL | 379 | Using where | | 1 | PRIMARY | emp | eq_ref | PRIMARY | PRIMARY | 4 | meituanorg.cl.ref_oid | 1 | Using where | | 2 | UNION | cl | range | cm_log_cls_id,idx_last_upd_date | idx_last_upd_date | 8 | NULL | 379 | Using where | | 2 | UNION | ec | eq_ref | PRIMARY,emp_certificate_empid | PRIMARY | 4 | meituanorg.cl.ref_oid | 1 | | | 2 | UNION | emp | eq_ref | PRIMARY | PRIMARY | 4 | meituanorg.ec.emp_id | 1 | Using where | | NULL | UNION RESULT | <union1,2> | ALL | NULL | NULL | NULL | NULL | NULL | | +—-+————–+————+——–+———————————+——————-+———+———————–+——+————-+ 53 rows in set (0.01 sec)
明确应用场景
举这个例子的目的在于颠覆我们对列的区分度的认知,一般上我们认为区分度越高的列,越容易锁定更少的记录,但在一些特殊的情况下,这种理论是有局限性的

select * from stage_poi sp where sp.accurate_result=1 and ( sp.sync_status=0 or sp.sync_status=2 or sp.sync_status=4 );
0.先看看运行多长时间,951条数据6.22秒,真的很慢

951 rows in set (6.22 sec)
1.先explain,rows达到了361万,type = ALL表明是全表扫描

+—-+————-+——-+——+—————+——+———+——+———+————-+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +—-+————-+——-+——+—————+——+———+——+———+————-+ | 1 | SIMPLE | sp | ALL | NULL | NULL | NULL | NULL | 3613155 | Using where | +—-+————-+——-+——+—————+——+———+——+———+————-+
2.所有字段都应用查询返回记录数,因为是单表查询 0已经做过了951条

3.让explain的rows 尽量逼近951

看一下accurate_result = 1的记录数

select count(*),accurate_result from stage_poi group by accurate_result; +———-+—————–+ | count(*) | accurate_result | +———-+—————–+ | 1023 | -1 | | 2114655 | 0 | | 972815 | 1 | +———-+—————–+
我们看到accurate_result这个字段的区分度非常低,整个表只有-1,0,1三个值,加上索引也无法锁定特别少量的数据

再看一下sync_status字段的情况

select count(*),sync_status from stage_poi group by sync_status; +———-+————-+ | count(*) | sync_status | +———-+————-+ | 3080 | 0 | | 3085413 | 3 | +———-+————-+
同样的区分度也很低,根据理论,也不适合建立索引

问题分析到这,好像得出了这个表无法优化的结论,两个列的区分度都很低,即便加上索引也只能适应这种情况,很难做普遍性的优化,比如当sync_status 0、3分布的很平均,那么锁定记录也是百万级别的

4.找业务方去沟通,看看使用场景。业务方是这么来使用这个SQL语句的,每隔五分钟会扫描符合条件的数据,处理完成后把sync_status这个字段变成1,五分钟符合条件的记录数并不会太多,1000个左右。了解了业务方的使用场景后,优化这个SQL就变得简单了,因为业务方保证了数据的不平衡,如果加上索引可以过滤掉绝大部分不需要的数据

5.根据建立索引规则,使用如下语句建立索引

alter table stage_poi add index idx_acc_status(accurate_result,sync_status);
6.观察预期结果,发现只需要200ms,快了30多倍。

952 rows in set (0.20 sec)
我们再来回顾一下分析问题的过程,单表查询相对来说比较好优化,大部分时候只需要把where条件里面的字段依照规则加上索引就好,如果只是这种“无脑”优化的话,显然一些区分度非常低的列,不应该加索引的列也会被加上索引,这样会对插入、更新性能造成严重的影响,同时也有可能影响其它的查询语句。所以我们第4步调差SQL的使用场景非常关键,我们只有知道这个业务场景,才能更好地辅助我们更好的分析和优化查询语句。

无法优化的语句
select c.id, c.name, c.position, c.sex, c.phone, c.office_phone, c.feature_info, c.birthday, c.creator_id, c.is_keyperson, c.giveup_reason, c.status, c.data_source, from_unixtime(c.created_time) as created_time, from_unixtime(c.last_modified) as last_modified, c.last_modified_user_id from contact c inner join contact_branch cb on c.id = cb.contact_id inner join branch_user bu on cb.branch_id = bu.branch_id and bu.status in ( 1, 2) inner join org_emp_info oei on oei.data_id = bu.user_id and oei.node_left >= 2875 and oei.node_right <= 10802 and oei.org_category = – 1 order by c.created_time desc limit 0 , 10;
还是几个步骤
0.先看语句运行多长时间,10条记录用了13秒,已经不可忍受

10 rows in set (13.06 sec)
1.explain

+—-+————-+——-+——–+————————————-+————————-+———+————————–+——+———————————————-+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +—-+————-+——-+——–+————————————-+————————-+———+————————–+——+———————————————-+ | 1 | SIMPLE | oei | ref | idx_category_left_right,idx_data_id | idx_category_left_right | 5 | const | 8849 | Using where; Using temporary; Using filesort | | 1 | SIMPLE | bu | ref | PRIMARY,idx_userid_status | idx_userid_status | 4 | meituancrm.oei.data_id | 76 | Using where; Using index | | 1 | SIMPLE | cb | ref | idx_branch_id,idx_contact_branch_id | idx_branch_id | 4 | meituancrm.bu.branch_id | 1 | | | 1 | SIMPLE | c | eq_ref | PRIMARY | PRIMARY | 108 | meituancrm.cb.contact_id | 1 | | +—-+————-+——-+——–+————————————-+————————-+———+————————–+——+———————————————-+
从执行计划上看,mysql先查org_emp_info表扫描8849记录,再用索引idx_userid_status关联branch_user表,再用索引idx_branch_id关联contact_branch表,最后主键关联contact表。
rows返回的都非常少,看不到有什么异常情况。我们在看一下语句,发现后面有order by + limit组合,会不会是排序量太大搞的?于是我们简化SQL,去掉后面的order by 和 limit,看看到底用了多少记录来排序

select count(*) from contact c inner join contact_branch cb on c.id = cb.contact_id inner join branch_user bu on cb.branch_id = bu.branch_id and bu.status in ( 1, 2) inner join org_emp_info oei on oei.data_id = bu.user_id and oei.node_left >= 2875 and oei.node_right <= 10802 and oei.org_category = – 1 +———-+ | count(*) | +———-+ | 778878 | +———-+ 1 row in set (5.19 sec)
发现排序之前居然锁定了778878条记录,如果针对70万的结果集排序,将是灾难性的,怪不得这么慢,那我们能不能换个思路,先根据contact的created_time排序,再来join会不会比较快呢?
于是改造成下面的语句,也可以用straight_join来优化
select
c.id,
c.name,
c.position,
c.sex,
c.phone,
c.office_phone,
c.feature_info,
c.birthday,
c.creator_id,
c.is_keyperson,
c.giveup_reason,
c.status,
c.data_source,
from_unixtime(c.created_time) as created_time,
from_unixtime(c.last_modified) as last_modified,
c.last_modified_user_id
from
contact c
where
exists (
select
1
from
contact_branch cb
inner join
branch_user bu
on cb.branch_id = bu.branch_id
and bu.status in (
1,
2)
inner join
org_emp_info oei
on oei.data_id = bu.user_id
and oei.node_left >= 2875
and oei.node_right <= 10802
and oei.org_category = – 1
where
c.id = cb.contact_id
)
order by
c.created_time desc limit 0 ,
10;

验证一下效果 预计在1ms内,提升了13000多倍! “`sql 10 rows in set (0.00 sec)
本以为至此大工告成,但我们在前面的分析中漏了一个细节,先排序再join和先join再排序理论上开销是一样的,为何提升这么多是因为有一个limit!大致执行过程是:mysql先按索引排序得到前10条记录,然后再去join过滤,当发现不够10条的时候,再次去10条,再次join,这显然在内层join过滤的数据非常多的时候,将是灾难的,极端情况,内层一条数据都找不到,mysql还傻乎乎的每次取10条,几乎遍历了这个数据表!
用不同参数的SQL试验下

select sql_no_cache c.id, c.name, c.position, c.sex, c.phone, c.office_phone, c.feature_info, c.birthday, c.creator_id, c.is_keyperson, c.giveup_reason, c.status, c.data_source, from_unixtime(c.created_time) as created_time, from_unixtime(c.last_modified) as last_modified, c.last_modified_user_id from contact c where exists ( select 1 from contact_branch cb inner join branch_user bu on cb.branch_id = bu.branch_id and bu.status in ( 1, 2) inner join org_emp_info oei on oei.data_id = bu.user_id and oei.node_left >= 2875 and oei.node_right <= 2875 and oei.org_category = – 1 where c.id = cb.contact_id ) order by c.created_time desc limit 0 , 10; Empty set (2 min 18.99 sec)
2 min 18.99 sec!比之前的情况还糟糕很多。由于mysql的nested loop机制,遇到这种情况,基本是无法优化的。这条语句最终也只能交给应用系统去优化自己的逻辑了。
通过这个例子我们可以看到,并不是所有语句都能优化,而往往我们优化时,由于SQL用例回归时落掉一些极端情况,会造成比原来还严重的后果。所以,第一:不要指望所有语句都能通过SQL优化,第二:不要过于自信,只针对具体case来优化,而忽略了更复杂的情况。

慢查询的案例就分析到这儿,以上只是一些比较典型的案例。我们在优化过程中遇到过超过1000行,涉及到16个表join的“垃圾SQL”,也遇到过线上线下数据库差异导致应用直接被慢查询拖死,也遇到过varchar等值比较没有写单引号,还遇到过笛卡尔积查询直接把从库搞死。再多的案例其实也只是一些经验的积累,如果我们熟悉查询优化器、索引的内部原理,那么分析这些案例就变得特别简单了。
写在后面的话
本文以一个慢查询案例引入了MySQL索引原理、优化慢查询的一些方法论;并针对遇到的典型案例做了详细的分析。其实做了这么长时间的语句优化后才发现,任何数据库层面的优化都抵不上应用系统的优化,同样是MySQL,可以用来支撑Google/FaceBook/Taobao应用,但可能连你的个人网站都撑不住。套用最近比较流行的话:“查询容易,优化不易,且写且珍惜!”

参考
参考文献如下:

1.《高性能MySQL》
2.《数据结构与算法分析》

(转)如何选择MySQL存储引擎

一、MySQL的存储引擎

完整的引擎说明还是看官方文档:http://dev.mysql.com/doc/refman/5.6/en/storage-engines.html

这里介绍一些主要的引擎

 

1、InnoDB存储引擎

InnoDB是MySQL的默认事务型引擎,它被设计用来处理大量的短期(short-lived)事务。除非有非常特别的原因需要使用其他的存储引擎,否则应该优先考虑InnoDB引擎。

建议使用MySQL5.5及以后的版本,因为这个版本及以后的版本的InnoDB引擎性能更好。

MySQL4.1以后的版本中,InnoDB可以将每个表的数据和索引存放在单独的文件中。这样在复制备份崩溃恢复等操作中有明显优势。可以通过在my.cnf中增加innodb_file_per_table来开启这个功能。如下:

 

InnoDB采用MVCC来支持高并发,并且实现了四个标准的隔离级别。其默认级别是REPEATABLE READ(可重复读),并且通过间隙锁(next-key locking)策略防止幻读的出现。(事务和事务隔离级别是另一个大题目,各自网补吧)。

 

InnoDB是基于聚簇索引建立的,聚簇索引对主键查询有很高的性能。不过它的二级索引(secondary index,非主键索引)中必须包含主键列,所以如果主键列很大的话,其他的所有索引都会很大。因此表上的索引较多的话,主键应当尽可能的小。

 

InnoDB的存储格式是平台独立的,可以将数据和索引文件从Intel平台复制到Sun SPARC平台或其他平台。

 

InnoDB通过一些机制和工具支持真正的热备份,MySQL的其他存储引擎不支持热备份。

 

2、MyISAM存储引擎

MyISAM提供了大量的特性,包括全文索引、压缩、空间函数(GIS)等,但MyISAM不支持事务和行级锁,有一个毫无疑问的缺陷就是崩溃后无法安全恢复。

 

MyISAM会将表存储在两个文件在中:数据文件和索引文件,分别是.MYD和.MYI为扩展名。

在MySQL5.0以前,只能处理4G的数据,5.0中可以处理256T的数据。

 

在数据不再进行修改操作时,可以对MyISAM表进行压缩,压缩后可以提高读能力,原因是减少了磁盘I/O。

 

3、Archive引擎

Archive存储引擎只支持INSERT和SELECT操作,在MySQL5.1之前不支持索引。

Archive表适合日志和数据采集类应用。

Archive引擎支持行级锁和专用的缓存区,所以可以实现高并发的插入,但它不是一个事物型的引擎,而是一个针对高速插入和压缩做了优化的简单引擎。

 

4、Blackhole引擎

Blackhole引擎没有实现任何存储机制,它会丢弃所有插入的数据,不做任何保存。但服务器会记录Blackhole表的日志,所以可以用于复制数据到备库,或者简单地记录到日志。但这种应用方式会碰到很多问题,因此并不推荐。

 

5、CSV引擎

CSV引擎可以将普通的SCV文件作为MySQL的表来处理,但不支持索引。

CSV引擎可以作为一种数据交换的机制,非常有用。

 

6、Federated引擎

Federated引擎是访问其他MySQL服务器的一个代理,尽管该引擎看起来提供了一种很好的跨服务器的灵活性,但也经常带来问题,因此默认是禁用的。

 

7、Memory引擎

如果需要快速地访问数据,并且这些数据不会被修改,重启以后丢失也没有关系,那么使用Memory表是非常有用。Memory表至少比MyISAM表要快一个数量级。

Memory表是表级锁,因此并发写入的性能较低。它不支持BLOB或TEXT类型的列,并且每行的长度是固定的,这可能呆滞部分内存的浪费。

临时表和Memory表不是一回事。临时表是指使用CREATE TEMPORARY TABLE语句创建的表,它可以使用任何存储引擎,只在单个连接中可见,当连接断开时,临时表也将不复存在。

 

8、NDB集群引擎

MySQL服务器、NDB集群存储引擎,以及分布式的、share-nothing的、容灾的、高可用的NDB数据库的组合,被称为MySQL集群(MySQL Cluster)。

 

其他第三方或社区引擎

XtraDB:是InnoDB的一个改进版本,可以作为InnoDB的一个完美的替代产品。

TokuDB:使用了一种新的叫做分形树(Fractal Trees)的索引数据结构。

Infobright:是最有名的面向列的存储引擎。

Groonga:是一款全文索引引擎。

OQGraph:该引擎由Open Query研发,支持图操作(比如查找两点之间的最短路径)。

Q4M:该引擎在MySQL内部实现了队列操作。

SphinxSE:该引擎为Sphinx全文索引搜索服务器提供了SQL接口。

 

二、选择合适的引擎

大部分情况下,InnoDB都是正确的选择,可以简单地归纳为一句话“除非需要用到某些InnoDB不具备的特性,并且没有其他办法可以替代,否则都应该优先选择InnoDB引擎”。

除非万不得已,否则建议不要混合使用多种存储引擎,否则可能带来一系列负责的问题,以及一些潜在的bug和边界问题。

如果应用需要不同的存储引擎,请先考虑以下几个因素:

事务:

如果应用需要事务支持,那么InnoDB(或者XtraDB)是目前最稳定并且经过验证的选择。

备份:

如果可以定期地关闭服务器来执行备份,那么备份的因素可以忽略。反之,如果需要在线热备份,那么选择InnoDB就是基本的要求。

崩溃恢复

MyISAM崩溃后发生损坏的概率比InnoDB要高很多,而且恢复速度也要慢。

特有的特性

如果一个存储引擎拥有一些关键的特性,同时却又缺乏一些必要的特性,那么有时候不得不做折中的考虑,或者在架构设计上做一些取舍。

 

有些查询SQL在不同的引擎上表现不同。比较典型的是:

SELECT COUNT(*) FROM table;

对于MyISAM确实会很快,但其他的可能都不行。

 

三、应用举例

 

1、日志型应用

MyISAM或者Archive存储引擎对这类应用比较合适,因为他们开销低,而且插入速度非常快。

如果需要对记录的日志做分析报表,生成报表的SQL很可能会导致插入效率明显降低,这时候该怎么办?

一种解决方法,是利用MySQL内置的复制方案将数据复制一份到备库,然后在备库上执行比较消耗时间和CPU的查询。当然也可以在系统负载较低的时候执行报表查询操作,但应用在不断变化,如果依赖这个策略可能以后会导致问题。

另一种方法,在日志记录表的名字中包含年和月的信息,这样可以在已经没有插入操作的历史表上做频繁的查询操作,而不会干扰到最新的当前表上的插入操作。

 

2、只读或者大部分情况下只读的表

有些表的数据用于编制类目或者分列清单(如工作岗位),这种应用场景是典型的读多写少的业务。如果不介意MyISAM的崩溃恢复问题,选用MyISAM引擎是合适的。(MyISAM只将数据写到内存中,然后等待操作系统定期将数据刷出到磁盘上)

 

3、订单处理

涉及订单处理,支持事务是必要的,InnoDB是订单处理类应用的最佳选择。

 

4、大数据量

如果数据增长到10TB以上的级别,可能需要建立数据仓库。Infobright是MySQL数据仓库最成功的方案。也有一些大数据库不适合Infobright,却可能适合TokuDB。