计算机面试基础知识汇总|数据库基础知识（面试）哈希算法|MYSQL|b树

一、基础知识 1、Char 和 Varchar 区别？
（1）Char是定长的，而 Varchar是可以变长。
Char 会根据声明的字符串长度分配空间，并会使用空格对字符串右边进行尾部填充。
（2）在存储方式上，Char 对英文字符占用 1 字节，对一个汉字使用用 2 字节。而 Varchar 对每个字符均使用 2 字节。
2、什么是数据库三大范式？
（1）第一范式：任何一张表都应该有主键，并且每一个字段原子性不可再分。

文章图片

（2）第二范式：建立在第一范式的基础之上，所有非主键字段完全依赖主键，不能产生部分依赖。

文章图片

（3）第三范式：建立在第二范式的基础之上，所有非主键字段直接依赖主键，不能产生传递依赖。

文章图片

多对多？使用三张表，关系表两个外键。
一对多？两张表，多的表加外键。
二、索引 1、索引的分类
单一索引：给单个字段添加索引
复合索引：给多个字段联合起来添加索引
主键索引：主键上会自动添加索引
唯一索引：有unique约束的字段上会自动添加索引
2、索引的优缺点
索引相当于一本书的目录，通过目录可以快速的找到对应的资源。
在数据库方面，查询一张表的时候有两种检索方式：全表扫描、索引检索（效率很高）。
索引虽然可以提高检索效率，但不能随意添加索引，因为索引也是数据库当中的对象，也需要数据库不断维护。比如，表中的数据经常被修改，这样就不适合添加索引，因为数据一旦修改，索引需要重新排序，进行维护。
3、索引的设计原则（什么时候考虑给字段添加索引）
数据量庞大（根据客户的需求，根据线上的环境）
该字段很少的DML操作（因为字段进行修改操作，索引也需要维护）
该字段经常出现在where子句中（经常根据哪个字段查询）

选择唯一性索引；
为常作为查询条件的字段建立索引；
为经常需要排序、分组和联合操作的字段建立索引；
限制索引的数目；
小表不建议索引（如数量级在百万以内）；
尽量使用数据量少的索引；
删除不再使用或者很少使用的索引。

4、索引的数据结构
索引的数据结构和具体存储引擎的实现有关，MySQL 中常用的是 Hash 和 B+ 树索引。

Hash 索引底层就是 Hash 表，进行查询时调用 Hash 函数获取到相应的键值（对应地址），然后回表查询获得实际数据。

文章图片

B+ 树索引底层实现原理是多路平衡查找树，对于每一次的查询都是从根节点出发，查询到叶子节点方可以获得所查键值，最后查询判断是否需要回表查询。

文章图片

（1）Hash 和 B+树索引的区别
Hash
1）Hash 进行等值查询更快，但无法进行范围查询。因为经过 Hash 函数建立索引之后，索引的顺序与原顺序无法保持一致，故不能支持范围查询。同理，也不支持使用索引进行排序。
2）Hash 不支持模糊查询以及多列索引的最左前缀匹配,因为 Hash 函数的值不可预测，如 AA 和 AB 的算出的值没有相关性。
3）Hash 任何时候都避免不了回表查询数据.
4）虽然在等值上查询效率高，但性能不稳定，因为当某个键值存在大量重复时，产生 Hash 碰撞，此时查询效率反而可能降低。
B+ Tree
1）B+ 树本质是一棵查找树，自然支持范围查询和排序。
2）在符合某些条件（聚簇索引、覆盖索引等）时候可以只通过索引完成查询，不需要回表。
3）查询效率比较稳定，因为每次查询都是从根节点到叶子节点，且为树的高度。
（2）为什么使用B+树而非二叉树和B树做索引
二叉树

文章图片

a. 如果索引数据很多，树的层次会很高（只有左右两个子节点），数据量大时查询还是会慢,查找效率为 O(logn)。
b. 二叉树每个节点只存储一个记录，一次查询在树上找的时候花费磁盘IO次数较多。文件系统需要从磁盘读取数据时，一般以页为单位进行读取，假设一个页内的数据过少，那么操作系统就需要读取更多的页，涉及磁盘随机 I/O 访问的次数就更多。将数据从磁盘读入内存涉及随机 I/O 的访问，是数据库里面成本最高的操作之一。
B树

文章图片

a.不再是二叉搜索，而是N叉搜索，树的高度会降低，查询快
b.叶子节点，非叶子节点，都可以存储数据，且可以存储多个数据
c.通过中序遍历，可以访问树上所有节点
B+树

文章图片

