1. 二叉树

1.1 什么是B-树

B树又名平衡多路查找树（也把B树称为B-树）查找路径不只两个，不同于常见的二叉树，它是一种多叉树，我们常见的使用场景一般是在数据库索引技术里，大量使用者B树和B+树的数据结构。

B树大多用在磁盘上用于查找磁盘的地址。因为磁盘会有大量的数据，有可能没有办法一次将需要的所有数据加入到内存中，所以只能逐一加载磁盘页，每个磁盘页就对应一个节点，而对于B树来说，B树很好的将树的高度降低了，这样就会减少IO查询次数，虽然一次加载到内存的数据变多了，但速度绝对快于AVL或是红黑树的。

特点：

• 所有键值分布在整个树中（区别与B+树，B+树的值只分部在叶子节点上）
• 任何关键字出现且只出现在一个节点中（区别与B+树）
• 搜索有可能在非叶子节点结束（区别与B+树，因为值都在叶子节点上，只有搜到叶子节点才能拿到值）
• 在关键字全集内做一次查找，性能逼近二分查找算法

1.2 什么是B+树

特点

• 所有叶子节点连接成为一个单链表，且这个链表是有序的。
• 所有关键字都在叶子节点出现，因此不可能在非叶子节点命中。
• 内节点不存数据，只存key。
• 非叶子节点相当于是叶子节点的索引，叶子节点相当于是存储数据的数据层。

B+Tree与B-Tree 的区别

1）B树的关键字和记录是放在一起的，叶子节点可以看作外部节点，不包含任何信息；B+树的非叶子节点中只有关键字和指向下一个节点的索引，记录只放在叶子节点中。

2）在B树中，越靠近根节点的记录查找时间越快，只要找到关键字即可确定记录的存在；而B+树中每个记录的查找时间基本是一样的，都需要从根节点走到叶子节点，而且在叶子节点中还要再比较关键字。

1.3 什么是红黑树

概念

一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是red或black（非红即黑）。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍。它是一种弱平衡二叉树，相对于要求严格的AVL树来说，它的旋转次数少，所以对于插入、删除操作较多的情况下，我们就用红黑树。

特点

• 每个节点非红即黑；
• 根节点是黑的；
• 每个叶节点(叶节点即树尾端NULL指针或NULL节点)都是黑的；
• 如果一个节点是红的,那么它的两儿子都是黑的；
• 对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点；
• 一般插入的是红色结点

1.4 为什么要用 B+ 树，而不用普通二叉树？

读取数据的时候，是从磁盘先读到内存。平衡二叉树的每个节点只存储一个键值和数据，而 B+ 树可以存储更多的节点数据，树的高度也会降低，因此读取磁盘的次数就会下降，查询效率就快。

1.5 >为什么用B+树，而不是B树

1. B+树的磁盘读写代价更低

B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能 容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

2. B+树的查询效率更加稳定

由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

3. 范围查找更快

mysql是关系型数据库，经常会按照区间来访问某个索引列，B+树的叶子节点间按顺序建立了链指针，加强了区间访问性，所以B+树对索引列上的区间范围查询很友好。而B树的数据有一部分存在在非叶子节点上面，而且默认的B树的相邻的叶子节点之间是没有指针的，所以范围查找相对更慢。

2. 索引

一篇文章讲清楚MySQL的聚簇/联合/覆盖索引、回表、索引下推

2.1 聚簇索引与非聚簇索引的区别

1. 数据存储方式：

• 聚簇索引：数据按照索引的顺序存储在表中，即索引本身就是数据本身。
• 非聚簇索引：数据不按照索引的顺序存储在表中，索引中存储的是指向数据行的指针。

2. 索引大小：

• 聚簇索引：只有一个聚簇索引，它的大小与表的大小相同。
• 非聚簇索引：可以有多个非聚簇索引，每个非聚簇索引的大小都小于表的大小。

3. 检索速度：

• 聚簇索引：对于主键查询和范围查询，聚簇索引的检索速度更快，因为数据本身就是索引。
• 非聚簇索引：对于非主键查询和范围查询，非聚簇索引的检索速度可能比聚簇索引慢，因为需要根据索引中的指针找到数据行。

4. 插入和删除数据：

• 聚簇索引：插入和删除数据时，需要移动数据，这会影响性能。
• 非聚簇索引：插入和删除数据时，只需要更新索引，这不会影响性能。

总结：

