mysq-B+Treel(一)

介绍
MySQL是一个关系型数据库管理系统，由瑞典 MySQL AB 公司开发，属于 Oracle 旗下产品。MySQL是最流行的关系型数据库管理系统之一，在 WEB 应用方面，MySQL是最好的RDBMS (Relational Database Management System，关系数据库管理系统)应用软件之一。
MySQL是一种关系型数据库管理系统，关系数据库将数据保存在不同的表中，而不是将所有数据放在一个大仓库内，这样就增加了速度并提高了灵活性。
MySQL所使用的 SQL 语言是用于访问数据库的最常用标准化语言。MySQL 软件采用了双授权政策，分为社区版和商业版，由于其体积小、速度快、总体拥有成本低，尤其是开放源码这一特点，一般中小型和大型网站的开发都选择 MySQL作为网站数据库。

1:B+ Tree
参考 https://www.cnblogs.com/wuzhenzhao/p/10341114.html
mysql索引就是通过B+ Tree实现的
先介绍下B-TREE
1>B-TREE
平衡多路查找树（B-Tree）：
　　B-Tree是为磁盘等外存储设备设计的一种平衡查找树。因此在讲B-Tree之前先了解下磁盘的相关知识。
　　系统从磁盘读取数据到内存时是以磁盘块（block）为基本单位的，位于同一个磁盘块中的数据会被一次性读取出来，而不是需要什么取什么。InnoDB存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位。InnoDB存储引
擎中默认每个页的大小为16KB，可通过参数innodb_page_size将页的大小设置为4K、8K、16K，在MySQL中可通过如下命令查看页的大小：mysql> show variables like ‘innodb_page_size’;
　　而系统一个磁盘块的存储空间往往没有这么大，因此InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB。InnoDB在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时如果一个页中的每条数据都
能有助于定位数据记录的位置，这将会减少磁盘I/O次数，提高查询效率。B-Tree结构的数据可以让系统高效的找到数据所在的磁盘块。为了描述B-Tree，首先定义一条记录为一个二元组[key, data] ，key为记录的键值，对应表中的主键
值，data为一行记录中除主键外的数据。对于不同的记录，key值互不相同。一棵m阶的B-Tree有如下特性：

1. 每个节点最多有m个孩子。
2. 除了根节点和叶子节点外，其它每个节点至少有Ceil(m/2)个孩子。
3. 若根节点不是叶子节点，则至少有2个孩子
4. 所有叶子节点都在同一层，且不包含其它关键字信息
5. 每个非终端节点包含n个关键字信息（P0,P1,…Pn, k1,…kn）
6. 关键字的个数n满足：ceil(m/2)-1 <= n <= m-1
7. ki(i=1,…n)为关键字，且关键字升序排序。
8. Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki，但都大于k(i-1)
   　　B-Tree中的每个节点根据实际情况可以包含大量的关键字信息和分支，
   　　
   2>B+Tree：
   　　B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构。
   　　从 B-Tree 结构图中可以看到每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。
   B+Tree相对于B-Tree有几点不同：
   B+节点关键字搜索采用闭合区间
   B+非叶节点不保存数据相关信息，只保存关键字和子节点的引用
   B+关键字对应的数据保存在叶子节点中
   B+叶子节点是顺序排列的，并且相邻节点具有顺序引用的关系
   　　将B-Tree优化，由于B+Tree的非叶子节点只存储键值信息，假设每个磁盘块能存储4个键值及指针信息

2：为什么不能超过 2000 万行?
MySQL 单表不要超过 2000 万行基本上是一个行业共识，只有当单表行数超过 500 万行或者单表容量超过 2GB，我们一般才推荐进行分库分表。
图片网上抄的


File Header（文件头部）

什么是聚集索引、非聚集索引和回表？
聚集索引和非聚集索引从数据结构上讲都是由B+树实现的。多个索引就有多个B+ TREE
简单来说，聚集索引可以理解成主键索引，非聚集索引可以理解成除主键索引外所有自建的索引。那么问题来了，聚集索引和非聚集索引都是由B+树实现的，那为什么主键索引为什么比其它索引的查询速度要快呢？这里就要引出回表这个问题了。
什么是回表呢？首先说一下聚集索引和非聚集索引的区别。聚集索引叶子节点存储的是数据，非聚集索引的叶子节点存储是的主键ID。通过非聚集索引查询出数据的主键，然后在使用聚集索引查询出最终的数据，这也就解释了什么是回表和为什么主键索引会比其它索引的查询速度要快

联合索引：最左前缀匹配原则
在MySQL建立联合索引时会遵守最左前缀匹配原则，即最左优先，在检索数据时从联合索引的最左边开始匹配。
索引的底层是一颗B+树，那么联合索引的底层也就是一颗B+树，只不过联合索引的B+树节点中存储的是键值。由于构建一棵B+树只能根据一个值来确定索引关系，所以数据库依赖联合索引最左的字段来构建

