数据结构和算法基础

索引的本质：数据结构，帮助高效获取数据

数据库的查询：最基本的查询算法当然是顺序查找（linear search）、二分查找（binary search）、二叉树查找（binary tree search）每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。

但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树（red-black 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 。（此时 1<=n<=2d）
所有叶节点具有相同的深度，等于树高h。
key和指针互相间隔，节点两端是指针。
一个节点中的key从左到右非递减排列。
所有节点组成树结构。
每个指针要么为null，要么指向另外一个节点。
如果某个指针在节点node最左边且不为null，则其指向节点的所有key小于v(key1)，其中v(key1)node的第一个key的值。
如果某个指针在节点node最右边且不为null，则其指向节点的所有key大于v(keym)，其中v(keym)为node的最后一个key的值。
如果某个指针在节点node的左右相邻key分别是keyi和keyi 1且不为null，则其指向节点的所有key小于v(keyi 1)且大于v(keyi)。

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

关于B-Tree有一系列有趣的性质，例如一个度为d的B-Tree，设其索引N个key，则其树高h的上限为logd((N 1)/2)，检索一个key，其查找节点个数的渐进复杂度为O(logdN)。从这点可以看出，B-Tree是一个非常有效率的索引数据结构。

B-tree的插入删除操作：插入一个元素时，首先在B树中是否存在，如果不存在，即在叶子结点处结束，然后在叶子结点中插入该新的元素，注意：如果叶子结点空间足够，这里需要向右移动该叶子结点中大于新插入关键字的元素，如果空间满了以致没有足够的空间去添加新的元素，则将该结点进行“分裂”，将一半数量的关键字元素分裂到新的其相邻右结点中，中间关键字元素上移到父结点中（当然，如果父结点空间满了，也同样需要“分裂”操作），而且当结点中关键元素向右移动了，相关的指针也需要向右移。如果在根结点插入新元素，空间满了，则进行分裂操作，这样原来的根结点中的中间关键字元素向上移动到新的根结点中，因此导致树的高度增加一层。

B-tree的插入删除操作：

删除(delete)操作

（1）删除操作的两个步骤
   　第一步骤：在树中查找被删关键字K所在的地点
    　第二步骤：进行删去K的操作
（2）删去K的操作
    　B-树是二叉排序树的推广，中序遍历B-树同样可得到关键字的有序序列（具体遍历算法【参见练习】）。任一关键字K的中序前趋(后继)必是K的左子树(右子树)中最右(左)下的结点中最后(最前)一个关键字。

　若被删关键字K所在的结点非树叶，则用K的中序前趋(或后继)K‘取代K，然后从叶子中删去K‘。从叶子*x开始删去某关键字K的三种情形为：

　情形一：若x->keynum>Min，则只需删去K及其右指针(*x是叶子，K的右指针为空)即可使删除操作结束。

注意： Min=【M/2】-1

　情形二：若x->keynum=Min，该叶子中的关键字个数已是最小值，删K及其右指针后会破坏B-树的性质(3)。若*x的左(或右)邻兄弟结点*y中的关键字数目大于Min，则将*y中的最大(或最小)关键字上移至双亲结点*parent中，而将*parent中相应的关键字下移至x中。显然这种移动使得双亲中关键字数目不变；*y被移出一个关键字，故其keynum减1，因它原大于Min，故减少1个关键字后keynum仍大于等于Min；而*x中已移入一个关键字，故删K后*x中仍有Min个关键字。涉及移动关键字的三个结点均满足B-树的性质(3)。请读者验证，上述操作后仍满足B-树的性质(1)。移动完成后，删除过程亦结束。

　情形三：若*x及其相邻的左右兄弟(也可能只有一个兄弟)中的关键字数目均为最小值Min，则上述的移动操作就不奏效，此时须*x和左或右兄弟合并。不妨设*x有右邻兄弟*y(对左邻兄弟的讨论与此类似)，在*x中删去K后，将双亲结点*parent中介于*x和*y之间的关键字K，作为中间关键字，与并x和*y中的关键字一起"合并"为一个新的结点取代*x和*y。因为*x和*y原各有Min个关键字，从双亲中移人的K‘抵消了从*x中删除的K，故新结点中恰有2Min(即2「m/2」-2≤m-1)个关键字，没有破坏B-树的性质(3)。但由于K‘从双亲中移到新结点后，相当于从*parent中删去了K‘，若parent->keynum原大于Min，则删除操作到此结束；否则，同样要通过移动*parent的左右兄弟中的关键字或将*parent与其左右兄弟合并的方法来维护B-树性质。最坏情况下，合并操作会向上传播至根，当根中只有一个关键字时，合并操作将会使根结点及其两个孩子合并成一个新的根，从而使整棵树的高度减少一层。

