面试【B树B+树】索引的由来，B树的缺陷，Mysql事务四大特性，隔离级别。Mysql锁，MVCC_mysql b+树面试

1、教程1：B树和B+树的区别

B树
B-树
B+ 树

拓展：MySQL为什么使用B-Tree（B+Tree）&& 存储知识

存储数据最小单元

主存存取原理
磁盘存取原理

B树 和B+树是 MySQL索引使用的数据结构，对于索引优化和原理理解都非常重要

1、B树

这里的 B 是 Balance（平衡）的缩写。

它是一种多路的平衡搜索树。
它跟普通的平衡二叉树的不同是，B树的每个节点可以存储多个数据，而且每个节点不止有两个子节点，最多可以有上千个子节点。

B树中每个节点都存放着索引和数据，数据遍布整个树结构，搜索可能在非叶子节点结束，最好的情况是O(1)。
一般一棵 B 树的高度在 3 层左右，3 层就可满足 百万级别的数据量

B树 每个节点都存储了一定的范围区间，区间更多的情况下，搜索也就更快。

比如普通的二叉树对于 1~ 100 的索引值，首先分为 1~ 50 和51~ 100 两部分。

而 B树可以分为四个区间 1~ 25, 26~ 50, 51~ 75, 76~ 100 。甚至可以划分为更多区间，这样一次就能排除四分之三的数据

2、B+树

B+树是B树的一种变种，它与 B树 的 区别 是：

• 叶子节点保存了完整的索引和数据，而非叶子节点只保存索引值，因此它的查询时间固定为 log(n).
• 叶子节点中有指向下一个叶子节点的指针，叶子节点类似于一个单链表

正因为叶子节点保存了完整的数据以及有指针作为连接，B+树可以增加了区间访问性，提高了范围查询，而B树的范围查询相对较差
B+树更适合外部存储。因为它的非叶子节点不存储数据，只保存索引。
B+树的示意图如下：

2、教程2：5分钟 精通Mysql的索引原理

• 猿人林克

索引基本

老师找一个学生，先找 这个学生所在的班级，

• 如果这个班级，是按照 姓名的 首字母缩写 排序的话，在首字母中 查找一次，就能把范围缩小到 3-4 个人了。
• 再次查找，即可找到了

创建了一个“班级-首字母”两个字段组成的联合索引。

假如 班级特别特别 多，需要 把 班级做成 平衡二叉树，或 红黑树

从根节点开始进行对比

• 判断它与节点值的大!
• 根据结果，分别向右或向左继续 节点的对比
• 直到找到 相等的数据

2000个数据构成

• log(2)4000=11的树

  • 2 4 8 16 32 64 128 256 512 1024 2048 4096 一共11层。算上底层12？

• 即11层。

• 最多只需要比对11次就可以找到确定的班级了

• 通过一个树结构就可以把搜索量从2000减 或少到11次了

B树

​ 4 8 12

2 6 10 14 16 18（这3个是一个节点）

1 3 5 7 9 11 13 15 17 19 20（这2个是 一个节点）

这棵树和平衡二叉树比较相似

只不过分叉数量变成了4

这种分多个叉的平衡树，就叫做B树

• 二叉树，每个节点，只会有一个数据。
• B数 每个节点 存在多个数据，节点上的数据都是 有序的，所以 可以用 二分法 来查找数据，

每个节点，都可以连接若干个子节点

每个子节点中会包含多个数据

• 子节点中的数据均是从小到大排列的
• 数据的调整，将树保持相对平衡

2000个数据变成树，将B树的最大Degrees 没置为5

• 这个Degree可以叫 做.“阶” 也可以叫做度.
• 代表了每个节点可以拥有的最多子节点数
• 也就是每个节点最多拥有Degree-1=4个数据
• log(4)1000 为约为4.98写也就说这 棵树只有5层
  • 4 16 64 256 1024
  • 只需要 4次 对比查找，就能找到 对应节点了。

如果把 Degrees 设置为 32，那就只有 2层了。每个节点 都做多可永久 32个子节点

degree
英
/dɪˈɡriː
n.
度，度数（温度单位）；（角的）度，度数；学位课程，学位；程度；音级；次，次数；
1
2
3
4
5

3大缺陷

• 如果搜索的是 > 10 和 < 15，或者 遍历所有数据

