深入理解Java多线程-笔记总结（2）-创建高性能索引
第五章 创建高性能索引
5.1 索引基础
5.1.1 索引的类型
在MySQL中索引是在存储引擎层而不是在服务层实现的。不同存储引擎的索引工作方式也不一样。
B-Tree 索引
InnoDB使用的B+Tree。
B~Tree数据结构：
B-tree又叫平衡多路查找树。一棵m阶的B-tree (m叉树)的特性如下：
- 树中每个结点至多有m个孩子；
- 除根结点和叶子结点外，其它每个结点至少有有ceil(m / 2)个孩子；
- 若根结点不是叶子结点，则至少有2个孩子
- 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部结点或查询失败的结点，实际上这些结点不存在，指向这些结点的指针都为null)；
- 每个非终端结点中包含有n个关键字信息： (n，P0，K1，P1，K2，P2，…，Kn，Pn)。其中：
- Ki (i=1…n)为关键字，且关键字按顺序排序K(i-1)< Ki。
- Pi为指向子树根的接点，且指针P(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。
- 关键字的个数n必须满足： ceil(m / 2)-1 <= n <= m-1。
B+ tree
一棵m阶的B±tree和m阶的B-tree的差异在于：
-
有n棵子树的结点中含有n个关键字； (B-tree是n棵子树有n-1个关键字)
-
所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (B-tree的叶子节点并没有包括全部需要查找的信息)
-
所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (B-tree的非终节点也包含需要查找的有效信息)
B±tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B-tree更小。
如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
B±tree*的查询效率更加稳定*
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
B*-tree
B*-tree是B±tree的变体，在*****B±tree*****的非根和非叶子结点再增加指向兄弟的指针
B-Tree 对索引列是顺序组织存储的，适合查找范围数据。
索引对多个值进行排序的一居室create table 语句中定义索引时的顺序。
可以使用B- Tree 索引的查询类型：
- 全值匹配
- 匹配最左前缀
- 匹配列前缀
- 匹配范围值
- 精确匹配到某一列并范围匹配另外一列
- 只访问索引的查询
哈希索引
只有精确匹配搜索索引所有列的查询才有效。哈希索引结构紧凑，访问内存速度很快。
限制：
哈希索引值包含哈希值和行指针，不能使用索引中的值来避免读取行
不是按照索引值顺序存储的，无法用于排序
不支持部分索引列匹配查找
只支持等值比较查询，不支持范围查询
如果哈希冲突多的话，维护索引代价很高。
InnoDB引擎有一个特殊的功能——自适应哈希索引
当某些索引值被非常频繁的使用时，会在内存中基于B-Tree索引之上再创建一个哈希索引。这是完全自动的内部行为，用户无法控制或者配置。
可以再表中增加一个哈希列，来专门做哈希索引，该列的值使用CRC32() 方法来获取哈希值，然后再创建一个触发器来维护哈希列，每次插入的时候，自动生成其哈系列的值。不使用MD5 和 SHAL是因为他们更长，浪费空间，比较也慢一些
这样的手动添加哈希索引还是可能造成哈希冲突，所以在搜索时的where里面包含常量值：
5.2 索引的优点
- 大大减少了服务器需要扫描的数据量
- 索引可以帮助服务器避免排序的临时表
- 索引可以将随意I/O变为顺序I/O
5.3 高性能索引策略
5.3.1 独立的列
如果查询中的列不是独立的，则MySQL就不会使用索引。
应养成简化where条件的习惯，始终将索引列单独放在比较号的一侧。
例如上图所式的actor_id则无法使用索引
5.3.2 前缀索引和索引选择性
若需要索引很长的字符列，可以选择哈希索引，也可以选则前缀索引，即仅使用字符串开始的部分字符。，大大节约索引空间，也可以提高索引效率。但是也要满足前缀的选择性足够高。
5.3.3 多列索引
在单独的列上建立单独的索引大多数情况下并不能提升MySQL的查询性能。
MySQL在5.0及之后的版本引入了 索引合并 策略。查询能够普同时对多个单列索引进行扫描，并将结果进行合并。包括：OR、AND、组合前两种情况的联合及相交。
5.3.4 选择合适的索引列顺序
在一个多列的B-Tree索引中，索引列的顺序意味着索引首先按最左列进行排序，依次往后。
选择索引的列顺序的经验法则：将选择性最高的列放到索引最前列。但不一定是有用的。
5.3.5 聚簇索引
聚簇索引并不是一种单独的索引类型，而是一种数据存储方式。
InnoDB的聚簇索引实际上在同一个结构中板寸了B-Tree索引和数据行。
一张表只能有一个聚簇索引。
聚簇引擎的优点:
- 可以把相关的数据保存在一起。减少I/O次数
- 数据访问更快
- 使用覆盖索引扫描的查询可以直接使用页节点中的主键值。
缺点：
- 如果数据全部放在内存中，访问顺寻则没有那么重要，聚簇也就起不到很大的作用。
- 插入速度严重依赖插入顺序。
- 更新聚簇索引列的代价很高
- 基于聚簇索引的表插入新行，主键被更新导致需要移动行的时候，面临页分裂的问题
- 导致全表扫描变慢
- 二级索引可能比想象中的更大
- 二级索引访问需要两次索引查找
5.3.6 覆盖索引
如果一个索引包含（或者说覆盖）所有需要查询的字段的值，我们就称之为覆盖索引。查询的时候不需要读取数据行。
覆盖索引的好处：
- 索引条目远小于数据行大小，只需要读取索引不需要读取行，极大减少数据访问量；
- 索引是按照列值顺序存储的，所以对于IO密集型的范围查找会比随意从磁盘读取每一行数据的IO要少的多。
- MyISAM 在内存中只缓存索引，数据则依赖于操作系统来缓存，访问数据需要调用系统，会极大影响速度。
- 由于Inn哦DB的聚簇索引，覆盖索引对InnoDB表特别有用。InnoDB的二级索引在叶子节点中保存了行的主键值，所以如果二级主键能够覆盖查询，则可以避免对主键索引的二次查询。
5.3.7 使用索引扫描来做排序
MySQL生成有序的结果的方法：
1.通过排序操作
2.按索引排序扫描
MySQL可以使用同一个索引即满足排序，又用于行查找。
使用限制：
当索引的顺序和order by 自护的顺序完全一致，并且所有列的排序方向都一样时，MySQL 才能够使用索引结果做排序。
多表关联时，只有当order by 子句引用的全部字段为第一个表时，才能使用索引做排序。
特别：
当前导列为常量的时候，索引不需要满足最左前缀的要求。
5.3.8 压缩（前缀压缩）索引
使用前缀压缩减少索引的大小，让更多的索引可以放入内存内，某些情况下可以极大的提高性能。默认只压缩字符串，但可以通过参数设置也可以对整数进行压缩。
MyISAM的压缩方式时：
先完全保存索引块中的第一个值，然后将其他值和第一个值进行比较得到相同前缀的字节数和剩余的不同后缀部分，把这部分存储起来即可。
5.3.9 冗余和重复索引
重复索引
MySQL 允许相同列上创建多个索引。MySQL需要单独维护重复的索引，并且优化器在优化查询的时候也需要逐个的进行考虑，影响性能。
常见的是一个用户想要创建一个主键，先加上唯一限制，然后再加上索引以供查询，这个时候就产生了重复索引。MySQL的唯一限制和主键限制都是通过索引实现的。
冗余索引
当创建了索引(A,B) ，再创建索引(A) ，这时的索引(A) 时冗余索引， 但是(B,A)不是，最左前缀列不同，B树的结构也不同。
大多数情况下都不需要冗余索引，应该尽量扩展已有的索引而不是创建新索引。
可以使用Shlomi Noach 的 common_schema 中的视图定位查找冗余索引和重复索引来删除他们。
5.3.10 未使用的索引
服务器永远用不到的索引，完全是累赘，十分建议删除。在Percona Server 或者MariaDB 中先打开userstates服务器变量，让服务器运行一段时间，再铜鼓哦查询INFORMATION_SCHEMA.INTEX_STATISTICS就能查询到每个索引的使用频率。
5.3.11 索引和锁
索引可以让查询锁定更少的行。上面提到过只访问索引来查询数据不需要读取行，也不需要锁定行。锁定超过需要的行会增加锁争并减少并发性。InnoDB只有在访问行的时候才会对其加锁。