MySQL底层原理

    二叉树：当不平衡时，单边增长，可能退化为线性

    红黑树：数据量大时，深度不可控

    AVL树：相比较与红黑树，严格平衡，但是增删情况下，通过旋转再平衡的开销过大，适合查找场景多的应用

    Hash： 不支持范围查找

    平衡的多路查找树，一个结点存放多个元素。

与红黑树相比，在相同的的节点的情况下，一颗B/B+树的高度远远小于红黑树的高度(在下面B/B+树的性能分析中会提到)。B/B+树上 *** 作的时间通常由存取磁盘的时间和CPU计算时间这两部分构成，而CPU的速度非常快，所以B树的 *** 作效率取决于访问磁盘的次数，关键字总数相同的情况下B树的高度越小，磁盘I/O所花的时间越少。

    m阶：节点中，子节点数的最大值（子节点数，不是结点存放元素）

1. 树中每个结点最多m个子树（最多m-1个关键字，两个子树夹一个关键字）

2. 根节点最少有1个关键字

3. 非根结点最少m/2个子树（m/2 - 1个关键字）

4. 每个关键字排序

5. 所有的叶子结点位于同一层

6. 每个结点都存有索引和数据

（1）简介

B+树是应文件系统所需而产生的一种B树的变形树（文件的目录一级一级索引，只有最底层的叶子节点（文件）保存数据）非叶子节点只保存索引，不保存实际的数据，数据都保存在叶子节点中。所有的非叶子节点都可以看成索引部分！

（2）B+树的性质(下面提到的都是和B树不相同的性质)

1. b+树有两种类型的结点：

1.1 内部结点（索引结点，非叶结点）： 只存索引，不存数据

1.2 叶子结点 （存数据）

2. 内部结点 和 叶子结点的 key递增排序

3. 每个叶结点存有相邻叶结点的指针

4. 父结点存有右孩子第一个元素索引

1.磁盘io代价低：b+树的非叶结点只存储索引，不存储数据，单一结点能存放的索引数更多，树更矮胖

2. b+树查询效率稳定：所有查询必须到叶节点

3. b+树叶子节点为有序表，效率更高，支持范围查询。

《MySQL是怎样运行的：从根儿上理解 MySQL》采用诙谐幽默的表达方式，对MySQL的底层运行原理进行了介绍，内容涵盖了使用MySQL的同学在求职面试和工作中常见的一些核心概念。总计22 章，划分为4个部分。第1部分介绍了MySQL入门的一些知识，比如MySQL的服务器程序和客户端程序有哪些、MySQL的启动选项和系统变量，以及使用的字符集等。第2部分是本书后续章节的基础，介绍了MySQL的一些基础知识，比如记录、页面、索引、表空间的结构和用法等。第3部分则与大家在工作中经常遇到的查询优化问题紧密相关，介绍了单表查询、连接查询的执行原理，MySQL基于成本和规则的优化具体指什么，并详细分析了Explain语句的执行结果。第4部分则是与MySQL中的事务和锁相关，介绍了事务概念的来源，MySQL是如何实现事务的，包括redo日志、undo日志、MVCC、各种锁的细节等。

尽管《MySQL是怎样运行的：从根儿上理解 MySQL》在写作时参考的MySQL源代码版本是5.7.22，但是大部分内容与具体的版本号并没有多大关系。无论是很早之前就已身居MySQL专家的人员，还是希望进一步提升技能的DBA，甚至是三五年后才会入行的“萌新”，本书都是他们彻底了解MySQL运行原理的优秀书

1.索引失效的原因

联合索引排序的原理：先对第一个字段进行排序，在第一个字段相同的情况下考虑第二个字段，然后在第二个字段相同的情况下才考虑第三个字段...

CREATE TABLE 'test_user'(

'id' int(11) not null auto_increment comment '主键id',

‘user_id’ varchar(36) not null comment '用户id',

'phone' varchar(20) not null comment '用户名称',

'lan_id' int(9) not null comment '本地网',

'region_id' int(9) not null comment '区域'

)ENGINE=InnoDB Auto_increment=4057960 Default charset=utf8mb4

假设将('phone', 'lan_id', 'region_id')组成的联合索引

Explain select * from test_user where lan_id = 1

此时的索引是失效的，因为联合索引是遵循最左前缀法则即第一个字段有序的情况下lan_id才有序。现在是跳过phone,直接搜索lan_id相当于在一个无序的B+树上搜索，所以只能全表扫描。

例1下例范围查找的右边索引会失效

Explain select * from test_user where a >1 and b = 1

为什么索引会失效？

因为我们可以找到a >1的所有的节点，但是此时的b索引是无序的，仍然不可以通过二分查找法来查找

例2. like查询中，如果%放在两边或者放到左边，它都是不走索引的。只有%放到右边，它某些情况才会走这个索引。这是什么原因？

字符串在B+树里面存储的时候，它也是按照字母的大小去排序。首先按照第一个字母去比较，如果第一个字母相同则按照第二个字母去比较和最佳左前缀法则相似。如果左边用了%，那后面的字符是无序的，此时就不能使用二分查找来定位元素还是退化为了全表扫描。

3.Mysql中的索引查询为什么使用了B+树结构，而不使用哈希索引或者B树？

首先哈希值是无序的，不能够进行范围查找。

平衡二叉树的缺点是当数据量非常大的时候，其深度也会非常深这样也会导致查找效率慢。其次其存在回旋查找的问题。比如说当存在范围查询>5的时候定位到该元素之后还得回溯到前面的节点元素6，7

B树的最大特点是一个节点可以存储多个值，这样可以使得树的高度变矮，从而使得树的查找速度变快。但是其也存在回旋查找的问题。

B+树则解决了这个问题，它的非叶子节点存储的是key,其叶子节点既存储了key也存储了value并且其叶子节点是有序的，节点之间用指针相连也正是因为这一点使得B+树在范围查询的时候不存在回旋问题。

---