聚簇索引和非聚簇索引各有优缺点，选择哪种索引类型取决于具体的应用场景。一般来说，对于主键查询和范围查询，使用聚簇索引可以提高检索速度；对于非主键查询和范围查询，使用非聚簇索引可以提高插入和删除数据的性能。

2.2 回表了解吗？

回表是指在数据库查询过程中，通过非聚簇索引（secondary index）查找到记录的主键值后，再根据这个主键值到聚簇索引（clustered index）中查找完整记录的过程。

回表操作通常发生在使用非聚簇索引进行查询，但查询的字段不全在该索引中，必须通过主键进行再次查询以获取完整数据。

换句话说，数据库需要先查找索引，然后再根据索引回到数据表中去查找实际的数据。

因此，使用非聚簇索引查找数据通常比使用聚簇索引要慢，因为需要进行两次磁盘访问。当然，如果索引所在的数据页已经被加载到内存中，那么非聚簇索引的查找速度也可以非常快。

例如：select * from user where name = '张三';，会先从辅助索引中找到 name=‘张三’ 的主键 ID，然后再根据主键 ID 从主键索引中找到对应的数据行。

2.3 覆盖索引

在辅助索引里面，不管是单列索引还是联合索引，如果 select 的数据列只用辅助索引中就能够取得，不用去查主键索引，这时候使用的索引就叫做覆盖索引，避免了回表。

比如，select name from user where name = ‘张三’;

2.4 最左前缀原则

最左匹配原则是指在使用联合索引（即包含多列的索引）时，查询条件从索引的最左列开始并且不跳过中间的列。

如果一个复合索引包含(col1, col2, col3)，那么它可以支持 col1、col1,col2 和 col1, col2, col3 的查询优化，但不会优化只有 col2 或 col3 的查询。

也就说，在进行查询时，如果没有遵循最左前缀，那么索引可能不会被利用，导致查询效率降低。

为什么不从最左开始查，就无法匹配呢？

比如有一个 user 表，我们给 name 和 age 建立了一个联合索引 (name, age)。

ALTER TABLE user add INDEX comidx_name_phone (name,age); 

联合索引在 B+ 树中是复合的数据结构，按照从左到右的顺序依次建立搜索树的 (name 在左边，age 在右边)。

注意，name 是有序的，age 是无序的。当 name 相等的时候，age 才有序。

当我们使用 where name= '张三' and age = '20' 去查询的时候， B+ 树会优先比较 name 来确定下一步应该搜索的方向，往左还是往右。

如果 name 相同的时候再比较 age。

但如果查询条件没有 name，就不知道应该怎么查了，因为 name 是 B+树中的前置条件，没有 name，索引就派不上用场了。

简言之，联合索引按照从左往右建立搜索树的，如果不按照顺序查找，索引无法使用。

2.5 索引下推优化

• 不使用索引条件下推优化时存储引擎通过索引检索到数据，然后返回给 MySQL Server，MySQL Server 进行过滤条件的判断。
• 当使用索引条件下推优化时，如果存在某些被索引的列的判断条件时，MySQL Server 将这一部分判断条件下推给存储引擎，然后由存储引擎通过判断索引是否符合 MySQL Server 传递的条件，只有当索引符合条件时才会将数据检索出来返回给 MySQL 服务器。

例如一张表，建了一个联合索引（name, age），查询语句：select * from t_user where name like '张%' and age=10;，由于name使用了范围查询，根据最左匹配原则：

不使用 ICP，引擎层查找到name like '张%'的数据，再由 Server 层去过滤age=10这个条件，这样一来，就回表了两次，浪费了联合索引的另外一个字段age。

但是，使用了索引下推优化，把 where 的条件放到了引擎层执行，直接根据name like '张%' and age=10的条件进行过滤，减少了回表的次数。

索引条件下推优化可以减少存储引擎查询基础表的次数，也可以减少 MySQL 服务器从存储引擎接收数据的次数。

2.6 innodb和myisam的区别innodb