• 要查找的数据离根节点近，找的快，离 根节点远，找的慢，

  • 这样不稳定的搜索时间并不利于我为程序猿大哥们做执行成本的预估

范围查询，力不从心
查询效率不稳定

树高度有下降空间

B树 + 数据“页”

首先要通过传入的磁盘地址，确定要读取磁片中的哪个磁道

然后转动磁头到该磁道上,由于磁片会高速旋转

这样磁头就可以读取一个磁道中的数据了

局部性原理：

• 当一个数据被用到时,
  其附近的数据也通常会马上被使用

磁盘每次都会在磁道上的扇区中，连续读取 4KB的数据，

• 我们把需要磁头转动的寻址读写称为“随机IO”和“连续IO”相对应

4K 太小所以我每次会连取他的4倍16KB的数据
放在我的内存中供我使用

• 这16KB就是我之前和大家反复介绍的数据“页”

页里可以装载大量的“行”

B树的每个节点中"可以装载很多数据"对上

• 就把这16KB的“页”做为B树对的节点

B树的每次对节点的搜索 比对，都会去磁盘读取这对应的16KB
‘页”，将其加载到我的内存缓冲Buffer Pool中

这样，把“行”中的主键作为B树节点的key

增加指向其他节点的信息，剩下的数据: 挂在key的后面

• 我们把树节点和“页”关联起来了

B+树

查询效率不稳定：

我们只需要把非叶子节点中的所有数据，都在最底层叶子节点冗余一份

• 要求所有查询都需要走到最底层叶子节点

• 这样就可以保证所有查询都会搜索固定的次数

  • 这个次数呢，就是树的高度

• 不过显而易见会造成空间浪费也很好解决

  • 既然最底层已经包含所有数据了
  • 那特非叶子节点就只需要存储与搜索有关的key值就够啦

B树的高度如何下降?

除了叶子节点之外，我B树上的目录节，由于不会存储真实数据了

那他必然能装更多的“key和下一页地址”数据

也就是会连接更多的子节点，树的高度自然就下来了

通常情况下，我的一个16KB“页”

• 可以存储三四百个由“key和下一页地址”构成的行
• 这样即使2000万的数据量
  • log以400为底2000万的对数也最多需要3层就够啦
    • log4 200万 = 2.69

范围查询：

我们已经将所有真实数据都存在了我B数的叶子节点上

而且都是从小到大有序的

那么我只需要把最底层叶子节点逐一链接

• 就可以很方便的读取一个范围内的连线续数据
• 同时也可以直接进行全数据的遍历

MySql事务

START TRANSACTION; ——开启事务
SET autocommit= 'N0';--自动提交
1
2

四大特性

Atomicity
Consiste
lsolation
Durability
原子性：指每一个事务中的所有操作，都需要像「原子」一样「不可分割」,操作要么全部成功，要么全部失败

• undolog

保证一致性隔离级别

一致性：最重要保证。其他三个都是为 一致性服务的。
隔离性

• 事务之间不能相互于扰

  • A事务执行过程中，读取到了B事务还没有提交的数据，称为「脏读」;

  • 问题二、A事务扭行过程中，若对同一条数据进行两次读取，在这两次 读取之间，B事务修改了这条数据并且进行了完整提交

    • A事务的两次读取读到了不同的数据,被称为「不可重复读」;

  • 问题三、A事务执行过程中，若对同一个集合数据进行两次读取，在这两次读取之间，B事务在集合中增加或者删除7部分数据，

    • A事务的两次读取读到了数量不一致的行数据，被称为「幻读J;

  • 读未提交 READ UNCOMMITED。三个问题都会出现 。

  • 读已提交 READ COMMITED，解决脏读。

  • 可重复读 REPEATABLE READ。解决脏读 和 不可重复读。

  • 串行读 SERIALIZABLE

  • SELECT @@tx_isolation;
    SET SESSION TRANSACTION ISOLATION LEVEL READ UNCOMMITTED
    
    #这应该是 8.0的指令
    SHOW VARIABLES LIKE 'transaction_isolation' ;
    set transition_isolcation = 'REPEATABLE-READ'
    1
    2
    3
    4
    5
    6

持久性

• 「D持久性J。指事务一旦提交。
  邢事务中所有的更改，就不会由电源故障、系统崩溃、竞等条件在内的意外而发生变化，

• 我体内的INNODB是通近REDOLOG和制来保证故障后，内存中丢失的数据会被恢复到磁盘中;

  • Redo Log + Double Write Buffer 双写缓冲区