B 树非叶子结点和叶子结点都存储数据，因此查询数据时，时间复杂度最好为 O(1)，最坏为 O(log n)。而 B+ 树只在叶子结点存储数据，非叶子结点存储关键字，且不同非叶子结点的关键字可能重复，因此查询数据时，时间复杂度固定为 O(log n)。
B+ 树叶子结点之间用链表相互连接，因而只需扫描叶子结点的链表就可以完成一次遍历操作，B 树只能通过中序遍历。
为什么 B+ 树比 B 树更适合应用于数据库索引？
B+ 树减少了 IO 次数。
由于索引文件很大因此索引文件存储在磁盘上，B+ 树的非叶子结点只存关键字不存数据，因而单个页可以存储更多的关键字，即一次性读入内存的需要查找的关键字也就越多，磁盘的随机 I/O 读取次数相对就减少了。而B 树非叶子结点和叶子结点都存储数据。
B+ 树查询效率更稳定
由于数据只存在在叶子结点上，所以查找效率固定为 O(log n)，所以 B+ 树的查询效率相比B树更加稳定。
B+ 树更加适合范围查找
B+ 树叶子结点之间用链表有序连接，所以扫描全部数据只需扫描一遍叶子结点，利于扫库和范围查询；B 树由于非叶子结点也存数据，所以只能通过中序遍历按序来扫。也就是说，对于范围查询和有序遍历而言，B+ 树的效率更高。
三、存储 1、存储引擎（MyISAM和InnoDB）
（1）InnoDB 支持事务，而 MyISAM 不支持。
（2）InnoDB 支持外键，而 MyISAM 不支持。因此将一个含有外键的 InnoDB 表转为 MyISAM 表会失败。
（3）InnoDB 和 MyISAM 均支持 B+ Tree 数据结构的索引。但 InnoDB 是聚集索引，而 MyISAM 是非聚集索引。
（4）InnoDB 不保存表中数据行数，执行 select count(*) from table 时需要全表扫描。而 MyISAM 用一个变量记录了整个表的行数，速度相当快（注意不能有 WHERE 子句）。
（5）InnoDB 支持表、行（默认）级锁，而 MyISAM 支持表级锁。
（6）InnoDB 必须有唯一索引（如主键），如果没有指定，就会自动寻找或生产一个隐藏列 Row_id 来充当默认主键，而 MyISAM 可以没有主键。
默认使用 InnoDB，MyISAM 适用以插入为主的程序，比如博客系统、新闻门户。
2、存储结构
InnoDB的页、区、段？
页（Page）
首先，InnoDB 将物理磁盘划分为页（page），每页的大小默认为 16 KB，页是最小的存储单位。
区（Extent）
如果只有页这一个层次的话，页的个数是非常多的，存储空间的分配和回收都会很麻烦，因为要维护这么多的页的状态是非常麻烦的。所以，InnoDB 又引入了区（Extent) 的概念。一个区默认是 64 个连续的页组成的，也就是 1MB。通过 Extent 对存储空间的分配和回收就比较容易了。
段（Segment）
B+ 树的叶子节点存放的是我们的具体数据，非叶子结点是索引页。所以 B+ 树将数据分为了两部分，叶子节点部分和非叶子节点部分，也就我们要介绍的段 Segment，也就是说 InnoBD 中每一个索引都会创建两个 Segment 来存放对应的两部分数据。
四、事务 1、什么是数据库的事务？
一个事务是一个完整的业务逻辑单元，不可再分。

文章图片

以上两条DML语句必须同时成功，或者同时失败，不允许出现一条成功，一条失败。
要想保证以上的两条DML语句同时成功或者同时失败，那么就需要使用数据库的“事务机制”。
2、什么是事务的四大特性？（ACID）
A：原子性：事务是最小的工作单元，不可再分。
C：一致性：事务必须保证多条DML语句同时成功或者同时失败。
I：隔离性：事务A与事务B之间具有隔离，各并发事务之间数据库是独立的。
D：持久性：最终数据必须持久化到硬盘文件中，事务才算成功的结束。
3、事务的并发问题？
脏读：一个事务读取到另一个事务尚未提交的数据。事务 A 读取事务 B 更新的数据，然后 B 回滚操作，那么 A 读取到的数据是脏数据。
幻读：一个事务中两次读取的数据量不一致。系统管理员 A 将数据库中所有学生的成绩从具体分数改为 ABCDE 等级，但是系统管理员 B 就在这个时候插入了一条具体分数的记录，当系统管理员 A 改结束后发现还有一条记录没有改过来，就好像发生了幻觉一样，这就叫幻读。
不可重复读：一个事务中两次读取的数据的内容不一致。事务 A 多次读取同一数据，事务 B 在事务 A 多次读取的过程中，对数据作了更新并提交，导致事务 A 多次读取同一数据时，结果不一致。
4、事务的隔离级别

文章图片

