1. 索引的数据结构

索引是帮助MySQL高效获取数据的排好序的数据结构，索引可以减少磁盘I/O的次数，加快查询效率。
索引是在存储引擎中实现的，每种存储引擎的索引不一定相同。
索引的数据结构：
二叉树：缺点可能退化成链表
红黑树：层数可能会很深
Hash表：查找速度快，但是不支持范围查询
B-Tree：

• 叶节点具有相同的深度，叶节点的指针为空
• 所有索引元素不重复
• 节点中的数据索引从左到右递增排列

优点：每一层可以存储更多的数据元素，降低树高，可以有效减少比较时的磁盘IO。
MySQL底层真正存储结构——B+Tree

• 非叶子节点不存储data，只存储索引（冗余），每一层可以放更多的索引（非叶子节点叫做目录页）
• 叶子节点包含所有索引字段（叶子节点叫做普通的用户记录页）
• 叶子节点用指针连接（即用户记录页用指针连接），提高区间访问性能
• 每个页中的数据也是用指针连接
• 目录页与用户记录页都会为主键生成页目录，从而按照主键值进行查找时可以使用二分法来加快查询速度。

优点：每一层可以存储的数据量大，树高小，区间访问能力强
B+Tree底层如何查找元素：
非叶子节点会先load进内存，然后在内存中逐个比对，直至查找到最终的元素

B-Tree与B+Tree的区别：

• B-Tree的数据遍布在每一个节点，B+Tree的数据只存放在叶子节点，非叶子节点值存储冗余索引（每一层可以存放的数据增多，降低了树高，树高为三时就可以存储千万级别的数据）
• B+Tree叶子节点用指针连接，提高区间访问性能

为什么不直接将所有数据分配在一层，直接将这层数据load进内存进行比较呢？
数据量大的时候load进内存时比较的速度不一定快，并且内存空间不允许。分层的话每次load进内存的数据量较少，比较的速度快。

B+树的存储能力如何？为何说一般查找行记录，最多只需1~3次磁盘IO？

2. MyISAM与InnoDB索引结构比较

MyISAM索引文件和数据文件是分离的（非聚集）
索引文件：MYI
数据文件：MYD

叶子节点存储的数据是索引所在行的磁盘文件地址

InnoDB索引实现（聚集）查找效率高于非聚集索引

• 表数据文件本身就是按B+tree组织的一个索引结构文件
• 使用的是聚集索引，叶子节点包含了完整的数据记录

非主键索引的叶子节点存储的数据是主键，最后会按照这个主键再去主键索引的B+Tree中找到最终的数据。
为什么非主键索引的叶子节点不直接存储数据？
节省空间，考虑修改时的一致性。

聚集索引的特点

1. 使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义：

• 页内的记录是按照主键的大小顺序排成一个单向链表。
• 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。
• 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。

1. B+树的叶子节点存储的是完整的用户记录。

聚集索引的优点
聚集索引的查询速度非常的快，因为整个 B+树本身就是一颗多叉平衡树，叶子节点也都是有序的，定位到索引的节点，就相当于定位到了数据。

聚集索引的缺点
更新代价大 ： 如果对索引列的数据被修改时，那么对应的索引也将会被修改， 而且况聚集索引的叶子节点还存放着数据，修改代价肯定是较大的， 所以对于主键索引来说，主键一般都是不可被修改的。

非聚集索引的优点
更新代价比聚集索引要小 。非聚集索引的更新代价就没有聚集索引那么大了，非聚集索引的叶子节点是不存放数据的

非聚集索引的缺点
可能会二次查询(回表) :这应该是非聚集索引最大的缺点了。 当查到索引对应的指针或主键后，可能还需要根据指针或主键再到数据文件或表中查询。

非聚集索引不一定回表查询。
特殊情况：使用了覆盖索引，用户准备使用 SQL 查询的字段，而该字段正好建立了索引。

为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？
因为底层会根据这个主键建立B+Tree，这课B+Tree的叶子节点存储了索引所在行的所有数据，如果没有建立主键，MySQL底层会自动寻找一列元素都是唯一的列，根据这列建立B+Tree，如果找不到这个列，MySQL底层会新增一个隐藏列，这个隐藏列每个元素唯一，根据这个隐藏列建立B+Tree，但是这样子会影响性能，因此需要建议自己建主键。
推荐使用整型主键因为整型数据比较速度快，并且整型所占空间小，使用自增主键时在建立B+Tree时性能高，减小节点分裂和树平衡的操作，提高效率。

