索引¶

树¶

B树¶

关键字分布在整棵树的所有节点，且出现且只出现在一个节点中。
搜索有可能在 非叶子节点 结束，搜索性能等价于在关键字全集内做一次二分查找。

B+ 树¶

非叶子节点的子树指针与关键字个数相同。
非叶子节点的子树指针 P[i]，指向关键字属于 [k[i]，K[i+1]) 的子树（区间是前闭后开)。
所有关键字都在叶子节点出现，叶子节点构成双向链表。
B+树是B树的升级版，只是把非叶子节点冗余，好处是提高范围查找的效率。
非叶子结点：键值，数据页偏移量

叶子结点：数据页，完整的行记录

局部性原理与磁盘预读¶

不管是内存中的数据还是磁盘中的数据，操作系统都是按页（一页的大小通常是 4kb，这个值可以通过getconfig(PAGE_SIZE)命令查看）来读取的，一次只会读取一页的数据。如果要读取的数据量超过了一页的大小，就会触发多次 IO 操作。所以在选择 m 大小的时候，要尽量让每个节点的大小等于一个页的大小。
红黑树更高，逻辑上很近的节点（父子）物理上可能很远（无法利用局部性原理），所以红黑树的I/O渐进复杂度也为O(h)（磁盘IO操作更多）
B树的每个节点可以存储多个关键字，它将节点大小设置为磁盘页的大小，充分利用了磁盘预读的功能。每次读取磁盘页时就会读取一整个节点。也正因每个节点存储着非常多个关键字，树的深度就会非常的小。进而要执行的磁盘读取操作次数就会非常少，更多的是在内存中对读取进来的数据进行查找。
Mysql的基本存储结构是页， B+树每一个叶子结点对应一个页。B+树中一个节点为一页或页的倍数最为合适。

B+ 树做索引的优势¶

B+ 树的磁盘读写代价更低。B+ 树的内部没有指向关键字具体信息的指针，所以其内部节点相对 B 树更小，如果把所有关键字存放在同一块盘中，那么盘中所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相应的，IO 读写次数就降低了。
树的查询效率更加稳定。B+ 树所有数据都存在于叶子节点，所有关键字查询的路径长度相同，每次数据的查询效率相当。而 B 树可能在非叶子节点就停止查找了，所以查询效率不够稳定。
B+ 树只需要去遍历叶子节点就可以实现整棵树的遍历。

数据放到叶子节点？索引字段要尽量的小？¶

磁盘块的大小也就是一个数据页的大小，是固定的，如果数据项占的空间越小，数据项的数量越多，树的高度越低。这就是为什么每个数据项，即索引字段要尽量的小，比如int占4字节，要比 bigint8 字节少一半。这也是为什么b+树要求把真实的数据放到叶子节点而不是内层节点，一旦放到内层节点，磁盘块的数据项会大幅度下降，导致树增高

索引原则¶

最左前缀匹配原则，非常重要的原则，mysql会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配，比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a，b，c，d)顺序的索引，d是用不到索引的

school	age
a	12
b	12
b	14
b	15
c	1

在这份数据中，school字段是完全有序的，索引school可以使用索引。而从全表来看，age字段不是有序的，因此无法直接使用索引，那么观察一下数据表，在什么时候age有序呢?在school进行定值匹配的时候，例如当school=b的时候，对于这三条数据而言，age是有序的，因此可以使用age索引.这就是最左前缀的原理。
此外，最左前缀索引只能使用一个范围查询，例如select * from user where school > a， select * from user where school = a and age > 12，都是可以命中索引的，但是select * from user where school > a and age > 12中，仅school可以命中索引，这也可以从上面得出结论。因为当school是范围匹配的时候，mysql无法确认age字段是否严格有序，比如 school的范围匹配命中了b，c的四条数据，那么age就不是有序的.无法使用后续的索引。

选择区分度高的列作为索引

就是字段不重复的比例，比例越大，扫描的记录数越少
索引列不能参与计算
尽量的扩展索引，不要新建索引。比如表中已经有a的索引，现在要加(a，b)的索引，那么只需要修改原来的索引即可。

索引失效¶

违反最左匹配原则
- 如果建立的索引是 (a，b，c)，也只有 (a)，(a，b)，(a，b，c) 三种查询可以生效
- 遇到范围查询（>、<、between、like）就会停止匹配
用 or 连接的条件，任何一个没有索引，就会直接全表扫描
在索引列上做任何操作：如计算、函数、（手动或自动）类型转换等操作
like 中以通配符开头 (‘%abc’)

普通索引与唯一索引¶

普通索引¶

查到满足条件的记录后，继续查找，直到不满足条件。

唯一索引¶

查找到第一个满足条件的记录后，就会停止搜索

change buffer¶

当需要更新一个数据页时，如果数据页在内存中就直接更新，而如果这个数据页还没有在内存中的话，在不影响数据一致性的前提下，InooDB会将这些更新操作缓存在change buffer中，这样就不需要从磁盘中读入这个数据页了。在下次查询需要访问这个数据页的时候，将数据页读入内存，然后执行change buffer中与这个页有关的操作。

