mysql存储结构索引案例，回表

MySQL innodb的

• 主键索引是簇集索引（聚簇索引），也就是索引的叶子节点存的是整个单条记录的所有字段值;

• 非主键索引（其它索引）的就是非簇集索引（非聚簇索引），非簇集索引的叶子节点存的是主键字段的值。

索引的叶子节点结构是key value，key是索引项，value存放具体值，

主键索引在mysql中是簇集索引，key是主键，value是单条记录的所有值。但一张表为了避免数据太冗余，只能有一个簇集索引，所以非簇集索引的value值存放的是主键值，这样才能根据主键找到具体的数据。
 

回表是什么意思？
就是你执行一条sql语句，需要从两个b+索引中去取数据。

举个例子：

表tbl有a,b,c三个字段，其中a是主键，b上建了索引，然后编写sql语句SELECT * FROM tbl WHERE a=1这样不会产生回表，因为所有的数据在a的索引树中均能找到;

如果是SELECT * FROM tbl WHERE b=1这样就会产生回表，因为where条件是b字段，那么会去b的索引树里查找数据，但b的索引里面只有a,b两个字段的值，没有c，那么这个查询为了取到c字段，就要取出主键a的值，然后去a的索引树去找c字段的数据。查了两个索引树，这就叫回表。

什么是索引覆盖？
索引覆盖就是查这个索引能查到你所需要的所有数据，不需要去另外的数据结构去查。其实就是不用发生回表操作。

怎么避免？

• 用主键搜索。
• 或者b,c建联合索引（只查询被联合索引覆盖的字段）。

但具体情况要具体分析，索引字段多了，存储和插入数据时的消耗会更大。这是个平衡问题。
为什么设置了命中了索引但还是造成了全表扫描

其中一个原因就是虽然命中了索引，但在叶子节点查询到记录后还要大量的回表，导致优化器认为这种情况还不如全表扫描会更快些

索引是什么?

索引是帮助MySQL高效获取数据的数据结构。

索引能干什么?

提高数据查询的效率。

索引：排好序的快速查找数据结构！索引会影响where后面的查找，和order by 后面的排序。

首先讲解一下数据结构类型

１、hash：无规则、不能排序、仅支持"=","IN"和"<=>"精确查询并且检索效率高，但不能使用范围查询

２、二叉树：解决hash索引不能排序问题，但是当数据有序时会出现线性排列，树的深度会变得很深，会消耗大量IO。

3、平衡二叉树：解决二叉树数据有序时出现的线性插入树太深问题，树的深度会明显降低，极大提高性能，但是当数据量很大时，一般mysql中一张表达到3-5百万条数据是很普遍的，因此平衡二叉树的深度还是非常大，mysql读取时还是会消耗大量IO，不仅如此，计算从磁盘读取数据时以页(4KB)为单位的,及每次读取4096byte。平衡二叉树每个节点只保存了一个关键字（如int即4byte），浪费了4092byte，极大的浪费了读取空间。

4、B-树：解决平衡二叉树树深度的问题，解决了平衡二叉树读取消耗大量内存空间的问题。因为B-树每个节点可以存放多个关键字，最大限度的利用了从磁盘读取的内存空间，单节点存放多个关键字同时也大大减少了树的深度。极大的提高了mysql的查询性能。但是B-树还是有缺点，B-树对有范围查找的查询（如age>20）时采用的还是中序排序法，因此也需要多遍历，并且查询性能不稳定，比如查询（select * from table where id = 222 和 select * from table where id = 223）时在查询效率（耗时）上可能会存在一定的差别，因为B-树还是将关键字，这里为id，存放在根节点和叶节点的，如果运气好，可能id=222这个关键字就在第一个节点，消耗一次IO就找到了，而id=223可能在叶节点，需要消耗3次IO才能找到。因此B-树对同一条sql语句的查询性能可能会有很大影响（确实感觉有点扯，但是事实时这样）。
任何一个关键字出现且只出现在一个结点中，数据不一定在子节点上，也可能是父节点，交叉节点等等

5、B+树：将关键字全部存放在叶子节点(查询更稳定，同一条mysql语句执行效率时相同的，都会消耗3次IO)，将相邻叶子节点的地址保存起来（相比于B-树，对于mysql的范围查找不用再使用中序查找，而是可以直接快读获取到。）

6、红黑树：树的高度随着数据量增加而增加，IO代价高。

总结如下：
hash：虽然可以快速定位，但是没有顺序，IO复杂度高。

二叉树：树的高度不均匀，不能自平衡，查找效率跟数据有关（树的高度），并且IO代价高。

红黑树：树的高度随着数据量增加而增加，IO代价高。

B-Tree： 矮胖型的树，IO效率相对其他要高，在范围查询时，需要获取所有节点进行遍历，效率相对低下

B+Tree对比B-Tree：数据都在叶子节点上，并且增加了顺序访问指针，每个叶子节点都指向相邻的叶子节点的地址。相比B-Tree来说，进行范围查找时只需要查找两个节点，进行遍历即可。而B-Tree需要获取所有节点，相比之下B+Tree效率更高。

所以说：mysql索引结构默认使用B+Tree，而不是hash，二叉树和红黑树

重点说明：
1、mysql底层使用的时B+树，根节点和分支节点中不保存数据，只用于索引，所有数据都保存在叶子节点中。mysql索引是放在磁盘上面的，因此每次读取索引时通过IO从磁盘读取。

2、结合B+Tree的特点，自增主键是连续的，在插入过程中尽量减少页分裂，即使要进行页分裂，也只会分裂很少一部分。并且能减少数据的移动，每次插入都是插入到最后。总之就是减少分裂和移动的频率。(设计概念专业名词：为啥速度快，以空间获取时间)
3、B树不是二叉树

如下连接更加详细了解mysql索引讲解
图解MySQL索引--B-Tree（B+Tree） - Java填坑笔记 - 博客园
 

mysql索引原理---查询一条sql索引到底是怎么使用的

例如一个学生信息表，我们设置学号（stu_id）为索引：

索引页之间存在一定的关联关系，一般为树形结构;分为根节点、分支节点、和叶子节点
根节点页中存放分段stu_id的起始值，当前索引页号，以及值所对应的分支索引页号
分支索引页中存放分段stu_id的起始值，当前索引页号，以及值所对应的叶子索引页号
叶子索引页中存放排序后的stu_id值，当前索引页号，该值所对应的表页号, 下一个叶子索引页的页号

 

stu_id建立索引后，执行select name,sex,height from stu where stu_id=13查询过程如下：

1、索引页存在关联关系，先找索引页号20的根节点，13在>=11和<17的范围内，需要查找25号索引页
2、读取25号索引页，13在>=11和<14范围内，得到了26号叶子索引页
3、读取26号叶子索引页，找到了13这个值，以及该值所对应表页的页号161，目前只得到了stu_id的值，还要得到name,sex,height等，因此需要再读一次编号为161的表页，里面存放了stu_id之外的值。
4、读取161号表页，获得sname,sex,height等值
以上4步，只读取了3个索引页1个表页，共4个页，比读取所有表页（5000个页），按照stu_id=13挨个翻一遍效率要高，这也是有些情况下索引可以加速查询的原因。