B Tree

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

与B-Tree相比，B Tree有以下不同点：

每个节点的指针上限为2d而不是2d 1。
内节点不存储data，只存储key；叶子节点不存储指针。

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

一般来说，B Tree比B-Tree更适合实现外存储索引结构，具体原因与外存储器原理及计算机存取原理有关.

带有顺序访问指针的B Tree

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

做这个优化的目的是为了提高区间访问的性能，例如如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。

为什么使用B-Tree（B Tree）

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

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

(最简化的，因为目前对主存的编制规则较为复杂)主存的存取过程如下：

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

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

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

磁盘存取原理

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

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

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

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

局部性原理与磁盘预读

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘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)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。

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

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

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

$$ d_{max}=floor(pagesize/(keysize datasize pointsize))$$

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

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

MySQL索引实现

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

MyISAM索引实现

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

（转引）数据库索引（MySQL）

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

（转引）数据库索引（MySQL）

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

MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。因为在MyISAM中索引不存放具体的数据，只是存放数据的地址，数据与索引是分开存放的

InnoDB索引实现

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

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

（转引）数据库索引（MySQL）

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

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

（转引）数据库索引（MySQL）

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

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

最左前缀原理与相关优化

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

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

SHOW INDEX FROM employees.titles;
 -------- ------------ ---------- -------------- ------------- ----------- ------------- ------ ------------ 
| Table  | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Null | Index_type |
 -------- ------------ ---------- -------------- ------------- ----------- ------------- ------ ------------ 
| titles |          0 | PRIMARY  |            1 | emp_no      | A         |        NULL |      | BTREE      |
| titles |          0 | PRIMARY  |            2 | title       | A         |        NULL |      | BTREE      |
| titles |          0 | PRIMARY  |            3 | from_date   | A         |      443308 |      | BTREE      |
| titles |          1 | emp_no   |            1 | emp_no      | A         |      443308 |      | BTREE      |
 -------- ------------ ---------- -------------- ------------- ----------- ------------- ------ ------------

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

ALTER TABLE employees.titles DROP INDEX emp_no;

情况一：全列匹配。

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

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

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

效果是一样的。

情况二：最左前缀匹配。

EXPLAIN SELECT * FROM employees.titles WHERE emp_no=‘10001‘;
 ---- ------------- -------- ------ --------------- --------- --------- ------- ------ ------- 
| id | select_type | table  | type | possible_keys | key     | key_len | ref   | rows | Extra |
 ---- ------------- -------- ------ --------------- --------- --------- ------- ------ ------- 
|  1 | SIMPLE      | titles | ref  | PRIMARY       | PRIMARY | 4       | const |    1 |       |
 ---- ------------- -------- ------ --------------- --------- --------- ------- ------ -------

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

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

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

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

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

SELECT DISTINCT(title) FROM employees.titles;
 -------------------- 
| title              |
 -------------------- 
| Senior Engineer    |
| Staff              |
| Engineer           |
| Senior Staff       |
| Assistant Engineer |
| Technique Leader   |
| Manager            |
 --------------------

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

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

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

SHOW PROFILES;
 ---------- ------------ ------------------------------------------------------------------------------- 
| Query_ID | Duration   | Query                                                                         |
 ---------- ------------ ------------------------------------------------------------------------------- 
|       10 | 0.00058000 | SELECT * FROM employees.titles WHERE emp_no=‘10001‘ AND from_date=‘1986-06-26‘|
|       11 | 0.00052500 | SELECT * FROM employees.titles WHERE emp_no=‘10001‘ AND title IN ...          |
 ---------- ------------ -------------------------------------------------------------------------------

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

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

