MySQL底层数据结构的深入分析_myisam 底层数据结构

目录

【二叉树】

【B树和B+树】

【Hash索引】

【MySQL的存储原理】

⾮聚簇索引（MyISAM）

聚簇索引（InnoDB）

【MySQL的底层存储原理】

【redo log 和 binlog】

【SQL语句的执行流程】

【存储引擎的选择】

【mysql基本设置相关命令】

【二叉树】

在之前的一篇文章 MySQL关于索引的理解_浮.尘的博客-CSDN博客 中提到了MySQL的MyISAM和InnoDB存储引擎的索引底层实际上是一个B+TREE（B+树），那么什么是B+树，今天就来简单说说。

在说B+树之前，先说说什么是二叉树，因为B+树是从二叉树演变过来的。

二叉树（Binary Tree）：二叉树的每个节点最多有两个子节点，分别是左子节点和右子节点。二叉树（Binary Tree）。二叉树的每个节点最多有两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。二叉树中，有两种比较特殊的树，分别是满二叉树和完全二叉树。满二叉树是完全二叉树的一种特殊情况。

 再比如下面的图就是一个简单的二叉树：

 其中1是根节点，2和3分别是1的左子树和右子树，4和5分别是2的左子树和右子树，6是3的右子树，3没有左子树。

一般遍历二叉树可以使用 前序遍历、中序遍历、后序遍历，其中，前、中、后序，表示的是节点与它的左右子树节点遍历的先后顺序。用递归代码来实现遍历的时间复杂度是 O(n)。（关于时间复杂度后面再讲）

• 前序遍历: 根节点 ---> 左子树 ---> 右子树
• 中序遍历: 左子树---> 根节点 ---> 右子树
• 后序遍历: 左子树 ---> 右子树 ---> 根节点

可以用代码实现一下做这个二叉树，这里用PHP代码实现一下，代码如下：

<?php
 
class BinaryTree1 {
    public $value;
    public $left;
    public $right;
}
 
/**
 * 前序遍历: 根节点 ---> 左子树 ---> 右子树
 */
function preorder($root) {
    if (empty($root)) {
        return;
    }
    echo $root->value . ' ';//输出根节点
    preOrder($root->left);
    preOrder($root->right);
}
 
/**
 * 中序遍历: 左子树---> 根节点 ---> 右子树
 */
function inorder($root) {
    if (empty($root)) {
        return;
    }
    inorder($root->left);
    echo $root->value . ' ';//输出根节点
    inorder($root->right);
}
 
/**
 * 后序遍历: 左子树 ---> 右子树 ---> 根节点
 */
function tailorder($root) {
    if (empty($root)) {
        return;
    }
    tailorder($root->left);
    tailorder($root->right);
    echo $root->value . ' ';//输出根节点
}
 
//测试
/*
      1
     / \
    2   3
   / \   \
  4   5   6
*/
 
$a = new BinaryTree1();
$b = new BinaryTree1();
$c = new BinaryTree1();
$d = new BinaryTree1();
$e = new BinaryTree1();
$f = new BinaryTree1();
 
$a->value = '1';
$b->value = '2';
$c->value = '3';
$d->value = '4';
$e->value = '5';
$f->value = '6';
 
$a->left = $b;
$a->right = $c;
$b->left = $d;
$b->right = $e;
$c->right = $f;
 
echo "前序遍历:";
preorder($a); //1 2 4 5 3 6
echo "\n";
 
echo "中序遍历:";
inorder($a);//4 2 5 1 3 6
echo "\n";
 
echo "后序遍历:";
tailorder($a);//4 5 2 6 3 1
echo "\n";

完整代码可以参考：https://gitee.com/rxbook/php_algo/blob/master/code18_BinaryTree2.php

虽然二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。原因是二叉树每个节点保存的数据较少，会增加IO操作。索引不止存在内存中，还要写到磁盘上。为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块。那么我们就不应该使用二叉树，而是要使用“N叉”树。这里，“N叉”树中的“N”取决于数据块的大小。

二叉树的基本原理就先说到这里，关于数据结构与算法的更多内容，后面再细说。接下来看看什么是B树和B+树。

【B树和B+树】

B树是为了磁盘或其它存储设备⽽设计的⼀种多叉平衡查找树，B树是⾮叶⼦节点和叶⼦节点都会存储数据。B树的⾼度⼀般都是在2-4这个⾼度，树的⾼度直接影响IO读写的次数。下面演示一下生成一颗B树的过程：