原子性 undo log机制

• 顾名思义就是为了回滚操作而诞生的机制

• 每个事务在进行磁盘操作的时候，都会在磁盘中创建与之对应的UNDOLOG

• 当事务导常是会根据UNDOLOG逐一进行撤销操作

• 什么时候写入 undo log ？

• 在事务中，每一条SQL通过执行器后

• 第一时间就会在回滚段UNDOLOG SEGMENT中申请一个UNDO LOG页

• 然后根据SQL信息来构造对应的UNDO LOG内容

• 同时将起写入磁盘，以保证每次操作 真正数据之前，undo log是完整的。

• 即使 发生异常，也可以保证 完美的撤销。

• undo log写入成功后，才会执行内存数据写入、记录REDO
  LOG、数据刷盘等

• 对于16KB的默认页来说，可申请 1024个， undolog 也

  • 8K 的话，可申请 512个

  • show variables like 'innoba_rollback_segments';
    set innodb_rollback_segments = '128' #默认
    
    #最大支持 1024 * 128
    1
    2
    3
    4

  • 分别是记录了UNDO类型、表ID、头尾信息等在内的「基本信是」,

    • undo 类型，最常见 增删改
      • TRX_UNDO_INSERT REC
      • TRX_UNDO_DEL_MARK REC
      • TRX_UNDO_UPD_EXIST_REC

锁信息

上锁事务的信息
被锁的索引信息
锁的类型和模式信息
基本信息

• 共享锁

SELECT user WHERE id < 10 LOCK IN SHARE MODE;
SELECT * FROM dept d WHERE d.deptno = 10 lock in share mode;

-- 一对查询结果中的每行，都添加「独占锁
SELECT user WHERE id <10 FOR UPDATE;
1
2
3
4
5

不过有关「读』的问题可以使用效率
更高的MVCC解决

锁的类型

5个锁的模式

• lock_mode

  • LocK_S 共享锁（读锁)
    LOCK_X 独占锁(写锁)

  • LOCK_lS
    共享意向锁：在数据所在表上 做一个标记，其他数据 只需看下 表的意向锁 即可。

  • LOCK_lX
    独占意向锁

  • LOCK_AUTO_INC
    自增锁：为自增列服务。事务回滚，自增值，不会回退。

  • —一自增锁的机制
    SHOw VARIABLES LIKE 'innodb_autoinc_lock_mode';
    SET innodb_autoinc_lock_mode = '1';
    
    # 0 自增场景，都添加自增锁。
    # 2指自增场景不忝加锁直接生成自增值
    # 1 是在确定插入数量时采用2机制。不确定，才用0机制。
    1
    2
    3
    4
    5
    6
    7

两种类型