EXPLAIN SELECT * FROM employees.titles WHERE from_date=‘1986-06-26‘;
 ---- ------------- -------- ------ --------------- ------ --------- ------ -------- ------------- 
| id | select_type | table  | type | possible_keys | key  | key_len | ref  | rows   | Extra       |
 ---- ------------- -------- ------ --------------- ------ --------- ------ -------- ------------- 
|  1 | SIMPLE      | titles | ALL  | NULL          | NULL | NULL    | NULL | 443308 | Using where |
 ---- ------------- -------- ------ --------------- ------ --------- ------ -------- -------------

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

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

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

此时可以用到索引，如果通配符%不出现在开头，则可以用到索引，但根据具体情况不同可能只会用其中一个前缀。

情况六：范围查询。

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

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

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

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

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

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

EXPLAIN SELECT * FROM employees.titles WHERE emp_no - 1=‘10000‘;
 ---- ------------- -------- ------ --------------- ------ --------- ------ -------- ------------- 
| id | select_type | table  | type | possible_keys | key  | key_len | ref  | rows   | Extra       |
 ---- ------------- -------- ------ --------------- ------ --------- ------ -------- ------------- 
|  1 | SIMPLE      | titles | ALL  | NULL          | NULL | NULL    | NULL | 443308 | Using where |
 ---- ------------- -------- ------ --------------- ------ --------- ------ -------- -------------

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

索引选择性与前缀索引

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

第一种情况是表记录比较少，例如一两千条甚至只有几百条记录的表，没必要建索引，让查询做全表扫描就好了。至于多少条记录才算多，这个个人有个人的看法，我个人的经验是以2000作为分界线，记录数不超过 2000可以考虑不建索引，超过2000条可以酌情考虑索引。
另一种不建议建索引的情况是索引的选择性较低。所谓索引的选择性（Selectivity），是指不重复的索引值（也叫基数，Cardinality）与表记录数（#T）的比值：Index Selectivity = Cardinality / #T。显然选择性的取值范围为(0, 1]，选择性越高的索引价值越大，这是由B Tree的性质决定的。例如，上文用到的employees.titles表，如果title字段经常被单独查询，是否需要建索引，我们看一下它的选择性：

SELECT count(DISTINCT(title))/count(*) AS Selectivity FROM employees.titles;
 ------------- 
| Selectivity |
 ------------- 
|      0.0000 |
 -------------

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

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

由于employees表只有一个索引<emp_no>，那么如果我们想按名字搜索一个人，就只能全表扫描了：

EXPLAIN SELECT * FROM employees.employees WHERE first_name=‘Eric‘ AND last_name=‘Anido‘;
 ---- ------------- ----------- ------ --------------- ------ --------- ------ -------- ------------- 
| id | select_type | table     | type | possible_keys | key  | key_len | ref  | rows   | Extra       |
 ---- ------------- ----------- ------ --------------- ------ --------- ------ -------- ------------- 
|  1 | SIMPLE      | employees | ALL  | NULL          | NULL | NULL    | NULL | 300024 | Using where |
 ---- ------------- ----------- ------ --------------- ------ --------- ------ -------- -------------

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

SELECT count(DISTINCT(first_name))/count(*) AS Selectivity FROM employees.employees;
 ------------- 
| Selectivity |
 ------------- 
|      0.0042 |
 ------------- 
SELECT count(DISTINCT(concat(first_name, last_name)))/count(*) AS Selectivity FROM employees.employees;
 ------------- 
| Selectivity |
 ------------- 
|      0.9313 |
 -------------

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

SELECT count(DISTINCT(concat(first_name, left(last_name, 3))))/count(*) AS Selectivity FROM employees.employees;
 ------------- 
| Selectivity |
 ------------- 
|      0.7879 |
 -------------

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

SELECT count(DISTINCT(concat(first_name, left(last_name, 4))))/count(*) AS Selectivity FROM employees.employees;
 ------------- 
| Selectivity |
 ------------- 
|      0.9007 |
 -------------

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

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

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

SHOW PROFILES;
 ---------- ------------ --------------------------------------------------------------------------------- 
| Query_ID | Duration   | Query                                                                           |
 ---------- ------------ --------------------------------------------------------------------------------- 
