MySQL索引、算法(基于InnoDB引擎)和优化

索引

索引是应用程序设计和开发的一个重要方面。如果索引太多，应用的性能可能会受到影响；如果索引太少，对查询性能又会产生影响。

1 innodb存储引擎介绍

innodb存储引擎支持两种常见的索引：B+树索引和哈希索引。

innodb支持哈希索引是自适应的，innodb会根据表的使用情况自动生成哈希索引。

B+树索引就是传统意义上的索引，是关系型数据库中最常用最有效的索引。B+树是从最早的平衡二叉树演变而来，但是B+树不是一个二叉树。B+中的B不代表二叉(Binary),而是代表平衡(Balance)。

注意：

B+树索引并不能找到一个键值对应的具体行。b+树索引只能查到被查找数据行所在的页，然后数据库通过把页读入内存，再在内存中查找，最后得到结果。

2 B+树索引介绍

B+树索引的本质是B+树在数据库中的实现。但是B+树索引有一个特点是高扇出性，因此在数据库中，B+树的高度一般在2到3层。也就是说查找某一键值的记录，最多只需要2到3次IO开销。按磁盘每秒100次IO来计算，查询时间只需0.0.2到0.03秒。

数据库中B+树索引分为聚集索引（clustered index)和非聚集索引（secondary index)，这两种索引的共同点是内部都是B+树，高度都是平衡的，叶节点存放着所有数据。不同点是叶节点是否存放着一整行数据。

1. 聚集索引
Innodb存储引擎表是索引组织表，即表中数据按主键顺序存放。而聚集索引就是按每张表的主键构造一颗B+树。并且叶节点存放整张表的行记录数据。每张表只能有一个聚集索引（一个主键）。
聚集索引的另一个好处是它对于主键的排序查找和范围的速度非常快。叶节点的数据就是我们要找的数据。

2. 辅助索引
辅助索引（也称非聚集索引）。叶级别不包含行的全部数据，叶级别除了包含行的键值以外，每个索引行还包含了一个书签（bookmark），该书签告诉innodb存储引擎，哪里可以找到与索引对应的数据。
辅助索引的存在并不影响数据再聚集索引中的组织，因此一个表可以有多个辅助索引。当通过辅助索引查找数据时，innodb会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键。然后再通过主键索引找到一行完整的数据

3 使用场景

1. 快速查找符合where条件的记录
2. 快速确定候选集。若where条件使用了多个索引字段，则MySQL会优先使用能使候选记录集规模最小的那个索引，以便尽快淘汰不符合条件的记录。
3. 如果表中存在几个字段构成的联合索引，则查找记录时，这个联合索引的最左前缀匹配字段也会被自动作为索引来加速查找。例如，若为某表创建了3个字段(c1, c2, c3)构成的联合索引，则(c1), (c1, c2), (c1, c2, c3)均会作为索引，(c2, c3)就不会被作为索引，而(c1, c3)其实只利用到c1索引。
4. 多表做join操作时会使用索引（如果参与join的字段在这些表中均建立了索引的话）
5. 若某字段已建立索引，求该字段的min()或max()时，MySQL会使用索引
6. 对建立了索引的字段做sort或group操作时，MySQL会使用索引

4 建立、修改索引

1 索引创建：两种方式

ALTER [ONLINE | OFFLINE] [IGNORE] TABLE tbl_name| ADD {INDEX|KEY} [index_name]   [index_type] (index_col_name,...) [index_option]

CREATE [ONLINE|OFFLINE] [UNIQUE|FULLTEXT|SPATIAL] INDEX index_name [index_type] ON tbl_name (index_col_name,...)

2 索引删除：两种方式

ALTER [ONLINE | OFFLINE] [IGNORE] TABLE tbl_name | DROP PRIMARY KEY | DROP {INDEX|KEY} index_names

DROP [ONLINE|OFFLINE] INDEX index_name ON tbl_name

---

算法（B+树）

B+树是为磁盘及其他存储辅助设备而设计一种平衡查找树（不是二叉树）。B+树中，所有记录的节点按大小顺序存放在同一层的叶节点中，各叶节点用指针进行连接。

下面演示一个B+数结构，高度为2，每页可放4条记录，扇出(fan out)为5。从下图1可以看出，所有记录都在页节点中，并且为顺序存放，我们从最左边的叶节点开始遍历，可以得到所有键值的顺序排序：5、10、15、20、25、30、50、55、60、65、75、80、85、90.

图1 高度为2的B+树

1. B+树的插入操作
   B+树的插入必须保证插入后叶节点的记录依然排序。同时要考虑插入B+树的三种情况，每种情况都可能导致不同的插入算法。如下表所示：
   

   B+树插入的3种情况
   我们实例分析B+树的插入，在图1的B+树中，我们需要插入28这个值。因为Leaf Page和Index page都没有满，我们直接将记录插入叶节点就可以了。如下图2所示：
   图2 插入键值28
   下面我们再插入70这个值，这时Leaf Page已经满了，但是Index Page还没有满，符合上面的第二种情况。这时插入Leaf Page的情况为50、55、60、65、70.我们根据中间的值60拆分叶节点，可得到下图3所示（双项链表指针依然存在，没有画出)：
   图3 插入键值70 最后我们再插入95，这个Leaf Page和Index Page都满了，符合上面第三种情况。需要做2次拆分，如下图4所示：
   图4 插入键值95
   可以看到，不管怎么变化，B+树总会保持平衡。但是为了保持平衡，对于新插入的键值可能需要做大量的拆分页操作。B+树主要用于磁盘，拆分意味着磁盘的操作，应该在可能的情况下尽量减少页的拆分。因此，B+树提供了旋转功能。旋转发生在Leaf Page已经满了，但是左右兄弟节点没有满的情况下。这时B+树并不是急着做页的拆分，而是旋转。旋转结果如图5所示，可以看到旋转操作使B+树减少了一次页的拆分操作，高度仍然为2.
   图5 B+树的旋转操作

