索引B+树的理解和坑

MYSQL单表数据达2000万性能严重下降，为什么？

在中国互联网技术圈流传着这么一个说法：MySQL 单表数据量大于 2000 万行，性能会明显下降。

可是，根据以往经验，社交产品，用户互相点赞关注的关系表，数据1亿9千万条且没有进行分表，甚至分区表都没有。
但是并没有感觉到明显的卡顿，也没有慢日志出现，跟这个说法明显相悖，这是为什么呢？

讨论这个差异先看另外个问题：InnoDB一棵B+树可以存放多少行数据？

B+树数据结构

要讨论这个问题我们首先来看MySQL InnoDB 引擎的数据存储方式：
1. InnoDB 存储引擎的最小存储单元是页（默认每页大小16kb），在B+树中叶子节点存放数据，非叶子节点存放键值+指针。
2. 索引组织表通过非叶子节点的二分查找法以及指针确定数据在哪个页中，进而在去数据页中查找到需要的数据。

叶子节点大概的数据存储量

接下来我们估算一下叶子节点大概的数据存储量：

假设主键ID为bigint类型，8字节。

假设一行数据大小为1K左右。

这样我们那么一个页可以存放 16 行这样的数据。

数据页16K是一个包含文件头/页头/页尾等结构的数据页。

所以以上只是估算。

非叶子节点大概的存储量

再来估算非叶子节点大概的存储量：
假设主键 ID 为 bigint 类型，长度为 8 字节，而指针大小在 InnoDB 源码中设置为 6 字节，这样一共 14 字节，我们一个页中能存放多少这样的单元，其实就代表有多少指针，即 16384/14=1170。

所以我们每个非叶子结点最多有1170个子节点。

那么可以算出一棵高度为 2 的 B+ 树，能存放 1170*16=18720 条这样的数据记录。

根据同样的原理我们可以算出一个高度为 3 的 B+ 树可以存放： 1170*1170*16=21902400 （2100万）条这样的记录。

那如果四层呢：那就是1170*1170*1170*16=256亿。

如果主键只是int，长度为4字节呢？一个页中就能能存放 16384/10=1638个子节点。

高度为2的B+树能存放 1638*16=26208 条这样的数据记录。

根据同样的原理我们可以算出一个高度为 3 的 B+ 树可以存放： 1638*1638*16=42928704 （4200万）条这样的记录。

而且上面我们假设的是一行数据的大小为1KB，但是如果一行数据只有512字节呢，那么数量还能再翻倍。

至此，我们都不要再继续第四层的数量，就可以得出 “MySQL 单表数据量大于 2000 万行，性能会明显下降。”这个论调纯属扯淡的结论。bullshit!

这里，需要注意的是，在机械硬盘时代，随机磁盘IO确实会成为瓶颈，三次磁盘IO和四次磁盘IO可能确实会有明显感觉。
但现在内存比硬盘大的时代，足以将整个数据表加载到内存中，磁盘的随机IO早已不是瓶颈。
所以“MySQL 单表数据量大于 2000 万行，性能会明显下降。”已经纯属无稽之谈。

大数据表实操：

表内总计一亿多条数据，未分表，未分区：

explain查看索引命中情况：

执行数据查询，查看执行时长：

MySQL InnoDB一颗B+树能存多少数据？

根据上面的计算过程：
三层的B+树，主键为8字节时，1170*1170*16=21902400；主键为4字节时，1638*1638*16=42928704
四层的B+树，主键为8字节时，1170*1170*1170*16=256亿；主键为4字节时，1638*1638*1638*16=706亿

MySQL InnoDB的B+树每个非叶子结点能有多少分支？

如果我们的主键是bigint类型（8字节），16384/(8+6)=1170。
如果我们的主键是int类型（4字节），那就是16348/(4+6)=1634。

如果你使用占用空间更大的字符串比如UUID，那么数量会更少，需要根据具体的空间占用进行计算。

MySQL InnoDB为什么使用B+树而非B树/Hash？

B树 B树和B+树最重要的一个区别就是B+树只有叶节点存放数据，其余节点用来索引，而B树是每个索引节点都会存数据。
存数据意味着用来索引的空间变少，每个节点的子节点变少，想要存放同样的数据量需要更多的层数，更多的磁盘IO次数。 同时对范围查找无法像B+数那样通过链表直接串联起来那么方便。

Hash Hash的检索效率非常高，但是Hash只能满足 “=”, “IN” 等查询，不能使用范围查询。 同时Hash无法利用索引的数据来进行排序。

MySQL InnoDB为什么推荐使用自增ID做主键？

如果主键是自增ID，那么就在一页插入满才插入下一页。
如果主键不是自增ID，为了保持B+树的有序，会造成频繁的页分裂和页旋转，插入速度比较慢。

主键占用空间越大，每个页存储的主键个数越少，B+树的深度会变长，导致IO次数会变多。
普通索引的叶子节点上保存的是主键 id 的值，如果主键 id 占空间较大的话，那将会成倍增加 MySQL 空间占用大小。

Buffer Pool