|       87 | 0.11941700 | SELECT * FROM employees.employees WHERE first_name=‘Eric‘ AND last_name=‘Anido‘ |
|       90 | 0.00092400 | SELECT * FROM employees.employees WHERE first_name=‘Eric‘ AND last_name=‘Anido‘ |
 ---------- ------------ ---------------------------------------------------------------------------------

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

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

InnoDB的主键选择与插入优化

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

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

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

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

（转引）数据库索引（MySQL）

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

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

（转引）数据库索引（MySQL）

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

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

Hash索引

在 MySQL 中，只有 Memory 引擎显式支持哈希索引。这也是 Memory 引擎表的默认索引，Memory 引擎也支持 B-Tree 索引。值的一提的是，Memory 引擎是支持非唯一哈希索引的，这在数据库世界里面是比较与众不同的。如果多个列的哈希值相同，索引会以链表的方式存放多个记录指针到同一个哈希条目中。

哈希索引（hash index）基于哈希表实现，只有精确匹配索引所有列的查询才有效。对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码（hash code）,哈希码是一个较小的值，并且不同键值的行计算出来的哈希码也不一样。哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。

因为索引自身只需存储对应的哈希值，所以索引的结构十分紧凑，这也让哈希索引查找的速度非常快。然而，哈希索引也有他的限制：

哈希索引只包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行，不过，访问内存中的行的速度很快，所以大部分情况下这一点对性能的影响并不明显。
哈希索引数据并不是按照索引值顺序存储的，所以也就无法用于排序
哈希索引也不支持部分索引列匹配查找，因为哈希索引始终是使用索引列的全部内容来计算哈希值的。
哈希索引只支持等值比较查询，包括=、IN()、<=>、也不支持任何范围查询。
访问哈希索引的数据非常快，除非有很多哈希冲突（不同的索引列值却有相同的哈希值）。当出现哈希冲突的时候，存储引擎必须遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的行。
如果哈希冲突很多的话，一些索引维护操作的代价也会很高。例如，如果在某个选择性很低（哈希冲突很多）的列上建立哈希索引，那么当从表中删除一行时，存储引擎需要遍历对应哈希值的链表中的每一行，找到并删除对应的引用，冲突越多，代价越大。

因为这些限制，哈希索引只适用于某些特定的场合。而一旦适合哈希索引，则它带来的性能提升将非常显著。举个例子，在数据仓库应用中有一种经典的“星型” schema，需要关联很多查找表，哈希索引就非常适合查找表的需求。

除了Memory引擎外，NDB集群引擎也支持唯一哈希索引，且在NDB集群引擎中作用非常特殊。InnoDB 引擎有一个特殊额功能叫做“自适应哈希索引”，当 InnoDB注意到某些索引值被使用得非常频繁时，它会在内存中基于B-Tree索引之上再创建一个哈希索引，这样就让B-Tree索引页具有哈希索引的一些优点，比如快速的哈希查找。这是一个完全自动的、内部的行为，用户无法控制或者配置，不过若果有必要，完全可以关闭该功能。

如果存储引擎不支持哈希索引，则可以模拟像InnoDB一样创建哈希索引，这可以享受一些哈希索引的便利，例如只需要很小的索引就可以为超长的键创建索引。
思路：在B-Tree基础上创建一个伪哈希索引。这和真正的哈希索引不是一回事，因为还是使用B-Tree进行查找，但是它使用哈希值而不是键本身进行索引查找。你需要做的就是在查询的WHERE子句中手动指定使用哈希函数。
由于是一次定位数据，不像BTree索引需要从根节点到枝节点，最后才能访问到页节点这样多次IO访问，所以检索效率远高于BTree索引。

索引优化 ORDER BY 排序语句

MySQL索引通常是被用于提高WHERE条件的数据行匹配或者执行联结操作时匹配其它表的数据行的搜索速度。
MySQL也能利用索引来快速地执行ORDER BY和GROUP BY语句的排序和分组操作。

通过索引优化来实现MySQL的ORDER BY语句优化：