2. B+树的删除操作
   B+树使用填充因子来控制数的删除变化。填充因子可以设置的最小值为50%。B+树的删除操作同样保证删除后叶节点的记录依然排序。
   根据填充因子的变化，B+树删除依然需要考虑三种情况，如下表所示：
   

   

根据图4的B+树，我们进行删除操作，首先删除键值为70的这条记录，该记录符合上表第一种情况，删除后如下图6所示：

图6 删除键值70
接着我们删除键值为25的记录，这也是属于上表第一种情况，不同的是该值还是index page中的值。因此在删除Leaf Page中的25后，还需要将25的右兄弟节点28更新到Index Page中，如下图7所示（图中有两个笔误，红色为修正值）：
图7 删除键值28 最后我们删除键值为60的记录。删除Leaf page键值为60的记录后，其填充因子小于50%。需要做合并操作。同样在删除Index page中相关记录后需要做Index Page的合并操作。

优化

MySQL数据库是常见的两个瓶颈是CPU和I/O的瓶颈，CPU在饱和的时候一般发生在数据装入内存或从磁盘上读取数据时候。磁盘I/O瓶颈发生在装入数据远大于内存容量的时候，如果应用分布在网络上，那么查询量相当大的时候那么平瓶颈就会出现在网络上，我们可以用mpstat, iostat, sar和vmstat来查看系统的性能状态。

除了服务器硬件的性能瓶颈，对于MySQL系统本身，我们可以使用工具来优化数据库的性能，通常有三种：使用索引，使用EXPLAIN分析查询以及调整MySQL的内部配置

1 性能分析工具

show profile;
mysqlsla;   // 压测
mysqldumpslow;  // 慢查询slow sql
explain;
show slow log;
show processlist;
show query_response_time(percona);

2 Explain

explain select count(*) from XXX;

+----+-------------+---------+------+---------------+------+---------+------+------+-------+
| id | select_type | table | type | possible_keys | key | key_len | ref | **rows** | Extra |
+----+-------------+---------+------+---------------+------+---------+------+------+-------+
| 1 | SIMPLE | XXX | ALL | NULL | NULL | NULL | NULL | 6897 | NULL |+----+-------------+---------+------+---------------+------+---------+------+------+-------+

EXPLAIN字段:

1. id:本次 select 的标识符。在查询中每个 select都有一个顺序的数值。
2. select_type:

1. SIMPLE：查询中不包含子查询或者UNION
2. PRIMARY：查询中若包含任何复杂的子部分，最外层查询则被标记为
3. SUBQUERY：在SELECT或WHERE列表中包含了子查询，该子查询被标记为
4. DERIVED（衍生)：在FROM列表中包含的子查询被标记为
5. UNION: 若第二个SELECT出现在UNION之后，则被标记为UNION；若UNION包含在 FROM子句的子查询中，外层SELECT将被标记为：DERIVED
6. 从UNION表获取结果的SELECT被标记为：UNION RESULT

3. Table：显示这一行的数据是关于哪张表的

4. possible_keys：显示可能应用在这张表中的索引。如果为空，没有可能的索引。可以为相关的域从WHERE语句中选择一个合适的语句

5. key：实际使用的索引。如果为NULL，则没有使用索引。MYSQL很少会选择优化不足的索引，此时可以在SELECT语句中使用USE INDEX（index）来强制使用一个索引或者用IGNORE INDEX（index）来强制忽略索引

6. key_len：使用的索引的长度。在不损失精确性的情况下，长度越短越好

7. ref：显示索引的哪一列被使用了，如果可能的话，是一个常数

8. rows：MySQL认为必须检索的用来返回请求数据的行数

9. type：这是最重要的字段之一，显示查询使用了何种类型。从最好到最差的连接类型为system、const、eq_reg、ref、range、index和ALL

system、const：可以将查询的变量转为常量. 如id=1; id为 主键或唯一键.

eq_ref：访问索引,返回某单一行的数据.(通常在联接时出现，查询使用的索引为主键或惟一键)

ref：访问索引,返回某个值的数据.(可以返回多行) 通常使用=时发生

range：这个连接类型使用索引返回一个范围中的行，比如使用>或<查找东西，并且该字段上建有索引时发生的情况(注:不一定好于index)

index：以索引的顺序进行全表扫描，优点是不用排序,缺点是还要全表扫描

ALL：全表扫描，应该尽量避免

10. Extra：关于MYSQL如何解析查询的额外信息。
    主要有以下几种：

1. using index：只用到索引,可以避免访问表.

2. using where：使用到where来过虑数据. 不是所有的where clause都要显示using where. 如以=方式访问索引.

3. using tmporary：用到临时表

4. using filesort：用到额外的排序. (当使用order by v1,而没用到索引时,就会使用额外的排序)

5. range checked for eache record(index map:N)：没有好的索引.

----
参考
- MySQL技术内幕I弄DB存储引擎
- http://www.oicto.com/mysql-explain-show/