为什么不用UUID：
自增ID有序，会按顺序往最后插入，而UUID无序，随机生成，随机插入，会造成频繁页分裂导致移动大量数据，内存碎片化，大量随机IO。

MyISAM 与 InnoDB对比：
MyISAM的索引方式都是“非聚簇”的，与InnoDB包含1个聚簇索引是不同的。小结两种引擎中索引的区别：

1. 在InnoDB存储引擎中，我们只需要根据主键值对聚簇索引进行一次查找就能找到对应的记录，而在MyISAM中却需要进行一次回表操作，意味着MyISAM中建立的索引相当于全部都是二级索引。
2. InnoDB的数据文件本身就是索引文件，而MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。
3. InnoDB的非聚簇索引data域存储相应记录主键的值，而MyISAM索引记录的是地址。换句话说，InnoDB的所有非聚簇索引都引用主键作为data域。
4. MyISAM的回表操作是十分快速的，因为是拿着地址偏移量直接到文件中取数据的，反观InnoDB是通过获取主键之后再去聚簇索引里找记录，虽然说也不慢，但还是比不上直接用地址去访问。
5. InnoDB要求表必须有主键（MyISAM可以没有）。如果没有显式指定，则MySQL系统会自动选择一个可以非空且唯一标识数据记录的列作为主键。如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。

主键索引与唯一索引的区别：

• 一个表最多只能创建一个主键，但是可以有多个唯一索引。
• 底层上的区别：主键索引的叶子节点带有数据，唯一索引叶子节点存放索引列+主键，没有存放其他数据。

唯一索引与普通索引的选择
查询情况下：二者性能差不多
插入情况下：

3. 联合索引底层存储结构

按照索引从左到右的顺序依次排序，相同则比较下一个索引。
最左前缀原则底层原理：
联合索引的底层是按照索引从左到右的顺序依次排序，相同则比较下一个索引。如果跳过前置索引，直接进行下一个索引比较，则无法保证索引从左到右依次递增，（下一个索引有序的前提是上一个索引元素相同），因此无法定位到目标字段，需要进行全索引扫描。

4. 覆盖索引

如果一个索引包含（或者说覆盖）所有需要查询的字段的值，我们就称之为“覆盖索引”。我们知道在 InnoDB 存储引擎中，如果不是主键索引，叶子节点存储的是主键+列值。最终还是要“回表”，也就是要通过主键再查找一次。这样就会比较慢覆盖索引就是把要查询出的列和索引是对应的，不做回表操作！

5. Buffer Pool

数据库中的Buffer Pool是个什么东西？其实他是一个非常关键的组件，数据库中的数据实际上最终都是要存放在磁盘文件上的，如下图所示。

我们在对数据库执行增删改操作的时候，不可能直接更新磁盘上的数据的，因为如果你对磁盘进行随机读写操作，那速度是相当的慢，随便一个大磁盘文件的随机读写操作，可能都要几百毫秒。如果要是那么搞的话，可能你的数据库每秒也就只能处理几百个请求了！在对数据库执行增删改操作的时候，实际上主要都是针对内存里的Buffer Pool中的数据进行的，也就是实际上主要是对数据库的内存里的数据结构进行了增删改
其实每个人都担心一个事，就是你在数据库的内存里执行了一堆增删改的操作，内存数据是更新了，但是这个时候如果数据库突然崩溃了，那么内存里更新好的数据不是都没了吗？MySQL就怕这个问题，所以引入了一个redo log机制，你在对内存里的数据进行增删改的时候，他同时会把增删改对应的日志写入redo log中.
万一你的数据库突然崩溃了，没关系，只要从redo log日志文件里读取出来你之前做过哪些增删改操作，瞬间就可以重新把这些增删改操作在你的内存里执行一遍，这就可以恢复出来你之前做过哪些增删改操作了。