第一级别：读未提交（Read uncommitted）
对方事务还没有提交，我们当前事务可以读取到对方未提交的数据。
读未提交存在脏读（dirty read）现象：表示读到了脏的数据。
第二级别：读已提交（Read committed）
对方事务提交之后的数据我方可以读取到。
读已提交存在的问题是：不可重复读。
第三级别：可重复读（Repeatable read）
这种隔离级别解决了不可重复读的问题。
这种隔离级别存在的问题是：读取到的数据是幻象、
第四级别：可串行化（Serializable）
解决了所有问题。效率低，需要事务排队。
oracle 数据库默认的隔离级别是读已提交；mysql 数据库默认的隔离级别是可重复读。
五、锁 1、数据库的锁的作用及分类
当数据库有并发事务的时候，可能会产生数据的不一致，这时候需要一些机制来保证访问的次序，锁机制就是这样的一个机制。即锁的作用是解决并发问题。
从锁的粒度划分，可以将锁分为表锁、行锁以及页锁
行级锁：是锁定粒度最细的一种锁，表示只针对当前操作的行进行加锁。行级锁能大大减少数据库操作的冲突。其加锁粒度最小，但加锁的开销也最大。
行级锁开销大，加锁慢，且会出现死锁。但锁定粒度最小，发生锁冲突的概率最低，并发度也最高。
表级锁：是粒度最大的一种锁，表示对当前操作的整张表加锁，它实现简单，资源消耗较少，被大部分MySQL引擎支持。
页级锁：是粒度介于行级锁和表级锁中间的一种锁。表级锁速度快，但冲突多，行级冲突少，但速度慢。所以取了折中的页级，一次锁定相邻的一组记录。
从使用性质划分，可以分为共享锁、排它锁以及更新锁
共享锁：S 锁，又称读锁，用于所有的只读数据操作。
S 锁并非独占，允许多个并发事务对同一资源加锁，但加 S 锁的同时不允许加 X 锁，即资源不能被修改。S 锁通常读取结束后立即释放，无需等待事务结束。
排他锁：X 锁，又称写锁，表示对数据进行写操作。
X 锁仅允许一个事务对同一资源加锁，且直到事务结束才释放，其他任何事务必须等到 X 锁被释放才能对该页进行访问。
更新锁：U 锁，用来预定要对资源施加 X 锁，允许其他事务读，但不允许再施加 U 锁或 X 锁。
当被读取的页将要被更新时，则升级为 X 锁，U 锁一直到事务结束时才能被释放。故 U 锁用来避免使用共享锁造成的死锁现象。
从主观上划分，又可以分为乐观锁和悲观锁
乐观锁：从主观上认定资源是不会被修改的，所以不加锁读取数据，仅当更新时用版本号机制等确认资源是否被修改。
乐观锁适用于多读的应用类型，可以系统提高吞吐量。
悲观锁：具有强烈的独占和排它特性，每次读取数据时都会认为会被其它事务修改，所以每次操作都需要加上锁。
2、隔离级别和锁的关系？
1）在 Read Uncommitted 级别下，读取数据不需要加共享锁，这样就不会跟被修改的数据上的排他锁冲突；
2）在 Read Committed 级别下，读操作需要加共享锁，但是在语句执行完以后释放共享锁；
3）在 Repeatable Read 级别下，读操作需要加共享锁，但是在事务提交之前并不释放共享锁，也就是必须等待事务执行完毕以后才释放共享锁；
4）在 SERIALIZABLE 级别下，限制性最强，因为该级别锁定整个范围的键，并一直持有锁，直到事务完成。
3、快照读和当前读
快照读就是读取的是快照数据，不加锁的简单 Select 都属于快照读。
当前读就是读的是最新数据，而不是历史的数据。加锁的 SELECT，或者对数据进行增删改都会进行当前读。
4、什么是 MVCC 以及实现？
MVCC 多版本并发控制，可以做到读写互相不阻塞，主要用于解决不可重复读和幻读问题时提高并发效率。
其原理是通过数据行的多个版本管理来实现数据库的并发控制，简单来说就是保存数据的历史版本。可以通过比较版本号决定数据是否显示出来。读取数据的时候不需要加锁可以保证事务的隔离效果。
六、SQL语句 1、SQL的左连接、右连接、内连接
（1）?Left join：即左连接，是以左表为基础，根据ON后给出的两表的条件将两表连接起来。结果会将左表所有的查询信息列出，而右表只列出ON后条件与左表满足的部分。左连接全称为左外连接，是外连接的一种。
（2）?Right join：即右连接，是以右表为基础，根据ON后给出的两表的条件将两表连接起来。结果会将右表所有的查询信息列出，而左表只列出ON后条件与右表满足的部分。右连接全称为右外连接，是外连接的一种。?
（3）Inner join：即内连接，同时将两表作为参考对象，根据ON后给出的两表的条件将两表连接起来。结果则是两表同时满足ON后的条件的部分才会列出。
内连接只能查询到两张表可以匹配到的数据，匹配不到的数据查不到。
外连接可以将主表的数据无条件的全部查询出来。
2、Where 和 Having 的区别？
where 子句的作用是在对查询结果进行分组前，将不符合条件的行去掉，即在分组之前过滤数据，where条件中不能包含聚组函数，使用where条件过滤出特定的行。
having 子句的作用是筛选满足条件的组，即在分组之后过滤数据，条件中经常包含聚组函数，使用having 条件过滤出特定的组，也可以使用多个分组标准进行分组。

【计算机面试基础知识汇总|数据库基础知识（面试）】