写在开头
本文是记录对林晓斌老师的《mysql45讲》的阅读，并整理成自己能更通俗理解的阅读笔记
前文
1.数据结构树
一个最简单的二叉树格式
image.png
//golang
type Node struct {
val any
left *Node
right *Node
}
多叉树就是用数组保存多个子节点
树结构的常见术语:
- 节点的深度，即从树根节点root到该节点的边数
- 节点的高度，即该节点到叶子节点(没有子节点的node叫叶子节点)的最长路径边数
- 树的高度，根节点的高度
- 树的阶，即此树的节点最多有多少个孩子
1.1二叉搜索树BST(binary search tree)
又称二叉排序树，满足以下条件:
- 非空左子树键值 < 根节点键值 < 非空右子树键值
-
左右子树都是二叉搜索树
image.png
即BST只对树的值如何放置有要求，对它进行中序遍历就是一个排好序的递增序列
1.2平衡二叉树AVL
对于任何节点，左子树和右子树的节点高度差不超过1（当然也满足BST的键值存放规则，也是一颗BST），平衡二叉树能减少二叉树查找的深度
-
例1：
image.png
root(val=25)的左子树高度=2，右子树高度=4，BT=4-2=2>1，不满足，这不是平衡二叉树
-
例2：
image.png
这是一颗平衡二叉树
1.3B树(B-Tree)
B树也叫B-树(这里不是减号，是连接)，查找路径不只两个，因此是多叉树(平衡多叉查找树)，数据库的索引技术大量使用B树和B+树结构。
大多数的BST都假设所有数据都在内存/主存中，但当数据达到了亿级别时，内存根本放不下，我们只能以块的形式从磁盘读取数据。
文件存储在磁盘/外存上，它最小的存储单位叫扇区。每个扇区存储512字节
操作系统读取外存不会一个个扇区读取，效率太低，而是一次性连续读取多个扇区，即一个块(block，多个扇区组成块)。块是文件存取的最小单位，最常见大小是4KB。
树的节点不是顺序存储，都是通过指针记录下一个节点位置，要想到下一层节点，就必须进行一次IO访问，因此树的高度跟IO挂钩
那么从内存读取数据和从外存块读取数据相比，肯定是外存更耗时(磁盘IO操作)，B-树的目的就是减少磁盘的IO操作，树的高度越高，访问磁盘就越多，即多数平衡树都需要O(h)次磁盘访问，h为树高度。对于B-树，树的高度是一个我们可控值。通过调整B-树中节点所包含的键的数目-关键字数(关键字是查找元素的标识，也可以叫做数据库中的索引，本质上是磁盘上的一个位置信息)，来使B-树高度保持较小值。
补充：
- 键值排序原则和BST一样，左小右大
- 度：一个节点拥有的子节点数量,一个m阶B树最多有m个子节点，关键字数>最小度t，小于最大度max=m-1
image.png
- B-树节点是保存数据的，所有键值分布在整颗树中(索引值和具体dat都在每个节点里面)
image.png
用代码抽象出B-树
type BtreeNode struct {
keys []unsafe.Pointer //存储关键字
n int //关键字数
t int //最小度，与关键字个数挂钩
nodes []*BtreeNode //孩子节点
leaf bool //是否叶子节点，标记位
data any //数据
}
1.4B+树
B+树是B-树的变体，为了减少B-树的层数，仅在叶子节点存储数据，非叶子节点不存储data，所有叶子节点增加一个链指针，从而减少记录的搜索时间
image.png
扩展阅读:为什么B+树更适合做索引
2.InnoDB的索引模型
innodb使用b+树索引模型，每一个索引在innodb中对应一颗B+树。主键索引（聚簇索引）的树的叶子节点才存储完整行数据，普通索引的树的叶子节点只存储了主键，真正要取完整数据需要回到主键索引的树上去找，这也叫回表。
同时以此类推，主键长度越小，普通索引的叶子节点越小，普通索引占用空间也越小
mysql> create table T(
id int primary key,
k int not null,
name varchar(16),
index (k))engine=InnoDB;
只需扫描一棵树
select * from T where ID=500
扫描2棵树
select * from T where k=5
那没有索引的呢？
select * from T where name="xxx"
image.png
同时还需要注意一点就是普通索引/二级索引，会默认和主键做联合索引，即上文默认存在一个(id,k)的联合索引
2.1页分裂
假设主键ID不是严格按序自增，那么可能存在这种情况：
- Row1,id=400
- Row2,id=500
那么此时想要：
- 插入id=600，很简单，后面插入记录即可。
- 插入id=450，麻烦来了，需要逻辑上去挪动后面的位置。更糟糕的是如果id=500所在的数据页满了，那么根据B+树算法，需要申请新页，然后挪动部分数据过去，这就是页分裂。
既然是挪动部分过去，必然会造成部分页空间的浪费（回忆一下删除产生碎片，这里页分裂也会产生空隙），因此除了性能影响外，还会影响数据页的利用率。所以更推荐插入数据不指定主键，主键采用自增的形式
2.2覆盖索引
普通索引树上存主键，查询语句的查询结果仅针对主键，不需要回表，称为覆盖索引。还是上面的表为例
select * from T where k between 3 and 5
若不进行索引覆盖则需要回表3次
select ID from T where k between 3 and 5
此时只查询主键不需要回表，这也是一种性能提升的优化方式。
2.3联合索引
CREATE TABLE `tuser` (
`id` int(11) NOT NULL,
`id_card` varchar(32) DEFAULT NULL,
`name` varchar(32) DEFAULT NULL,
`age` int(11) DEFAULT NULL,
`ismale` tinyint(1) DEFAULT NULL,
PRIMARY KEY (`id`),
KEY `id_card` (`id_card`),
KEY `name_age` (`name`,`age`)
) ENGINE=InnoDB
2.3.1最左前缀原则
在MySQL建立联合索引时会遵守最左前缀匹配原则，即最左优先，在检索数据时从联合索引的最左边开始匹配，这就是最左匹配原则。
即上面联合索引(name,age)相当于同时创建了索引(name)和索引(name,age)，因此仅用name可以走联合索引
image.png
age查询走的是全表扫描，联合索引没有创建该索引，因此不走索引
image.png
那么name和age互换一下顺序呢？
select * from tuser where age=10 and name="zjb"
也会走联合索引。那为啥没按照联合索引顺序从左到右匹配，却也使用了联合索引？因为mysql有查询优化器explain，所以mysql语句中的字段顺序不需要和联合索引相同。
还有一种解释是，单age查询之所以会失效，是因为(name,age)联合索引，是先按照name排序，在name相同的情况再按age排序，所以age是全局无序的(回想一下搜索树是根据值顺序查找的)，局部相对有序的(age相对于name有序，前提是name相同)，所以单age无序无法利用索引去找，即利用索引的前提是索引里的key是有序的。
2.3.2联合索引范围查询
上面都是等值匹配的情况。
联合索引有一些特殊情况，并不是查询过程使用联合索引查询，就代表联合索引中所有字段都使用了联合索引进行索引查询，也可能存在部分使用联合索引查询，部分字段没有使用的情况。
这种情况就发生在范围查询，也就是mysql八股文对最左匹配的定义
联合索引的最左匹配原则会一直向右匹配直到遇到范围查询(>、<、between、like) 就会停止匹配。
但是实际情况要比这定义复杂的多，因此更推荐使用上面的有序无序去判断
- 例子1.like模糊查询前半段不模糊可以使用索引查询
select * from tuser where name like ‘张 %’
image.png
- 例子2.大于的范围查询
已知联合索引(a,b)
select * from t_table where a > 1 and b = 2
根据最左匹配原则，遇到a>1就停止匹配，从a>1找到的范围中再判断b=2，然后再回表(这里就是下文要说的索引下推)。此时因为a是有序的,a>1能根据索引树找到，但是b是全局无序的，因此只用了部分联合索引a，b未被使用
- 例子3.大于等于的范围查询
已知(a,b)
select * from t_table where a >= 1 and b = 2
a>=1因为a的有序，所以能使用索引树找，b字段是无序的。但是对于符合a=1的索引记录范围里(a相同的情况下b是有序的),b是有序的，所以这里的a和b都使用了联合索引，这也是>=不在上文定义中出现的原因
- 例子4 between查询
已知(a，b)
SELECT * FROM t_table WHERE a BETWEEN 2 AND 8 AND b = 2
between包括边界，即a=2，a=8，因此a,b都能用到
- 例子5 like后面跟age查询
回到上面例子
select * from tuser where name like 'z%' and age=10
name有序，但是like 包括 z，即上面区间范围是[z,xxx)，对于符合name=z的范围里,age是有序的，因此都能用到
image.png
因此上面的定义并不是对的，实验证明只有在遇到范围查询(>/<)时会停止匹配，对于>=/<=/between,like并不会
2.3.3索引下推
索引下推是mysql5.6的一个新特性，为了减少回表次数，在索引遍历过程中，对索引中包含的字段先判断，直接过滤掉不满足条件
mysql>select * from tuser where name like '张%' and age=10 and ismale=1;
image.png
5.6版本之后因为索引下推的加入，在联合索引内部就判断age=10，因此只回表2次
image.png
网友评论