1、ORDER BY的索引优化。如果一个SQL语句形如：
SELECT [column1],[column2],…. FROM [TABLE] ORDER BY [sort];
在[sort]这个栏位上建立索引就可以实现利用索引进行order by 优化。
2、WHERE ORDER BY的索引优化，形如：
SELECT [column1],[column2],…. FROM [TABLE] WHERE [columnX] = [value] ORDER BY [sort];
建立一个联合索引(columnX,sort)来实现order by 优化。
注意：如果columnX对应多个值，如下面语句就无法利用索引来实现order by的优化
SELECT [column1],[column2],…. FROM [TABLE] WHERE [columnX] IN ([value1],[value2],…) ORDER BY[sort];
3、WHERE 多个字段ORDER BY
SELECT * FROM [table] WHERE uid=1 ORDER x,y LIMIT 0,10;
建立索引(uid,x,y)实现order by的优化,比建立(x,y,uid)索引效果要好得多。

MySQL Order By不能使用索引来优化排序的情况

* 对不同的索引键做 ORDER BY ：(key1,key2分别建立索引)
SELECT * FROM t1 ORDER BY key1, key2;
* 在非连续的索引键部分上做 ORDER BY：(key_part1,key_part2建立联合索引;key2建立索引)
SELECT * FROM t1 WHERE key2=constant ORDER BY key_part2;
* 同时使用了 ASC 和 DESC：(key_part1,key_part2建立联合索引)
SELECT * FROM t1 ORDER BY key_part1 DESC, key_part2 ASC;
* 用于搜索记录的索引键和做 ORDER BY 的不是同一个：(key1,key2分别建立索引)
SELECT * FROM t1 WHERE key2=constant ORDER BY key1;
* 如果在WHERE和ORDER BY的栏位上应用表达式(函数)时，则无法利用索引来实现order by的优化
SELECT * FROM t1 ORDER BY YEAR(logindate) LIMIT 0,10; 1>mysql一次查询只能使用一个索引。如果要对多个字段使用索引，建立复合索引。
2>在ORDER BY操作中，MySQL只有在排序条件不是一个查询条件表达式的情况下才使用索引。

覆盖索引

解释一：就是select的数据列只用从索引中就能够取得，不必从数据表中读取，换句话说查询列要被所使用的索引覆盖。
解释二：索引是高效找到行的一个方法，当能通过检索索引就可以读取想要的数据，那就不需要再到数据表中读取行了。如果一个索引包含了（或覆盖了）满足查询语句中字段与条件的数据就叫做覆盖索引。
解释三：是非聚集组合索引的一种形式，它包括在查询里的Select、Join和Where子句用到的所有列（即建立索引的字段正好是覆盖查询语句[select子句]与查询条件[Where子句]中所涉及的字段，也即，索引包含了查询正在查找的所有数据）。

不是所有类型的索引都可以成为覆盖索引。覆盖索引必须要存储索引的列，而哈希索引、空间索引和全文索引等都不存储索引列的值，所以MySQL只能使用B-Tree索引做覆盖索引

当发起一个被索引覆盖的查询(也叫作索引覆盖查询)时，在EXPLAIN的Extra列可以看到“Using index”的信息

几种优化场景

　1.无WHERE条件的查询优化：

ALERT TABLE t1 ADD KEY(staff_id);

无where条件的查询，可以通过索引来实现索引覆盖查询，但前提条件是，查询返回的字段数足够少，更不用说select *之类的了。毕竟，建立key length过长的索引，始终不是一件好事情。

2、二次检索优化

select sql_no_cache rental_date from t1 where inventory_id<80000;
…
…
| 2005-08-23 15:08:00 |
| 2005-08-23 15:09:17 |
| 2005-08-23 15:10:42 |
| 2005-08-23 15:15:02 |
| 2005-08-23 15:15:19 |
| 2005-08-23 15:16:32 |
 --------------------- 
79999 rows in set (0.13 sec)

执行计划

explain select sql_no_cache rental_date from t1 where inventory_id<80000G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t1
         type: range
possible_keys: inventory_id
          key: inventory_id
      key_len: 3
          ref: NULL
         rows: 153734
        Extra: Using index condition
1 row in set (0.00 sec)

Extra：Using index condition 表示使用的索引方式为二级检索，即79999个书签值被用来进行回表查询。可想而知，还是会有一定的性能消耗的，尝试针对这个SQL建立联合索引，如下