生成的B树可能是下面的结构：

 B+树是只有叶⼦节点才会存储数据，⽽且存储的数据都是在⼀⾏上，⽽且这些数据都是有指针指向的。下面演示一下生成一颗B+树和查找的过程：

怎么样，是不是很有趣，大家可以点这个链接自己去试一试：B+ Tree Visualization

• B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。
• B+ 树查询效率更稳定，因为 B+ 树每次只有访问到叶子节点才能找到对应的数据，而在 B 树中，非叶子节点也会存储数据，这样就会造成查询效率不稳定的情况，有时候访问到了非叶子节点就可以找到关键字，而有时需要访问到叶子节点才能找到关键字。
• B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。
• B+ 树的查询效率更高，这是因为通常 B+ 树比 B 树更矮胖（阶数更大，深度更低），查询所需要的磁盘 I/O 也会更少。同样的磁盘页大小，B+ 树可以存储更多的节点关键字。
• 不仅是对单个关键字的查询上，在查询范围上，B+ 树的效率也比 B 树高。这是因为所有关键字都出现在 B+ 树的叶子节点中，并通过有序链表进行了链接。而在 B 树中则需要通过中序遍历才能完成查询范围的查找，效率要低很多。
• 在构造索引的时候，我们更倾向于采用“矮胖”的数据结构（B+树），而不是“高瘦”的B树。

聚簇索引（InnoDB）：

#主键查询，只需要搜索id这棵B+树
select * from user where id=1;  #应该尽量使用主键查询
 
#普通索引查询，需要先搜索name索引树，得到id的值为1，再到上面的id索引树搜索一次，这个过程称为回表。也就是说，基于非主键索引的查询需要多扫描一棵索引树。
select * from user where name='renxing'; #回表查询，检索两次：⾮主键索引 —> 主键索引 —> 数据。
 
# 不需要回表，在辅助索引树上就可以查询到了，叫做覆盖索引，因此要多⽤组合索引。
select id,name from user where name='renxing'; 