• lock_type
  • LOCK_IABLE 「表锁」和LOCK_REC[行锁」两种
  • 行锁：使用一个BlT数组记录哪些行被了

四种 行子类型

• rec_lock_type
  • 行子 类型，
  • LOCK_REC_NOT__GAP 精准行锁.
  • LOCK_GAP 行GAP锁：锁住 行与行 之间的间隙。
  • LOCK_ORDINARY NEXT-KEY锁：精准行锁和Next Key锁组合。
  • LOCK_INSERT_INTENTION
    插入意向锁。是一个 特殊的 GAP 锁。也是共享锁，如果一个行间隙：加了 GAP 锁，其他事务 要在这里插数据，就会加 插入意向锁。多个事务 都可以加这个锁。

隔离性 另一实现 MVCC

即multi-version concurrency control多版本并发控制机制

为了解决「脏读」不可重复读」等事务之间读写问题而诞生的

MVCC在某些场景中替代了相对低效的「锁」，提升读取效率 和 并发性。

是基于「Undo Log版本链」和 Read view 来达成的

• Read View 选择版本。
• 是一个视图一个内存结构

MVCC 解决了 脏读。但：幻读 无法解决。

• 不可重复读 解决：事务在 第一次查询时，创建一个 Readview，后续都是用这个 判断，所以 每次查询都是一样的。
  • 读 已提交，是每次都创建一个 Readview

3. 教程3：索引和B+树由来

1、为什么要有索引?
一般的应用系统，读写比例在10:1左右，而且插入操作和一般的更新操作很少出现性能问题，在生产环境中，我们遇到最多的，也是最容易出问题的，还是一些复杂的查询操作，因此对查询语句的优化显然是重中之重。说起加速查询，就不得不提到索引了。

2、什么是索引?
索引在MySQL中也叫是一种*键”，是存储引擎用于快速找到记录的一种数据结构。索引对于良好的性能非常关键，尤其是当表中的数据量越来越大时，索引对于性能的影响愈发重要。
索引优化应该是对查询性能优化最有效的手段了。索引能够轻易将查询性能提高好几个数量级.索引相当于字典的音序表，如果要查某个字，如果不使用音序表，则需要从几百页中逐页去查。

3、索引的原理
索引的目的在于提高查询效率，与我们查阅图书所用的目录是一个道理:先定位到章，然后定位到该童下的一个小节，然后找到页数。相似的例子还有:查字典，查火车车次，飞机航班领
本质都是:通过不断地缩小想要获取数据的范围来筛选出最终想要的结果，同时把随机的事件变成顾序的事件，也就是说，有了这种索引机制，我们可以总是用同一种查找方式来锁定数据。

4、索引的数据结构
MySQL主要用到两种结构:B+Tree索引和Hash索引lnodb存储引擎默认是B+Tree索引
Memory存储引擎默认 Hash索引;
MySQL中，只有Memory(Memory表只存在内存中，断电会消失，适用于临时表)存储引擎显示支持Hash索引，

是Memory表的默认索引类型，尽管Memory表也可以使用B+Tree索引。Hash索引把数据以hash形式组织起来,因此当查找某一条记录的时候，速度非常快。但是因为hash结构，每个键只对应一个值，而且是散列的方式分布。所以它并不支持范围查找和排序等功能。

B+Tree是mysql使用最频繁的一个索引数据结构，是InnoDB和MyIlSAM存储引擎模式的索引类型。相对Hash索引，B+Tree在查找单条记录的速度比不上Hash索引，但是因为更适合排序等操作，所以它更受欢迎。毕竟不可能只对数据库进行单条记录的操作。
对比:
hash类型的索引:查询单条快，范围查询慢
btrec类型的索引: b+树，层数越多，数据量指数级增长〈我们就用它，因为innodb默认支持它)

B和B+树

B树和B+树的区别，为什么Mysql使用B+树

B树的特点:

1，节点排序
2，—个节点了可以存多个元素，多个元素也排序了

B+树的特点:

• 拥有B树的特点
• 叶子节点之间有指针
• 非叶子节点上的元素在叶子节点上都冗余了，也就是叶子节点中存储了所有的元素，并且排好顺序
• B*树，非叶子节点，也有指针。Oracle用。

Mysql索引使用的是B+树，因为索引是用来加快查询的，而B+树通过对数据进行排序所以是可以提高查询速度的，然后通过一个节点中可以存储多个元素，从而可以使得B+树的高度不会太高，在Mysql中一个innodb页就是一个B+树节点，一个innodb页默认16kb，所以一般情况下一颗两层的B+树可以存2000万行左右的数据，然后通过利用B+树叶子节点存储了所有数据并且进行了排序，并且叶子节点之间有指针，可以很好的支持全表扫描。范围查找等SQL语句。

• log以400为底2000万的对数也最多需要3层就够啦
  • log400 2000万 = 2.69

Mysql锁有哪些，如何理解

按锁粒度分类:
1.行锁:锁某行数据，锁粒度最小,并发度高

2，表锁:锁整张表，锁粒度最大，并发度低

3。间隙锁:锁的是一个区间

B+树的由来

B+树索引就是传统意义上的索引，这是目前关系型数据库系统中查找最常用和最为有效的索引。

• balance

• Oracle 用的是 B*树，是B+树的变种

B+树是通过二叉查找树，再由平衡二叉树，B树演化而来。

二分查找法 时间复杂度为O(log2n)

二叉树，每个节点，最多2个 子节点。

• 二叉查找树，左子树，一定小于 又子树。

10、25、34、48、61、73、81转为二叉查找树

48 作为根节点

25 和 73 作为左右子树

10 和 34 作为 25的子树

61 和 81 左右为 81的 子树

B-Tree，多路搜索树、多叉平衡查找树

B+树的 叶子节点：依然是有序的。

• 查找范围，通过根节点，找到 28，最后找到叶子节点，
• 在叶子节点 往前扫描，全是 < 28 的