MySql索引基本原理

前置概念：

磁盘预读：内存跟磁盘在发生数据交互的时候，一般情况下有一个最小的逻辑单元，即"页"/“datapage”，页一般由操作系统决定是多大，一般是4k或8k。而进行数据交互的时候，可以取页的整数倍来读取。如innodb引擎每次读取数据都是16k
B+树
- 每个关键字对应一棵子树
- 每个结点关键字个数n的范围是[m/2]<=n<=m
- 叶节点是包含信息的，其他所有非叶节点仅起到索引作用，包含了对应子树的最大关键字和指向该子树的指针
mysql底层构造
- client层——>server层——>存储引擎
- - client向server层发送SQL语句，server层通过连接器接收
  - server层的分析器对SQL语句进行语法分析，转变为AST抽象语法树
  - server层使用优化器对语句中具体查询的数据
  - 执行器与存储引擎进行IO交互，获取查询结果

从头遍历

没有索引的查找方法：从第一页记录开始查，遍历所有数据页，相当耗费资源和时间。

简单的索引方案——一层目录

假设一个数据页的数据已经存储满了，这时再添加一条记录。如果该记录的主键比现有记录最大的主键小：首先必然会产生页的分裂，其次，现有的最大主键用户记录会移到新的数据页，而新插入的用户记录则插入到原来已满的数据页。页的分裂始终保持——下一个数据页中用户主键值必须大于上一页的用户记录主键值。
再假设上述页分裂操作多次执行，导致数据页数量非常多。此时应该给这些数据页按照主键大小整合目录页。目录页只包含1.数据页上最小的用户主键值。2.数据页的页号。如此，只要将目录页放在连续的内存中，即可快速通过主键查找到用户记录

InnoDB的索引——B+树

前置信息：由于面向的是真实的数据库用户，因此数据量有时会非常大。一个page只有16KB,别说用户记录了，就连目录项都有可能装不完。并且，如果数据页做了增删操作，那么所有目录项也需要做调整，这样非常浪费空间和资源。

因此，MySQL将数据页和目录页做一个复用，由于目录项和用户记录比较相似，因此让他们使用同一个页模版——0x45BF，即FIL_PAGE_INDEX。只使用一条属性record_type将二者区分。除此之外，页的结构、记录分组(槽)等等都是一样的（另外，page Header中信息自然时不一样的）。
如果数据量实在太多，一张16KB全部装着目录项的page也不够用，则产生页分裂，使用多个目录页来装；数据量巨大，连目录页都太多了，查找起来很慢，则会产生更高层次的目录，将目录页存储起来！这种结构，就称之为B+树。最顶端的节点是根节点，中间的节点为非叶子节点，而最底端的节点为叶子节点。所有的用户记录均被存储在叶子节点中。

像这种层级往上叠的结构，每增加一个层级，所能容纳的数据成几何倍数增长，一个数据页已经可以存放很多条用户记录了，一层数据页则可以更多，一层目录页更是数量爆炸！

一般情况下，我们用到B+树的层级不会超过4层，这样只需查找3个目录页+1个数据页+页内二分查找，即可快速定位记录。不要小看这4层的B+树，4层B+ 树已经可以存放千万级数据了，如果还想放再多数据，只能扩容或者加表

聚簇索引，具有以下两个特点的B+树称为聚簇索引：

使用记录主键的大小进行记录和页的排序
- 页内记录按住键大小排序形成单向链表结构，页内划成分组，每组最大记录的偏移量记录在槽中，放在页目录中。
- 数据页按页中用户记录的主键大小排序成双向链表（用于对主键的范围查找和分页查找）
- 目录页（存放目录项的数据页）分为不同层级，同层目录页根据页中住键大小顺序排列形成双向链表
叶子节点存储的是完整的用户记录，即不是二级索引，而是记录中存储了所有列的值（包括隐藏列）

只要我们的记录拥有以下特点，那么我们就不需要手动显式地使用INDEX创建索引，MYSQL会自动创建聚簇索引，在InnoDB中，聚簇索引就是数据的存储方式，即：索引即数据，数据即索引。

而从存储方面来说，索引和数据本身是存储在磁盘的，查询数据时会优先将索引加载在内存。索引存储的信息就是存放目录项的数据页。在一个磁盘块中，指针大小是固定的，因此当选择某字段当索引时，应该尽量减小键值所占用的空间，这样可以指数级地增加用于存放数据的空间

Mysql中的索引使用的是B+树，而为什么不使用其他数据结构做呢？