1、innodb支持事务，而myisam不支持事务。
2、innodb支持外键，而myisam不支持外键。
3、innodb默认表锁，使用索引检索条件时是行锁，而myisam是表锁（每次更新增加删除都会锁住表）。
4、innodb和myisam的索引都是基于b+树，但他们具体实现不一样，innodb的b+树的叶子节点是存放数据的，myisam的b+树的叶子节点是存放指针的。
5、innodb是聚簇索引，必须要有主键，一定会基于主键查询，但是辅助索引就会查询两次，myisam是非聚簇索引，索引和数据是分离的，索引里保存的是数据地址的指针，主键索引和辅助索引是分开的。
6、innodb不存储表的行数，所以select count( * )的时候会全表查询，而myisam会存放表的行数，select count(*）的时候会查的很快。

总结:mysql默认使用innodb，如果要用事务和外键就使用innodb，如果这张表只用来查询，可以用myisam。如果更新删除增加频繁就使用innodb。

mysql__innodb__155">2.7 mysql 为什么建议 innodb 表要建一个主键？并且推荐使用整形自增主键？

mysql 为什么建议 innodb 表要建一个主键？

innoDB索引文件和数据文件是在一起的
frm：表结构；ibd：索引文件和数据文件

在 mysql 的数据存储中 idb 文件中，要使用一颗聚簇索引来维护一个 b+ 树保存数据，那么 mysql 在组织索引的时候，会依赖唯一id，有下列几种情况：

• 如果有一个主键，可以直接使用主键建索引
• 如果没有主键，第一个不包含有NULL值的唯一索引作为主键索引
• 如果没有选到唯一值的索引列，mysql 会帮忙建立一个隐藏列，维护一个唯一id，以此来组织索引

那么为了避免 mysql 选择索引列和建立隐藏列的性能损耗，建议手动建立一个主键。

为什么推荐使用整形作为主键

• 使用整形作为主键相比字符型可以节省数据页的空间。
• 构建索引 b+ 树时，为了保证索引的有序性，使用整形可以避免页分裂。
• 在索引中查找数据时，减少比较的性能。

主键为什么要自增

每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，主键的顺序按照数据记录的插入顺序排列，自动有序。当一页写满，就会自动开辟一个新的页

如果主键不是自增的，在进行增删数据的时候，会判断数据应该存放的位置，进行插入和删除，为了保持平衡，会对数据页进行分裂等操作移动数据，严重影响性能，所以主键需要是自增的，插入时，插入在索引数据页最后。

2.8 为什么innodb采用B+树

• MySQL 的默认存储引擎是 InnoDB，它采用的是 B+树索引，B+树是一种自平衡的多路查找树，和红黑树、二叉平衡树不同，B+树的每个节点可以有·m 个子节点，而红黑树和二叉平衡树都只有 2 个。

• 和 B 树不同，B+树的非叶子节点只存储键值，不存储数据，而叶子节点存储了所有的数据，并且构成了一个有序链表。
  这样做的好处是，非叶子节点上由于没有存储数据，就可以存储更多的键值对，再加上叶子节点构成了一个有序链表，范围查询时就可以直接通过叶子节点间的指针顺序访问整个查询范围内的所有记录，而无需对树进行多次遍历。查询的效率会更高。

2.9 为什么 MongoDB 索引用 B树，而 MySQL 用 B+ 树？

B树的特点是每个节点都存储数据，相邻的叶子节点之间没有指针链接。

B+树的特点是非叶子节点只存储索引，叶子节点存储数据，并且相邻的叶子节点之间有指针链接。

• 那么在查找单条数据时，B 树的查询效率可能会更高，因为每个节点都存储数据，所以最好情况就是 O(1)。
  但由于 B 树的节点之间没有指针链接，所以并不适合做范围查询，因为范围查询需要遍历多个节点。

• 而 B+ 树的叶子节点之间有指针链接，所以适合做范围查询，因为可以直接通过叶子节点间的指针顺序访问整个查询范围内的所有记录，而无需对树进行多次遍历。

MySQL 属于关系型数据库，所以范围查询会比较多，所以采用了 B+树；但 MongoDB 属于非关系型数据库，在大多数情况下，只需要查询单条数据，所以 MongoDB 选择了 B 树。

2.10 Hash 索引和 B+ 树索引区别是什么？

• B+ 树索引可以进行范围查询，Hash 索引不能。
• B+ 树索引支持联合索引的最左侧原则，Hash 索引不支持。
• B+ 树索引支持 order by 排序，Hash 索引不支持。
• Hash 索引在等值查询上比 B+ 树索引效率更高。
• B+ 树使用 like 进行模糊查询的时候，LIKE ‘abc%’ 的话可以起到索引优化的作用，Hash 索引无法进行模糊查询。

2.11 MySQL 模糊查询怎么查，什么情况下模糊查询不走索引？

MySQL 中进行模糊查询主要使用 LIKE 语句，结合通配符 %（代表任意多个字符）和 _（代表单个字符）来实现。

SELECT * FROM table WHERE column LIKE ‘%xxx%’;
这个查询会返回所有 column 列中包含 xxx 的记录。

但是，如果模糊查询的通配符 % 出现在搜索字符串的开始位置，如 LIKE ‘%xxx’，MySQL 将无法使用索引，因为数据库必须扫描全表以匹配任意位置的字符串。

3. 日志

3.1 redo log 和 binlog 有什么区别？

这两个日志有四个区别。

1、适用对象不同：

• binlog 是 MySQL 的 Server 层实现的日志，所有存储引擎都可以使用；
• redo log 是 Innodb 存储引擎实现的日志；

2、文件格式不同：

记录的是逻辑 SQL 语句，而 redo log 记录的是物理数据页的修改操作，不是具体的 SQL 语句。

3、写入方式不同：

• binlog 是追加写，写满一个文件，就创建一个新的文件继续写，不会覆盖以前的日志，保存的是全量的日志。
• redo log 是循环写，日志空间大小是固定，全部写满就从头开始，保存未被刷入磁盘的脏页日志。

4、用途不同：

• binlog 用于备份恢复、主从复制；
• redo log 用于掉电等故障恢复。

4. 锁

4.1 意向锁是什么

美团一面：能不能通俗的解释下为什么要有意向锁这个东西？
众所周知，InnoDB 中既有读锁也有写锁，也称为共享锁和排他锁，这两种锁既可以加在整张表上，也可以加在行上。

MySQL 自身就提供了表锁的能力：

• 读锁：LOCK TABLE table_name READ 用读锁锁表，会阻塞其他事务的写操作
• 写锁：LOCK TABLE table_name WRITE 用写锁锁表，会阻塞其他事务的读和写操作

行锁是 InnoDB 存储引擎提供的，MySQL 本身并不提供行级锁的能力：

• 读锁，如SELECT * FROM table_name WHERE … LOCK IN SHARE MODE 加行级读锁，会阻塞其他事务对该行记录的写操作
• 写锁，如SELECT * FROM table_name WHERE … FOR UPDATE 加行级写锁，会阻塞其他事务对该行记录的的读和写操作

又有表锁又有行锁，我们来考虑下这两种类型的锁共存的问题。看下面这个例子：

事务 A 加了行级读锁，锁住了表中的一行，让这一行只能读，不能写。

之后，事务 B 尝试申请整个表的写锁。

如果事务 B 申请成功，那么理论上它就能修改表中的任意一行，这与 A 持有的行级读锁是冲突的。

数据库需要避免这种冲突，就势必要让 B 的申请被阻塞，直到 A 释放行级读锁。

那数据库要怎么判断这个冲突呢？

• 步骤 1：判断表是否已被其他事务用表级锁锁住了整张表
• 步骤 2：判断表中的每一行是否已被行级锁锁住

看起来没有什么困难的，但请注意步骤 2，判断表中的每一行，各位，如何判断？

显然，需要遍历！遍历表中的每一行。

小学生都能想到这样的判断方法效率实在太过于低下了。

于是就有了意向锁！

我们先来看下意向锁的解释：

Intention locks are table-level locks that indicate which type of lock (shared or exclusive) a transaction requires later for a row in a table.

意向锁是一个表级锁，其作用就是指明接下来的事务将会用到哪种锁。

有两种意向锁：

• 意向共享锁/读锁（IS Lock）：当事务想要获得一张表中某几行的读锁（行级读锁）时，InnoDB 存储引擎会自动地先获取该表的意向读锁（表级锁）
• 意向排他锁/写锁（IX Lock）：当事务想要获得一张表中某几行的写锁（行级写锁）时，InnoDB 存储引擎会自动地先获取该表的意向写锁（表级锁）

注意这里的自动：申请意向锁的动作是数据库完成的，就是说，事务 A 申请一行的行锁的时候，数据库会自动先开始申请表的意向锁，不需要我们程序员使用代码来申请。

在意向锁存在的情况下，事务 A 如果想申请行级读锁，就必须先申请该表的意向读锁，申请成功后才能继续申请某行记录的行级读锁。

在意向锁存在的情况下，上面的判断可以改成：

• 步骤 1（不变）：判断表是否已被其他事务用表级锁锁住了整张表
• 步骤 2：发现表上有意向读锁（说明表中有些行被行级读锁锁住了），意向读锁和表级写锁互斥，因此，事务 B 申请表的写锁会被阻塞。

也就是说原先步骤 2 的遍历表中每一行的操作，简化成了判断下整张表上有无表级意向锁就行了，效率大幅提升。

这就是为什么要有意向锁了。