nber1994



mysql-索引

January 8, 2019

ps:平衡查找树

B B+ https://zhuanlan.zhihu.com/p/27700617

MySQL索引背后的数据结构及算法原理 http://blog.codinglabs.org/articles/theory-of-mysql-index.html

联合索引结构原理 https://blog.csdn.net/weixin_30531261/article/details/79329722

覆盖索引 https://yq.aliyun.com/articles/62419

联合索引如何选取wherer http://hedengcheng.com/?p=577

索引数据结构基础知识

平衡二叉树

平衡二叉树是基于二分法的策略提高数据查找速度的数据结构

B-tree

与平衡二叉树的区别是B树属于多叉树,每个节点多于两个查找路径

规则

B+树

B+树让查询速度更加稳定,完全趋近于二分查找

与B树的区别

特点:飞叶子节点中不保存记录指针,每个节点可以存更多的关键字,数据只保存在叶子节点,每次查询的速度一定
每个节点的出度增加,进而树高会降低,提高了查找速度。

为什么使用B/B+树

一般来说,索引本身都很大,所以一般会存在磁盘上,而相对于内存读取,读取磁盘的开销是十分大的,所以衡量一个索引性能的一个标准
就是一次查询IO的次数

mysql索引实现

MyIsAM索引结构是通过B+树实现的,叶子节点存放的是数据的地址
而对于辅助索引来说,其结构和主键索引没有任何区别

这类索引成为非聚簇索引,即数据和索引文件是分开的

InnoDB索引实现

对于InnoDB来说,数据本身就是主索引文件,

因为索引和数据是被保存在一起的,与MyIsAm不同的是,InnoDB的B+树的叶子节点
包含完整的数据行记录,因而该索引称为聚簇索引
因而InnoDB表必须有主键,如果没有的话,InnoDB会自动隐世的创建主键索引

另外对于InnoDB引擎来说,辅助索引叶子节点存储的是主键的值而不是地址

因而InnoDB检索需要经过两边索引:首先通过辅助索引拿到主键的值,在检索一遍主键索引
因而不建议将索引做的过大,因为会导致过大的索引文件
不单调的字段作为索引会导致数据插入时频繁的分裂调整

索引使用策略&优化

最左前缀原理&优化

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      |
+--------+------------+----------+--------------+-------------+-----------+-------------+------+------------+

情况一:全列匹配

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 |       |
+----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+

where后的字段InnoDB会自动调整顺序

情况二:最左前缀匹配

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 |       |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------+

这个时候可以看到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 |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+

这个时候无法命中后续的索引字段,所以key_len使用了4

情况四:没有指定第一列

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 |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+

最左前缀的字段可以使用索引,但是后面的字段就无法使用了。 对于between来说,其实不属于范围操作

情况七:查询条件中存在函数或者表达式

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 |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+
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 |
+----+-------------+--------+------+---------------+------+---------+------+--------+-------------+

可以看到当第一个字段如果存在表达式时,则不会命中索引

索引的选择

索引并不是越多越好,

不建议建立索引的情况:

逐渐选择

永远建议使用自增字段作为主键 因为基于B+树的索引结构,如果使用自增的主键,每次新插入一条数据,InnoDB会选择合适的位置建立索引,如果达到装载因子则会重新开辟页面。
如果使用非自增的主键,每次新插入的数据可以看为随机的,此时插入数据时,InnoDB寻找随机的位置建立索引,因此不得不为了插入新的数据而把后面的页进行重新的移动,增加了很多开销

辅助索引

对于辅助索引,大致的结构是这样的。 如果存在联合索引,则只会生成一个辅助索引树

联合索引

对于联合索引,其大致结构是如下所示

大致是在第一个索引的基础上筛选出数据后,在根据后面的字段进行筛选

索引覆盖

索引覆盖指的是一次查询只需要从辅助索引中就能得到查询信息,而不需要查询聚簇索引中的数据

当没有where条件的优化

二次索引优化

 mysql> 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)

mysql> explain select sql_no_cache rental_date from t1 where inventory_id<80000\G
*************************** 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,说明会通过index进行了回表查询 在rental_date字段增加索引之后:

mysql> explain select tid,return_date from t1 order by inventory_id limit 50000,10\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t1
         type: index
possible_keys: NULL
          key: liu
      key_len: 9
          ref: NULL
         rows: 50010
1 row in set (0.00 sec)
执行计划也可以看到,使用到了复合索引,并且不需要回表