对索引使用左或者左右模糊匹配（少用）
当我们使用左或者左右模糊匹配的时候，也就是 like %xx 或者 like %xx% 这两种方式都会造成索引失效

B+树承载的记录数量
参考 https://juejin.cn/post/7116381265300815903
B+树的最末级叶子结点里放了record数据。而非叶子结点里则放了用来加速查询的索引数据。
也就是说
同样一个16k（innodb默认页面大小）的页，非叶子节点里每一条数据都指向一个新的页，而新的页有两种可能。
如果是末级叶子节点的话，那么里面放的就是一行行record数据。
如果是非叶子节点，那么就会循环继续指向新的数据页。
(1)非叶子结点内指向其他内存页的指针数量为x
(2)叶子节点内能容纳的record数量为y
(3)B+树的层数为z

B+树放的行数据总量等于 (x ^ (z-1)) * y

X计算
非叶子节点里主要放索引查询相关的数据，放的是主键和指向页号。
主键假设是bigint（8Byte），而页号在源码里叫FIL_PAGE_OFFSET（4Byte），那么非叶子节点里的一条数据是12Byte左右。
整个数据页16k， 页头页尾那部分数据全加起来大概128Byte，加上页目录预估占1k。15*1024/12=1280，也就是可以指向x=1280页
Y计算
叶子节点和非叶子节点的数据结构是一样的，预估剩余15K。
叶子节点里放的是真正的行数据。假设一条行数据1kb，所以一页里能放y=15行

(x ^ (z-1)) * y
层数Z 行数
1 15 、#直接存放Y，不需要X
2 151280 =19200
3 1512801280 = 24576000
4 151280*1280 *1280=31457280000

如果 单行数据为100字节 那么同样三层
(1280 ^ (3-1)) * (151024/100) ≈ 12801280*153 ≈ 250675200 ≈ 2.5亿

搜索路径延长导致性能下降的说法，与当时的机械硬盘和内存条件不无关系。
之前机械硬盘的IOPS在100左右，而现在普遍使用的SSD的IOPS已经过万，之前的内存最大几十G，现在服务器内存最大可达到TB级
因此，即使深度增加，以目前的硬件资源，IO也不会成为限制MySQL单表数据量的根本性因素。
IOPS是存储性能指标，指的是单位时间内系统能处理的I/O请求数量，通常，计算IOPS的基本公式是：（总的读+写的操作量）/ 时间（秒）常见的4K随机读IOPS、4K随机写IOPS、64K顺序读IOPS、64K顺序写IOPS指标

3:SMO并发
参考 https://baijiahao.baidu.com/s?id=1769955141223678320&wfr=spider&for=pc
InnoDB引擎使用的是索引组织表，它是通过索引来组织数据的，而它采用B+tree作为索引的数据结构。B+Tree操作非原子，所以当一个线程做结构调整（SMO，Struction-Modification-Operation）时一般会涉及多个节点的改动。
SMO动作过程中，此时若有另一个线程进来可能会访问到错误的B+Tree结构，InnoDB为了解决这个问题采用了乐观锁和悲观锁的并发控制协议。

InnoDB对于叶子节点的修改操作如下：
1>先采用乐观锁的方式尝试进行修改。
对根节点加S锁（shared lock，叫共享锁，也称读锁），依次对非叶子节点加S锁。
如果叶子节点的修改不会引起B+Tree结构变动，如分裂、合并等操作，那么只需要对叶子节点进行加X锁（exclusive lock，叫排他锁，也称为写锁）即可完成修改。如下图中所示
2>采用悲观锁的方式
如果对叶子结点的修改会触发SMO，那么会采用悲观锁的方式。
采用悲观锁，需要重新遍历B+Tree，对根节点加全局SX锁（SX锁是行锁），然后从根节点到叶子节点可能修改的节点加X锁）。在整个SMO过程中，根节点始终持有SX锁（SX锁表示有意向修改这个保护的范围，SX锁与SX锁、X锁冲突，与S锁不冲突），此时其他的SMO，则需要等待

InnoDB可以实现较好的1与1、1与2的并发，但是无法解决2的并发。因为在2中，根节点始终持有SX锁，必须串行执行，等待上一个SMO操作完成。这样在具有大量的SMO操作时，InnoDB的B+Tree实现就会出现很严重的性能瓶颈。
白话就是 对叶子结点的修改会触发SMO，那么会采用悲观锁的方式 这种时，多线程 必须串行执行

解决方案 B-Link Tree （华为云数据库GaussDB采用这种）

1. 在中间节点增加字段link pointer，指向右兄弟节点，B-link Tree的名字也由此而来
2. 在每个节点内增加一个字段high key，在查询时如果目标值超过该节点的high key，就需要循着link pointer继续往后继节点查找

4：如果觉得有用，麻烦点个赞，加个收藏