基本概念

缓冲池，也称BP。
由缓存数据页（Page）和对缓存数据页进行描述的控制块组成，
控制块中存储着对应缓存页的的所属的表空间、数据页的编号、以及对应缓存页在Buffer Pool中的地址等信息。

大小

以Page页为单位，Page页默认大小16K，默认缓冲池大小一般设置为实例内存的四分之三。
控制块的大小约为数据页的5%，大概800字节

作用

缓存表数据与索引数据，减少磁盘IO，提升性能。

如何判断一个页是否在BufferPool中缓存？

Mysql中有一个哈希表数据结构，它使用表空间号+数据页号，作为一个key，然后缓冲页对应的控制块作为value。

当需要访问某个页的数据时，先从哈希表中根据表空间号+页号看看是否存在对应的缓冲页。
有，则直接使用；没有，则从free链表中选出一个空间的缓冲页
再将磁盘中对应的页加载到该缓冲页的位置。

InnoDB与MyISAM的区别

1 事务和外键

InnoDB：支持事务和外键，具有安全性和完整性，适合大量insert和update操作。
MyISAM：不支持事务和外键，提供告诉存储和检索，适合大量select操作。

2 锁机制

InnoDB：支持行级锁，锁定指定记录。基于索引来加锁实现。
MyISAM：支持表级锁，锁定整张表。

3 索引结构

InnoDB：使用聚集索引（聚簇索引），索引和记录在一起存储。
MyISAM：使用非聚集索引（非聚簇索引），所以你和记录分开。

4 并发处理能力

InnoDB：读写阻塞可以与隔离级别有关，可以采用多版本并发控制（MVCC）来支持高并发。
MyISAM：使用表锁，会导致写操作并发率低，读之间并不阻塞。

5 存储文件

InnoDB：表对应两个文件，一个.frm表结构文件，一个.ibd数据文件。最大支持64TB。
MyISAM：表对应三个文件，一个.frm表结构文件，一个MYD表数据文件，一个.MYI索引文件。从MySQL5.0开始默认限制时256TB。

6 InnoDB适用场景

需要事务支持（具有较好的事务特性）
行级锁定对高并发有很好的适应能力
数据更新较为频繁的场景
数据一致性要求较高
硬件设备内存较大，可以利用InnoDB较好的缓存能力来提高内存利用率，减少磁盘IO

7 MyISAM适用场景

不需要事务支持
并发相对较低（锁定机制问题）
数据修改相对较少，以读为主
数据一致性要求不高

并发事务带来了哪些问题？

（1）脏读：一个事务对数据进行了修改，还未提交到数据库；另一个事务使用了未修改的数据，依据这个脏数据所做的操作可能是不正确的。
（2）丢失修改：两个事务同时访问并修改同一个数据，那么第一个事务修改的结果就会被丢失。
（3）不可重复读：在一个事务内多次读取同一数据。在这个事务结束之前，另一个事务进修改了数据，那么第一个事务两次读取的数据就会不一样了。
（4）幻读：发生在一个事务读取了几行数据，接着另一个并发事务插入了一些数据，在随后的查询中，第一个事务就会发现多了一些原本不存在的数据。

MySQL视图

为什么要使用视图？什么是视图？

为了提高复杂SQL语句的复用性和表操作的安全性。
一种虚拟表，在物理上是不存在的，其内容与真实的表相似，包含一系列带有名称的列和行数据。
视图并不在数据库中以储存的数据值形式存在。行和列数据来自定义视图的查询所引用基本表，并且在具体引用视图时动态生成。

视图有哪些特点？

视图的列可以来自不同的表，是表的抽象和在逻辑意义上建立的新关系。
视图是由基本表(实表)产生的表(虚表)。
视图的建立和删除不影响基本表。
对视图内容的更新(添加，删除和修改)直接影响基本表。
当视图来自多个基本表时，不允许添加和删除数据。

视图的使用场景

重用SQL语句；
简化复杂的SQL操作。在编写查询后，可以方便的重用它而不必知道它的基本查询细节；
使用表的组成部分而不是整个表；
保护数据。可以给用户授予表的特定部分的访问权限而不是整个表的访问权限；
更改数据格式和表示。视图可返回与底层表的表示和格式不同的数据。

视图的优缺点

优点：

查询简单化。视图能简化用户的操作
数据安全性。视图使用户能以多种角度看待同一数据，能够对机密数据提供安全保护
逻辑数据独立性。视图对重构数据库提供了一定程度的逻辑独立性

缺点：

性能。数据库必须把视图的查询转化成对基本表的查询，如果这个视图是由一个复杂的多表查询所定义，那么，即使是视图的一个简单查询，数据库也把它变成一个复杂的结合体，需要花费一定的时间。

修改限制。当用户试图修改视图的某些行时，数据库必须把它转化为对基本表的某些行的修改。事实上，当从视图中插入或者删除时，情况也是这样。对于简单视图来说，这是很方便的，但是，对于比较复杂的视图，可能是不可修改的