ALTER TABLE table_name ADD INDEX index_name('name','age','sex'）;
select name,age,sex from table_name where name='xxx'; #实现覆盖索引，不需要回表。
## 组合索引遵循最左前缀原则：like a%能用到索引，like %a 用不到索引；

【MySQL的底层存储原理】

【SQL语句的执行流程】

一个 SQL 提交到数据库， 经过连接器将 SQL 语句交给语法分析器，生成一个抽象语法树 AST（Abstract Syntax Tree），AST 经过语义分析与 优化器，进行语义优化，使计算过程和需要获取的中间数据尽可能少，然后得到数据库执行计划；执行计划提交给具体的执行引擎进行计算，将结果通过连接器再返回给应用程序。

一条查询语句的执行过程一般是经过连接器、分析器、优化器、执行器等功能模块，最后到达存储引擎。简单地说就是：SQL 语句→缓存查询→解析器→优化器→执行器。（注意：MySQL8.0已经把缓存部分删掉了）

• 连接器：数据库连接器会为每个连接请求分配一块专用的内存空间用于会话上下文管理。建立连接对数据库而言相对比较重，需要花费一定的时间，因此应用程序启动的时候，通常会初始化建立一些数据库连接放在连接池里，这样当处理外部请求执行 SQL 操作的时候，就不需要花费时间建立连接了。所以对于一个大规模互联网应用集群来说，如果启动了很多应用程序实例，这些程序每个都会和数据库建立若干个连接，即使不提交 SQL 到数据库执行，也就会对数据库产生很大的压力。所以应用程序需要对数据库连接进行管理，一方面通过连接池对连接进行管理，空闲连接会被及时释放；另一方面微服务架构可以大大减少数据库连接。
• 语法分析器：当连接器收到 SQL 以后，会将 SQL 交给语法分析器进行处理，根据 SQL 语法规则生成对应的抽象语法树。语法分析器生成的抽象语法树不仅可以用来做语法校验，语义分析与优化器会对抽象语法树进一步做语义优化，也就是在保证 SQL 语义不变的前提下，进行语义等价转换，使最后的计算量和中间过程数据量尽可能小。下图所示就是一个SQL的抽象语法树。

SELECT语句的执行顺序：FROM > WHERE > GROUP BY > HAVING > 字段 > DISTINCT > ORDER BY > LIMIT。

比如对于这样一个 SQL 语句，其语义是表示从 users 表中取出每一个 id 和 order 表当前记录比较是否相等。

mysql> select f.id from orders f where f.user_id = (select id from users);

事实上，这个 SQL 语句在语义上等价于下面这条 SQL 语句，表间计算关系更加清晰。

mysql> select f.id from orders f join users u on f.user_id = u.id;

数据库里面的长连接是指连接成功后，如果客户端持续有请求则一直使用同一个连接。短连接则是指每次执行完很少的几次查询就断开连接，下次查询再重新建立一个。在使用中要尽量减少建立连接的动作，也就是尽量使用长连接。但是需要注意：定期断开长连接。使用一段时间，或者程序里面判断执行过一个占用内存的大查询后，断开连接，之后要查询再重连。

客户端如果太长时间没动静，连接器就会自动将它断开。这个时间是由参数 wait_timeout 控制的，默认值是 8 小时。如果在连接被断开之后，客户端再次发送请求的话，就会收到一个错误提醒： Lost connection to MySQL server during query。这时候如果你要继续使用mysql，就需要重连，然后再执行请求。

如果查询命中缓存，MySQL 不需要执行后面的复杂操作就可以直接返回结果，这个效率会很高。查询缓存可以看做是SQL文本和查询结果的映射，第二次查询的SQL和第一次查询的SQL完全相同，则会使用缓存。表的结构或数据发生改变时，查询缓存中的数据不再有效。mysql中关于缓存的配置和命令如下：

query_cache_type  #查询缓存类型，有0、1、2三个取值。0则不使用查询缓存。1表示始终使用查询缓存。2表示按需使用查询缓存。
query_cache_type  #为1时，也可以手动关闭查询缓存：SELECT SQL_NO_CACHE * FROM my_table WHERE condition;
query_cache_type  #为2时，按需查询缓存：SELECT SQL_CACHE * FROM my_table WHERE condition;
query_cache_size  #默认情况下值为0，表示为查询缓存预留的内存为0，则无法使用查询缓存。
 
SHOW STATUS LIKE 'Qcache_hits';   #查看缓存命中次数
FLUSH QUERY CACHE;  #清理查询缓存内存碎片
RESET QUERY CACHE;  #从查询缓存中移出所有查询
FLUSH TABLES;  #关闭所有打开的表，同时该操作将会清空查询缓存中的内容

但是大多数情况下不要使用查询缓存，因为查询缓存的失效非常频繁，只要有对一个表的更新，这个表上所有的查询缓存都会被清空。可以将参数 query_cache_type 设置成 DEMAND，这样对于默认的 SQL 语句都不使用查询缓存。可以用 SQL_CACHE 显式指定，像下面这个语句一样：

mysql> select SQL_CACHE * from T where ID=10;

 需要注意的是，MySQL 8.0 版本直接将查询缓存的整块功能删掉了，也就是说 8.0 开始彻底没有这个功能了。

优化器 是在表里面有多个索引的时候，决定使用哪个索引；或者在一个语句有多表关联（join）的时候，决定各个表的连接顺序。

【存储引擎的选择】

MySQL的存储引擎有：MyISAM、InnoDB、Memory、Archive、Blackhole、CSV。

InnoDB的特点：

• 适合大量的读取和大量的更新操作，数据量大，并发量高；
• 性能优秀，数据存储在共享表空间，支持高并发，使用聚簇索引；
• 支持崩溃后的安全恢复，支持行级锁，支持外键，支持事务，支持MVCC；
• 从磁盘读取数据时自动在内存构建hash索引，插入数据时自动构建插入缓冲区；

MyISAM：

• 大量读取，少量更新，数据量小，并发不高，查询速度快；
• 支持表级锁，不支持行级锁，不支持事务，使用非聚簇索引；
• 支持全文索引（仅限英文）；

应用场景：

• MyIASM管理非事务表，提供高速存储和检索以及全文搜索能力，如果再应用中执行大量select操作，update较少，并发不高，不需要事务，数据量小，应该选择MyIASM；
• InnoDB用于事务处理，具有ACID事务支持等特性，如果在应用中执行大量insert和update操作，读取和写入差不多，频繁更新大字段，并发高，安全性和可用性要求高，应该选择InnoDB；

【问】为什么MyISAM会比Innodb 的查询速度快？

【答】InnoDB 在做SELECT的时候，要维护的东西比MYISAM引擎多很多：

（1）InnoDB 要缓存数据和索引，MyISAM只缓存索引块，这中间还有换进换出的减少

（2）innodb寻址要映射到块，再到行，MyISAM记录的直接是文件的OFFSET，定位比INNODB要快

（3）InnoDB 还需要维护MVCC一致；就算你没有用到，但还是需要去检查和维护

Memory：如果只是临时存放数据，数据量不大，并且不需要较高的数据安全性，可以选择将数据保存在内存中的Memory引擎，MySQL中使用该引擎作为临时表，存放查询的中间结果。数据的处理速度很快但是安全性不高。一般用得不多，可以使用redis来代替。

Archive：如果只有INSERT和SELECT操作，可以选择Archive，Archive支持高并发的插入操作，但是本身不是事务安全的。Archive非常适合存储归档数据，如记录日志信息可以使用Archive。

【mysql基本设置相关命令】

# 查看mysql提供什么存储引擎:  
show engines;
 
# 查看默认的存储引擎:
show variables like '%storage_engine%'; 或 SELECT @@default_storage_engine;
 
# 修改默认的存储引擎：
SET DEFAULT_STORAGE_ENGINE=MyISAM; 或者修改 my.cnf
 
# 修改数据表存储引擎：
ALTER TABLE engine_demo_table ENGINE = InnoDB;
 
# 查询MySQL数据库服务器的性能参数、执行频率: 
SHOW [GLOBAL|SESSION] STATUS LIKE '参数';
   
#常用的性能参数如下: 
Connections //连接MySQL服务器的次数。 
Uptime //MySQL服务器的上 线时间。 
Slow_queries //慢查询的次数。 
Innodb_rows_read:Select //查询返回的行数 
Innodb_rows_inserted //执行INSERT操作插入的行数 
Innodb_rows_updated //执行UPDATE操作更新的行数 
Innodb_rows_deleted //执行DELETE操作删除的行数 
Com_select //查询操作的次数。 
Com_insert //插入操作的次数。对于批量插入的 INSERT 操作，只累加一次。 
Com_update //更新操作的次数。 
Com_delete //删除操作的次数。
 
# 统计SQL的查询成本: 
SHOW STATUS LIKE 'last_query_cost';
 
# 开启慢查询日志参数: 
set global slow_query_log='ON'; #开启slow_query_log
show variables like '%long_query_time%'; #修改long_query_time阈值 
 
# 查询当前系统中有多少条慢查询记录: 
SHOW GLOBAL STATUS LIKE '%Slow_queries%';
 
# 慢查询日志分析工具: 
mysqldumpslow
 
# 查看 SQL 执行成本: 
show variables like 'profiling';
 
# 开启 show profile: 
set profiling = 'ON';
 
# 当前会话都有哪些 profiles: 
show profiles;
 
# 慢查询日志是否打开
show variables like '%slow'    
 
# 查看MySQL允许的最大连接数
show variables like 'max_connections'   
 
# 系统当前状态,com_xxx表示xxx语句执行的次数，例如com_select.
show global status 
 
# 查看慢查询的条数
show global status like '%slow'   
 
# 查看索引的使用情况：
show status like 'Handler_read%'    
 
# 显示当前所有连接的工作状态
show processlist;

慢查询相关：

mysql > show variables like '%slow_query_log'; #先看下慢查询是否已经开启
mysql > set global slow_query_log='ON'; #把慢查询日志打开，注意设置变量值的时候需要使用 global
mysql > show variables like '%long_query_time%'; #查看慢查询的时间阈值设置
mysql > set global long_query_time = 3; #如果想把时间缩短，比如设置为 3 秒
 

可以使用 MySQL 自带的 mysqldumpslow 工具统计慢查询日志: perl mysqldumpslow.pl -s t -t 2 "/tmp/slow.log”

能看到开启了慢查询日志，并设置了相应的慢查询时间阈值之后，只要大于这个阈值的 SQL 语句都会保存在慢查询日志中，然后就可以通过 mysqldumpslow 工具提取想要查找的 SQL 语句了。

MySQL 对一条 SQL 语句的执行时间进行分析:

【日拱一卒，再小的坚持也是进步！】