唯一索引的更新不使用 change buffer ：需要将数据页读入内存才能判断是否唯一。若数据页不在内存中，**需要将数据页读入内存，判断到没有冲突，插入这个值。

普通索引的更新直接写入 change buffer。适用于日志、账单。

前缀索引¶

在对一个比较长的字符串进行索引时，可以仅索引开始的一部分字符，这样可以大大的节约索引空间，从而提高索引效率.但是这样也会降低索引的选择性

联合索引¶

联合索引只可以进行最左前缀匹配，因此应该将选择性高的列放在联合索引的前面。

覆盖索引¶

一个索引包含 (或者说是覆盖) 需要查询的所有字段的值

覆盖索引可以减少树的搜索次数，提升性能，他也是我们在实际开发过程中经常用来优化查询效率的手段。

很多联合索引的建立，就是为了支持覆盖索引，特定的业务能极大的提升效率。

前缀索引和覆盖索引无法一起使用

聚簇索引¶

聚簇索引不是一种索引类型，而是一种存储数据的方式。Innodb的聚簇索引是在同一个数据结构中保存了索引和数据。

Innodb使用主键来进行聚簇索引，没有主键的话就会选择一个唯一的非空索引。

聚集索引表记录的排列顺序和索引的排列顺序一致，所以查询效率快，因为只要找到第一个索引值记录，其余的连续性的记录在物理表中也会连续存放，一起就可以查询到。

缺点：新增比较慢，因为为了保证表中记录的物理顺序和索引顺序一致，在记录插入的时候，会对数据页重新排序。

非聚簇索引¶

索引的逻辑顺序与磁盘上行的物理存储顺序不同，非聚集索引在叶子节点存储的是主键和索引列，当我们使用非聚集索引查询数据时，需要拿到叶子上的主键再去表中查到想要查找的数据。这个过程就是我们所说的回表。

非聚集索引在叶子节点存储的是主键和索引列。

聚集索引或非聚集索引？¶

动作描述	使用聚集索引	使用非聚集索引
返回某范围内的数据	使用	不使用
小数目的不同值	使用	不使用
大数目的不同值	不使用	使用
频繁更新的列	不使用	使用
频繁修改索引列	不使用	使用

Explain¶

输出说明¶

列名	说明
id	执行编号，标识select所属的行。如果在语句中没子查询或关联查询，只有唯一的select，每行都将显示1。否则，内层的select语句一般会顺序编号，对应于其在原始语句中的位置
select_type	显示本行是简单或复杂select。如果查询有任何复杂的子查询，则最外层标记为PRIMARY（DERIVED、UNION、UNION RESUlT）
table	访问引用哪个表（引用某个查询，如“derived3”）
type（重要）	数据访问/读取操作类型性能排序：ALL < index < range < index_merge < ref < eq_ref < const < system
possible_keys	类型揭示哪一些索引可能有利于高效的查找
key	显示mysql决定采用哪个索引来优化查询
key_len	显示mysql在索引里使用的字节数
ref	显示了之前的表在key列记录的索引中查找值所用的列或常量
rows（核心）	为了找到所需的行而需要读取的行数（估算值）
Extra（重要）	额外信息 `Using filesort` , 表示 MySQL 需额外的排序操作, 不能通过索引顺序达到排序效果。可能是ordery by，group by语句的结果，CPU密集型的过程，可以通过选择合适的索引来改进性能，用索引来为查询结果排序 Using index 覆盖索引扫描, 表示查询在索引树中就可查找所需数据, 不用扫描表数据文件, 往往说明性能不错 Using temporary 说明查询有使用临时表, 一般出现于排序, 分组和多表 join 的情况, GROUP BY 和 ORDER BY操作中

type¶

类型	说明
All	最坏的情况,全表扫描
index	和全表扫描一样。只是扫描表的时候按照索引次序进行而不是行。主要优点就是避免了排序, 但是开销仍然非常大。如在Extra列看到Using index，说明正在使用覆盖索引，只扫描索引的数据，它比按索引次序全表扫描的开销要小很多
range	范围扫描，一个有限制的索引扫描。key 列显示使用了哪个索引。当使用=、 <>、>、>=、<、<=、IS NULL、<=>、BETWEEN 或者 IN 操作符,用常量比较关键字列时,可以使用 range
ref	一种索引访问，它返回所有匹配某个单个值的行。此类索引访问只有当使用非唯一性索引或唯一性索引非唯一性前缀时才会发生。这个类型跟eq_ref不同的是，它用在关联操作只使用了索引的最左前缀，或者索引不是UNIQUE和PRIMARY KEY。ref可以用于使用=或<=>操作符的带索引的列。
eq_ref	最多只返回一条符合条件的记录。使用唯一性索引或主键查找时会发生（高效）
const	当确定最多只会有一行匹配的时候，MySQL优化器会在查询前读取它而且只读取一次，因此非常快。当主键放入where子句时，mysql把这个查询转为一个常量（高效）
system	这是const连接类型的一种特例，表仅有一行满足条件。
Null	意味说mysql能在优化阶段分解查询语句，在执行阶段甚至用不到访问表或索引（高效）

索引¶

树¶

B树¶