这些视图有如下特征：1.有UNIQUE等集合操作符的视图。2.有GROUP BY子句的视图。3.有诸如AVG\SUM\MAX等聚合函数的视图。 4.使用DISTINCT关键字的视图。5.连接表的视图（其中有些例外）

大表数据查询优化思路

优化shema、sql语句+索引；
第二加缓存，memcached, redis；
主从复制，读写分离；
垂直拆分，根据你模块的耦合度，将一个大的系统分为多个小的系统，也就是分布式系统；
水平切分，针对数据量大的表，这一步最麻烦，最能考验技术水平，要选择一个合理的sharding key, 为了有好的查询效率，表结构也要改动，做一定的冗余，应用也要改，sql中尽量带sharding key，将数据定位到限定的表上去查，而不是扫描全部的表；
数据库层面,这也是我们主要集中关注的(虽然收效没那么大),类似于select * from table where age > 20 limit 1000000,10这种查询其实也是有可以优化的余地的. 这条语句需要load1000000数据然后基本上全部丢弃,只取10条当然比较慢. 当时我们可以修改为select * from table where id in (select id from table where age > 20 limit 1000000,10).这样虽然也load了一百万的数据,但是由于索引覆盖,要查询的所有字段都在索引中,所以速度会很快. 同时如果ID连续的好,我们还可以select * from table where id > 1000000 limit 10,效率也是不错的,优化的可能性有许多种,但是核心思想都一样,就是减少load的数据.
从需求的角度减少这种请求…主要是不做类似的需求(直接跳转到几百万页之后的具体某一页.只允许逐页查看或者按照给定的路线走,这样可预测,可缓存)以及防止ID泄漏且连续被人恶意攻击.

底层原理八股文

一条SQL查询语句是如何执行的？

1. 客户端连接到连接器，进行鉴权，并由连接器进行权限控制。
2. 查询缓存，如果命中缓存，直接返回结果给客户端。
3. 如果没有命中缓存，进入分析器对SQL语句进行词法，语法分析，如果分析不通过，存在语法错误，则返回错误给到客户端。
4. 词法语法分析通过后进入优化器，生成执行计划，选择优化器认为最优的索引或客户端指定的索引。
5. 进入执行器执行，操作引擎进行执行，返回结果给客户端；这里还会再次确定有没有对表的查询权限。

MySQL 可以分为 Server 层和存储引擎层两部分。

Server 层包括连接器、查询缓存、分析器、优化器、执行器等，涵盖 MySQL 的大多数核心服务功能，以及所有的内置函数（如日期、时间、数学和加密函数等），所有跨存储引擎的功能都在这一层实现，比如存储过程、触发器、视图等。

而存储引擎层负责数据的存储和提取。其架构模式是插件式的，支持 InnoDB、MyISAM、Memory 等多个存储引擎。现在最常用的存储引擎是 InnoDB，它从 MySQL 5.5.5 版本开始成为了默认存储引擎。

一条SQL更新语句是如何执行的？

1. 连接器：
客户端连接到连接器，进行鉴权，并由连接器进行权限控制。

2. 语法和语义解析：
MySQL首先对更新语句进行语法解析，验证语句的正确性，并将其转换为内部的数据结构（解析树）表示。
接下来，MySQL进行语义分析，检查表名、列名、函数等是否存在，并对其进行访问权限验证。

3. 查询优化：
在执行更新操作之前，MySQL会进行查询优化，根据更新语句的逻辑和物理特性选择最优的查询计划。这包括选择合适的索引、决定连接顺序、使用合适的算法等。

4. 执行查询计划：
MySQL根据优化器生成的查询计划执行更新操作。
执行过程涉及以下主要步骤：
锁定数据：MySQL会获取合适的锁来保证更新操作的一致性和并发控制。这可以防止其他会话对正在更新的数据进行干扰。
检索数据：MySQL根据更新语句的条件定位并检索需要更新的数据。
更新数据：MySQL对检索到的数据进行修改，根据更新语句指定的值或表达式进行更新操作。
写入日志和持久化：MySQL会将更新操作写入事务日志，以支持数据的恢复和持久化存储。

5. 提交事务：
如果更新语句在一个事务中执行，MySQL会在更新操作完成后提交事务，将更新结果永久保存到数据库中。

怎么减少行锁对性能的影响？

1. 在事务中尽可能的将可能产生锁冲突的语句往后放。
2. 控制并发量来减少死锁检测的CPU占用量。

https://pdai.tech/md/db/sql-mysql/sql-mysql-mvcc.html
https://lianglianglee.com/%E4%B8%93%E6%A0%8F/MySQL%E5%AE%9E%E6%88%9845%E8%AE%B2/00%20%E5%BC%80%E7%AF%87%E8%AF%8D%20%20%E8%BF%99%E4%B8%80%E6%AC%A1%EF%BC%8C%E8%AE%A9%E6%88%91%E4%BB%AC%E4%B8%80%E8%B5%B7%E6%9D%A5%E6%90%9E%E6%87%82MySQL.md

程序猿老龚（龚杰洪）原创，版权所有，转载请注明出处.