为什么Mysql不能直接更新磁盘上的数据而且设置这么一套复杂的机制来执行SQL了？
因为来一个请求就直接对磁盘文件进行随机读写，然后更新磁盘文件里的数据性能可能相当差。
因为磁盘随机读写的性能是非常差的，所以直接更新磁盘文件是不能让数据库抗住很高并发的。
Mysql这套机制看起来复杂，但它可以保证每个更新请求都是更新内存BufferPool，然后顺序写日志文件，同时还能保证各种异常情况下的数据一致性。
更新内存的性能是极高的，然后顺序写磁盘上的日志文件的性能也是非常高的，要远高于随机读写磁盘文件。
正是通过这套机制，才能让我们的MySQL数据库在较高配置的机器上每秒可以抗下几干的读写请求。

顺序读写效率远高于随机读写。

Buffer Pool内存数据结构

如何配置你的Buffer Pool的大小

Buffer Pool本质其实就是数据库的一个内存组件，你可以理解为他就是一片内存数据结构，所以这个内存数据结构肯定是有一定的大小的，不可能是无限大的。这个Buffer Pool默认情况下是128MB，还是有一点偏小了，我们实际生产环境下完全可以对Buffer Pool进行调整。比如我们的数据库如果是16核32G的机器，那么你就可以给Buffer Pool分配个2GB的内存，使用下面的配置就可以了。[server]innodb_buffer_pool_size = 2147483648。

数据页：MySQL中抽象出来的数据单位

我们都知道数据库的核心数据模型就是 表+字段+行 的概念，所以大家觉得我们的数据是一行一行的放在Buffer Pool里面的吗？这就明显不是了，实际上MySQL对数据抽象出来了一个数据页的概念，他是把很多行数据放在了一个数据页里，也就是说我们的磁盘文件中就是会有很多的数据页，每一页数据里放了很多行数据，如下图所示。

所以实际上假设我们要更新一行数据，此时数据库会找到这行数据所在的数据页，然后从磁盘文件里把这行数据所在的数据页直接给加载到Buffer Pool里去。也就是说，Buffer Pool中存放的是一个一个的数据页，如下图。

磁盘上的数据页和Buffer Pool中的缓存页是如何对应起来的？

实际上默认情况下，磁盘中存放的数据页的大小是16KB，也就是说，一页数据包含了16KB的内容。而Buffer Pool中存放的一个一个的数据页，我们通常叫做缓存页，因为毕竟Buffer Pool是一个缓冲池，里面的数据都是从磁盘缓存到内存去的。而Buffer Pool中默认情况下，一个缓存页的大小和磁盘上的一个数据页的大小是一一对应起来的，都是16KB。

如果一行的数据大于16KB怎么办？
大于16KB的数据会用溢出页保存，而当前页中保存溢出页的地址。

三个链表

free链表：保存Buffer Pool中的空闲内存区域
flush链表：更新数据并不是直接在磁盘上更新的，而是更新Buffer Pool上的缓存页中的数据，但是最终还是需要持久化到磁盘中，flush链表就是保存那些有数据更新的缓存页。
LRU链表：用于淘汰缓冲池中的缓存页。

Buffer Pool的缓存页淘汰机制

什么是预读？
磁盘读写，并不是按需读取，而是按页读取，一次至少读一页数据（一般是 4K），如果未来要读取的数据就在页中，就能够省去后续的磁盘 IO，提高效率。

预读为什么有效？
数据访问，通常都遵循 “集中读写” 的原则，使用一些数据，大概率会使用附近的数据，这就是所谓的“局部性原理”，它表明提前加载是有效的，确实能够减少磁盘 IO。

为什么MySQL不使用传统的LRU？
传统的LRU会造成缓冲池污染：当某一个 SQL 语句，要批量扫描大量数据时，可能导致把缓冲池的所有页都替换出去，导致大量热数据被换出，MySQL 性能急剧下降，这种情况叫缓冲池污染。例如执行select *语句。

MySQL优化的LRU算法：

将整个链表分成热数据区和冷数据区：默认5:3。

• 新加入的数据块加入冷数据的头
• 被访问的冷数据块如果不是在冷数据区的头，则会加到冷数据区的头

冷数据区什么时候升到热数据区：两次访问同一个数据块的时间大于1s。为什么这么设计？举个例子，select *这种语句执行时，同一块数据块的相邻两次访问的时间很短，但是不能表示这个数据块在未来会被频繁使用，如果两次访问时间大于1s，有经验值可知这个数据块可能会被频繁使用，所以加入热数据区。