alter table t1 add key(inventory_id,rental_date);

这个联合索引前置列为where子句的检索字段，第二个字段为查询返回的字段。下面来看下效果如何。

explain select sql_no_cache rental_date from t1 where inventory_id<80000G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t1
         type: range
possible_keys: inventory_id,inventory_id_2
          key: inventory_id_2
      key_len: 3
          ref: NULL
         rows: 162884
        Extra: Using index
1 row in set (0.00 sec)

和前面场景限制类似，当where条件与查询字段总数较少的情况下，使用这种优化建议，是个不错的选择。

3、分页查询优化

分页查询的优化，相信大部分的DBA同学都碰到过，通常比较常规的优化手段就是查询改写，这里主要介绍一下新的思路，就是通过索引覆盖来优化

未使用优化前：

explain select tid,return_date from t1 order by inventory_id limit 50000,10G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t1
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 1023675
        
1 row in set (0.00 sec)

看出是全表扫描。加上而外的排序，性能消耗是不低，如何通过覆盖索引优化呢？

我们创建一个索引，包含排序列以及返回列，由于tid是主键字段，因此，下面的复合索引就包含了tid的字段值

alter table t1 add index liu(inventory_id,return_date);

select tid,return_date from t1 order by inventory_id limit 50000,10;
 ------- --------------------- 
| tid   | return_date         |
 ------- --------------------- 
| 50001 | 2005-06-17 23:04:36 |
| 50002 | 2005-06-23 03:16:12 |
| 50003 | 2005-06-20 22:41:03 |
| 50004 | 2005-06-23 04:39:28 |
| 50005 | 2005-06-24 04:41:20 |
| 50006 | 2005-06-22 22:54:10 |
| 50007 | 2005-06-18 07:21:51 |
| 50008 | 2005-06-25 21:51:16 |
| 50009 | 2005-06-21 03:44:32 |
| 50010 | 2005-06-19 00:00:34 |
 ------- --------------------- 
10 rows in set (0.03 sec)

可以发现，添加复合索引后，速度提升0.7s！我们看一下改进后的执行计划

explain select tid,return_date from t1 order by inventory_id limit 50000,10G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t1
         type: index
possible_keys: NULL
          key: liu
      key_len: 9
          ref: NULL
         rows: 50010
　　　　Extra: Using index
1 row in set (0.00 sec)

执行计划也可以看到，使用到了复合索引，并且不需要回表

　　对比一下如下的改写SQL，思想是通过索引消除排序

select a.tid,a.return_date from  t1 a 
inner join 
(select tid from t1 order by inventory_id limit 800000,10) b on a.tid=b.tid;

并在此基础上，我们为inventory_id列创建索引，并删除之前的覆盖索引

alter table t1 add index idx_inid(inventory_id)；
drop index liu;

这种优化手段较前者时间多消耗了大约140ms。这种优化手段虽然使用索引消除了排序，但是还是要通过主键值回表查询。因此，在select返回列较少或列宽较小的时候，我们可以通过建立复合索引的方式优化分页查询，效果更佳，因为它不需要回表！

参考：

http://blog.codinglabs.org/articles/theory-of-mysql-index.html

https://blog.csdn.net/olizxq/article/details/82313489

秒客网

（转引）数据库索引（MySQL）

数据结构和算法基础

B-tree 和 B tree

B-tree

B Tree

带有顺序访问指针的B Tree

为什么使用B-Tree（B Tree）

磁盘存取原理

局部性原理与磁盘预读

B-/ Tree索引的性能分析

MySQL索引实现

MyISAM索引实现

InnoDB索引实现

最左前缀原理与相关优化

情况一：全列匹配。

情况二：最左前缀匹配。

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

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

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

情况六：范围查询。

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

索引选择性与前缀索引

InnoDB的主键选择与插入优化

Hash索引

索引优化 ORDER BY 排序语句

通过索引优化来实现MySQL的ORDER BY语句优化：

MySQL Order By不能使用索引来优化排序的情况

覆盖索引

几种优化场景

1.无WHERE条件的查询优化：

2、二次检索优化

3、分页查询优化

参考：

相关文章