hash：哈希冲突；范围查询时需逐个遍历；对于内存空间要求高。mysql中也存在hash，即memory引擎使用的是hash索引，innodb支持自适应hash，即系统根据数据类型判断使用哪种存储结构
树
- 二叉树：无序
- BST：二叉查找树：插入时有序，左子树小于子树根节点，右子树大于子树根节点
- - 插入连续值时，可能退化成链表，时间复杂度提高
- AVL：平衡二叉查找树：有序，为了解决连续值退化的问题，通过左旋或右旋让树平衡，保持最短子树和最长子树高度不能超过1
- - 通过插入性能的损失来弥补查询性能的提升
- 红黑树：在旋转平衡的基础上，添加变色的行为。保持最长子树不超过最短子树的2倍即可。使得查询性能和插入性能近似一致
随着数据的插入，树的深度越来越深，意味着IO次数越多，影响数据读取的效率，因此使用开始使用树
- B树：多岔树，有序，非叶子节点也是存储着数据的，占用空间较大
- B+树：多岔树，有序，只有叶子节点存储着数据，非叶子节点存储的是指针

索引的创建跟存储引擎是挂钩的，存储引擎表示不同数据在磁盘的不同组织形式

在windows上的Mysql中，文件都是以不同后缀并成对的形式存在。数据结构用的都是B+树，而存储形式又有所不同

.frm：存放表结构
.MYD和.MYI：引擎是myisam，非聚簇索引。
- .MYD：数据，Data
- .MYI：索引，index
.ibd：存储数据+索引，即引擎是innodb。只能有一个聚簇索引，可以有很多非聚簇索引。在插入数据时，必须要包含一个索引的key值。这个索引的key值可以是主键；若没有主键也可以是唯一键；若唯一键也没有，就会有一个自生成的6字节的rowid（对用户不可见）

——聚簇索引与非聚簇索引——二者取决于数据和索引是否是放在一起的

——mysql表中有且至少有一个索引

索引覆盖：若查询结果包含普通索引列和聚簇索引列，则会直接返回，不需要从聚簇索引查询任何数据，这就叫索引覆盖

注：面试常问——在设置主键时是否需要自增？答：在满足业务需求的情况下，能自增尽量自增。因为自增是累加的，对前面的数据没有影响，无需做插入操作，也就无需做磁盘块/页分裂的操作（即：页分裂。当在一页数据里插入数据时，如果数据满了就需要分裂成多个页或者磁盘块来存储，父亲节点也可能需要分裂，而分裂会影响效率）。追加的效率较高

最左匹配：组合索引的匹配规则。若一张表里有两列是组合索引，那么使用时必须先匹配左侧的列，再匹配右侧列

select * fro table where name=? and age=? 允许使用
select * fro table where name=? 允许使用
select * fro table where age=? 无法使用
select * fro table where age=? and name=? 允许使用
只要查询条件是组合索引，那么就算顺序相反，mysql内部的优化器会调整对应的顺序

索引下推（mysql5.7后特性）：使用组合索引时，直接根据组合索引在存储引擎中获取对应数据，无需在server层二次过滤（5.7之前），减少了server层于存储引擎的交互，减少了IO量，提高了效率

聚簇索引的条件必须是以主键大小排序，即这个B+树的查询条件为主键。而如果以其他列作为查询条件，我们需要换一个树！重新新建一颗B+树，这个树采用其他列作为查询条件，而它的叶子节点并不会存放完整的用户记录，只会存放该列所在记录的主键。它的目录项也不会使用主键+页号，而是使用其他列+页号搭配。

二级索引的查询过程：

由于其他列可能没有唯一约束，所以匹配到的可能有多个主键（记录）。因此当查询到第一条记录后，我们通过查询到的主键到聚簇索引中查找完整的用户记录。这个过程（通过携带主键回到聚簇索引里查询完整的用户记录的过程）就叫回表。然后再返回到刚才的B+树，回到刚才定位到的那条用户记录，顺着记录所形成的单向链表找到其他符合条件的记录，然后再回表，再继续找……

回表的定义：根据普通索引查询到聚簇索引的key值之后，再根据key值在聚簇索引中获取所有行记录。回表走了2次B+树

由于这种以非主键列的大小为排序规则而建立的树需要执行回表才能查到完整用户记录，所以这种B+树也称为二级索引，这颗B+树是为其他列所建立的索引，该列是索引列。索引列记录的不是完整的用户信息。

数据存储在磁盘，一般情况况下查询速率慢，都是卡在IO上。因此需要在满足需求的前提下提高IO效率：

减少IO次数
减少IO量

profiling——mysql自带的性能分析工具（单条语句）

开启profiling：set profiling=1;
执行SQL语句，然后show profiles; 即可查出上条语句执行的实际时间
想要查询profiles结果表中具体某条语句的所有状态耗费时长，或者想查询某条语句的某个状态的使用情况，根据可使用profiles表语句对应的Query_ID来查询，语法如下：show profile for [type] query [id]。但这种查询方式在未来版本可能会被其他工具所取代